Разработка и исследование редактора и компилятора запросов системы логического программирования

программирования
Бебчик Алексей Михайлович
Специальность 05.13.11 – Математическое и программное обеспечение вычислительных

машин, комплексов и компьютерных сетей

Московский институт радиотехники, электроники и автоматики (МИРЭА ТУ)

д.т.н., проф. Фальк Вадим Николаевич

Москва 2005

Научный руководитель:

Раздаточный материал к диссератции

и формальное описание его семантики;
∙ разработка основных принципов и метода

компиляции FLOGOL-запросов;

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

программная реализация и интеграция в СФЛП компилятора запросов и
структурно-ориентированного редактора, основанного на разработанной
технологии ввода;

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

Структура диссерации:

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

Глава 2: Теория направленных отношений и язык функционально-логического
программирования S-FLOGOL.

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

Глава 4: Структурно-ориентированный редактор.

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

FLOGOL, позволяющая выполнить
компиляцию программы

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

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

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

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

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

«Девятой национальной конференции по искусственному интеллекту с между-
народным участием КИИ-2004».
Основные

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

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

Апробация работы

Публикации

Поддерживает аппликативный и композиционный стили программирования.
∙ Обладает развитой схемной надстройкой,

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

Основные ограничения по сравнению с языком FLOGOL:
∙ Упрощенная модульная структура.
∙ Исключение пользовательских связок.
∙ Упрощенный механизм параметризации (компиляция).
∙ Отсутствие открытых интервалов в свертках (компиляция).

R =

Базис КССГ:
Вт = {Null(0,1), Succ(1,1)},
Вн

= {Nat1(0,1), Nat2(0,1), Add(2,1),QUERY(0,1)}.
Аксиома КССГ:
α = QUERY(0,1).

,

,

,

,

.

НО:
∙ Объединение описаний:
Дом → Спец Имя
Дом → Спец Имя =

Рел

Дом → Дом ; Дом

(+0+:+1)Null

(+1+:+1)Succ

