Разработка и исследование структурно-ориентированного редактора и компилятора запросов системы функционально-логического программирования Бебчик Алексей Михайлович

Содержание к диссертации

Введение

1. Языки и системы декларативного программирования 11

1.1. Основные парадигмы программирования 11

1.1.1. Императивная парадигма 11

1.1.2. Декларативная парадигма 12

1.1.2.1. Функциональное программирование 13

1.1.2.2. Логическое программирование 16

1.1.2.3. Функционально-логическое программирование 20

1.2.Методы описания синтаксиса и семантики

языков программирования 23

1.2.1. Описание синтаксиса языков программирования... 23

1.2.1.1. Форма Бэкуса-Наура 25

1.2.1.2. Синтаксические диаграммы 26

1.2.1.3. Синтаксический анализ 27

1.2.2. Методы описания семантики языков программирования 27

1.2.2.1. Статическая семантика 28

1.2.2.2. Динамическая семантика 29

1.3.Интегрированные среды разработки программ 31

1.3.1. Средства текстового построения программ 32

1.3.2, Графическое программирование 33

1.4.Основные формы реализации языков программирования 33

1.4.1. Компиляция 33

1.4.2. Интерпретация 35

1.4.3. Смешанная форма 36

1.5.Выбор программных средств для реализации СФЛП 37

Основные результаты и выводы 38

2. Язык функционально-логического программирования S-FLOGOL 39

2.1.Теория направленных отношений (НО) 39

2.1.1. Основные понятия 39

2.1.2. Языки схем направленных отношений 40

2.1.2.1. Принципы построения 41

2.1.2.2. Комбинаторные константы 42

2.1.2.3. Операции композиции НО 43

2.1.3. Сетевое представления схем направленных отношений 44

2.1.3.1. Основные определения 44

2.1.3.2. Графическая нотация 45

2.1.3.3. Элементарные сети и композиции сетей 45

2.1.3.4. Сетевая грамматика и сетевой язык 47

2.2.Язык функционально-логического программирования FLOGOL 48

2.2.1. Принципы построения 48

2.2.2. Основные элементы и особенности языка FLOGOL 48

2.2.2.1. Модульная структура 48

2.2.2.2. Способы описаний направленных отношений 50

2.3.Входной язык системы функционально-логического программирования S-FLOGOL (Small FLOGOL) 55

2.3.1. Общая характеристика и система ограничений 55

2.3.2. Формальное семантики языка S-FLOGOL 57

2.3.2.1. Основные принципы описания семантики 57

2.3.2.2. Семантика выражений 58

2.3.2.3. Семантика синтаксических конструкций языка 61

2.3.2.4. Семантика многомодульных запросов 71

Основные результаты и выводы 73

3. Компилятор запросов программ на языке S-FLOGOL 74

3.1.Цель, задачи и стадии компиляции 74

3.1.1. Предварительная стадия компиляции 74

3.1.2. Основная стадия компиляции 76

3.1.3. Заключительная стадия компиляции 76

3.2.Принципы формирования ЛПК 77

3.2.1. Метод конструктивного построения КССГ 78

3.2.2. Управляющие правила компиляции 80

3.3.Методы формирования сетевых определений НО 81

3.3.1. Язык описания сетевого представления SimpIeNet 81

3.3.2. Конструктивное построение сетей 83

3.3.3. Формирование определений для вызова НО 85

3.4. Правила компиляции основных конструкций языка S-FLOGOL 87

3.4.1. Вычисление имени отношения 87

3.4.2. Компиляция выражений 89

3.5.Компиляция многомодульных запросов 101

3.6.Оптимизационные модификации методов компиляции запроса 102

3.6.1. Оптимизация компиляции многомодульных запросов 102

3.6.2. Оптимизация получения спецификатора 103

3.7.Особенности реализации компилятора запросов СФЛП 105

3.7.1. Технологический процесс компиляции в СФЛП 105

3.7.2. Индикация хода выполнения компиляции запроса 106

3.7.3. Компиляция системных отношений 107

3.7.4. Редукция имен скомпилированных отношений 108

Основные результаты и выводы 108

4. Структурно-ориентированный редактор СФЛП 110

4.1 .Технология дедуктивного построения программ (ТДГТП) 110

4.2.0сновные задачи ТДПП 112

4.3.Теоретические основы и базовые операции ТДПП 113

4.3.1. Основные определения 113

4.3.2. Синтаксическая корректность программ 115

4.3.3. Структурное представление программы 116

4.3.4. Основные технологические операции ТДПП 118

4.4.Специализированные технологические операции ТДПП 120

4.4.1. Операции работы с опциональными символами 120

4.4.2. Операции работы со списками 124

4.4.3. Операции построения выражений 126

4.4.4. Ручной ввод 129

4.4.5. Использование дерева объектов 130

4.4.6. Работа с буферами обмена 131

4.5.Отображение текста программы 132

4.5.1. Стилистическое оформление 132

4.5.2. Автоматическое структурирование текста программы 133

4.5.3. Изменение детализации отображения программы 135

4.6.Структурно-ориентированный редактор 136

4.6.1. Принципы построения и архитектура редактора 137

4.6.2. Интерфейс редактора 138

4.6.3. Инструменты общего назначения 139

4.6.4. Расширенный режим работы курсора 140

4.6.5. Специализированные инструменты 140

4.6.6. Построение программы при помощи клавиатуры 141

4.6.7. Компиляция запросов 142

Основные результаты и выводы 132

Заключение. Основные результаты работы 145

Список сокращений 146

Список литературы

• Декларативная парадигма
• Методы описания семантики языков программирования
• Сетевое представления схем направленных отношений
• Правила компиляции основных конструкций языка S-FLOGOL

Введение к работе

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

Одним из наиболее актуальных направлений развития современных языков декларативного типа является поиск новых формализмов, позволяющих естественным образом соединить методы и средства функционального и логического программирования в рамках единого подхода. Одним из таких объединяющих формальных понятий является направленное отношение (НО), введенное и исследованное в работах В.П. Кутепова и В.Н. Фалька [33,34,43]. В последней работе был также описан высокоуровневый язык интегрированного функционального, логического и реляционного программирования FLOGOL, созданный на основе теории НО. В рамках выполнения проекта РФФИ № 01-01-00690 «Разработка теоретических основ построения вычислительных сред и интеллектуальных систем, ориентированных на функционально-логический стиль программирования» была поставлена задача создания системы функционально-логического программирования (СФЛП) на базе этого языка, что и явилось основной целью диссертации.

Язык FLOGOL является современным языком декларативного программирования, предоставляющим средства компактного описания сложнооргани-зо ванных областей данных с использованием технологических принципов объектно-ориентированного программирования и средств схемной надстройки, характерных для языков высокого уровня. Сложность синтаксиса и семантики языка определяют важность создания специализированных средств как поддержки самого процесса программирования, так и выбора методов и алгоритмов компиляции программ к форме, непосредственно воспринимаемой вычислительным компонентом СФЛП. В диссертации решены следующие научные и

7 прикладные задачи, связанные с указанными аспектами реализации системы

программирования, осуществленной автором совместно с Бебчиком Ан.М.; -проанализированы методы реализации современных языков и систем декларативного программирования с целью определения возможности их применения при реализации СФЛП; -выполнен анализ методов описания семантики языков функционального и

логического программирования; -уточнены принципы построения языка FLOGOL, определено его представительное подмножество S-FLOGOL и осуществлено формальное описание его синтаксиса и семантики; -разработаны принципы и методы обработки S-FLOGOL-запросов на вычисления; -разработаны специальная технология дедуктивного построения и ввода

S-FLOGOL-программ и соответствующие интерфейсные средства; -осуществлена программная реализация и интеграция в СФЛП компилятора запросов и структурно-ориентированного редактора, основанного на разработанной технологии дедуктивного построения и ввода программ; -проведено тестирование работы СФЛП на наборе типовых задач декларативного программирования из области искусственного интеллекта. Методы исследования. При выполнении работы использовались методы теории направленных отношений, теории формальных грамматик, методы формального описания синтаксиса и семантики языков программирования, методы объектно-ориентированного программирования, а также методы тестирования программных продуктов.

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

8 Научная новизна. В работе получены следующие новые научные результаты:

1. Предложена система ограничений языка FLOGOL, позволяющая выполнить компиляцию программы в представление в виде конечной контекстно-свободной сетевой грамматики (КССГ) до начала работы подсистемы исполнения запросов и значительно упрощающая реализацию языка без существенного снижения его основных выразительных возможностей.

2. На основе предложенной системы ограничений разработан язык S-FLOGOL, формально описаны его синтаксис и семантика.

3. Сформулированы основные принципы обработки S-FLOGOL-запросов в СФЛП и разработаны алгоритмы их реализации, опирающиеся на формальное описание семантики языка.

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

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

Апробация работы. Основные результаты диссертации докладывались и обсуждались на научно-технических конференциях МИРЭА (Москва, 2002, 2003, 2004), международных конференциях «Информационные средства и технологии» (Москва, 2003, 2004), всероссийской межвузовской научно-технической конференции «Микроэлектроника и информатика — 2004» (Зеленоград, 2004), международной научно-технической конференции «Информаци-

