Инструментальная система программирования, ориентированная на построение специализированных синтезаторов программ тема автореферата и диссертации по математике, 01.01.10 ВАК РФ

ВВЕДЕНИЕ.

ГЛАВА I. GEL - СИСТЕМА ОРГАНИЗАЦИИ ВЫЧИСЛЕНИЙ, УПРАВЛЯЕМЫХ ДАННЫМИ

§ I. Схемы функционирования

§ 2. Входной язык.

§ 3. Порядок применения дешнов.

§ 4. Фреймы и семантические сети.

§ 5. Трансляция и редактирование.

§ 6. Убавляющая программа.

ГЛАВА 2. МОДЕЛЬ ПАРАЛЛЕЛЬНЫХ АСИНХРОННЫХ ВЫЧИСЛЕНИЙ

§ I. Концептуальный уровень.

§ 2. Потоки данных

§ 3. Монитор.

§ 4. Уровень примитивов синхронизации

§ 5. Вхфтуальная память.

ГЛАВА 3. ЯЗЫК АНАЛИЗА И ОБРАБОТКИ ТЕКСТОВ

§ I. Общие сведения.*Ю

§ 2. Функции

§ 3. Операции

§ 4. Специальные средства.

§ 5. Примеры программирования.

ГЛАВА 4. ВОПРОСЫ РЕАЛИЗАЦИИ СИСТЕШ-ЙУ

§ I. Раскрутка транслятора.

§ 2. Трансляция.

§ 3. Интерпретация вну^еннего языка.

§ 4. Сервисные средства.*.1D

ГЛАВА 5. СИСТЕМА СИНТЕЗА ПРОГРАММ

§ I. Назначение системы.Ю

§ 2. Входной язык.3D

§ 3. Модель данных.

§ 4. Алгоритмы обработки именных наборов.

ЗАКЖЯЕНИЕ.

СПИСОК ОСНОВНОЙ ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ.

В настоящее время ЭВМ является мощным инструментом решения народнохозяйственных задач, а программирование как сфера деятельности людей приобретает черты материального производства [85]. Известно, что современный уровень индустрии переработки информации характеризуется значительным опережением темпов роста затрат на математическое обеспечение (МО) ЭВМ по сравнению с темпами увеличения расходов на вычислительную технику [18].

В связи с этим ведущими специалистами в области программирования выдвигается требование ускорения развития инструментальных технологических комплексов, которые должны играть значительную роль на всех этапах создания и сопровождения программ [20,33]. Проблемам построения таких комплексов посвящены работы И.В.Вельбицкого, В.М.Глушкова, А.П.Ершова, Д.А.Коря-гина, С.С.Лаврова, И.В.Поттосина, В.Л.Рвачева, В.Н.Редько, И.В.Сергиенко, Э.Х.Тыугу, Е.Л.Ккценко и многих других ученых.

Указанное научное направление способствует повышению производительности труда программистов, а также расширению круга специалистов, которые смогут участвовать в процессе создания программного продукта. Растущий интерес вызывают синтезаторы программ (СП) как инструментальные системы программирования, в которых уровень автоматизации труда программистов наиболее высок. Процесс разработки подобных систем обладает рядом характерных особенностей, поскольку они в той или иной степени имитируют интеллектуальную работу программиста. На практике эти особенности часто выражаются в необходимости обрабатывать данные сложной логической структуры, включая в алгоритмы обработки элементы дедуктивного вьюода.

Традиционные программные средства (универсальные алгоритмические языки, базы данных и др.) часто оказываются недостаточно приспособленными для разработки синтезаторов программ, что приводит к высокой трудоемкости их изготовления, а также сложности сопровождения и модификации. Одним из основных путей решения данной проблемы является создание специализированных инструментальных средств, предназначенных для реализации алгоритмов синтеза программ.

Актуальной является также задача экономичной организации вычислений при автоматизированном построении программ значительных размеров, при котором возникает необходимость многократного просмотра информации во внешней памяти ЭВМ.

Целью диссертационного исследования является разработка принципов организации и создание инструментальной системы программирования, допускающей удобную и эффективную реализацию тех структур данных и алгоритмов их обработки, которые применяются в синтезаторах программ.

Круг применения СП достаточно широк. Часто пакеты прикладных программ (ЕШП), являющиеся распространенной и эффективной формой организации прикладного МО, содержат в себе те или иные средства генерации программ, что повышает их гибкость, позволяет значительно расширить множество решаемых задач Г13, 65].

СП не только являются средством многократного увеличения производительности труда программистов (в [112] описана система генерации программ некоторого класса, повышающая эту производительность в 20 раз), но и определяют одно из возможных направлений повышения интеллектуальности МО [14]. Под интеллектуальностью системы программирования здесь понимается ее способность воспринимать и выполнять задания, содержащие постановки задач без детального описания процессов их решения.

СП создаются для различных областей прикладного и системного программирования:

1) построение систем обработки данных [21],

2) разработка баз данных [Зб],

3) создание ППП [7,68,79],

4) построение управляющих программ для вычислительных систем [35],

5) создание диалоговых и обучающих систем [10,64],

6) реализация численных методов [22,71,88,95].

Задача автоматизации производства программ для конкретных прикладных областей часто выходит за рамки собственно программирования. Рассмотрим, в частности, проблемы численного моделирования сплошных сред [57,60]. В таблице I представлены основные возможные этапы решения подобных проблем, исполнители указаны для случая традиционного подхода - без использования СП.

5-й этап, как правило, проводится без непосредственного участия человека. Применение СП позволяет автоматизировать некоторые другие этапы, при этом на СП возлагается выполнение соответствующих функций исполнителей. Синтез программ будет проводиться по мере поступления постановок задач. При автоматизации 3-4-го этапов эти постановки должны быть математическими, 2-4-го - декларативными.

Таблица I.

Содержание этапа Исполнитель Способ представления результатов этапа

I Постановка задачи Специалист- Декларативные в терминах при- прикладник описания кладной области