(2:1)Add = {Succ(x),y:Succ(Add(x,y)}

(2:1)Add = {Null,x:x}

(2:1)Add = {Succ(x),y:Succ(Add(x,y)}

(2:1)Add = {Null,x:x};

исключена внешняя пользовательская интерпретация НО.

Ограничение:

(+0+:+1)Null;

(+1+:+1)Succ;

Общая форма:

входная арность

выходная арность

функциональность

Спец →( + Ар + : + Ар + )

тотальность

обратная тотальность

обратная функциональность

Описания НО могут быть специфицированы:

(+0+:+1)Null

(+1+:+1)Succ

Примеры:

(2:1)Add

(3:0)Add

Полиморфизм -

Ключевая спецификация:

Спец →Ключ

Спец →Ключ(Ар)

Спец →Ключ(Ар:Ар)

Ключ – ключевое слово, оределяющее
свойства и, возможно, арности НО.

OBJECT ≅ (+0+:+1)

Пример:

OBJECT Null

идентичные имена, но
разные спецификации:

График - аппликативная форма определения НО:
Рел → Имя
Рел → {Терм

: Терм ? Формула}

Рел → @

∙ Рекурсивный вызов:

∙ Вызов параметра:

Рел → <<Ар>>

Входной терм – аргументы вызова.

Выходной терм – результат вызова.

Формула – ограничения на
интерпретацию
переменных графика.

Succ

Add

x

y

Пример:

Переменная

Succ(Add(x,y))

Терм , Терм

Терм | Терм

∙ Терм:

Вызов

Терм=Терм

Формула & Формула

Формула | Формула

Терм<>Терм

∙ Формула:

∙ Формула:

Вызов

Positive(x) & x<>y

Пример:

= {x:x,x}
>-- = {x,x:x}
-/- = {x:y?xy}
Пример: композиционное определение

НО сложения:

Add = (~Succ # ---)∙Add∙Succ ∪ (~N # ---)

∙ Композиция отношений:

Рел → Рел ⊗ Рел, где

⊗ ∈ {∙,#,→,∇,*,∪,∩},

--- = {x:x}

При помощи комбинаторных констант и операций композиции можно задать любое
комбинаторное НО.

R1∪R2

Пересечение:

R1∩R2

Объединение:

Унификация:

R1∇R2

Инверсия:

~R1

R1→ R2

Условная:

Сетевая интерпретация операций компопозиции НО:

--- = {x:x}

При помощи комбинаторных констант и операций композиции можно задать любое
комбинаторное НО.

имя НО
СпПар → @

собственные параметры
СпПар → _ пропуск параметра
СпПар → СпПар ; СпПар объединение в список

Map[---] = {Cons(x,y): Cons(<<0>>(x),@(xs))}∪{Nil:Nil};

QUERY = Map[Succ];

Пример параметризованного НО – отношение Map:

Вызов параметризованного НО:

Имя[СпПар]

Вызов параметра в определении:

<<Ар>>

*Значения по умолчанию:

Имя[СпПар] = Рел

--- = {x:x};

Параметризованные описания НО

Map[Succ]

Ограничения:

3) Нет СпПар→График

1) Нет групп
параметров

СпПар → Имя полное имя НО
СпПар → @ собственные параметры
СпПар → _ пропуск параметра
СпПар → СпПар ; СпПар объединение в список

Список параметров:

Параметризация позволяет задавать своего рода шаблоны описаний НО.

Условная конструкция IF позволяет выбирать варианты определения НО.

Map[---] = IF ►<<0>> <> 1 OR <<0>>► <> 1 THEN ---
ELSE {Cons(x,y): Cons(<<0>>(x),@(xs))} ∪ {Nil:Nil} ;

QUERY = Map[(2:1)Add];

{Cons(x,y): Cons(---(x), Map[(2:1)Add](xs))} ∪ {Nil:Nil}

Пример: контроль арностей входного параметра отношения Map .

[ CпИнд ] Ид
Имя отношения:
Имя переменной терма:
Натуральные числа:
Список индексов:
СпИнд →

Ар

СпИнд → СпИнд, СпИнд

[1]Nat= Null∙Succ;

[2]Nat= Null∙Succ∙Succ;

QUERY=[1]Nat # [2]Nat∙Succ

Add={Succ([1]x),[2]x:Succ(@([1]x,[2]x));

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

[1,2]Cell= [4]Nat;

[2,1]Cell= [2]Nat;

[2,2]Cell= [10]Nat;

QUERY= ([1,1]Cell#[1,2]Cell)∙Add

[1,1]Cell= [1]Nat;

Массивы объектов:

Свертка

Выр → (Инф ИдСв = СпЗнач) Выр

СпЗнач – список значений переменной.

Инф – инфиксная связка.

Ограничение: нет пользовательских связок для реляционного выражения.

Ид – операторная переменная свертки.

Выр – выражение-операнд свертки.

Свертка позволяет в компактной форме задавать объекты (и множества объектов),
а также эффективно формировать сетевое определение параметризованных НО.

(⊗ J=1..10)Выр

⊗([1/J]Выр, ⊗([2/J]Выр,… ⊗([9/J]Выр,[10/J]Выр)…)), где

[x/J]Выр обозначает результат подстановки x вместо J в выражение Выр.

отношений.
Свертка (продолжение)
1) [3]Nat = Null∙(∙ J=1..3)Succ
Пример: натуральные числа

(∙ J=1..100)[J]Nat = Null∙(∙K=1..J)Succ

2) [0]Nat = Null;

[3]Nat = Null∙Succ∙Succ∙ Succ

[0]Nat = Null;

[1]Nat = Null∙Succ;

[2]Nat = Null∙Succ∙Succ;

[100]Nat = Null∙Succ∙…∙Succ;

…

Типизация

входных(выходных) данных, определяется как:

Типовое отношение для типа

где – НО арности (0,1), генерирующее данные сорта t.

где

– сорта

TypeNat[Add]

//Генератор натуральных чисел
Nat = Null∪@∙Succ;
//Отношение сложения
Add = {Null,x:x};
Add = {Succ(x),y:Succ(@(x,y))};
//Типиовое отношение арности (2,1)
(2:1)TypeNat = {Nat,Nat:Nat} ∩<<0>>;
//Типизированное отношение сложения
TypedAdd = TypeNat[Add]

Пример типизации НО сложения:

в КССГ, индуцированную выделенным в программе запросом к системе.
Принципы описания:

– интерпретация синтаксической конструкции языка при интерпретации
контекста ее переменных.

– контекст вызова НО, где

– контекст сверки,

– имя вызываемого НО.

– спецификатор, список индексов, идентификатор

признак НО – конструктора, список параметров вызова.

∙

∙

– значения операторных переменных свертки (

находится описываемая конструкция.

∙

∙

∙

Контекст, имя вызова, список индексов и список параметров записываются в виде списков.
Для работы со списками используются функции elm(Список, Номер) – выборка элемента списка с
указанным номером, append(Список, Список) – конкатенация списков, пустой список обозначается [ ].

), в области действия которых

Область интерпретации выражений:

 …



где


имя вызываемого НО
имя вызываемого НО без параметров
имя определяемого

НО

унификация имен вызываемого и определяемого НО

подстановка значений по умолчанию в параметры вызова

формирование сети вызываемого НО и индуцированных сетевых определений

формирование сетевого определения

формирование результата

Семантика определения НО в доменном выражении:

Семантика объявления НО в доменном выражении:













, где

имя вызываемого НО

имя определяемого НО

Семантика объединения описаний НО:













, где

унификация имен вызываемого и определяемого НО

makeS1 – функция, формирующая
одноэлементную сеть, содержащую
элемент НО с именем Name.

объединение множеств правил КССГ

контекстно-свободной сетевой грамматики (КССГ), эквивалентной сетевой

интерпретации S-FLOGOL-программы с выделенным запросом к системе.

Интерпретация – вычисление КССГ подсистемой исполнения запросов (ПСИЗ).

Стадии компиляции:

∙ предварительная: завершение формирования и дополнительная обработка внутреннего
представления программы;

∙ основная: формирование и вычисление логической программы-компилятора (ЛПК), результатом
которого является КССГ запроса;

∙ заключительная: обработка полученной КССГ запроса, запись КССГ в сетевой модуль СФЛП и
передача в графический редактор.

значениями по умолчанию:
∙ Индексирование вхождений операторных переменных сверток:
CONSTRUCTOR(Ар) Succ
СпИнд Add

= {Succ(x),y:Succ(@(x,y))}

Add = ИмяОтн

CONSTRUCTOR(0) Succ

Add = {Succ(x),y:Succ(@(x,y))}

Add = EmptyRel

∙ Первичный семантический анализ:

- контроль вызова не объявленных НО,

- чистка грамматики (исключение не используемых НО).

описаний НО.
• AR -правила (AdditionalRules) - управляющие и вспомогательные

правила компиляции.

Формирование КССГ выполняется логической программой-компилятором (ЛПК), база данных которой содержит:

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

дом_1(Контекст, Правило).
дом_0(Контекст, Правило):-
дом_2(Контекст, Правило).
дом_1(Контекст, Правило):-
спец_3(Контекст, Спец),
одноэлСеть(Спец, ‘Null’, Сеть),
Правило = [‘Конс’, ‘Query’, Сеть].
спец_3(Контекст, cСпец(+,0,+,+,1,-)).
дом_2(Контекст, Правило):-
спец_5(Контекст,Спец),
рел_7(Контекст, Сеть)
Правило = [‘Прав’, ‘Query’, Сеть].
рел_7(Контекст, Сеть):-
рел_8(Контекст, Сеть1),
рел_9(Контекст, Сеть2),
послКомп(Сеть1,Сеть2,Сеть).
рел_8(Контекст, Сеть):-
одноэлСеть(Спец, ‘Null’, Сеть).
рел_9(Контекст, Сеть):-
одноэлСеть(Спец, ‘Null’, Сеть).

Программа:

SR-БД:

Внутреннее представление:

Контекст (вызова НО):
- список значений переменных свертки;
- имя вызываемого отношения.

Для каждой синтаксической конструкции программы на основании семантических
функций трансляции строится правило на языке Пролог и добавляется во множество
SR-правил базы описаний НО.

корневой
домен

именем,
выполнить шаг 1) для всех имен НО, индуцированных этим определением.
Схема

формирования КССГ (AR-правило GRL):

Формирование КССГ:
• начинается с шага 1) для НО запроса,
• завершается, когда список зависимостей пуст.