9 онные технологии в науке, образовании и производстве» (Орел, 2004), международной конференции «Континуальные алгебраические логики, исчисления и нейроинформатика в науке и технике» (Ульяновск, 2004), международной научно-технической конференции «Компьютерное моделирование 2004» (Санкт-Петербург, 2004) и «Девятой Национальной конференции по искусственному интеллекту с международным участием КИИ-2004» (Тверь, 2004).

Реализованная СФЛП демонстрировалась на выставке программных продуктов «Девятой Национальной конференции по искусственному интеллекту с международным участием КИИ-2004».

Публикации. Основные результаты, полученные при выполнении диссертационной работы, опубликованы в 9 печатных работах.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы (93 наименования) и приложений. Диссертация содержит 154 страницы машинописного текста без учета приложений.

В первой главе проводится анализ принципов построения и реализации современных языков и систем декларативного программирования. Определяются методы описания синтаксиса и семантики языка FLOGOL. Рассматриваются современные технологические средства разработки и отладки программ. Выбирается форма реализации языка FLOGOL. Формулируются требования к СФЛП и определяются основные подходы к ее созданию.

Во второй главе кратко представлены основные понятия теории НО и используемые в работе средства построения языков НО, выполнен анализ синтаксиса и семантики языка FLOGOL. Приводятся результаты исследования операций композиции НО. Вводится система ограничений языка FLOGOL, которые несколько ограничивают его выразительные возможности, однако позволяют выполнить компиляцию запроса в представление в виде конечной КС СГ с целью повышения эффективности выполнения FLOGOL-программ. На основе

10 введенных ограничений разрабатывается язык S-FLOGOL (Small FLOGOL),

формально описываются его синтаксис и семантика.

В третьей главе формулируется цель и задачи компиляции, выделяются основные стадии компиляции. Определяется метод конструктивного построения КССГ и предлагается использование логической программы-компилятора (ЛПК) для его реализации. Описываются правила трансляции основных конструкций языка S-FLOGOL. Предлагается язык описания сетевого представления SimpleNet Приводится ряд оптимизационных преобразований, позволяющих сократить время выполнения компиляции. Кратко описываются особенности программной реализация компилятора запросов.

В четвертой главе предлагается оригинальная технология дедуктивного построения программ (ТДГШ), уточняются цель и задачи ее разработки, определяются основные методы и специальные расширения ТДГШ. Разрабатывается внутреннее представление программ. Определяется схема стилистического оформления и разрабатывается алгоритм автоматического структурирования текста программ. Описывается архитектура и особенности реализации структурно-ориентированного редактора СФЛП, поддерживающего ТДГГП.

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

1. ЯЗЫКИ И СИСТЕМЫ ДЕКЛАРАТИВНОГО ПРОГРАММИРОВАНИЯ.

1.1 Основные парадигмы программирования.

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

1.1.1. Императивная парадигма. Императивное программирование предполагает задание программы в виде последовательности инструкций, определяющих алгоритм ее решения [38], то есть в виде явного указания того, как именно надо решать задачу. Такой подход объясняется стремлением к наиболее эффективному выполнению программ, естественным образом обеспечиваемому в том случае, если язык программирования опирается на архитектуру используемой ВМ. Поскольку основания часть существующих в настоящий момент ВМ построена по архитектуре Фон-Неймана, разделяющей основную память и вычислительный блок процессора, процесс выполнения программы заключается в последовательной загрузке значений из ячеек памяти, выполнения вычислительных операций и записи полученных результатов в память ВМ. Императивные языки, по сути, на более высоком уровне абстракции предлагают программисту записывать программу в терминах выполнения отдельных операций и изменения состояния ячеек памяти, что, как правило, существенно отличается от семантики решаемой задачи и осложняет понимание программы. Другим недостатком императивного подхода является возможность изменения присвоенных ранее значений переменных, а также использование глобальных переменных, что может приводить к нежелательным побочным эффектам [44].

Несмотря на эти недостатки, императивное программирование является наиболее распространенным благодаря, во многом, исторически более раннему появлению, высокой скорости выполнения программ, а также наличию широкого круга задач, имеющих естественное алгоритмическое описание. Очевидно также, что в области системного программирования императивные языки на данный момент практически не имеют достойной альтернативы. Тем не менее, для решения многих задач, в том числе задач из области искусственного интеллекта [20,41], алгоритмический подход не представляется естественным, что ставит задачу исследования иных подходов к программированию. 1,1.2. Декларативная парадигма. Декларативное программирование [24] предполагает задание программы в виде описания задачи в терминах некоторого формализма без явного указания того, каким именно образом должна вычисляться эта программа. Выбор подходящего метода решения вычислительная система, как правило, производит самостоятельно, позволяя при этом программисту указать дополнительную информацию, которая может быть полезна для более эффективного выполнения программы.

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

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

ІЗ недостатком систем декларативного типа являются, как правило, низкая (относительно систем императивного типа) скорость выполнения программ и, в общем случае, высокие требования к объему свободной оперативной памяти.

Декларативное программирование можно условно разделить на несколько направлений: функциональное, логическое, функционально-логическое. 1.1.2.1. Функциональное программирование. Функциональное программирование [47,44] предполагает определение программы при помощи математических функций, задающих различные семантические объекты предметной области. При этом выражение одних функций через другие задается при помощи ап-пликативного применения функций или их композиции. Первый функциональный язык LISP был создан Дж. Маккарти [76] для символьных вычислений, в частности, для решения задач из области искусственного интеллекта. Этот язык и его диалекты до сих пор широко используются в практических и исследовательских целях.

Теоретической основой большинства аппликативных языков программирования функционального типа является Х-исчисление [54,3,66]. В Я-исчислении функции задаются при помощи Я-выражений, конструируемых из переменных применением Я-оператора и операции применения. В языках программирования, как правило, при построении выражений также используются константы, обычно представляющие натуральные числа, арифметические операции, булевы значения и функции, условные функции, конструкторы и т.д.

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

14 случае, если такая форма для редуцируемого выражения существует. Другим важным преимуществом ленивой модели является возможность работы с неполными структурами данных. Современные функциональные языки используют как ленивую (Miranda, Haskell), так и энергичную (Scheme) модели вычисления программ.

Реализации функциональных языков также различаются статическим (ML) или динамическим (CommonLisp) связыванием переменных. Хотя статическое связывание признано более безопасным, поддержка динамического связывания позволяет повысить гибкость языка.

Важной особенностью функциональных языков программирования является использование механизма сопоставления с образцом [60,90]. Этот механизм, в частности, позволяет применять различные определения функции в зависимости от того, какие аргументы были переданы при ее вызове, а также разбирать конструктивно построенные аргументы вызова и использовать их отдельные элементы при определении результата вычисления функции. Сопоставление с образцом используется в таких языках, как Haskell, Hope, Miranda, однако, по-видимому, впервые этот метод был предложен в отечественном функциональном языке Refal, созданным Турчиным [88].

Одним из высокоуровневых средств языков функционального программирования является возможность определения функций высших порядков (функциональных форм), принимающих в качестве параметра имя или определение другой функции. Однако на практике можно ограничиться использованием лишь небольшого числа таких форм, покрывающих потребности в применении функций высших порядков. Весьма показательным в этом смысле является язык FP [68,49,48], в котором жестко закреплен ограниченный набор функциональных форм (константа, условное выражение, композиция, конструкция, применить-ко-всем и вставка) и не предоставляется возможности определения собственных пользовательских форм. Программирование на языке FP ведется чисто композиционным образом без оперирования индивидными переменными

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

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

Язык LISP и многие его диалекты являются нетипизированными языками, или, более точно, языками с динамической типизацией, позволяющей определять несоответствие типов во время исполнения программы при помощи встроенных, либо определенных пользователем типовых функцией. Динамическая типизация является удобным средством обработки разнородных данных, но в то же время, она не позволяет выполнять обнаружение ошибок несовместимости типов на стадии компиляции. Поэтому большинство современных языков, предназначенных для промышленного использования, имеют статическую типизацию, позволяющую выявить большое число ошибок на стадии компиляции и тем самым существенно повысить надежность программного обеспечения, а также снизить трудозатраты на его разработку. Наиболее широкое распространение получила системе типов Милнера [77], позволяющая задавать алгебраические типы данных и автоматически выводить тип данных в случае, если он не был задан пользователем явно. Статическая типизация также являет-

ся основой для большинства объектно-ориентированных расширений декларативных языков, таких как ML [78], Haskell [50], Objective Caml [61] и др.

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

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

1.1.2.2. Логическое программирование. Другим подходом к декларативному программированию, получившим название логического программирования [72,83,19], является использование аппарата математической логики для описания и вычисления программ. Программа в логическом программировании представляет собой формальную модель предметной области, заданную при помощи языка логики предикатов. Предикаты определяют свойства объектов и

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

Заметим, что под логическим программированием, по-видимому, следует понимать лишь такую систему, для которой найдена эффективная с вычислительной точки зрения процедура вывода, поскольку без такой процедуры логическую программу, скорее, следует рассматривать лишь как формальную спецификацию задачи [1], На сегодняшний день эффективные с точки зрения выполнения с применением ВМ процедуры вывода найдены лишь для небольшого числа формализмов на основе логики предикатов, наиболее известным из которых является логика хорновских дизъюнктов. В связи с этим логическое программирование обычно ассоциируется с основанным на хорновских дизъюнктах языком Пролог [56].