2 Выбор и обоснова- Математик, Математические ние математической знакомый с формулы и утверждемодели прикладной ния областью

3 Построение метода Специалист Неформальное решения по вычисли- описание алгоритма тельной математике

4 Программирование Программист Программа

5 Трансляция и ЭВМ со стан- Числовая и символьсчет дартным ная информация математиче- ским обе- спечением

6 Анализ результа- Все указан- Все указанные выше тов ные выше способы исполнители

Очевидно, что при автоматизации отдельных этапов потребуется не только генерация текста программ, но и синтезирование иных элементов данных: формул, фрагментов математических моделей и других.

Часто проблема построения СП настолько сложна, что требует для своего решения предварительной разработки специализированных инструментальных средств.Обычно такие средства оформляются в виде параметрических систем синтеза программ (ПССП). Первоначально идея параметрических систем программирования была вццвинута в [74] применительно к транслирующим системам. В современных ПССП реализуются определенные методы синтеза программ на основе фиксированных форм описаний моделей предметной области (МПО), а также представлений элементарных обрабатывающих модулей и операций. После подстановки фактических параметров вместо формальных, то есть после внесения в базу данных ПССП конкретной MII0 и информации об имеющихся обрабатывающих модулях, такая параметрическая система становится реально действующим СП. МПО, а также архив модулей могут изменяться, пополняться, в чем выражаются модификация и развитие синтезатора программ. В то же время реализованные в нем методы синтеза, как правило, остаются неизменными. На таких принципах основаны, в частности, системы ПРИЗ [36,83"], СПРУТ [19], САФРА [22].

Множество разработанных до настоящего времени СП делится на два больших класса, которые можно условно назвать системами жестких методов синтеза (класс А) и системами гибких методов (класс В).

Системы первого класса осуществляют генерацию программ путем последовательного преобразования и уточнения их прототипов. Исходным прототипом программы является задание на языке пользователя. На заключительном этапе синтеза в программу включаются модули из архива системы согласно их вызовам в преобразованном тексте задания. Рассматриваемые СП можно классифицировать по типу входных заданий:

AI. Задание представляет собой постановку задачи, записанную на специализированном непроцедурном языке [71,88].

А2. Заданием является схема счета, то есть последовательность укрупненных операторов, определяющая в основном порядок вычислений в генерируемой программе ["9,21,22,65,78,110].

A3. Задание составляется на некотором базовом алгоритмическом языке, расширенном специализированными средствами (встроенные проблемно—ориентированные системы) [3,5,17,112].

Для СП класса В характерно использование структурного моделирования предметной области и вычислительных алгоритмов. Во входных заданиях для таких синтезаторов обычно отсутствует " описание общего порядка вычислений, схема счета вырабатывается автоматически на основе сопоставления поступившей постановки задачи с возможными последовательностями вычислительных модулей и операций, реализованных в системе. В рассматриваемых СП проводится преобразование и порождение моделей алгоритмов и предметной области на базе интеграции информации, хранящейся в системе, со сведениями, поступающими с заданиями. Данный класс можно разделить на следующие подклассы: BI. Системы, модели в которых основаны на представлении отношений вычислимости [19,36,47,66,82].

Под отношением вычислимости здесь понимается совокупность

- 10 четверок (* } у,} d j f) , где f - вычислительная процедура, х - ее входные параметры, ^ - выходные, Д - условие над значениями входных параметров, при выполнении которого процедура F применима.

Постановка задачи для таких систем включает список искомых параметров, а также параметры, значения которых известны. В ходе синтеза программы указанные процедуры или их вызовы располагаются в таком порядке, который обеспечивает корректность вычислений: все входные параметры каждой процедуры должны быть вычислены в предшествующих участках программы или заданы в постановке задачи; каждый искомый параметр вычисляется одной из процедур. В программу встраиваются также средства изменения последовательного порядка выполнения процедур на основе проверки условий И .

Построение указанной программы может быть проведено с помощью алгоритмов перебора различных вариантов последовательностей процедур. Часто такое построение основывается на автоматическом поиске конструктивного доказательства существования требуемой программы [67,83]. Тот факт, что для решения отдельной задачи существует множество соответствующих последовательностей вычислительных процедур, открывает возможность оптимизации программ в ходе их синтеза [6,13,16,69].

В2. СП, использующие как вычислительные модели систем класса BI, так и модели иных типов, в том числе математические [68,75,90]. Подсистемы автоматизированного построения математических моделей описываются, в частности, в [24,25,61,89].

ВЗ. Системы индуктивного синтеза программ (синтеза программ по примерам) [94,I03j.

- II

Приведенная классификация является в значительной степени условной, поскольку некоторые системы по отдельным признакам могут быть отнесены к различным классам. Большинство созданных до настоящего времени СП и ПССП принадлежит классам BI, А2, A3, методология которых наиболее разработана. Рассмотрим некоторые известные типичные системы, указывая классы, которым они принадлежат.

1. ПРИЗ (AI, BI) Г36,83]. Входное задание для этой системы составляется на языке УТОПИСТ [66]. Оно содержит операторы, аналогичные традиционно используемым в алгоритмических языках, а также описания моделей и операторы задач. Модели здесь задаются путем определения значений некоторых параметров, а также отношений вычислимости, для описания которых в УТОПИСТе имеются развитые средства. Операторы задач выражают требования вычисления тех или иных групп параметров на заданных моделях.

Для реализации операторов задач система ПРИЗ осуществляет планирование последовательности вычислений, как это описано при определении класса систем BI. Имеющиеся в системе макросредства позволяют реализовать во входном языке элементы непроцедурного языка пользователя.

2. МАРС (В2) [75] - система генерации программ, выполняющих обработку информации в реляционных базах данных [97]. Входное задание описывается на языке референций РЕФ [8]. Каждая референция задает условия и операции формирования всех атрибутов некоторой связи (отношения между атрибутами) по значениям атрибутов других связей. В языке РЕФ выражаются информационные зависимости между единицами данных без описания последовательности вычислений. Алгоритм обработки данных формируется автоматически, при этом оптимизируется реализуемое в генерируемой программе дерево запросов к базе данных.

