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

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

Бебчик Алексей Михайлович

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

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

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

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

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

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

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

Алексей Михайлович

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

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

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

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

формальное описание его семантики;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример графика обратного НО для НО 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) исключение открытых интервалов сверток,
2) запрет транзитной передачи отдельных параметров.

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

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

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

(Имя1, …, Имяn) =

Модуль3

Открытая часть

Описания НО

Модуль5

Закрытая часть

Описания НО

Add={Succ(x),y:Succ(@(x,y))};
//Композиционные определения
--- = {x:x};
[0]Nat=Null;
(K=1..100)
[K]Nat=Null∙(∙J=1..K)Succ;
AddС= (~Succ # ---)∙@∙Succ ∪ (~Null # ---);
//Запросы к системе
QAdd={:Add(Nat0,Nat1)};
QAddC=([1]Nat#[2]Nat)∙AddС;
END

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

имя модуля

свертка

описания НО

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

комментарии

=

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

? Формула}

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

Логическая формула
описывает дополнительные
ограничения на интерпретацию
переменных термов

R1 = R2

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

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

ИмяНО

Пример:

Пример:

ИмяНО(Терм)

Терм , Терм

∙ Терм:

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

Примеры:

Переменная

x

Succ(Null)

x , y

Null;

CONSTRUCTOR(1) Succ

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

Add = {Null,x:x};

Del = {x,Cons(x,y) : 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?x<>y}

∙ Композиция НО:

Рел ⊗ Рел, где

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

~Рел

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

Ар + )

тотальность

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

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

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

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) & x<>y

Positive(Терм)

Пример:

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

Терм<>Терм

x

y

x

{x:x,x}

>-- = {x,x:x}

-/- = {x:y?x<>y}

OBJECT Null;

CONSTRUCTOR(1) Succ;

Add = (--- # Null # ---)∙(>-- # ---)∙(>-- # ---);

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

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

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

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

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

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

Рел → ~Рел

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

<-- ∙ --<

N13= ---

N14=Succ

N15= ---

N16= >-- ∙ -->

N17= ---

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

или 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(<<0>>(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;

…

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

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

J = 1..2)[I,J]Cell

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

Операции над массивами объектов:

FLOGOL:

F = (<<0>># ---)∙<<1>>;

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

генерирующее данные сорта t.

где

– сорта

//Генератор натуральных чисел
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];

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

TypeNat[Add]

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

Принципы описания:

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

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

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

∙

∙

∙

∙

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

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

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

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

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

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

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

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

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

сетевой грамматики (КССГ),
эквивалентной сетевой интерпретации S-FLOGOL-программы с
выделенным запросом к системе.

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

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

программы

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

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

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

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

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

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

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

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

по умолчанию:

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

CONSTRUCTOR(Ар) Succ

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

Add = ИмяОтн

CONSTRUCTOR(0) Succ

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

Add = EmptyRel

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

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

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

-правила (AdditionalRules) - управляющие и вспомогательные правила компиляции.

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

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

Правило):-
дом_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-БД:

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

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

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

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

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

= x, y

#

x

y

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

∙

Формула = x <> y

#

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)

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

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

скрыть

1)

2)

3)

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

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

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

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

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

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

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

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

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

МODULE Cmn(System)= …

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

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

добавить

удалить

в начало

в конец

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

1)

2)

… [1]Nat=Null

[СпПар]=Рел

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

2)

…Спец Add=Рел

Также разработаны и реализованы:

● Алгоритм автоматического структурирования
текста программы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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