Основной причиной признания Пролога как практически полезного языка логического программирования является положенная в его основу эффективная процедура логического вывода, называемая методом резолюций [83], а также прекрасная реализация, созданная Д. Уорреном в Эдинбургском университете [91,62]. Для повышения эффективности вычисления в Пролог введены также средства, нарушающие чистоту декларативной семантики языка, а именно — отсечение, отрицание как неудача (negation as failure) [55] и внелогические предикаты (assert, retract), обеспечивающие динамическую модификацию программы во время ее исполнения. Использование этих средств стало восприниматься как естественная часть логического программирования, однако их применение ведет к большому числу ошибок, что стимулирует исследования в области повышения эффективности вычислений без нарушения чистоты декларативной семантики языка [24]. Другим недостатком Пролога является зависи-

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

За относительно небольшую историю развития логического программирования было предложено большое число расширений хорновского программирования, связанных, в частности, с введением высокоуровневых средств, позволяющих использовать определенные на правилах программы метапредика-ты. Например, Ковальским было предложено использовать метапредикат Demo(P,Q,X), где Р — программа, Q - запрос к программе Р, и X — результат выполнения этого запроса; при этом программы, запросы и результаты вычисления определяются в виде термов. Вычисление самого метапредиката Demo производится при помощи специальной логической метапрограммы [51].

Другим расширением является использование параметризованных определений, в которых имя предиката-параметра является свободной переменной. Одним из подходов к параметризации является указание в заголовке правила имени предиката в качестве предикатной переменной, используемой в правой части правила, например P(x,y,F)<- F(x,y). Другим подходом, предложенным В.Б. Борщовым [18,19], является использование специальной синтаксической конструкции, в которой имя отношения-параметра указывается в квадратных скобках после имени предиката, например P[F](x,y) <- F(x,y). Похожий

поход используется в языке HiLog, который позволяет использовать переменные и сложные термы на месте функтора. Известно [56], что параметризованные программы могут быть преобразованы в обычные логические программы.

Расширения логического программирования направлены также на введение возможности декларативно чистого управления ходом вычисления. В языке Пролог-П [57] реализован специальный системный предикат второго уровня freeze(X,Goal), позволяющий задерживать вычисление цели Goal до тех пор, пока переменная X не получит значения. Такой подход снижает зависимость

19 порядка вычислений от расположения целей в теле правила и повышает декларативность программы.

В SICStus- и СІао-прологе используется более развитый подход, позволяющий задавать условие вычислимости цели в виде when(Cond, Goal), где в условии Cond могут использоваться обычные системные предикаты nonvar, ground и логические связки. В языках MU-Prolog, NU-Prolog и Gedel подобные декларации используется непосредственно в объявлениях предикатов.

Другой аспект управления вычислением, а именно, установление допустимости ветвления дерева решений, реализуется в языках VisuaWrolog и Mercury [85] с применением так называемых деклараций видов. Например, определение предиката append в виде :-mode append(in, in, out) det указывает на детерминированный характер его вычисления. Применение подобных деклараций позволило разработчикам Mercury полностью отказаться от оператора отсечения без потери эффективности вычисления программ.

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

В языке определен набор встроенных различающих деревьев, называемых также режимами (mode). Например, режимы in и out определяют специфические ограничения для значений, рассматриваемых как входные и выходные атрибуты отношения, соответственно. Заметим, что формального разделения вхо-

20 дов и выходов отношения здесь нет; присутствуют лишь полезные с практической точки зрения ограничения. Например, при задании режима in для некоторого атрибута отношения, вычисление этого отношения не будет начато до тех пор, пока значение указанного атрибута будет содержать несвязанные переменные. Как и отдельные языки функционального типа, многие логические языки также поддерживают объектно-ориентированные расширения (VisualProlog, Ас-torProlog [37] и др.).

1.1.2.3. Функционально-логическое программирование. Данное направление декларативного программирования ставит своей основной задачей объединение преимуществ функционального и логического программирования, в частности, возможности недетерминированных вычислений логического программирования и эффективности вычисления программ функциональных языков. В свое время Дж. Робинсон называл логическое программирование реляционным, а совокупность функционального и реляционного программирования — логическим программированием, особо подчеркивая их тесную взаимосвязь. Однако, эта терминология не нашла широкого распространения и в нашей работе мы будем использовать термин функционально-логическое программирование.

Робинсоном был разработан язык LogLisp [84], объединяющий в себе методы функционального и логического программирования. Основой языка является LISP, в который добавлены специальные примитивы под общим названием Логика, организующие механизм поиска с отличной от используемой в Прологе стратегией поиска, обеспечивающей выбор очередной ветви вычисления на базе некоторой эвристической оценки, правила вычисления которой могут быть заданы пользователем. Таким образом, формулировка и вызов на вычисление логической программы записываются непосредственно в LISP-программе, причем полученные в виде списка результаты вычисления могут быть естественным образом обработаны с помощью того же LISP&.

LogLisp обладает еще одним важным преимуществом перед чистыми языками логического программирования — после каждого шага вывода выпол-

21 няется обычная і/УР-редукция, позволяющая, в некоторых случаях, упростить программу или исключить из рассмотрения те ветви, которые гарантированно не приведут к получению результата вычисления. И все же, явное разделение функционального и логического программирования не позволяет рассматривать LogLisp как язык, естественным образом сочетающий эти виды программирования, что, по-видимому, явилось причиной его низкой популярности.

Интересный подход к функционально-логическому программированию выражен в достаточно новом языке Curry [63]. Авторы языка называют его мультипарадигмным, поскольку из функциональных языков Curry использует вложенные выражения, ленивые вычисления, функции высших порядков, из логических — логические переменные, неполные структуры данных и встроенный поиск, из языков программирования в ограничениях — параллельное вычисление ограничений с синхронизацией логических переменных [64].

Дополнительным преимуществом по сравнению с логическими языками указывается также более эффективное детерминированное вычисление функций. Подобно LogLisp-y, после каждого шага логического вывода применяется упрощение (редукция) программы, а вместо сопоставления с образцом для вычисления функций с логическими переменными применяется основанная на унификации технология сужения (Narrowing) [81,82,93].

Другим подходом является интеграция функций в логические языки. Следует различать два уровня интеграции функций — синтаксический уровень и уровень вычислений. Ряд языков содержат чисто синтаксические средства описания функций, преобразуемых в предикатную форму описания на этапе компиляции запроса {flattening) [74,75,79]. Интеграция функций на уровне вычислений предполагает реализацию специализированных механизмов вычисления функций, как правило, учитывающих их детерминизм и исключающих установку точки выбора (choice point) в дереве решений, что позволяет сократить время выполнения программы [85].

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

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

Одним из таких формализмов является формализм направленных отношений (НО), предложенный в разработанной совместно В.П. Кутеповым и В.Н. Фальком теории направленных отношений [33,43], предполагающей выражение основных семантических объектов программы (функций, констант, кортежей, отношений и др.) в виде НО определенной арности, возможно, обладающих фундаментальными свойствами функциональности и тотальности. На основе формализма НО В.Н. Фальком разработан функционально-логический язык высокого уровня FL0GOL [43], поддерживающий аппликативный и композиционный стили программирования, обладающий развитыми средствами схемной надстройки и модульной структурой.

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

23 решение целого ряда научных и практических задач, начиная от средств ввода программы до ее вычисления на ВМ.

Отметим, что работа под научным руководством В.Н. Фалька по созданию СФЛП была выполнена автором совместно с Ан.М. Бебчиком, поэтому отдельные задачи по реализации языка решены с использованием созданных Ан.М. Бебчиком подсистем СФЛП.

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

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

программирования.

1.2.1. Описание синтаксиса языков программирования. Известные методы описания синтаксиса языков программирования опираются, как правило, на теорию формальных грамматик, значительный вклад в исследование которых

24 внес Хомский [53]. Его исследования были направлены на формализацию, в основном, естественных языков, однако применение формальных грамматик к описанию синтаксиса языков программирования позволило эффективно выполнять синтаксический анализ программ высокоуровневых языков программирования. Хомский выделил четыре класса формальных грамматик [23], однако для описания синтаксиса языков программирования в силу своей простоты и достаточно высоких выразительных возможностей наибольшее распространение получили грамматики 2-го класса, или, контекстно-свободные (КС-) грамматики.

Формально, КС-грамматика определяется тройкой , где V g(N*uT) — множество терминальных (из У) и нетерминальных (из N) символов, {Nг\Т) = 0, S є N — начальный символ, Р - множество правил вида а—>Р, а є N и /3 — цепочка из любых символов грамматики (NuT). Под цепочкой понимается, возможно пустая, последовательность символов из V. Цепочка терминальных символов образует предложение языка.

Применением правила а -> /?' к символу а цепочки /3 называется результат подстановки всех символов цепочки (У вместо вхождения символа а в цепочку у? и обозначается . Вывод предложения языка начинается с применения правила к начальному символу и выполняется путем последовательного применения правил к нетерминальным символам цепочки.