3. САФРА (А2) [22]. В данной системе программа создается на основе схемы счета, в которой перечисляются функциональные имена модулей и вставок (макроопределений), отражающих основные этапы решения задачи. В системе хранятся так называемые модули версии, которые детализируют схемы счета путем установления соответствия между отдельными функциональными именами и архивными именами соответствующих программных единиц. Пользователь имеет возможность окончательной детализации версии в своем задании, на основании чего происходит генерация текста основного модуля и сборка программы.

Разработка СП и ПССП может вестись с помощью стандартного МО (трансляторов универсальных алгоритмических языков, средств операционной системы), а также на базе специализированных систем, составляющих инструментарий синтезаторов программ (ИСП). Процесс построения одних инструментальных систем на основе других подобных же систем в принципе не ограничивается. Так, в [107] описывается СП, с помощью которого строятся препроцессоры, являющиеся инструментами построения других СП; синтезатор программ ЯОД-75 [9] был .сгенерирован с помощью ПССП ДИСПРОМ [10].

В качестве ИСП используются следующие средства:

1. Макрогенераторы и препроцессоры [3,29,36,90,II2J, в частности - препроцессор транслятора с языка PL/1 [95,113].

2. Средства обработки текстов[17,31,88].

3. Специализированные системы хранения и обработки данных, в том числе архивы модулей [21,22,110]. Характерным является хранение в архиве вместе с модулями их паспортов, содержащих дополнительную информацию: назначение и характеристики модулей, описания их входных и выходных параметров [65]. Паспорта используются при сборке программ из отдельных модулей.

4. Системы представления знаний (СПЗ), содержащие информацию о предметной области, а также о возможных вычислениях, обеспечиваемых синтезатором программ [14,93]. Как показано в [1,34], указанная информация может быть эффективно представлена на основе реляционной модели данных. Используются также фреймовые представления [8l] и семантические сети [109].

Системам представления знаний посвящено значительное количество работ, соответствующие обзоры можно найти в [46,45, 108]. Множество СПЗ можно разбить на три класса: процедураль-ные, декларативные и смешанные. В основе систем первого класса лежит отождествление понятия знаний о некоторых объектах с возможностью моделирования их поведения некоторыми процедурами. Расширение знаний требует изменения набора этих процедур. Поскольку методы обработки данных в настоящее время более развиты, чем методы обработки процедур, СПЗ первого класса не получили широкого применения в СП.

Второй класс разделяется на два подкласса:

1. Логические СПЗ [83], реализующие правила вывода формул, описывающих знания.

2. Системы, основанные на обработке семантических сетей [50]. В таких сетях вершины отождествляются с понятиями описываемой области знаний, дуги - с отношениями между ними.

СПЗ третьего класса используют центральное понятие фрейма [1^,77] - некоторой структуры, содержащей как элементы данных (слоты), так и описания механизмов их обработки. Считается, что фрейм задает некоторую стереотипную частную ситуацию в рассматриваемой предметной области, которая сопоставляется с реальной ситуацией путем заполнения его слотов. Системы фреймов описываются на специальных языках [4,44].

Рассмотренные типы ИСП резко отличаются по своему назначению, организации, языковым средствам. Это затрудняет их совместное использование и часто предопределяет одностороннюю ориентацию разработчиков СП на тот или иной тип инструментальных средств.

В связи с этим представляется актуальной проблема создания достаточно универсальных ЙСП, соединяющих в себе достоинства инструментальных систем различных типов. Такие ИСП, по-видимому, должны включать средства обработки текстовой информации, поскольку результатом работы СП является текст программы. Рассмотрим некоторые известные системы текстовой обработки.

В языке СНОБОЛ [23,100] обработка строк текста проводится путем сопоставления их с образцами. Образцом является выражение, использующее операции конкатенации (последовательного расположения частей текста) и альтернации (альтернативы между несколькими типами текстовых фрагментов), а также элементарные функции, часть из которых предназначена для сопоставления с простейшими элементами текста. В основном процесс сопоставления организован подобно алгоритму нисходящего синтаксического разбора для контекстно-свободных грамматик [49]. Результатом сопоставления может быть расчленение текста на части, выполнение условных переходов в программе.

Язык РЕШАЛ [43] является средством организации рекурсивного вычисления функций путем их сопоставления с явными вызовами в тексте, замены этих вызовов согласно описанию функций фрагментами текста. Данные фрагменты могут содержать другие вызовы.

В системе R77C [18], для которой обработка текста является лишь одной из возможных областей применения, первичной в программе является логическая структура данных (например, описание грамматики языка анализируемых текстов), представленная в виде ориентированного нагруженного графа. Указанная структура доопределяется операторами обработки, записываемыми на дугах графа. Система RTK поддерживает коллективную организацию труда программистов, базирующуюся на постепенном уточ-нениии и детализации структуры программы, отладка которой возможна на всех этапах ее изготовления.

При построении ИСП, расчитанных на широкое применение, невозможно обойти вниманием вопрос об эффективной организации вычислений. Алгоритмы синтеза программ могут потребовать значительных затрат машинного времени, особенно в тех случаях, где размер этих программ не позволяет разместить всю обрабатываемую информацию в оперативной памяти ЭВМ.

Одним из резервов повышения экономичности вычислений является организация параллельного выполнения программ. При этом важной проблемой является осуществление синхронизации параллельных вычислительных процессов с целью разделения моментов использования ими общих ресурсов, в частности, областей памяти.

-16

Можно выделить следующие основные способы организации параллельных вычислений:

1. Синхронные вычисления, основанные на подобии выполняемых одновременно операций.

2. Использование специальных общих переменных (семафоров), с помощью которых процесс сигнализирует о том, что он занял те или иные ресурсы [92]. Подобные же механизмы применяются при явном выделении в процессах критических интервалов - участков программы, на которых используются общие ресурсы [101,104, 106]. Сигналы синхронизации в этом случае вырабатываются автоматически при входе в критический интервал и выходе из него.

3. Создание мониторов - специальных программ, реализующих дисциплину использования общих ресурсов [63,102,105,115]. В целях передачи данных процессы посылают запросы мониторам, которые могут организовывать очереди процессов на удовлетворение этих запросов.

4. Распределенные асинхронные вычисления, задаваемые описанием преобразователей информации и потоков данных между ними [99,III]. Данные в потоках динамически организовываются в очереди, неявным условием начала работы каждого преобразователя является наличие необходимых данных на его входе.

5. Управляемые асинхронные вычисления [2,58,59]. В дополнение к средствам, описанным в предыдущем пункте, предусматриваются спусковые функции, задающие явные условия активизации (начала работы) преобразователей. Подобный тип организации вычислений нуждается в специальной управляющей программе, которая реализует вычисление спусковых функций для проверяемых преобразователей, динамическое присвоение им статусов 11 активный", "пассивный", "проверяемый" в соответствии с событиями,

- 17 происходящими в ходе вычислений.

Значительный интерес представляют специализированные модели параллельных вычислений.

В [15,86] рассматриваются способы вычисления выражений, основанные на неявно определяемых потоках данных между элементами программы, реализующими отдельные операции. В [41] арифметические выражения определяют лишь нижний уровень организации параллельных вычислений, реализуемый в рамках одного оператора. Более высокий уровень описывается специальными выражениями, в которых используются имена операторов, а также операции, задающие ограничения на порядок их выполнения.

В [37,38] предлагается реляционная модель параллельных вычислений для логической СПЗ, основанная на представлении данных как множества конституэнт вида р(С,,.,Ск) , где р -предикатный символ, Ct , Ск - константы. Программа записывается как множество Т замкнутых формул исчисления предикатов первого порядка следующего вида (кванторы и связанные с ними переменные могут отсутствовать):

Р-* Л f) , где Y, Y - конъюнкции атомных формул без функциональных символов.