Запрос на получение определения НО осуществляется вызовом SR-правила корневого
доменного выражения с контекстом, содержащим имя запрашиваемого НО.

дублирующиеся имена
исключаются

терм = x, y




#
x
y
выходной терм = Add(x,y)
∙


формула = x

y

#

x

y

∙

y

x

Проблема:
имя вызываемого и определяемого
НО, как правило, не специфицировано.

Имя

?

необходимо
знать арность

Решение:
получить определение вызываемого НО,
извлечь информацию о его спецификации.

композиций НО.
Спец? (Add∙Succ):

Add




Succ


∙



Add



Succ





Спец= (2,1)
Спец= (3,0)
Спец= (2,1)

для конструктивного
построения формат внутреннего представления КССГ в ПСИЗ.

Сеть →

сСеть(Имя,СпЭл,СпТоч,СпДуг),
Имя → сИмя(Спец,СпИнд,Ид,СпПар,ТипОпр) ,
Спец → сСпец(Ф,ВхАр,Т,Оф,ВхАр,От),
СпЭл → {Эл}+ , Эл → сЭл (НомЭл,Спец,Имя) ,
СпТоч → {Точ} , Точ → сТоч (НомТоч,СпИнд,Ид) ,
СпДуг → {Дуга} , Дуга → сДуга (НомДуги,Тип,НомЭл,НомТоч).

Основные грамматические правила:

Сеть – универсальная структура данных, содержащая результат интерпретации доменного и реляционного выражения, терма и формулы.

