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

Антон Михайлович

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

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

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

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

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

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

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

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

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

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

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

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

), если

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

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

App

(1,1,1)

(1,0,0)

(0,0,1)

предикатов первого порядка.

∙ логические формулы представляются сетями арности (0, 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

Импорт программ, написанных на языке логического программирования Пролог повышает универсальность СФЛП и обеспечивает поддержку компиляции входного языка СФЛП S-FLOGOL.

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

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

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

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

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

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

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

P([a,b|c]).

на каждом шаге ее построения.

Формирование КССГ:

Формирование сетей:

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

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

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

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

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

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

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

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

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

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

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

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

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

точки сети:

Пример удаления элемента сети:

в сетевом виде требуется по внутреннему представлению сетей строить их графическое отображение.

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

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

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

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

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

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

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

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

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

3. Предложены и реализованы методы повышения эффективности вычисления НО – редукция «по фронту», кольцевая подстановка, оптимизации последнего вызова, маски вычислимости и мультиправила.

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

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

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

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

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

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