Работа программы т заключается в построении по начальному множеству конституэнт некоторого минимального (в определенном смысле) множества конституэнт ^ такого,что $ь входит в £ и все формулы программы Т истинны в предположении истинности тех и только тех конституэнт, которые входят в $ . Это построение осуществляется путем ряда параллельных сопоставлений элементов динамически растущего множества конституэнт с атомными формулами из f и продуцировании других конституэнт по атомным формулам из У.

Предлагаемая в [30J концепция смешанных вычислений не выходит за рамки последовательного программирования, однако выражает общий взгляд на вычисления при задержке (запрете) выполнения отдельных операций. Смешанное вычисление включает в себя:

1. Частичное просчитывание исходной программы (выполняются все операции, кроме задержанных непосредственно или вынужденно - в силу информационной или логической зависимости от иных задержанных операций).

2. Проведение генерации остаточной программы, способной завершить требуемые вычисления при отмене всех задержек.

Настоящая диссертационная работа представляет собой попытку создания инструментальной системы программирования, соединяющей и развивающей, насколько это возможно, положительные качества различных программных средств и приемов программирования, применяемых разработчиками СП.

Научная новизна работы заключается в следующем.

1. В предлагаемой системе программисту предоставляется возможность задания правил синтезирования программ, а также определения синтаксиса и семантики анализируемых и синтезируемых элементов данных. В качестве последних, в частности, могут выступать тексты, формулы, различные математические модели.

2. В системе реализован язык описания вычислений, управляемых данными, который базируется на специально построенном аппарате отслеживания ситуаций, инициирующих те или иные вычислительные процессы.

3. Для указанного языка разработан механизм асинхронного параллельного выполнения программ на основе модели смешанных вычислений.

4. Создан язык описания алгоритмов обработки текстов, который характеризуется структурированным представлением программ, а также совмещением в единых синтаксических конструкциях описаний процессов анализа и генерации данных.

5. На основе предлагаемых инструментальных средств построена система синтеза программ решения краевых задач математической физики некоторого класса. Исходными данными для синтеза являются дифференциальные и иные математические уравнения.

Практическое значение диссертационной работы состоит в повышении производительности труда программистов, использующих разработанные инструментальные средства. Эти средства позволяют компактно и достаточно наглядно описывать процессы обработки текстовой информации, а также синтеза программ. Практический интерес представляют построенный синтезатор программ решения краевых задач и синтезированные программы численных расчетов.

Инструментальная система программирования реализована на ЭВМ СМ-4. Ряд ее компонент, применяемых автономно, разработан и для ЕС ЭВМ. Общий объем реализации: 5.1 тысяч команд языка Ассемблер, 7.6 тысяч предложений языка PL /1 , 570 строк текста на оригинальных специализированных языках.

Диссертация состоит из введения, пяти глав, заключения и приложения.

Основные результаты работы состоят в следующем. I. Разработаны специализированные языки программирования: а) G-EL . Этот язык позволяет описывать вычислительные процессы без детального указания порядка вычислений. Достаточным является задание лишь способов построения требуемых элементов данных на основе обработки других элементов. б)Специальные структурированные выражения этого языка обеспечивают описание процессов обработки текстовой информации, в том числе синтаксический анализ, перевод, генерацию текстов.

Z, На основе реализации указанных языков создана инструментальная система программирования, позволяющая задавать правила синтезирования данных различной структуры, в том числе текстов программ.

3. Построена многоуровневая модель асинхронных параллельных вычислений, повышающая эффективность созданной инструментальной системы при обработке информации, объем которой значительно превышает размер оперативной памяти ЭШ.

4. Возможности предлагаемой инструментальной системы продемонстрированы на примере построения синтезатора программ решения краевых задач математической физики одного из классов. Синтезатор строит программы по математическим постановкам задач.