Несмотря на то, что КС-грамматики позволяют достаточно хорошо описывать синтаксис языков программирования, они не учитывают их некоторые специфические особенности. Поэтому для описания синтаксиса языков программирования используются специальные методы, позволяющие в наглядной и компактной форме описывать различные конструкции языка. Наибольшее распространение получили методы описания синтаксиса в форме Бэкуса-Наура [21] и в форме синтаксических диаграмм, называемых также диаграммами Вир-та [40]. В нашей работе мы будем использовать оба метода описания синтакси-

25 са, в зависимости от специфики конкретной задачи, поэтому далее кратко укажем основные особенности этих методов.

1.2.1.1. Форма Бэкуса-Наура. Форма Бэкуса-Наура (БНФ) была предложена Дж. Бэкусом для описания языка ALGOL 58 и позднее была доработана П. Науром при работе над описанием языка ALGOL 60. По сути, БНФ представляет собой достаточно простой и удобный метаязык.

Нетерминальные символы языка программирования в БНФ заключаются в уголковые скобки, а терминальные символы записываются либо в неизменном виде, либо при помощи мнемонических имен (например, Точка для символа V). Правила грамматики записываются посредством знака ::=, слева от которого указывается левая часть (заголовок) правила, а справа — правая часть (тело) правила. Начальный символ грамматики, обычно, представляется символом < программа >. Для повышения компактности записи в БНФ применяется специальный символ '[' , обозначающий альтернативное определение тела правила. Например, правило < заголовок >\\=<тело\>\<тепо7.> рассматривается как два правила < заголовок >::=< тгло\ > и < заголовок >::=< тело! > ,

соответственно.

Для определения списков в БНФ применяется рекурсия. При этом рекурсивное правило описывает список как элемент списка, разделитель списка (возможно пустой), и хвост списка, а не рекурсивное - пустой список.

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

Другой способ предполагает определение двух правил, одно из которых содержит цепочку опциональных символов, а другое - нет. Если таких цепочек

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

Помимо исходной формы для БНФ известны расширения, касающиеся описания опциональных элементов и списков. Для описания опций предлагается заключать опциональные символы в квадратные скобки, например:

< выбор >::= if{< выражение >) < оператор > [else < оператор >].

Для списков предлагается заключать образующие список символы в фигурные скобки, Например, список модулей может быть определен так:

< спис_мод >::=< мод > {,< мод >}.

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

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

Недостатком синтаксических графов является в некоторых случаях менее компактное, по сравнению с БНФ, описание синтаксиса языка. В качестве примера приведем диаграмму, описывающую правило вида:

< терм >::=< первичное выражение > {[+ | -] < терм >} * (Рис. 1.1).

Известны также расширенные версии синтаксических диаграмм, позволяющие естественно и компактно описывать параметризованные синтаксические понятия. Описание языка FLOGOL выполнено в виде расширенных синтаксических диаграмм.

терм

первичное выражение

Рис. 1.1. Пример синтаксической диаграммы.

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

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

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

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

1.2.2. Методы описания семантики языков программирования. Значительное число языков программирования имеют неформально описанную семанти-

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

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

Формальное описание семантики обычно является достаточно громоздким и трудным для восприятия, поэтому в дополнение к формальному описанию в руководстве программиста и официальном отчете по языку (language report) обычно предлагается также неформальное описание семантики, выполненное на естественном языке.

Различают два основных вида формального описания семантики -статическое и динамическое.

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

29 описания статической семантики языка используются предложенные Дональдом Кнутом атрибутивные грамматики [69].

