- 2 -
Оглавление .
ВВЕДЕНИЕ......................................................... 4
ГЛАВА I. GEL - СИСТЕМА ОРГАНИЗАЦИИ ВЫЧИСЛЕНИЙ, УПРАВЛЯЕМЫХ ДАННЫМИ
§ I. Схемы функционирования ;..............................23
§ 2. Входной язык..........................................33
§ 3. Порядок приме нения деюяов............................4D
§ 4. Фреймы и семантические сети . . . . ..................44
§ 5. Трансляция и редактирование .....................50
§ 6. Управляющая проірамма ...............................53
ГЛАВА 2. МОДЕЛЬ ПАРАЛЛЕЛЬНЫХ АСИНХРОННЫХ ВЫЧИСЛЕНИЙ
§ I. Концептуальный уровень................................55
§ 2. Потоки данных.......................................62
§ 3. Монитор .............................................63
§ 4. Уровень примитивов синхронизации ....................65
§ 5. Віртуальная память....................................66
ШВА 3. ЯЗЫК АНАЛИЗА И ОБРАБОТКИ ТЕКСТОВ
§ I. Общие сведения........................................ТО
§ 2. Функции . . . . .....................................75
§ 3. Операции......................................... . .78
§ 4. Специальные средства..................................84
§ 5. Примеры программирования..............................88
ГЛАВА 4. ВОПРОСЫ РЕАЛИЗАЦИИ СИСТЕШ^/У
§ I. Раскрутка аранслятора.................................92
§ 2. Трансляция............................................95
§ 3. Интерпретация внутреннего языка.......................99
§ 4. Сервисные средства.....................................*..................................JD3
- 3 -
ГЛАВА 5. СИСТЕМА СИНТЕЗА ПРОГРАММ
§ I. Назначение системы....................................... Ш6
§ 2. Входной язык...............................................Ю9
§ 3. Модель данных.............-...............................112
§ 4. Алгоритмы обработки именных наборов , .................. 114
ЗАКЛЮЧЕНИЕ...........................................................116
СПИСОК ОСНОВНОЙ ИСПОЛЬЗОВАННОЙ ЛИТЕРАОТ>Ы............................121
ПРИШЖЕНИЕ............................................................134
- 4 -
ВВЕДЕНИЕ
В настоящее время ЭВМ является мощным инструментом решения народнохозяйственных задач, а программирование как сфера деятельности людей приобретает черты материального производства [85]. Известно, что современный уровень индустрии переработки информации характеризуется значительным опережением темпов роста затрат на математическое обеспечение (МО) ЭВМ по сравнению с темпами увеличения расходов на вычислительную технику [18].
В связи с этим ведущими специалистами в области программирования выдвигается требование ускорения развития инструментальных технологических комплексов, которые должны играть значительную роль на всех этапах создания и сопровождения программ [20,33]. Проблемам построения таких комплексов посвящены работы И.В.Вельбицкого, В.М.Глушкова, А.П.Ершова, Д.А.Коря-гина, С.С.Лаврова, И.В.Поттосина, В.Л.Рвачева, В.Н.Редько, И.В.Сергиенко, Э.Х.Тцугу, Е.Л.Йценко и многих других ученых.
Указанное научное направление способствует повышению производительности труда программистов, а также расширению крута специалистов, которые смогут участвовать в процессе создания программного продукта. Растущий интерес вызывают синтезаторы программ (СП) как инструментальные системы программирования, в которых уровень автоматизации труда программистов наиболее высок. Процесс разработки подобных систем обладает рядом характерных особенностей, поскольку они в той или иной степени имитируют интеллектуальную работу программиста. На практике эти особенности часто выражаются в необходимости обрабатывать
- 5 -
данные сложной логической структуры, включая в алгоритмы обработки элементы дедуктивного вывода.
Традиционные программные средства (универсальные алгоритмические языки, базы данных и др.) часто оказываются недостаточно приспособленными для разработки синтезаторов программ, что приводит к высокой трудоемкости их изготовления, а также сложности сопровождения и модификации. Одним из основных путей решения данной проблемы является создание специализированных инструментальных средств, предназначенных для реализации алгоритмов синтеза программ.
Актуальной является также задача экономичной организации вычислений при автоматизированном построении программ значительных размеров, при котором возникает необходимость многократного просмотра информации во внешней памяти ЭВМ.
Целью диссертационного исследования является разработка принципов организации и создание инструментальной системы программирования, допускающей удобную и эффективную реализацию тех структур данных и алгоритмов их обработки, которые применяются в синтезаторах программ.
Круг применения СП достаточно широк. Часто пакеты прикладных программ (ППП), являющиеся распространенной и эффективной формой организации прикладного МО, содержат в себе те или иные средства генерации программ, что повышает их гибкость, позволяет значительно расширить множество решаемых задач Г13, 65].
СП не только являются средством многократного увеличения производительности труда программистов (в [112] описана система генерации программ некоторого класса, повышающая эту
- 6 -
производительность в 20 раз), но и определяют одно из возможных направлений повышения интеллектуальности МО [14]. Под интеллектуальностью системы программирования здесь понимается ее способность воспринимать и выполнять задания, содержащие постановки задач без детального описания процессов их решения.
СП создаются для различных областей прикладного и системного программирования:
1) построение систем обработки данных [21],
2) разработка баз данных [36],
3) создание ППП [7,68,79],
4) построение управляющих программ для вычислительных систем [35],
5) создание диалоговых и обучающих систем [10,64],
6) реализация численных методов [22,71,88,95].
Задача автоматизации производства программ для конкретных прикладных областей часто выходит за рамки собственно программирования. Рассмотрим, в частности, проблемы численного моделирования сплошных сред [57,60]. В таблице I представлены основные возможные этапы решения подобных проблем, исполнители указаны для случая традиционного подхода - без использования СП.
5-й этап, как правило, проводится без непосредственного участия человека. Применение СП позволяет автоматизировать некоторые другие этапы, при этом на СП возлагается выполнение соответствующих функций исполнителей. Синтез программ будет проводиться по мере поступления постановок задач. При автоматизации 3-4-го этапов эти постановки должны быть математическими, 2-4-го - декларативными.
- 7 -
Таблица !•
№ Содержание этапа Исполнитель Способ представления результатов этапа
І Постановка задачи Специалист- Декларативные
в терминах прикладной области прикладник описания
2 Выбор и обоснова- Математик, Математические
ние математической знакомый с формулы и утвержде-
модели прикладной областью ния
3 Построение метода Специалист Неформальное
решения по вычислительной математике описание алгоритма
4 Программирование Программист Программа
5 Трансляция и ЭВМ со стан- Числовая и символь-
счет дартным математическим обеспечением ная информация
6 Анализ результа- Все указан- Все указанные выше
тов ные выше исполнители способы
- 8 -
Очевидно, что при автоматизации отдельных этапов потребуется не только генерация текста программ, но и синтезирование иных элементов данных: формул, фрагментов математических моделей и других.
Часто проблема построения СП настолько сложна, что требует для своего решения предварительной разработки специализированных инструментальных средств.Обычно такие средства оформляются в виде параметрических систем синтеза программ (ПССП). Первоначально идея параметрических систем программирования была вьщвинута в [74] применительно к транслирующим системам. В современных ПССП реализуются определенные методы синтеза программ на основе фиксированных форм описаний моделей предметной области (МПО), а также представлений элементарных обрабатывающих модулей и операций. После подстановки фактических параметров вместо формальных, то есть после внесения в базу данных ПССП конкретной МПО и информации об имеющихся обрабатывающих модулях, такая параметрическая система становится реально действующим СП. МПО, а также архив модулей могут изменяться, пополняться, в чем выражаются модификация и развитие синтезатора программ. В то же время реализованные в нем методы синтеза, как правило, остаются неизменными. На таких принципах основаны, в частности, системы ПРИЗ [36,83*], СПРУТ [19], САФРА [22].
Множество разработанных до настоящего времени СП делится на два больших класса, которые можно условно назвать системами жестких методов синтеза (класс А) и системами гибких методов (класс В).
Системы первого класса осуществляют генерацию программ
- 9 -
путем последовательного преобразования и уточнения их прототипов* Исходным прототипом программы является задание на языке пользователя. На заключительном этапе синтеза в программу включаются модули из архива системы согласно их вызовам в преобразованном тексте задания. Рассматриваемые СП молено классифицировать по типу входных заданий:
А1. Задание представляет собой постановку задачи, записанную на специализированном непроцедурном языке [71,88].
А2. Заданием является схема счета, то есть последовательность укрупненных операторов, определяющая в основном порядок вычислений в генерируемой программе [9,21,22,65,78,110].
АЗ. Задание составляется на некотором базовом алгоритмическом языке, расширенном специализированными средствами (встроенные проблемно-ориентированные системы) [3,5,17,112].
Для СП класса В характерно использование структурного моделирования предметной области и вычислительных алгоритмов.
Во входных заданиях для таких синтезаторов обычно отсутствует описание общего порядка вычислений, схема счета вырабатывается автоматически на основе сопоставления поступившей постановки задачи с возможными последовательностями вычислительных модулей и операций, реализованных в системе. В рассматриваемых СП проводится преобразование и порождение моделей алгоритмов и предметной области на базе интеграции информации, хранящейся в системе, со сведениями, поступающими с заданиями.
Данный класс можно разделить на следующие подклассы:
В1. Системы, модели в которых основаны на представлении отношений вычислимости [19,36,47,66,82].
Под отношением вычислимости здесь понимается совокупность
- 10 -
четверок ( х} у 9 Ц $ Р) » где р - вычислительная процедура, х — ее входные параметры, ^ - выходные, £ - условие над значениями входных параметров, при выполнении которого процедура Р применима.
Постановка задачи для таких систем включает список искомых параметров, а также параметры, значения которых известны.
В ходе синтеза программы указанные процедуры или их вызовы располагаются в таком порядке, который обеспечивает корректность вычислений: все входные параметры каждой процедуры должны быть вычислены в предшествующих участках программы или заданы в постановке задачи; каждый искомый параметр вычисляется одной из процедур. В программу встраиваются также средства изменения последовательного порядка выполнения процедур на основе проверки условий Я .
Построение указанной программы может быть проведено с помощью алгоритмов перебора различных вариантов последовательностей процедур. Часто такое построение основывается на автоматическом поиске конструктивного доказательства существования требуемой программы [67,83]. Тот факт, что для решения отдельной задачи существует множество соответствующих последовательностей вычислительных процедур, открывает возможность оптимизации программ в ходе их синтеза [6,13,16,69].
В2. СП, использующие как вычислительные модели систем класса В1, так и модели иных типов, в том числе математические [68,75,90]. Подсистемы автоматизированного построения математических моделей описываются, в частности, в [24,25,61,89].
ВЗ. Системы индуктивного синтеза программ (синтеза программ по примерам) [94,ЮЗ].
- II -
Приведенная классификация является в значительной степени условной, поскольку некоторые системы по отдельным признакам могут быть отнесены к различным классам. Большинство созданных до настоящего времени СП и ПССП принадлежит классам В1, А2, АЗ, методология которых наиболее разработана. Рассмотрим некоторые известные типичные системы, указывая классы, которым они принадлежат.
1. ПРИЗ (А1, В1) [36,83]. Входное задание для этой системы составляется на языке УТОПИСТ [66]. Оно содержит операторы, аналогичные традиционно используемым в алгоритмических языках, а также описания моделей и операторы задач. Модели здесь задаются путем определения значений некоторых параметров, а также отношений вычислимости, для описания которых в УТОПИСТе имеются развитые средства. Операторы задач выражают требования вычисления тех или иных групп параметров на заданных моделях.
Для реализации операторов задач система ПРИЗ осуществляет планирование последовательности вычислений, как это описано при определении класса систем В1. Имеющиеся в системе макросредства позволяют реализовать во входном языке элементы непроцедурного языка пользователя.
2. МАРС (В2) [75] - система генерации программ, выполняющих обработку информации в реляционных базах данных [97]. Входное задание описывается на языке референций РЕФ [8]. Каждая референция задает условия и операции формирования всех атрибутов некоторой связи (отношения между атрибутами) по значениям атрибутов других связей. В языке РЕФ выражаются информационные зависимости между единицами данных без описания
- 12 -
последовательности вычислений. Алгоритм обработки данных формируется автоматически, при этом оптимизируется реализуемое в генерируемой программе дерево запросов к базе данных.
3. САФРА (А2) [22]. В данной системе программа создается на основе схемы счета, в которой перечисляются функциональные имена модулей и вставок (макроопределений), отражающих основные этапы решения задачи. В системе хранятся так называемые модули версии, которые детализируют схемы счета путем установления соответствия между отдельными функциональными именами и архивными именами соответствующих программных единиц. Пользователь имеет возможность окончательной детализации версии в своем задании, на основании чего происходит генерация текста основного модуля и сборка программы.
Разработка СП и ПССП может вестись с помощью стандартного МО (трансляторов универсальных алгоритмических языков, средств операционной системы), а также на базе специализированных систем, составляющих инструментарий синтезаторов программ (ИСП). Процесс построения одних инструментальных систем на основе других подобных же систем в принципе не ограничивается. Так, в [107] описывается СП, с помощью которого строятся препроцессоры, являющиеся инструментами построения других СП; синтезатор программ ЯОД-75 [9] был сгенерирован с помощью ПССП ДИСПРОМ [10].
В качестве ИСП используются следующие средства:
1. Макрогенераторы и препроцессоры [3,29,36,90,112], в частности - препроцессор транслятора с языка Р1/1 [95,113].
2. Средства обработки текстов[17,31,88].
3. Специализированные системы хранения и обработки данных,
- 13 -
в том числе архивы модулей [21,22,110]. Характерным является хранение в архиве вместе с модулями их паспортов, содержащих дополнительную информацию: назначение и характеристики модулей, описания их входных и выходных параметров [65]. Паспорта используются при сборке программ из отдельных модулей.
4. Системы представления знаний (СПЗ), содержащие информацию о предметной области, а также о возможных вычислениях, обеспечиваемых синтезатором программ [14,93]. Как показано в [1,34], указанная информация может быть эффективно представлена на основе реляционной модели данных. Используются также фреймовые представления [81] и семантические сети [109].
Системам представления знаний посвящено значительное количество работ, соответствующие обзоры можно найти в [46,45, 108]. Множество СПЗ можно разбить на три класса: процедураль-ные, декларативные и смешанные. В основе систем первого класса лежит отождествление понятия знаний о некоторых объектах с возможностью моделирования их поведения некоторыми процедурами. Расширение знаний требует изменения набора этих процедур. Поскольку методы обработки данных в настоящее время более развиты, чем методы обработки процедур, СПЗ первого класса не получили широкого применения в СП.
Второй класс разделяется на два подкласса:
1. Логические СПЗ [83], реализующие правила вывода формул, описывающих знания.
2. Системы, основанные на обработке семантических сетей [50]. В таких сетях вершины отождествляются с понятиями описываемой области знаний, дуги - с отношениями между ними.
СПЗ третьего класса используют центральное понятие фрей-
- 14 -
ма [12,77] - некоторой структуры, содержащей как элементы данных (слоты), так и описания механизмов их обработки. Считается, что фрейм задает некоторую стереотипную частную ситуацию в рассматриваемой предметной области, которая сопоставляется с реальной ситуацией путем заполнения его слотов. Системы фреймов описываются на специальных языках [4,44].
Рассмотренные типы ИСП резко отличаются по своему назначению, организации, языковым средствам. Это затрудняет их совместное использование и часто предопределяет одностороннюю ориентацию разработчиков СП на тот или иной тип инструментальных средств.
В связи с этим представляется актуальной проблема создания достаточно универсальных ИСП, соединяющих в себе достоинства инструментальных систем различных типов. Такие ИСП, по-видимому, должны включать средства обработки текстовой информации, поскольку результатом работы СП является текст программы. Рассмотрим некоторые известные системы текстовой обработки.
В языке СНОБОЛ [23,100] обработка строк текста проводится путем сопоставления их с образцами. Образцом является выражение, использующее операции конкатенации (последовательного расположения частей текста) и альтернации (альтернативы между несколькими типами текстовых фрагментов), а также элементарные функции, часть из которых предназначена для сопоставления с простейшими элементами текста. В основном процесс сопоставления организован подобно алгоритму нисходящего синтаксического разбора для контекстно-свободных грамматик [49]. Результатом сопоставления может быть расчленение текста на
- Київ+380960830922