5. Разработана и применена методика совместного использования различных языков программирования. Организовано взаимодействие языков C-EL , ,PL/2 на уровне модулей, предложений и отдельных выражений.

Ниже проводится сравнение некоторых известных систем со средствами, разработанными в рамках данной работы. Для каждой пары сравниваемых систем приводятся их названия, разделенные чертой.

I. ПРИЗ [36,83] - GEL/SN .

В обеих системах предусматривается формализованное описание предметных областей, для которых осуществляется синтез программ, при этом значительное внимание уделяется процедурной форме представления знаний с помощью языков, относящихся к классу алгоритмических.

Синтез программы в этих системах можно представить как реализацию правил вывода на модели предметной области, то есть как процесс порождения новых объектов, составляющих эту модель, на основе уже имеющихся объектов.

В системе ПРИЗ зафиксированы как правила вывода, так и характер используемых информационных объектов. В системе &BL/SN в качестве объектов вывода фигурируют такие общие структуры данных, как именные наборы, а правилами вывода могут служить произвольные алгоритмы обработки объектов. Определение правил вывода, а также синтаксиса и семантики строящихся информационных объектов возлагается на разработчика конкретных синтезаторов программ.

Благодаря этому становится возможным создание СП, оперирующих в процессе своего функционирования сведениями различной природы. Так, в системе El/М объектами вывода могут быть уравнения, разностные схемы, декларативные описания краевых задач.

Особенностями системы &EL являются также исполь

- XI8 зование виртуальной памяти, параллельных вычислений, развитых средств обработки текстов.

2. МАРС [75] - &EL .

Входным языком системы МАРС является РЕф [8], который можно который можно сопоставить с языком GEL » соотнеся друг с другом следующие пары терминов, используемых при их описании: связь - именной набор, атрибут - элемент, референция - демон.

Между указанными системами имеются следующие различия: а) различное назначение систем: генерируемая средствами МАРС программа обрабатывает информацию в реляционной базе данных, в то время как система GEL предназначена для построения синтезаторов программ решения задач различных классов, в частности - задач математической физики; б) любые средства языков PL/1 и $N доступны в CEL при описании демонов; в) с помощью одного демона в языке CEL можно полностью или частично заполнить произвольное число различных именных наборов; в языке РЕФ каждая референция заполняет одну связь, причем полностью; г) в CEL возможны циклические информационные зависимости между именными наборами; д) два предыдущих пункта приводят к тому, что в CEL невозможно привести граф информационных зависимостей к ярусно-параллельной форме и оптимизировать его, что выполняется в системе МАРС; в качестве альтернативы в GEL реализуется модель параллельных вычислений, способствующая повышению экономичности расчетов; е) значениями элементов именных наборов системы GEL могут быть сложно организованные тексты, подвергаемые анализу средствами fN.

3. RTK [18] - М.

Обе системы основаны на подчинении структуры программы структуре обрабатываемых данных, однако ориентация языка &А/ на совместное использование с языками G-EL, PL/1 приводит к отказу от каких-либо графических формализованных представлений программ, поскольку для указанных двух языков такие представления не предусмотрены.

Тем не менее в языке применяется прием, позволяющий придать программе достаточную наглядность: запись ее в структурированном виде с явным указанием номеров уровней. Представление программы в виде выражения или структуры позволило отказаться от использования меток.

Существенной является также возможность состыковки в программе различных конструкций языков $t\f , GEL> PL/1* вплоть до отдельных выражений.

4. СН0Б0Л-4 С23] - $7/.

Как одна, так и другая системы основаны на концепции сопоставления анализируемой строки с образцом, однако в процесс сопоставления проводится по-иному, в него добавлен этап генерации. К оригинальным средствам относятся также следующие: а) множественная замена подстрок; б) включение в образец фрагментов программ и выражений языка PL /1; в) &EN - функция генерации; г) отложенное (с помощью операции "-") сопоставление;

- 120 д) средства трассировки; е) расширенный набор операций, используемых в образцах: из 15 операций II не имеют аналога в языке СН0Б0Л-4.

5. РЕШАЛ [43] - .

Оба алгоритмических языка предусматривают замену подстрок в анализируемой строке. Однако в языке $Ы такие замены осуществляются на основе дерева синтаксического разбора, построенного на этапе анализа, а в языке РЕШАЛ - в случае явного вызова соответствующих функций в анализируемом или преобразованном тексте.

Из всего набора операций в РЕФАЛе могут быть непосредственно выражены только три: конкатенация, альтернация и подстановка; при этом глубина вложенности операций в сопоставляющейся части функции не превышает I.

Текст программы на языке главным образом демонстрирует структуру обрабатываемых данных, а не то, каким образом проводится эта обработка. Это освобовдает программиста от необходимости екурпулезно отслеживать ситуации, которые могут возникнуть при выполнении программы.

В целом система GEL /$Ы представляет собой попытку комплексной разработки инструментальных программных средств, ориентированных на определенный класс проблем, возникающих при создании синтезаторов программ.

Данная работа в дальнейшем может развиваться как в направлении создания конкретных СП, так и в направлении совершенствования средств формализованного описания моделей предметных областей на основе систем именных наборов, а также разработки типовых процедур преобразования и уточнения этих моделей.

ЗАКЛЮЧЕНИЕ

1. Аксенов К.Е.,Каминский Л.Л.,Куликов В.М.,Цыганков Ю.А. Представление проблемных знаний при автоматическом синтезе программ.- В кн.: Представление знаний в системах искусственного интеллекта. М.: ЩНТП, 1980, с.127-131.

2. Алексеев Г.И.,Лельчук Т.И.,Мыльников С.П. Реализация асинхронного управления в языке описания архитектуры проекта МАРС.- В кн.: Параллельные вычислительные и программные системы. Новосибирск: ВЦ СО АН СССР, 1981, с.55-67.

3. Бабенко Л.П. ,Синяговская В.Г. Макробол генератор Кобол-программ.- Кибернетика, 1976, № 2, с.22-27.

