FLIDE Система функционально-логического программирования на языке S-FLOGOL

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

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

Основные задачи:

∙ исследование языка FLOGOL и формальное описание его семантики,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

носителе D называется множество упорядоченных пар кортежей элементов D длины

Пример графика НО сложения:

входной
кортеж

выходной
кортеж

Обратное отношение:

Пример графика обратного НО для НО Add(2,1):

входной
кортеж

выходной
кортеж

( T(R) ), если
∙ НО R называется функциональным ( F(R)

Пример представления некоторых семантических объектов:

(0,0)

(0,1)

(n,1)

(n,1)

(n,0)

(m,n)

НО. Автор – Фальк В.Н.
Форма реализации – смешанная: компиляция в

Промежуточное представление – контекстно-свободная сетевая грамматика (КССГ), задаваемая четверкой :
Bт – терминальный базис сортов,
Bн – нетерминальный базис сортов,
α ∈ Bн – аксиома КССГ,
R – множество правил вида b →S , где b ∈ Bн , S – сеть в базисе Bт∪Bн .

Сорт – имя, входная и выходная арности, а также наличие
свойств функциональности и тотальности НО.

Терминальный базис – НО, определенные вне КССГ,
Нетерминальный базис – НО, определенные правилами КССГ,
Аксиома – НО, заданное КССГ.

ее

Сеть задается пятеркой , где
P – множество точек сети,
I,O – входной и выходной кортежи точек,
E – множество элементов сети,
U – граф семантического различия.

P

N

S

F

Сеть без органичения на интерпретацию точек:

Сеть с отождествленными точками и ребром dif-графа:

представление в
виде КССГ с конечным множеством правил невозможна.
Основные ограничения:
1)

Дополнительные ограничения (упрощение реализации):
1) упрощенная внутрення организация модуля,
2) исключение виртуальных определений и наследования,
3) упрощенная форма параметризации,
4) отсутствие пользовательских связок и внешних определений.

Расширения:
1) транзитная передача всех параметров вызова,
2) Поддержка системных типов данных и отношений.

Решение:
введение системы ограничений и определение на ее основе языка S-FLOGOL.

Имя (Имя1, …, Имяn) =
Модуль3
Открытая часть
Описания НО
Модуль5
Закрытая часть
Описания НО

//Аппликативные определения
Nat0={:Null};
Nat1={:Succ(Null)};
Add={Null,x:x};
Add={Succ(x),y:Succ(@(x,y))};

Пример программы (модуль “Arithm”)

имя модуля

свертка

описания НО

индексированные
имена НО

комментарии

R =

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

,

,

,

,

.

НО:
∙ Объединение описаний НО:
Спец Имя
Спец Имя = Рел
Дом ; Дом
(+0+:+1)

(+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;

Терм ? Формула}
Входной терм
задает входной
кортеж НО
Логическая формула
описывает

R1 = R2

Выходной терм
задает выходной
кортеж НО

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

ИмяНО

Пример:

Пример:

ИмяНО(Терм)

Терм , Терм

∙ Терм:

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

Примеры:

Переменная

x

Succ(Null)

x , y

