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

∙ разработка основных принципов и метода компиляции FLOGOL-запросов;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации

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

Базис КССГ:
Вт = {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:y?x<>y}

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

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 .

Имя отношения:

Имя переменной терма:

Натуральные числа:

Список индексов:

СпИнд → Ар

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

[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.

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

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

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

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

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

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

∙ Индексирование вхождений операторных переменных сверток:

CONSTRUCTOR(Ар) Succ

СпИнд Add = {Succ(x),y:Succ(@(x,y))}

Add = ИмяОтн

CONSTRUCTOR(0) Succ

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

Add = EmptyRel

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

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

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

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

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

Программа:

SR-БД:

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

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

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

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

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

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

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

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

#

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

Ручной ввод

● Интерфейсные средства поддержки ТДВП.

● Типизированные буферы обмена.

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

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

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

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

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