4. Байдун В.В. О реализации языка FRL на ЕС ЭВМ.- В кн.: Представление знаний в системах искусственного интеллекта. М.: ВДНТП, 1980, с.106-113.

5. Бежанова М.М. Анализ и систематизация встроенных проблемно-ориентированных систем.- УСиМ, 1981, № 4, с.ПЗ-118.

6. Бежанова М.М. Анализирующая система решения задач на ЭВМ.-В кн.: Некоторые проблемы вычислительной и прикладной математики. Новосибирск, 1975, с.257-263.

7. Бежанова М.М.,Москвина Л.А. Система построения и функционирования пакетов прикладных программ.- Программирование, 1982, № 2, с.59-63.

8. Беличенко В.И.,Романов В.М. Проблемно-ориентированный язык постановки задач РЕФ.- В кн.: Вопросы системного программирования. Киев: ИК АН УССР, 1975, с.56-66.

9. Берестовая С.Н.,Верник Л.В.,Перевозчикова О.Л. Структура и основные приемы реализации системы для решения задач пользователями-непрофессионалами.- УСиМ, 1977, № 6, с.68-73.

10. Берестовая С.Н., Перевозчикова О.Л., Ющенко Е.Л. О применении метода параметризации к построению процессов диалоговых систем.- Кибернетика, 1977, № 6, с.41-60.

11. Бублик Ж.А., Долидзе Д.Ш., Мистецкий Г.Е. Об одном классе задач подземного массопереноса.- В кн.: Краевые задачи теории фильтрации: Тез. докл. Всесоюз. совещания-семинара. 4.1. Ровно, 29 мая I июня 1979 г. Ровно: Б.и., 1979,с.148-149.

12. Бургин М.С., Слюсарь В.И. Структурная организация систем фреймов для построения базы знаний.- В кн.: Представление знаний в системах искусственного интеллекта. М.: ВДНТП, 1980, с.21-24.

13. Бухштаб Б.А., Горлин А.И., Камынин С.С., Корягин Д.А., Лю-бимский Э.З. Об одном методе планирования расчетных цепочек. Программирование, 1981, № 3, с.34-38.

14. Бухштаб Ю.А., Горлин А.И., Камынин С.С., Любимский Э.З. Интеллектуальный пакет, использующий при планировании вычислений знания о предметной области и функциональных модулях.- Изв. АН СССР. Техн. кибернетика, 1981, № 5, с.ПЗ-124.

15. Вальковский В.А. Вычисления с несинхронным поступлением аргументов.- В кн.: Параллельные вычислительные и программные системы. Новосибирск: ВЦ СО АН СССР, 1981, с.5-12.

16. Вальковский В.А. О синтезе оптимальных программ на базе вычислительных моделей.- Программирование, 1980, № 6, с.27-36.

17. Вельбицкий И.В., Ковалев А.Л. Метасистема СТЭЛЗ. Принципы эволюционного развития языков программирования.- УСиМ, 1980, № I, с.56-60.

18. Вельбицкий И.В., Ходаковский В.Н., Шолмов Л.И. Технологический комплекс производства программ на машинах ЕС ЭВМ и БЭСМ-6.- М.: Статистика, 1980. 258 с.

19. Глушков В.М. Фундаментальные исследования и технология программирования. Программирование, 1980, № 2, с.3-13.

20. Говорун Н.Н., Иванов В.Г., Стриж Т.А. К вопросу генерации прикладных программ системы "Гидра". Дубна, 1978. - 15 с.-(Сообщения Объед. ин-та ядер, исслед.: Р I0-II6I2).

21. Горбунов-Посадов М.М., Карпов В.Я., Корягин Д.А., Красот-ченко В.В., Мартынюк В.В. Пакет прикладных программ САФРА. Системное наполнение. М., 1977. - 27 с. - (Препринт / ИПМ АН СССР: № 85)

22. Грисуолд Р., Поудж Дж., Полонски И. Язык программирования СН0Б0Л-4. М.: Мир, 1980. - 268 с.

23. Диваков О.Г., Кузьмин В.А. Алгоритмическое обеспечение процессора построения математических моделей и его реализация. В кн.: Разработка пакетов прикладных программ. Новосибирск: Наука, Сибирское отделение, 1982, с.39-46.

24. Диваков О.Г., Кузьмин В.А., Мадьяров Т.И., Шуров Ю.В. Подход к автоматизации построения математических моделей.

25. В кн.: Пакеты прикладных программ: Методы и разработки. Новосибирск: Наука, Сибирское отделение, 1981, с.63-81.

26. Долидзе Д.Ш. Анализ и обработка текстов средствами языка• В кн.: Языки и системы программирования. Новосибирск: ВЦ Сиб. отд-ния АН СССР, 1981, с.40-46.

27. Долидзе Д.Ш. Инструментальная система программирования

28. GEL /$N и бе использование для автоматизированного построения прикладных программ. В кн.: II Всесоюз. конф. "Автоматизация производства пакетов прикладных программ и трансляторов".: Тез. докл. 12-14 апр. 1983 г. Таллин: ТЛИ, 1983, с.91-92.

29. Долидзе Д.Ш., Мистецкий Г.Е. К вопросу автоматизации расчета подземного массопереноса. УСиМ, 1983, № 4, с.110-113.

30. Елин B.G., Олюнин В.Ю., Скццлов Н.В., Сомин Н.В. Система для разработки больших программных комплексов. Программирование, 1977, № 2, с.55-59.

31. Ершов А.П. Об одном теоретическом принципе системного программирования. Докл. АН СССР, 1977, т.233, № 2, с.272-275.

32. Жоголев Е.А., Пилинец Е.А. Программирование в метасинтак-сических обозначениях. УСиМ, 1980, № I, с.61-65.

33. Жоголев Е.А. Синтаксически управляемое конструирование программ. Программирование, 1979, № 6, с.20-25.

34. Задачи в области программирования в СССР : Редакционная статья . Программирование, 1981, № 3, с.3-6.