списка:
OBJECT Null;
CONSTRUCTOR(1) Succ
Add = {Succ(x),y:Succ(Add(x,y)}
Add = {Null,x:x};
Del = {x,Cons(x,y) :

Del = {x,Cons(y,ys) : Cons(y,Del(x,ys)) ? x<>y }

∙ Вычисление длины списка:

Length = {Nil : Null};

Length = {Cons(x,xs) : Succ(Length(xs))}

∙ Конструкторы натуральных чисел:

формула

= {:x}
--> = {x:}
--< = {x:x,x}
>-- = {x,x:x}
-/- = {x:y?xy}
∙

Рел ⊗ Рел, где

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

~Рел

∙ Инверсия отношения:

+ Ар + )
тотальность
обратная тотальность
обратная функциональность
Ключевая спецификация:
OBJECT
CONSTRUCTOR(n)
(+0+:+1)
(+n+:+1)
OPERATOR
(1+:1)
PREDICATE(n)
(+n:0)
Примеры:
OBJECT Null
CONSTRUCTOR(1)Succ
Ключевое слово

(2:1)Add

(3:0)Add

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

Неявная спецификация определений: (2:1)Add={Succ(x),y:Succ(Add(x,y)}∪{Nil,x:x}

FUNCTION(n)

(+n+:1)

График (аппликативная форма):
Рел → Имя
Рел → {Терм : Терм ?

Рел → @

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

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

Рел → <<Ар>>

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

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

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

Формула
Формула | Формула
ТермТерм
∙ Формула:
Positive(x) & xy
Positive(Терм)
Пример:
Формула & Формула
ТермТерм
x
y
x

= {x:x,x}
>-- = {x,x:x}
-/- = {x:y?xy}
OBJECT Null;
CONSTRUCTOR(1) Succ;
Add = (---

Add = ((--- # <-- ∙ --<)∙(--- # Succ # ---)∙(>-- ∙ --> # ---)# ---)∙Add∙Succ;

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

или Add = (~Succ # ---)∙Add∙Succ ∪ (~N # ---);

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

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

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

Рел → ~Рел

∙ Инверсия отношения:

---
N12=
N17= ---
Net

или Net = (~Succ # ---)∙Add∙Succ

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

QUERY = Map[Succ];

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

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

Имя[СпПар]

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

<<Ар>>

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

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

--- = {x:x};

Map = {Nil:Nil};

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

…

Map[Succ]

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

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

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

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

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

1 THEN ---
ELSE {Cons(x,y): Cons((x),@(xs))} ∪ {Nil:Nil}
Пример (контроль

Выр → IF Лог THEN Выр ELSE Выр

--- = {x:x};

…

Лог → Ар АрСр Ар, где АрСр ∈{=,<>,>,>=,<,<=};

Лог → NOT Лог;

Логическое выражение:

Лог → Ар ЛогСр Ар, где ЛогСр ∈{AND,OR,XOR}.

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

Map[(2:1)Add] →

[ 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));

[0]Nat= Null;

…

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

…

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

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

1..2)(ADD J = 1..2)[I,J]Cell
[1,1]Cell= [1]Nat;
Операции над массивами объектов:
FLOGOL:
F =

SummCells = Null∙(∙I = 1..2)(∙J = 1..2)F[[I,J]Cell;Add];

SummCells

F[[1,1]Cell;Add]

F[[2,2]Cell;Add]

пользовательская связка

комбинирующая форма

после подстановки комб. форм

<<0>>

<<1>>

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



где
– сорта
//Генератор

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

TypeNat[Add]

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





– контекст вызова

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

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

∙

∙

∙

∙

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

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

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

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

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

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

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

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

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

представления программы
Формирование и вычисление логической программы-компилятора (ЛПК), результатом которого является

∙ Заключительная стадия

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

Текстовый
редактор

Дополнение вн.
представления

Формирование и
вычисление ЛПК

Обработка КССГ
запроса

Графический
редактор

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

Add = ИмяОтн

CONSTRUCTOR(0) Succ

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

Add = EmptyRel

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

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

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

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

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

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

Программа:

SR-БД:

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

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

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

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

терм = x, y




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


Формула = x

#

x

y

∙

y

x

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

Имя

?

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

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

GRL

Имя

(2:1)Имя

(3:0)Имя

определения

Спец

композиций НО.
Спец? (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)
Опциональные элементы
…

скрыть

1)

2)

3)

восстановить

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

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

опциональные
элементы

… (2:1) Add[СпПар]=Рел

… (2:1) [СпИнд]Add[СпПар]=Рел

Фрагмент текста программы:

отобразить
опции

Обработка списков

МODULE Cmn(System)= …

Модуль→ИмяМод(ИмяМод)= …

список с разделителем ‘,’

добавить

удалить

в начало

в конец

МODULE Cmn(System,ИмяМод)= …

1)

2)

… [1]Nat=Null

Ид [СпПар]=Рел
Элемент ручного ввода
2)
…Спец Add=Рел
Также разработаны и реализованы:
● Алгоритм автоматического

● Схема стилистического оформления текста.

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

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

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

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

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

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

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

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

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

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

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

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

По теме диссертации опубликовано 9 печатных работ.