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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

//Аппликативные определения
Nat0={:Null};
Nat1={:Succ(Null)};
Add={Null,x:x};
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”)

имя модуля

свертка

описания НО

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

комментарии

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;

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

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

(+0+:+1)Null ;(

(+1+:+1)Succ ;

+ Ар + )
тотальность
обратная тотальность
обратная функциональность
Ключевая спецификация:
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 = (---

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

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

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

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

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

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

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

Рел → ~Рел

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

---
N12=
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((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 =

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

– НО арности (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

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

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

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

описаний НО.
• 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-БД:

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

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

именем,
выполнить шаг 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 печатных работ.