35. Ильинский Н.И., Мясников А.В., Стрижевский B.C. Модели и методы в автоматическом синтезе программных систем. В кн.: Представление знаний в системах искусственного интеллекта. М.: ВДНТП, 1980, с.65-71.

36. Казьмин А.И., Менн А.А., Непейвода Н.Н. Табличный подход к автоматическому синтезу программ. Программирование, 1982, № 2, с.24-34.

37. Кахро М.И., Калья А.П., Тыугу Э.Х. Инструментальная система программирования ЕС ЭВМ (ПРИЗ). М.: Финансы и статистика,1981. 158 с.

38. Клещев А.С. Реляционная модель вычислений. Программирование, 1980, № 4, с.20-29.

39. Клещев А.С. Реляционный язык программирования и принципы его реализации на последовательной ЭВМ. Программирование, 1981, № 6, с.45-53.

40. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. М.: Мир, 1978. - 844 с.

41. Котов В.Е. Введение в теорию схем программ. Новосибирск: Наука. Сибирское отделение, 1978. - 257 с.

42. Котов В.Е. О параллельных языках программирования. Кибернетика, 1980, № 4, с.1-10.

43. Котов В.Е. Теория параллельного программирования. Прикладные аспекты. I. Кибернетика, 1974, № I, с.1-16.

44. Красовский А.Г., Флоренцев С.Н., Хорошевский В.Ф. РЕШАЛ.

45. Ч. I. Описание языка и приемы программирования. М.: МИФИ, 1977. - 75 с.

46. Кузин Л.Т., Билялитдинов А.Х., Гришин Е.А. Язык представления знаний KR.L и Я-исчисление. В кн.: Представление знаний в системах искусственного интеллекта. М.: ЩНТП, 1980, с.136-140.

47. Кузин Л.Т. Основы кибернетики. Т. 2. М.: Наука, 1979. -584 с.

48. Кузин Л.Т. Особенности систем представления знаний. В кн.: Представление знаний в системах искусственного интеллекта. М.: ЩНТП, 1980, с.3-7.

49. Лавров С.С., Залогова Л.А., Петрушина Т.И. Принципы планирования решения задач в системе автоматического синтеза программ. Программирование, 1982, № 4, с.35-43.

50. Лебедь М.Я. Структура управления виртуальной памятью в операционной системе ОС ЕС ЭВМ. Вопросы радиоэлектроники. Серия ЭВТ, 1980, вып. I, с.90-100.

51. Льюис $., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. М.: Мир, 1979. - 654 с.

52. Любарский Ю.А. Представление знаний об объекте управления в диспетчерских информационных системах. Программирование, 1978, Ш I, с.41-50.

53. Ляшко И.И., Демченко Л.И., Долидзе Д.Ш., Миетецкий Г.Е. Численный расчет влагосолепереноса в грунте при напорных течениях. В кн.: Теория и расчеты фильтрации: Сб. науч. тр. Киев: Наук, думка, 1980, с.75-83.

54. Ляшко И.И., Долидзе Д.Ш. Синтез программ численного решения краевых задач. Вычисл. и прикл. математика, 1983, вып. 50, с.100-108. ^

55. Ляшко И.И., Сергиенко И.В., Мистецкий Г.Е., Скопецкий В.В. Вопросы автоматизации решения задач фильтрации на ЭВМ. -Киев: Наук, думка, 1977. 287 с.

56. Марчук Г.И., Котов В.Е., Модульная асинхронная развиваемая система. I. Новосибирск, 1978. - 48 с. - (Препринт /1. ВЦ СО АН СССР ; № 86).

57. Марчук Г.И., Котов В.Е. Модульная асинхронная развиваемая система. II. Новосибирск, 1978. - 52 с. - (Препринт / ВЦ СО АН СССР ; № 87).

58. Марчук Г.И. Методы вычислительной математики. М.: Наука, 1977. - 455 с.

59. Матросов В.М., Васильев С.Н., Диваков О.Г., Тятюшкин А.И. О технологии моделирования и оптимизации сложных систем. -В кн.: Пакеты прикладных программ: Методы и разработки. Новосибирск: Наука. Сибирское отделение, 1981, с.21-35.

60. Маурер У. Введение в программирование на языке ЛИСП. -М.: Мир, 1976. 104 с.

61. Мелещук С.В., Недумов А.Н., Толстяков А.В. Об управлении доступом к сложному ресурсу средствами ОС ЕС. Программирование, 1982, № I, с.38-43.

62. Михайлов В.Ю. Логический подход к синтезу правильных обучающих программ. В кн.: Синтез, тестирование, верификация и отладка программ: Тез. докл. Всесоюз. науч. конф. Рига, 22-24 сент. 1981 г. Рига, 1981, с.135.

63. Михайлюк В.А. Об одном подходе к генерации исходных программ в современных пакетах программ на ЕС ЭВМ. Программирование, 1979, № б, с.52-57.

64. Мяннисалу М.А., Тыугу Э.Х., Унт М.И., Фуксман В.Л. Язык УТОПИСТ. Алгоритмы и организация решения экономических задач, 1977, вып. 10, с.80-112.

65. Непейвода Н.Н. 0 построении правильных программ. Вопросы кибернетики, 1978, вып. 46, с.88-122.

66. Опарин Г.А. САТУРН метасистема для построения пакетов прикладных программ. - В кн.: Разработка пакетов прикладных программ. Новосибирск: Наука. Сибирское отделение, 1982, с.130-160.

67. Поттосин И.В. Направленные преобразования линейного участка. В кн.: Языки и системы программирования. Новосибирск: ВЦ Сиб. отд-ния АН СССР, 1981, с.47-63.

68. Развитие исследований по теории фильтрации в СССР (1917 -1967) / Под ред. П.Я.Полубариновой-Кочиной. М.: Наука, 1969. - 545 с.

69. Рвачев В.Л. Теория Я -функций и некоторые ее приложения. -Киев: Наук, думка, 1982. 551 с.

