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

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

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

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

∙ разработка и исследование моделей вычислений НО,

разработка технологии графического построения программ,

∙ программная реализация подсистемы исполнения запросов,

∙ программная реализация графического редактора СФЛП.

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

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

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

Пример графика НО факториала:

Направленные отношения.

), если
1. НО называется функциональным (

Свойства НО и представимые семантические объекты.

3. НО называется обратным для , если

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

(0,0)

(0,1)

(n,1)

(n,1)

(n,0)

на носителе

Размеченной сетью арности , в базисе элементов называется шестерка , где

Сетевое представление НО

Базисом сети называется тройка , где - множество сортов элементов, а задают арность элементов каждого сорта.

− множество точек сети;

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

− множество элементов сети;

− граф семантического различия;

− начальная разметка сети.

Интерпретация сети есть









Графическая нотация СПНО:

P

N

S

F

| I | = n ′, |O| = n″;

НО общего типа
R
голова
хвост
пустой список
пустое дерево
левое поддерево
правое поддерево
вершина
Семантические примитивы
Составные объекты

Пример: НО сложения Add.

− терминальный базис;

− нетерминальный базис ;

− аксиома;

− множество правил вида , где , − сеть в базисе

Null

Вычисление

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

3. Шаг вывода (применение правила КССГ к сети) производится путем выполнения подстановки сети правила вместо элемента сорта сети (обозначается ).

R

M

M′

b

M

=

M′

e

замещаемый элемент

исходная сеть

тело правила

e

4. Интерпретация программы .

свойствах интерпретации их элементов.





С




С







С









функциональность деструкторов



С







прямое распространение


С







Редукция по структуре
Редукция по разметке



обратное

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

∙ реализовать Data - Flow подход,

Введенное понятие размеченной сети и предложенные правила редукции по разметке положены в основу режима вычисления с разметкой.

∙ использовать системные типы данных и системные НО,

Недостатки использования разметки:

∙ отсутствие поддержки неполных структур данных,

∙ необходимость использования смешанной редукции.

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

в глубину,
∙ смешанная стратегия.
Реализация смешанной стратегии основана на использовании масок

+ гарантированное получение результата

- высокие требования к вычислительным ресурсам

+ высокая эффективность выполнения программ

- возможность «зацикливания»

+ сохранение преимуществ чистых стратегий и
ослабление их недостатков

- необходимость учета специфики задачи

входов и выходов элементов для выполнения подстановки.
Пример: Вычисление без использования

сорта App заданы маски {(1,1,1), (1,0,0), (0,0,1)}, тогда элемент

App

App

App

(1,1,1)

(1,0,0)

(0,0,1)

логики предикатов первого порядка.
∙ логические формулы представляются сетями арности (0,

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

∙ проводится прямое доказательство общезначимости,

Особенности процедуры доказательства:

∙ используется сетевая резолюция (реализована через подстановку).

E

V

Y

z

E

V

Y

S

z

E

Для повышения удобства построения программ и увеличения эффективности вычисления введено понятие мультиправила.

Пример: зададим формулу

машине
вычисления НО (АМНО).
Реализация ПСИЗ СФЛП основана на
предложенной абстрактной

параметры подстановки
FindNet − поиск исходной сети
FindElm − поиск замещаемого элем.
FindRule − поиск правила

подстановка
Subst − выполнение подстановки

редукция
Normalize − редукция сети

вспомогательные
DelNet − удаление сети
CopyNet − копирование сети
MoveNet − перемещение сети
IsResult − проверка на результат

реализовать эффективные алгоритмы выполнения основных вычислительных операций.

точек сети на удаляемый элемент.

Succ

Null



Простое ссылочное представление
Представление ПСИЗ

Succ

Null

- Необходимо просматривать список связей точки с элементами сети.

+ Точно известно, какую связь необходимо скорректировать.

последнего вызова
∙ оптимизация порядка применения правил
Оптимизация вычислений
(позволяет сократить область сети,

(позволяет уменьшить количество элементов сети при ее копировании для выполнения подстановки за счет реализации копирования «по необходимости»);

(уменьшает вычислительные затраты за счет отказа от копирования исходной сети в том случае, если для замещаемого элемента осталось применить только одно правило);

(позволяет повысить эффективность вычисления рекурсивных НО за счет применения сначала не рекурсивного, а затем рекурсивного правила, как правило, с оптимизацией последнего вызова);

удобства ее использования введены системные типы данных и системные НО*

Системные типы данных:

∙ натуральные числа,

∙ списки,

∙ строки,

∙ термы.

Системные НО:

Пример: [A,B,C]

Пример: 2

Пример: "TXT"

Пример: F(B,G(C,A))

*Системные НО поддерживаются только в режиме вычисления с разметкой.
Системные НО можно рассматривать как НО с внешней интерпретацией.

отладки
Системное НО $Write
Системное НО $Show
(отображает построение дерева вывода

(отображает разметку входных точек элемента сети сорта $Write в специализированном окне редактора),

(отображает сеть в момент начала вычисления элемента сети сорта $Show),

Окно статистики

(отображает основные параметры процесса вычисления).

+ 10*15
Импорт программ, написанных на языке логического программирования Пролог повышает

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

∙ отсутствие синтаксического анализа,

∙ отсутствие поддержки отсечения и отрицания,

∙ отсутствие поддержки полиморфизма предикатов,

из системных предикатов поддерживаются:
=\=, = =, >=, is, write, fail, [ | ], = и \=.

Пример преобразования предиката is:

Пример конструкции [ | ]:

P([a,b|c]).

программы на каждом шаге ее построения.
Формирование КССГ:
Формирование сетей:
добавление элемента

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

добавление правила грамматики

добавление элемента

отождествление точек

добавление ребра dif-графа

удаление элемента

«расщепление» точек

удаление ребра dif-графа

удаление элемента базиса

удаление правила грамматики

определение свойств элемента базиса

Для каждой технологической операции формально определено изменение сети после ее выполнения.

(«расщепления») точки сети:
Пример удаления элемента сети:

вычисления в сетевом виде требуется по внутреннему представлению сетей строить

основная расстановка методом силовых воздействий

обработка полученного изображения

Особенности реализации основного этапа:

особое распределение сил отталкивания

использование метода оболочек для ускорения расстановки

обнаружение и гашение циклических колебаний

моделирование вязкости среды

учет геометрических размеров объектов сети

линейной сложности для выполнения подстановки и редукции.
3. Предложены и

5. Разработана технология графического построения программ (ТГПП), гарантирующая корректность формируемой программы.

1. Введено понятие размеченной сети. Предложены правила редукции для размеченных сетей.

4. На основе предложенных методов и алгоритмов выполнена программная реализация подсистемы исполнения запросов СФЛП. Реализован импорт программ на языке Пролог.

6. Предложены оптимизационные модификации и реализован силовой метод автоматического формирования изображения сетей.

7. Разработана архитектура и выполнена программная реализация графического редактора СФЛП, поддерживающего ТГПП.

8. Подсистема исполнения запросов и графический редактор интегрированы в реализованную совместно с Бебчиком Ал.М. СФЛП.