Атрибутивными грамматиками называют грамматики, дополненные атрибутами (attributes), атрибутивными вычислительными функциями {attribute computation functions) и предикативными функциями {predicate functions). Атрибуты «привязываются» к нетерминальным символам грамматики и представляют собой переменные, значения которых вычисляются при помощи соответствующих атрибутивных функций, называемых также семантическими функ-і(иями. Предикативные функции определяют ограничения на возможные значения атрибутов.

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

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

стояние ВМ изменяется согласно правилам перехода до тех пор, пока ВМ не окажется в некотором конечном состоянии.

Операционная семантика является удобным средством описания семантики при разработке транслятора императивного языка программирования, поскольку детально описывает поведение ВМ при выполнении программ. При разработке транслятора языка декларативного типа использование операционной семантики имеет смысл, прежде всего, для описания работы абстрактной машины (AM), реализующей базовые элементы вычислительной модели языка. Одним из самых известных языков, предназначенных для описания операционной семантики, является язык VDL {Vienna Definition Language) [92], в котором состояние вычисления непосредственно включается в дерево программы и выполнение очередного оператора переводит это дерево в новое состояние.

Денотационная семантика на данный момент является наиболее широко используемым видом описания семантики языков программирования. Денотационная семантика определяет отображение синтаксически корректного выражения в значение в некотором домене [87]. Таким образом, денотационная семантика точно специфицирует именно то, что является значением любого исходного выражения. Денотационная семантика функциональных языков непосредственно опирается на семантику Х-исчисления [40], а для языков логического программирования денотационная семантика, как правило, аналогична семантике неподвижной точки [1]. Поэтому, обычно, описание семантики этих языков сводится к формальному описанию преобразования некоторых надстроек языка к лежащему в его основе формализму. С одной стороны, в число таких надстроек входят различного рода синтаксические улучшения — списки, инфиксные формы записи операторов и т.п. С другой — важные технологические особенности, такие как типизация, генерируемые последовательности, сопоставление с образцом и др. Для языков функционально-логического программирования важным вопросом является также формальное описание расширений, отражающих взаимосвязь функциональных и логических элементов языка (ис-

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

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

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

Практически все современные реализации языков программирования выполняются с использованием интегрированных сред программирования (ИСП) {Integrated development environment — IDE). Под ИСП понимается программный комплекс, содержащий средства ввода (построения), выполнения и отладки программ. Отметим, что на данный момент существует незначительное количество систем декларативного программирования, обладающих развитой ИСП, что, несомненно, сдерживает широкое распространение и развитие языков и систем декларативного программирования.

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

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

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

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

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

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

1.3.2. Графическое программирование. Помимо технологий текстового построения программ, существуют также и технологии графического построения программ, получающие в последнее время широкое распространение благодаря возможностям современных персональных ВМ по работе со сложной графикой [32,35,73]. Графическое построение программ обладает достоинствами визуального представления семантических объектов, однако, как правило, ограничено в сложности формируемых конструкций. Наибольший интерес, с нашей точки зрения, представляет гибридная ИСП, позволяющая выполнять разработку программ как в текстовом, так и в графическом виде, с возможностью взаимной конвертации текстового и графического представлений программ. Задача создания и интеграции в СФЛП модуля графического построения программ решена Бебчиком Ан.М. [4,8,12]. 1.4. Основные формы реализации языков программирования.

Под реализацией языка программирования здесь будем понимать совокупность методов и средств, позволяющих выполнить программу этого языка на некоторой ВМ. Различают три основные формы реализации языков программирования; компиляцию, интерпретацию и смешанную форму. 1.4.1. Компиляция. Компиляция языка программирования предполагает перевод программы на некоторый объектный язык (объектный код), как правило, на язык используемой ВМ. Программа на объектном языке может быть непосредственно загружена в память и выполнена этой ВМ. Основным преимуществом такого метода является скорость выполнения программ, поэтому большинство реализаций современных языков программирования используют именно метод компиляции. Компиляция выполняется путем анализа исходной программы и

34 последующего синтеза объектной программы [31]. Общая схема компиляции отображена на рис. 1.2.

Рис. 1.2. Общая схема компиляции программы.

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

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

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

После завершения генерации кода выполняется присоединение (linking) объектного кода, представляющего вызовы внешних программ операционной системы (ОС) и программ из других модулей. Для этого выполняется процедура связывания, помещающая адрес входа во внешнюю программу на место ее вызова из скомпилированной программы. После выполнения связывания компиляция программы считается завершенной, и полученный код помещается в файл, который может быть исполнен стандартными средствами ОС. 1.4.2. Интерпретация. Под интерпретацией понимают выполнение программы при помощи специальной программы-интерпретатора, последовательно считывающей и выполняющей записанные в программе команды исходного языка программирования. Интерпретатор играет роль виртуальной машины, реализующей исходный язык программирования, при этом инструкции для этой виртуальной машины считываются и транслируются «на лету» по мере выполнения программы.

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

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

Вследствие невысокой скорости выполнения программ интерпретаторы используются в основном для реализации языков, не очень критичных к данному фактору. Важной областью применения интерпретаторов также является реализация языков программирования, модели вычислений которых отличаются от моделей, аппаратно реализуемых на ВМ с Фон-неймановской архитектурой. К таким языкам относятся и языки декларативного типа, 1.4.3. Смешанная форма. Помимо чистых методов компиляции и интерпретации для реализации языков программирования также применяется метод смешанной реализации (hybrid implementation system). Смешанная реализация предполагает компиляцию программы исходного языка в промежуточный код, оптимизированный для последующей интерпретации. Далее программа в промежуточном коде передается интерпретатору, непосредственно выполняющему эту программу.

Такой подход обеспечивает увеличение скорости выполнения программ, поскольку отпадает необходимость в постоянной трансляции команд исходного языка во время выполнения ее интерпретатором. Важно отметить, что этот метод, по-видимому, является наиболее эффективным для реализации языков декларативного программирования, поскольку чистая компиляция этих языков невозможна, а чистая интерпретация замедляет выполнение программ. Как правило, для построения интерпретаторов используется абстрактные машины, глубоко оптимизированные для выполнения на ВМ с Фон-неймановской архитектурой. Для языков функционального программирования такой AM является iSECD-машина [44], а для языков логического программирования - абстрактная машина Уоррена (WAM - Warren Abstract Machine) [91,62]. Для реализации языков функционально-логического программирования, как правило, используются различные модификации SECD- и и^М-машин.

Исходя из соображений эффективности вычислений, для реализации языка FLOGOL была выбрана смешанная форма реализации с компиляцией программы в промежуточное представление и последующее его вычисление ин-

37 терпретирующей подсистемой исполнения запросов (ПСИЗ) СФЛП, реализованной Бебчиком Ан.М. Смешанная форма реализации ставит вопрос о принципиальной возможности разделения фаз компиляции и интерпретации, для ответа на который требуется провести исследование языка FLOGOL и, при необходимости, ввести соответствующие ограничения, позволяющие выполнить программную реализацию языка в смешанной форме. 1.5. выбор программных средств для реализации СФЛП.

Основной задачей при выборе средств для реализации системы программирования является определение языка и среды разработки. В качестве основного языка выбран объектно-ориентированный язык C++, обладающий развитыми средствами поддержки системного программирования и обеспечивающий эффективное выполнение программ.

Целевой операционной системой выбрана Windows, имеющая широкое распространение в нашей стране и содержащая стандартизированные средства построения графических интерфейсов. В качестве среды программирования выбрана среда Borland C++ Builder 5.0. , обладающая средствами визуального построения графических интерфейсов и широким набором программных компонентов. Для обеспечения специфических потребностей реализации СФЛП также использованы дополнительные компоненты библиотеки RXLib.

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

На начальных этапах создания компилятора запросов на языке FLOGOL для разработки и отладки основных элементов компилятора использовалась бесплатная версия современной интегрированной среды Amzil IDE для программирования на языке Пролог — Amzil Prolog + Logic Server.

38 Основные результаты и выводы.

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

6. Перспективным языком программирования является основанный на теории направленных отношений функционально-логический язык FLOGOL. Реализация этого языка является важной и актуальной задачей развития систем декларативного программирования.

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

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

9. Существенным препятствием на пути широкого распространения декларативных языков программирования является отсутствие для большинства из них развитых интегрированных сред разработки и отладки программ.

10. Для реализации СФЛП выбрана операционная система Windows и система программирования Borland C++ Builder 5.0, обладающая развитыми средствами построения интерфейсов и предоставляющая средства построения эффективных программ системного назначения.

2. ЯЗЫК ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОГО

ПРОГРАММИРОВАНИЯ S-FLOGOL.

2,1. Теория направленных отношений.

Теория направленных отношений, разработанная Фальком В.Н. и Кутепо-вым В. П. [33,43], является универсальной теоретической моделью, позволяющей в естественной форме описывать и вычислять рекурсивно заданные объекты некоторой предметной области. Как кратко отмечалось в главе 1, на базе теории направленных отношений Фальком В.Н. был разработан функционально-логический язык программирования высокого уровня FLOGOL (Function and LOGic Oriented Language) [43], поддерживающий основные тенденции развития современных языков программирования и позволяющий в компактной схемной форме задавать определения конструктивных объектов в терминах направленных отношений.

2,1.1. Основные понятия. В основе рассматриваемой теории лежит понятие направленного отношения. Направленным отношением (НО) на носителе D называется график соответствия из D" в Dⁿ ,п',п">0. Пара (п\п") называется арностью этого НО и при необходимости указывается в виде правого верхнего индекса. Класс НО на D обозначается Я_в. Вследствие того, что в языке FLOGOL носитель D предполагается односортным, тип любого НО вполне определяется его арностью, поэтому с привычных позиций язык FLOGOL можно считать нетипизированным. Однако, многосортный носитель может быть легко промоделирован с использованием других возможностей языка, и введение в язык пользовательских типов данных затруднений не вызывает.

Для любого НО R существует обратное ему НО, обозначаемое R"¹ и определяемое следующим образом: VarV/?((or,/?) є R » (/?, а) є R ').

Помимо арности, НО может обладать некоторыми фундаментальными свойствами, в определенном смысле не зависящими от выбора носителя. К таким свойствам относятся функциональность и тотальность.

HO R называется функциональным, если

У a V/? V/Г ((аг, /Г) є R&(a,fi')eR^ /3' = 0").

НО R арности («',«") на D называется тотальным, если

Va(a є D"' =э 3fi(0 є >"* & (a, p) є Л)).

Определенные выше свойства могут иметь место как для самого НО, так и для обратного ему НО.

Свойства функциональности и тотальности НО R~^l будем называть свойствами обратной функциональности и обратной тотальности НО R.

Эти свойства, совместно с заданием арности, позволяют определять в виде НО различные семантические объекты. Так, функции представляются НО арности (лД) со свойством функциональности, константы — НО арности (ОД) со свойствами тотальности, прямой и обратной функциональности, а предикаты — в виде НО арности (и,0), обладающими только свойством функциональности.

Неоднозначные отображения из D" в D" задаются как НО арности («',«"), ^а принятое представление «-арного отношения как подмножества D" задается НО арности (0,я), отображающим D⁰ в D", где D⁰ -множество, содержащее единственный кортеж нулевой длины.

Свойства функциональности и тотальности играют важную роль в процедурах редукции сетей, использующихся в моделях вычисления НО [43]. 2.1.2. Языки схем направленных отношений. Для описания сложных, в общем случае рекурсивных НО в [42,43] разработаны языки схем НО, которые были положены в основу построения языка FLOGOL.

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

_лл I РОССИЙСКАЯ і

⁴¹ ГОСУДАРСТПЄННАЯІ

) БИБЛИОТЕКА j

2.1.2.1. Принципы построения. Принципы построения языков схем НО уточняются следующим образом:

1. область интерпретации Я_в задается уточнением носителя D;

2. множество X переменных НО содержит неограниченное количество переменных каждой арности («', и"), п',п" > 0;

3. множество К элементарных констант содержит имена конкретных НО на D. Денотат константы к є К обозначается к;

4. каждой связке /^(/) из множества связок F сопоставляется, в общем

случае, частичная функция /⁽⁰ \(Я_В)' ->Я₀ в области интерпретации, определяющая операцию композиции НО. Применимость операций композиции к НО определяется только некоторыми ограничениями на арность их аргументов, подробнее рассмотренными далее. Схема, полученная применением связки fк схемам А₁,...,А₁, в общем случае, обозначается /A_v..A_l;

5) результат применения оператора рекурсии к схеме А по операторной пе
ременной х обозначается {х = А}.

Пусть сЛ - язык схем НО. Интерпретация схем этого языка как НО определяется заданием интерпретации переменных <р\Х->Я₀, <р\ х^{п'^п'^} єЯ^'^п),

где Яр*'— класс НО арности («',«") на D. Индуцированная <р интерпретация схем языка сА обозначается через Ф_р и определяется следующим образом:

1. Ф I к\ ~к длявсех кеК;

2. Ф^ \ х = q> 1х\ для всех хеХ;

3. фД/<'Ч-.^]=АфД^,...,фДлф длявсех /ef;

4. Ф,

{х = А} = Х_т]п - минимальное решение уравнения х- А в интерпре-

тации, индуцированной (р.

X называется решением уравнения х = А в индуцированной <р интерпретации, если X = Ф_р. А , где ф х\ =Х и ф \ У \ = <р \у для всех у, отличных от х. Минимальное относительно теоретико-множественного включения решение Х_тіл удовлетворяет условию Х_сЫа с X для всех других решений X уравнения х ~ А в той же интерпретации. Поскольку все функции f — интерпретанты связок f є F языка с4 монотонны и непрерывны относительно включения НО как графиков, то для любого уравнения х = А минимальное решение существует, и оно является пределом последовательности

1^№и^,1,₁„.Д⁽⁰₎... при /->оо, где Х^т- пустое НО, Х^(М) =фДл], где

ф\х = X^{0 и ф \у\ = <р \У Д^{ля всех} У» отличных от х.

Ъ = {К, F) называется сигнатурой языка схем НО и обозначается сА_г. 1.\*Ъ*Ъ. Комбинаторные константы. Множество FV(A) свободных переменных схемы А определяется следующим образом: FV{k) = 0 для всех к є К;

FV(x)~{x} для всех хєХ; FV(f^wA_r..A_!) = FV(A_l)v...uFV(A_l) для всех f eF; FV{{x = A}) = FV(A)\ {х}. Схема А, такая что FV(A)-0, называется

константой языка. В теории НО особое внимание уделяется сигнатурам, в определенном смысле не зависящим от выбора конкретного носителя D. Константы, удовлетворяющие условию независимости от выбора носителя, называются комбинаторными. Выделяется следующий набор элементарных комбинаторных констант: {о, —>, <—, >^, —< , -/—, X}, где о- {(,)},

—>={(a,)\aeD},<—= {С,а)| aeD},>—={(аа,а)\аєВ),—<={(a,aa)\aeD],

-I- = {(a_tp)\agD& figD&a*P},x~ {(а*а",a"tf)\a'zD&a"eZ)}.

Как показано в [43], используя приведенный набор комбинаторных констант и операции композиции, можно определять любые комбинаторные НО. 2.1.2.3. Операции композиции НО. В [33] введена основная универсальная сигнатура, в которой в качестве операций композиции НО рассматриваются операции объединения, последовательной и параллельной композиции. В языке FLOGOL дополнительно используются введенные в [43] операции унификации, конкатенации, условной композиции, пересечения и инверсии НО, позволяющие существенно расширить возможности практического применения композиционного стиля программирования.

Последовательная композиция НО R_x и R₂ обозначается через R_x R₂ и определяется как произведение графиков R_{ и R₂:

Параллельная композиция НОЛ, и R₂ обозначается через R_X#R₂ и определяется как раздельное декартово произведение компонентов графиков R_x и R₂:

(^^w^^hWf⁴^^ = {(«,«₂.ААЖ«і,А)є л, &(а₂,А)єл₂}.

Операции последовательной и параллельной композиции ассоциативны. Объединение НО R_l и R₂ обозначается через R_:^jR₂ и определяется

как теоретико-множественное объединение if, и R₂ как графиков.

(R U RMyW _{s {{aJ3)} і _{{aJ3) eR}^ _{ap) ^_Ri)

Пересечение HO R_{ и R₂ обозначается через Д, r\ R₂ и определяется как теоретико-множественное пересечение J?, и R₂ как графиков.

Операции объединения и пересечения ассоциативны и коммутативны. Конкатенация НО R_{ и Л₂ определяется как декартово произведение вторых компонентов графиков при равных первых компонентах: _№<*у> „ _R^,y_n,^ _{{(flfi д/?2)} | _{(0Гі/?і) є} д, & (_ttf/) _є д₂}.

44 Унификация НО Л, и Я₂ определяется как декартово произведение первых компонентов графиков при равных вторых компонентах:

Условная композиция НО R_l и Л₂ обозначается символом -> и представляет собой проекцию R₂ по первому компоненту графика на область определения R_l:

(Д/^ -> *₂<-">)<-"> = {(a,/?) J («,/?) _є R₂ &3/Г(а,Я є Л,}.

Инверсия НО Л обозначается ~ Л и определяется в виде:

2.1.3. Сетевое представление схем направленных отношений. Сетевое представление является как естественной формой задания НО, так и основной для используемых в СФЛП моделей вычисления НО. В основе сетевого представления схем НО лежат понятия сети, сетевого языка и контекстно-свободной сетевой грамматики (КССГ).

2.1.3.1 Основные определения. Базисом элементов В называется тройка (X, //,//"), где X - конечное множество сортов элементов; //,// : X ~> О,, задают арность (р'(х),/і"(хУ) элементов сорта х є X. По определению, р'(х) называется количеством входов, а //"(*) ^_ количеством выходов элементов сорта X. Далее для краткости базисы будем рассматривать как множества сортов элементов с указанием их арностей в качестве верхних индексов.

Сетью S арности {п\й"), п\п" > О, в базисе элементов В называется

пятерка , где Р - конечное множество точек сети S; І_уО єР* - кортежи входных и выходных точек сети S, |/|=и' и \0\=п" (\А\ обозначает длину кортежа А); Е с:ХхР* — множество элементов сети S, такое, что для всех e=eE \q\= /и'(х)+ ^"(х); если е =>єЕ и \q'\=p'(x), \q"\— m"(R), то е называется элементом сети S сорта х, q'~ кортежем его входных, a q" - кортежем его выходных точек; V с Р ^і2] - граф семантического различия (неравенства разметки) точек сети S, или, сокра-

ского различия (неравенства разметки) точек сети S, или, сокращенно,

dif-граф сети S.

2.1.3.2 Графическая нотация. Графически сеть S арности {п',п") в базисе

В изображается в виде прямоугольного контура, на левой границе которого выделено п' входов, а на правой границе - и" выходов сети; внутри контура изображены неизолированные точки сети, соединенные с входами и выходами сети согласно компонентам / и О, между собой согласно компоненту U и через изображения элементов соответствующих сортов согласно компоненту Е. Элемент е=<х^'ц">^Е изображается прямоугольником, внутри которого указан символ х, а \д'\ выделенных на его левой границе входов и |#"| выделенных на правой границе выходов соединены (в порядке перечисления сверху вниз) с соответствующими точками -элементами кортежей q' и q". Графически такое соединение отображается ненаправленной дугой. Пример графического изображения сети арности (2,1) показан на рис. 2.1. Подписи справа указывают виды объектов сети, а слева - возможную интерпретацию ее элементов.

функция

предикат

конструктор

ребро dif-графа

тонка сети

элемент сети

Рис. 2.1. Пример графического изображения сети.

2,1,3.3 Элементарные сети и композиции сетей. В теории НО определено два класса элементарных сетей — безэлементные и одноэлементные.

Безэлементные сети ^ не содержат элементов и поэтому не зависят от выбора базиса В. В нашей работе в основном будут использоваться безэлементные сети, вид которых представлен на рис. 2.2, а.

46 Класс одноэлементных сетей определяется как $\ = {S^ | х є В}, и включает сети, сформированные путем добавления в пустую сеть арности (и', и") элемента jt'"'"' є В и связывания точек входных и выходных кортежей элемента и сети, соответственно. Общий вид одноэлементной сети показан на рис, 2.2, б.

а» б)

Рис. 2.2. Безэлементная и одноэлементная сети. Пусть S=, S, =_l,I_l,O_l,E_l,U_l > и S₂ =₂J₂, 0₂,E₂,U₂ > есть сети в базисе В (множества объектов различных сетей не пересекается). Тогда последовательная композиция сетей определяется как: S, S₂=[I₂/O_i]_iuP₂,I_l,0₂,E_l uE₂,U_x kjU₂ >, где

[X/X\S = S, [p»X"!p'X']S = [[/////]Х7[р7р^'][р"/У]5, 0^p_u..._Pln и І_г ~ р_2Г..р_2п. Подстановка [р"/р']Х доопределяется для множеств и кортежей естественным образом. Если в результате подстановки в U_x wC/₂ получаются петли, то результат последовательной композиции не определен. Параллельная композиция сетей определяется в виде: S_l#S₂ =₁uP₂,I₁I₂,0₁0₂,E_l \jE₂,U_x uU₂ >. Теорема 2.1. [43] Любая сеть в базисе В может быть получена (,#)-композицией сетей из $\J$¹_B (где < включает некоторое ограниченное

множество комбинаторных сетевых констант, эквивалентных комбинаторным константам, приведенным в пар. 2.1.2.2).

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

47 2.1.3.4 Сетевая грамматика и сетевой язык. Контекстно-свободной сетевой грамматикой (КССГ) G называется четверка _T,B_H,a,R>, где В_Т -терминальный базис, В_н — нетерминальный базис, В_ТГ\В_Н - 0, аеВ_н — аксиома, R — непустое множество правил вида ,—>,., где Ь_{єВ_И, S_s ~ сеть в базисе В₁иВ_[1. Сетевой язык L(G), порождаемый КССГ G, определяется одним из известных способов — индуктивно или дедуктивно.

Интерпретация сети S и сетевого языка L(G) как НО на носителе D индуцируется интерпретацией <р сортов элементов как НО на D :

4'₉[s} = {{a\a*)\(3cr:P->D){a' = a(I)&a'^f = a{0)A (\/{_Pl,p₂}eU)

SsL{G)

Сетевая интерпретация рекурсивных схем НО задается следующим образом. Пусть А — рекурсивная схема НО. Преобразуем ее к эквивалентной форме задания в виде конечной системы уравнений вида у₍ = А_п і є 1../:, такой, что

для всех і <= 1.. k переменные у. < FV(A). Используя дистрибутивность объединения относительно операций последовательной и параллельной композиции,

"і преобразуем все А_п i0 .. к, к виду \JA_V , где все A_;j — простые схемы НО,

>i

т.е. в них не используются операция объединения и оператор рекурсии; для любой интерпретации q> свободных переменных Ф_р \А 1 - первый компонент

кортежа — минимального решения этой системы уравнений в интерпретации (р. Сетевая интерпретация Е рекурсивной схемы А определяется так:

Ни] = ДС),где G=_T,B_H,y_lfR>, B^FV(A) = (j.

B_n = {y_i\ie\.,k},R = {y_i^E.[A_iJ]\ith.k&j_i}.

48 Теорема 2.2. Ф JЫ =_р I 5 Ы 11 для всех рекурсивных схем А и для

всех интерпретаций <р.

Согласно теореме 2.2, доказанной в [43], КССГ может рассматриваться как форма задания рекурсивных схем НО, что гарантирует возможность корректной трансляции схем FLOGOL-программы в эквивалентную КССГ. 2.2, Язык функционально-логического программирования FLOGOL.

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

2. Основные элементы и особенности языка FLOGOL. База данных FLOGOL-программы формируется из описаний НО, расположенных в программных модулях, причем одно из описаний выделяется в качестве запроса, модели и алгоритмы вычисления которого, непосредственно опирающиеся на сетевое представление НО, подробно рассматриваются в работах [43,13,17]. 2.2.2.1. Модульная структура. Модули языка могут образовывать гамакооб-разную структуру, формируемую при помощи задания для каждого модуля списка подключенных модулей. При включении (импорте) модуля в этот список множество описанных в нем объектов попадает в область видимости текущего модуля. В языке используется три типа модулей — текстовые, сетевые (графические) и объектные.

В текстовых модулях расположены описания НО, заданные при помощи текстовой грамматики языка с использованием возможностей схемной надстройки. Текстовые модули создаются при помощи специализированного структурно-ориентированного текстового редактора [5,15], позволяющего использовать расширенный набор символов.

Сетевые модули предназначены для задания описаний НО непосредственно в виде КССГ. Для ввода и редактирования сетевых модулей предназначен специализированный графический редактор. Поскольку КССГ не поддерживает схемную надстройку языка FLOGOL, сетевые модули лишь частично реализуют его возможности. Заметим, что сетевая (графическая) и текстовая формы определения НО являются взаимно конвертируемыми с учетом сделанного замечания.

Объектные модули представляют собой записанную в форме специальных кодов базу описаний НО и получаются путем раздельной компиляции текстовых и сетевых модулей. Использование объектных модулей позволяет исключить избыточную информацию, необходимую для редактирования описанных в модуле НО, а также создать универсальный механизм компиляции запросов для сетевых и текстовых модулей.

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

Основным синтаксическим понятием текстовой грамматики языка является выражение. Все выражения строятся по единому шаблону. Для выражения каждого типа определено множество первичных выражений, множество инфиксных связок и, возможно пустое, множество префиксных и постфиксных связок. Помимо указанных конструкций, выражения языка FLOGOL также включают свертку, условные конструкции IF и CASE. Каждое выражение языка может быть заключено в скобки.

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

Декларативная парадигма

Императивное программирование предполагает задание программы в виде последовательности инструкций, определяющих алгоритм ее решения [38], то есть в виде явного указания того, как именно надо решать задачу. Такой подход объясняется стремлением к наиболее эффективному выполнению программ, естественным образом обеспечиваемому в том случае, если язык программирования опирается на архитектуру используемой ВМ. Поскольку основания часть существующих в настоящий момент ВМ построена по архитектуре Фон-Неймана, разделяющей основную память и вычислительный блок процессора, процесс выполнения программы заключается в последовательной загрузке значений из ячеек памяти, выполнения вычислительных операций и записи полученных результатов в память ВМ. Императивные языки, по сути, на более высоком уровне абстракции предлагают программисту записывать программу в терминах выполнения отдельных операций и изменения состояния ячеек памяти, что, как правило, существенно отличается от семантики решаемой задачи и осложняет понимание программы. Другим недостатком императивного подхода является возможность изменения присвоенных ранее значений переменных, а также использование глобальных переменных, что может приводить к нежелательным побочным эффектам [44].

12, императивное программирование является наиболее распространенным благодаря, во многом, исторически более раннему появлению, высокой скорости выполнения программ, а также наличию широкого круга задач, имеющих естественное алгоритмическое описание. Очевидно также, что в области системного программирования императивные языки на данный момент практически не имеют достойной альтернативы. Тем не менее, для решения многих задач, в том числе задач из области искусственного интеллекта [20,41], алгоритмический подход не представляется естественным, что ставит задачу исследования иных подходов к программированию. 1,1.2. Декларативная парадигма. Декларативное программирование [24] предполагает задание программы в виде описания задачи в терминах некоторого формализма без явного указания того, каким именно образом должна вычисляться эта программа. Выбор подходящего метода решения вычислительная система, как правило, производит самостоятельно, позволяя при этом программисту указать дополнительную информацию, которая может быть полезна для более эффективного выполнения программы.

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

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

Декларативное программирование можно условно разделить на несколько направлений: функциональное, логическое, функционально-логическое. 1.1.2.1. Функциональное программирование. Функциональное программирование [47,44] предполагает определение программы при помощи математических функций, задающих различные семантические объекты предметной области. При этом выражение одних функций через другие задается при помощи ап-пликативного применения функций или их композиции. Первый функциональный язык LISP был создан Дж. Маккарти [76] для символьных вычислений, в частности, для решения задач из области искусственного интеллекта. Этот язык и его диалекты до сих пор широко используются в практических и исследовательских целях.

Теоретической основой большинства аппликативных языков программирования функционального типа является Х-исчисление [54,3,66]. В Я-исчислении функции задаются при помощи Я-выражений, конструируемых из переменных применением Я-оператора и операции применения. В языках программирования, как правило, при построении выражений также используются константы, обычно представляющие натуральные числа, арифметические операции, булевы значения и функции, условные функции, конструкторы и т.д.

Вычисление Я-выражений производится при помощи трансформационных правил редукции. Если правила редукции не применимы, то считается, что выражение находится в нормальной форме. Порядок применения правил редукции определяет модель вычисления Я-выражений. Различают две основные модели - ленивую и энергичную. Энергичная модель является более эффективной, однако допускает не завершающееся вычисление выражения даже в тех случаях, когда нормальная форма существует. Ленивая модель менее эффективна, однако она позволяет гарантировать достижение нормальной формы в случае, если такая форма для редуцируемого выражения существует. Другим важным преимуществом ленивой модели является возможность работы с неполными структурами данных. Современные функциональные языки используют как ленивую (Miranda, Haskell), так и энергичную (Scheme) модели вычисления программ.

Реализации функциональных языков также различаются статическим (ML) или динамическим (CommonLisp) связыванием переменных. Хотя статическое связывание признано более безопасным, поддержка динамического связывания позволяет повысить гибкость языка.

Важной особенностью функциональных языков программирования является использование механизма сопоставления с образцом [60,90]. Этот механизм, в частности, позволяет применять различные определения функции в зависимости от того, какие аргументы были переданы при ее вызове, а также разбирать конструктивно построенные аргументы вызова и использовать их отдельные элементы при определении результата вычисления функции. Сопоставление с образцом используется в таких языках, как Haskell, Hope, Miranda, однако, по-видимому, впервые этот метод был предложен в отечественном функциональном языке Refal, созданным Турчиным [88].

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

Методы описания семантики языков программирования

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

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

Формальное описание семантики обычно является достаточно громоздким и трудным для восприятия, поэтому в дополнение к формальному описанию в руководстве программиста и официальном отчете по языку (language report) обычно предлагается также неформальное описание семантики, выполненное на естественном языке.

Различают два основных вида формального описания семантики -статическое и динамическое.

Статическая семантика. Статическая семантика позволяет определять такие свойства программы, задание которых в синтаксисе языка либо невозможно, либо крайне затруднительно в силу существенного возрастания количества грамматических правил, необходимых для их синтаксического определения, что приводит к значительному замедлению скорости выполнения синтаксического анализа и усложнению языка в целом. В качестве примера задачи, решаемой с использованием статической семантики, можно привести определение совместимости типов данных. В качестве основного формализма для описания статической семантики языка используются предложенные Дональдом Кнутом атрибутивные грамматики [69].

Атрибутивными грамматиками называют грамматики, дополненные атрибутами (attributes), атрибутивными вычислительными функциями {attribute computation functions) и предикативными функциями {predicate functions). Атрибуты «привязываются» к нетерминальным символам грамматики и представляют собой переменные, значения которых вычисляются при помощи соответствующих атрибутивных функций, называемых также семантическими функ-і(иями. Предикативные функции определяют ограничения на возможные значения атрибутов.

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

Сетевое представления схем направленных отношений

Сетевое представление схем направленных отношений. Сетевое представление является как естественной формой задания НО, так и основной для используемых в СФЛП моделей вычисления НО. В основе сетевого представления схем НО лежат понятия сети, сетевого языка и контекстно-свободной сетевой грамматики (КССГ).

Основные определения. Базисом элементов В называется тройка (X, //,//"), где X - конечное множество сортов элементов; //,// : X О,, задают арность (р (х),/і"(хУ) элементов сорта х є X. По определению, р (х) называется количеством входов, а //"( ) _ количеством выходов элементов сорта X. Далее для краткости базисы будем рассматривать как множества сортов элементов с указанием их арностей в качестве верхних индексов.

Сетью S арности {п\Й"), п\п" О, в базисе элементов В называется пятерка P,I,0,E,U , где Р - конечное множество точек сети S; ІуО єР - кортежи входных и выходных точек сети S, /=и и \0\=п" (\А\ обозначает длину кортежа А); Е с:ХхР — множество элементов сети S, такое, что для всех e= x,q eE \q\= /и (х)+ "(х); если е = x,q q" єЕ и \q \=p (x), \q"\— M"(R), ТО е называется элементом сети S сорта х, q кортежем его входных, a q" - кортежем его выходных точек; V с Р і2] - граф семантического различия (неравенства разметки) точек сети S, или, сокра ского различия (неравенства разметки) точек сети S, или, сокращенно, dif-граф сети S. Графически сеть S арности {п ,п") в базисе

В изображается в виде прямоугольного контура, на левой границе которого выделено п входов, а на правой границе - и" выходов сети; внутри контура изображены неизолированные точки сети, соединенные с входами и выходами сети согласно компонентам / и О, между собой согласно компоненту U и через изображения элементов соответствующих сортов согласно компоненту Е. Элемент е= х ц" Е изображается прямоугольником, внутри которого указан символ х, а \д \ выделенных на его левой границе входов и #" выделенных на правой границе выходов соединены (в порядке перечисления сверху вниз) с соответствующими точками -элементами кортежей q и q". Графически такое соединение отображается ненаправленной дугой. Пример графического изображения сети арности (2,1) показан на рис. 2.1. Подписи справа указывают виды объектов сети, а слева - возможную интерпретацию ее элементов.

В теории НО определено два класса элементарных сетей — безэлементные и одноэлементные.

Безэлементные сети не содержат элементов и поэтому не зависят от выбора базиса В. В нашей работе в основном будут использоваться безэлементные сети, вид которых представлен на рис. 2.2, а.

Класс одноэлементных сетей определяется как $\ = {S х є В}, и включает сети, сформированные путем добавления в пустую сеть арности (и , и") элемента jt " " є В и связывания точек входных и выходных кортежей элемента и сети, соответственно. Общий вид одноэлементной сети показан на рис, 2.2, б. Рис. 2.2. Безэлементная и одноэлементная сети. Пусть S= P,I,0,E,U , S, = Pl,Il,Ol,El,Ul и S2 = P2J2, 02,E2,U2 есть сети в базисе В (множества объектов различных сетей не пересекается). Тогда последовательная композиция сетей определяется как: S, S2=[I2/Oi] PiuP2,Il,02,El uE2,Ux KJU2 , где [X/X\S = S, [p»X"!p X ]S = [[/////]Х7[р7р ][р"/У]5, 0 pu...Pln и Іг р2Г..р2п. Подстановка [р"/р ]Х доопределяется для множеств и кортежей естественным образом. Если в результате подстановки в Ux wC/2 получаются петли, то результат последовательной композиции не определен. Параллельная композиция сетей определяется в виде: Sl#S2 = P1uP2,I1I2,0102,El \JE2,UX UU2 . Теорема 2.1. [43] Любая сеть в базисе В может быть получена (,#)-композицией сетей из $\J$1B (где включает некоторое ограниченное множество комбинаторных сетевых констант, эквивалентных комбинаторным константам, приведенным в пар. 2.1.2.2).

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

Сетевая грамматика и сетевой язык. Контекстно-свободной сетевой грамматикой (КССГ) G называется четверка BT,BH,a,R , где ВТ -терминальный базис, Вн — нетерминальный базис, ВТГ\ВН - 0, аеВн — аксиома, R — непустое множество правил вида ,— ,., где Ь{єВИ, Ss сеть в базисе В1иВ[1. Сетевой язык L(G), порождаемый КССГ G, определяется одним из известных способов — индуктивно или дедуктивно.

Интерпретация сети S и сетевого языка L(G) как НО на носителе D индуцируется интерпретацией р сортов элементов как НО на D : 4 9[s} = {{a\a )\(3cr:P- D){a = a(I)&a f = a{0)A (\/{Pl,p2}eU) SsL{G) Сетевая интерпретация рекурсивных схем НО задается следующим образом. Пусть А — рекурсивная схема НО. Преобразуем ее к эквивалентной форме задания в виде конечной системы уравнений вида у( = Ап і є 1../:, такой, что для всех і = 1.. k переменные у. FV(A). Используя дистрибутивность объединения относительно операций последовательной и параллельной композиции, "і преобразуем все Ап i0 .. к, к виду \JAV , где все A;j — простые схемы НО, i т.е. в них не используются операция объединения и оператор рекурсии; для любой интерпретации q свободных переменных Фр \А 1 - первый компонент кортежа — минимального решения этой системы уравнений в интерпретации

Правила компиляции основных конструкций языка S-FLOGOL

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

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

Для задания имени отношения в левой части описания НО соответствующие компоненты имени определяются непосредственно в первичном доменном выражении. Для задания имени отношения, определяющего вызов НО, используется синтаксическое понятие ИмяОти, представляющее вызов отношения по имени, вызов параметра или рекурсивный вызов отношения.

Вызов отношения по имени определяется следующим Л-правилом: имяОтн_ном(Тип,СпСв,Имя, ИмяОтпСпец,СпЗав) — спец_ном1(Тип,СпСв, Имя, Спец), спИнд_ном2(Тип,СпСє, Имя, СпИнд), спПар_номЗ(Тип,СпСв, Имя, СпПар), ИмяОтн = сИмя(Спец,СпИнд,Ид,СпПар,ТипОпр), датьСпецССпец , ИмяОтн, ИмяОтн Спец), формСпЗав(ТипОпр,ИмяОтнСпец, СпЗав),

Идентификатор, список индексов, список параметров, и, возможно, спецификатор (отмечен ) собираются при помощи конструктора сИмя и обрабатываются правилом датьСпег}, результатом выполнения которого является специфицированное имя отношения (ИмяОтнСпец). Формирование списка зависимостей выполняется правилом формСпЗае, не допускающим попадание в список зависимостей имен НО конструкторов на эрбрановском универсуме. Вызов параметра определяется -правилом вида: гшяОтн_ном(Тж,СпСв,Имя, Пар,[]) — ар_ном2(МодВыз, Tun, CnCe, Имя, НомПар), вызовПар(НомПар,Имя, Пар), провИар(Пар).

Арифметическое выражение ар_ном2 определяет номер параметра, а правило ВызовПар осуществляет доступ к контексту вызова и извлечение параметра с этим номером из списка параметров вызова НО. В случае, если указанного параметра в списке не существует, или значение выбранного параметра пред ставляет пустое отношение (контролируется предикатом провПар), вычисление данной ветви дерева решений завершается неудачей.

57ї-ТТравило для рекурсивного вызова НО, записанного при помощи @, определяется простой выборкой значения атрибута Имя из контекста вызова: имяОтн_пит( Опр ,СпСв,Имя, Имя,[]). имяОтн_пит{!Спец ,СпСв,Имя, ИмяОтп,[У) fail.

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

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

Для условной конструкции IF SR -правило имеет вид: выр_иом(Тип,СпСв,Имя, ...) — лог_ком1{Тип,СпСв,Имя, Лог), вырЕсли_пом(Лог, Тип,СпСв,Имя, ,.,). вырЕсли_ном(1,Тип,СпСв,Имя, ...) выр_ном2(Тип,СпСв,Имя, ...). домЕсли іюм(р,Тип,СпСє,Имя, ...) -е вырномЗ(Тип,СпСв,Имя, ...).

Где выр_ном обозначает выражение произвольного типа, а многоточием обозначены индивидуальные атрибуты для выражений различных типов (на пример, для доменного выражения — вырном примет форму дом_ном, а дополнительными атрибутами будут Сеть и СпЗав). В случае, если ELSE-часть условной конструкции не определена, результатом вычисления выриомЗ будет значение по умолчанию, определенное для выражения этого типа.

Правила для свертки согласно свойствам используемой в свертке операции можно разделить на две группы - множественная свертка и свертка по структуре. Множественная свертка применятся для операций, выполняющих теоретико-множественное объединение результатов вычисления своих аргументов (моделируется ветвлением дерева решений). К таким операциям относятся объединение в доменном и реляционном выражениях и альтернатива в терме и формуле. Множественная свертка реализуется при помощи применения правила спВоМнож к вычисленному списку значений переменной свертки, что приводит к ветвлению дерева решений. Количество ветвей соответствует количеству элементов в списке значений, причем каждая ветвь дополняет контекст свертки соответствующим значением из списка значений переменной свертки.

Похожие диссертации на Разработка и исследование структурно-ориентированного редактора и компилятора запросов системы функционально-логического программирования

Разработка и исследование подсистемы исполнения запросов и графического редактора системы функционально-логического программированияБебчик Антон Михайлович

Исследование и разработка инструментальной системы программирования ParJava для параллельных вычислительных системАветисян Арутюн Ишханович

Разработка и исследование системы концептуального программирования с использованием лингвистического процессораЛебедев, Андрей Сергеевич

Разработка и исследование продукционной системы параллельного программированияТютюнник, Михаил Борисович

Исследование и разработка языковых средств описания неоднородных вычислительных систем и их реализация в системе программирования mpCЛедовских, Илья Николаевич

Исследование и разработка системы поддержки принятия решений на основе прецедентовЮдин Валерий Николаевич

Тип-технология и её применение при разработке систем программирования и экспертных систем для высокопроизводительных вычислительных комплексовСафонов, Владимир Олегович

Разработка интеллектуальной системы программированияДанг Чыонг Шон

Язык и система параллельного программирования для разработки программ, эффективно переносимых в классе распределенных вычислительных системЛастовецкий, Алексей Леонидович

Разработка векторизатора для системы кросс-программированияМаслов, Вадим Юрьевич