70. Редько В.Н. Композиции программ и композиционное программирование. Программирование, 1978, № 5, с.3-24.

71. Редько В.Н. Основания композиционного программирования. -Программирование, 1979, № 3, с.3-13.

72. Редько В.Н., Ющенко Е.Л. Алгоритмические языки и транслирующие системы. Кибернетика, 1967, № 5, с.87-91.

73. Романов В.М., Ющенко E.JI. Методы и системы автоматизированного проектирования программ обработки данных. Киев, 1980. - 40 с. - (Препринт / ИК АН УССР ; 80-19).

74. Самарский А.А. Введение в теорию разностных схем. М.: Наука, 197I. - 624 с.

75. Староверов А.Н., Малкин И.В., Черняев В.В. Об одном подходе к реализации систем представления знаний в АСУ. В кн.: Представление знаний в системах искусственного интеллекта. М.: ВДТП, 1980, с.75-79.

76. Стогний А.А., Ющенко E.JI., Машбиц Е.И., Верник Л.В. Человеко-машинная система решения задач обработки данных, ориентированная на непрофессиональных пользователей ЭВМ. -Алгоритмы и организация решения экономических задач, 1977, вып. 9, с.36-51.

77. Сухомлин В.А. Метасистема для построения проблемно-ориентированных языков и пакетов прикладных программ. Программирование, 1976, № 2, с.63-70.

78. Терещенко В.А. Сетевая память, принципы и реализация.

79. В кн.: Математические основы систем искусственного интеллекта. Киев: ИК АН УССР. Научный совет по проблеме "Кибернетика", 1981, с.56-64.

80. Тыугу Э.Х. Вычислительные фреймы и структурный синтез программ. Ученые записки Тартусского государственного университета, 1981, вып. 594. Диалоговые системы и представление знаний, с.149-161.

81. Тыугу Э.Х. На пути к практическому синтезу программ.

82. Кибернетика, 1976, № 6, с.34-43.

83. Тыугу Э.Х., Харф М.Я. Алгоритмы структурногосинтеза программ. Программирование, 1980, № 4, с.3-13.

84. Уинстон П. Искусственный интеллект. М.: Мир, 1980. -519 с.

85. Фуксман А.Л. Технологические аспекты создания программных систем. М.: Статистика, 1979. - 184 с.

86. Халилов А.И. Распараллеливание арифметических выражений методом последовательного углубления. Программирование, 1979, № I, с.15-25.

87. Хмельник С.И. Обработка списков в ЭВМ ЕС. Программирование, 1981, № 6, с.54-63.

88. Шевченко А.Н. Программирование структур решения краевых задач на языке RL/1 . Харьков, 1979. - 24 с. - (Препринт / ИПМ АН УССР ; № 132).

89. Шуров Ю.В. Лингвистический процессор в системе автоматизации построения математических моделей. В кн.: Разработка пакетов прикладных программ. Новосибирск: Наука. Сибирское отделение, 1982, с.46-54.

90. Юдин С.М. Язык описания вычислений на моделях. М., 1980. - 16 с. - Рукопись предст. Московским авиационным институтом. Деп. в ВИНИТИ 31 марта 1980 г., № 1218-80.

91. Кйценко Е.Л., Перевозчикова О.Л. Развитие языков программирования и диалоговых систем в СССР. Кибернетика, 1976, № 6, с.16-33.

92. Язык программирования АДА : (предварительное описание). -М.: Финансы и статистика, 1981. 190 с.

93. АЛ. An tr-pzxCme-yit щ. ktiowizJtgzautomatcc рхорхаммСпр. fati^, Inte£. t , V. 12} jf 2}p. 13-119.1. Baizdcn

94. J.M. On Cnefuctcve o^ px e^xamA. —

95. Seated o^ata. Banis. ~ Comw\tu\.1. ACM, WO, 1.11, лГч,p. зп-зп.

96. Cc&tK У., Ca-x-icLgl coiitctcom. oj! Jlata ?txuttuiz$.4Ш Conput. Sutlr., 19S1, b.13, /1^3, p341-3Gi.99. Зеппс? J. 6.

97. Fcxft Mif ion а оftata " Flow Pxottduxai' MlT . CowwMnice'tcc/i tftxuctvt€fxoy MEMO (93-1 ,1914. -30p.

98. Gic$wotJl Я.Е. A Icstoxy tfa SNOBOLtuHjucLgiS. tl&PLAN Notcc} 19И, nr.13 , Jv>3,p.2K-30$.101. Hcwjre* Z9./?.1. Conxpaxtfon Two CoMtp"t$

99. Acta U/cx^tcca, 19U , ъЛ, jf°3,p. 190-199.f02 . Hansen P.O. рхо^хатмС»-^ Сап^нл^*- Concuxxetit1. Putt*?.

100. IEEE TxanfactConf oj! So^twaxt ЕпуСпе.гхСл^ 19H, Jf'L , f. 19$-lot.

101. Haxt R. PattlXH af a taot in%txtc^a^tt'^w?. So^twaxZ - Piatt. «"><1 E%pzx ,,19Ц0, 10,f.kor-kllfoif. Ho«xe C.A. $ztpuet\tta€ Pxcczs$t$.

102. Comnxun. лг/ч, mi, ir.nt j\T*sгрлы->£??. 10 f. Htate C.A. Monitors: An opexatCncp £yfteyi\ StiuituxCng

103. Concept. Comnun. ACM, 1974, ъ. n, Jf'10 ^.SW-tf?. 106. Hoatt C.A. TowcKtls a TAeoxy 0f PaxMei faopxawty. -In: Opixatinjj, fpftimf TkcAnt'<yue$ , A/ew Ye-t^:

104. Academe /W , 1911} f.lZ0~2Z0.10?. tottifcfi t МясАиха M.f petttzofef W. ir*p(e.r**nt*tCon a spttiaf. puy.

105. Nctu19S0t г-.ff, ylT'S^.tftf-r?.