сСеть(
[
сЭл([276],сСпец(-,2,-,-,1,-),сИмя(сСпец(-,2,-,-,1,-),Nil,Add,Nil,Прав)),
сЭл([280],сСпец(-,0,-,-,1,-),сИмя(сСпец(-,0,-,-,1,-),Nil,Null,Nil,Конс))],
[
сТоч([2,1,[280]],Nil,АвтоТочка),
сТоч([[276],Nil,x],Nil,...)
],
[
сДуга([1,2,1,[280]],Вх,[276],1,[2,1,[280]]),
сДуга([2,285],Вх,[276],2,[[276],Nil,x]),
сДуга([2,289],Вых,[276],1,[[276],Nil,x]),
сДуга([2,2,1,[280]],Вых,[280],1,[2,1,[280]])
])

Null

Add

x

АвтоТочка

SimpleNet (SN-) представление:

Пример. Сеть НО Add:

КССГ элементов имени.
∙ Установка интерпретации системных типов данных и отношений.
∙

Сохранение полученной КССГ и ее отображение пользователю.

∙ Преобразование КССГ из SN-формата в формат КССГ (выполняется в ПСИЗ).

(-,0,-,-,1,-),Nil,Null,Nil,Конс Null

(-,2,-,-,1,-),Nil,Add,Nil,Прав (-,2,-,-,1,-)Add

(-,3,-,-,0,-),Nil,Add,Nil,Прав (-,3,-,-,0,-)Add

имя НО после компиляции:

∙ Редукция имен – исключение не значимых для КССГ элементов имени.

(-,1,-,-,1,-),Nil,Map,Succ,Прав Map[Succ]

(-,3,-,-,0,-),Nil,$$Add,Nil,Конс

(-,3,-,-,0,-),Nil,124,Nil,Конс

КССГ сохраняется в сетевой модуль текущего проекта и открывается

графическим редактором для:

– просмотра и возможной корректировки результата компиляции,

– выполнения запроса.

→ системное НО – сложение нат. чисел

→ системный тип – натуральное число

Исключить лексический и синтаксический анализ программы.
∙ Снизить число семантических ошибок

ввода.

∙ Повысить читаемость текста программы.

∙ Обеспечить переносимость на различные естественные языки.

∙ Использовать математические и др. специальные символы.

Недостатки:

∙ Необходимость введения в грамматику дополнительных атрибутов.

∙ Несколько сниженная скорость ввода программ.

Возможные специальные области применения:

∙ Учебные приложения и скриптовые языки.

∙ Блокнотные КПК, не обладающие полноразмерной клавиатурой.

∙ Приложения для людей с ограниченными возможностями.

Основа технологии

Программа – выводимая из грамматики цепочка символов.

Шаг ввода – применение правила к нетерминальному символу цепочки.

Исходное состояние – начальный нетерминальный символ грамматики.

[СпИнд] Ид
Вызов
График
Рел→ИмяОтн
Рел→{Терм:Терм?Формула}
Переменная
Вызов
Дом→Дом ; Дом
Объединение
Рел→Рел РелИнф Рел
Композиция
Соединение
Терм→ [СпИнд] ИдТ
Терм→ИмяОтн(Терм)
Терм→Терм

, Терм

1)

2)

3)

MODULE Common=
Спец [СпИнд]Ид[СпПар]=Рел
END

MODULE Common=
Спец [СпИнд]Ид[СпПар]=
{Терм:Терм?Формула}
END

MODULE Common=
Дом
END

Раскрыть

1)

…Спец Ид=Рел

Дом→Спец [СпИнд] Ид [СпПар]=Рел

Элемент ручного ввода

2)

…Спец Add=Рел

Ид→ПравилоДляИд

Выражения

… [1]Nat=Null∙Рел

РелИнф→{ ∙ , *, ∇, → ,#, ∪, ∩, ~ }

Ид→Рел РелИнф Рел

1)

2)

∙ , *, ∇, → ,
#, ∪, ∩, ~

… [1]Nat=Null

Ручной ввод

Схема стилистического оформления текста.
● Интерфейсные средства поддержки ТДВП.
● Типизированные буферы

обмена.

● Управление детализацией отображения текста.

● Многоуровневый откат.

● Выполнение операций по горячим клавишам.

Общий вид окна редактора

Форма компиляции

компиляцию в конечную КССГ и значительно упрощающая реализацию.
2. На

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

3. Разработан метод компиляции запросов S-FLOGOL-программ. На основании
формального описания семантики определены функции трансляции для
всех синтаксических конструкций языка.

4. Предложены оптимизационные модификации, позволившие существенно
сократить время компиляции запросов.

5. Предложена оригинальная технология дедуктивного ввода программ (ТДВП),
позволяющая полностью исключить синтаксические ошибки и значительно
сократить количество семантических ошибок при вводе программ.

6. Разработаны архитектура и интерфейсные средства структурно-ориентиро-
ванного редактора, реализующего ТДВП.

7. Выполнена программная реализация структурно-ориентированного редактора
и компилятора запросов и их интеграция в СФЛП.