автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Разработка и исследование подсистемы исполнения запросов и графического редактора системы функционально-логического программирования

На правах рукописи

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

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ПОДСИСТЕМЫ ИСПОЛНЕНИЯ ЗАПРОСОВ И ГРАФИЧЕСКОГО РЕДАКТОРА СИСТЕМЫ ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва-2005

Работа выполнена на кафедре «Прикладная математика» Московского государственного института радиотехники, электроники и автоматики (технического университета).

Научный руководитель: докюр технических наук, доцепт Фальк Вадим Николаевич

Официальные оппоненты доктор технических паук, профессор Кутепов Виталий Павлович

кандидат технических наук, доцент Хорев Павел Борисович

Ведущая организация- Институт программных систем РАН (г Переславль-Залесский)

Защита состоится «20» мая 2005 г. в 18 час. 00 мин. на -заседании диссертационного совета Д 212.157 01 при Московском энергетическом институте (техническом университете) по адресу: 111250, г Москва, Красноказарменная ул., д.17 (ауд. Г-306).

С диссертацией можно ознакомиться в библиотеке МЭИ (ТУ).

Отзывы в двух экземплярах, заверенные печатью, просьба направлять по адресу: 111250, г Москва, Красноказарменная ул., д 14, Ученый Совет МЭИ (ТУ)

Автореферат разослан » апреля 2005 г. Ученый секретарь

диссертационного совета Д 212.157.01

кандидат технических наук, профессор

ъъчч

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Разработка языков и сред программирования, предназначенных для представления знаний, и лежащих в их основе формальных систем является актуальной задачей. Известные уже достаточно давно языки функционального программирования Лисп и логического программирования Пролог создавались на основе теории вычислимых функций ( А -исчисления) и логики предикатов как средства программирования и эффективного решения задач искусственного интеллекта, обработки сложно организованных данных на основе формального, как правило, аксиоматического задания их свойств и взаимосвязи. В проектах создания вычислительных систем нового поколения автоматизация и эффективность логических доказательств были и остаются центральными проблемами.

Указанные языки легли в основу направления декларативного програм-« мирования, которое предполагает определение программы в виде совокупности формального описания объектов и зависимостей между ними, характеризующего некоторую предметную область, и запроса на нахождение (построение) объектов с конкретными заданными свойствами. Декларативный подход к построению программ позволяет получать интересующую пользователя информацию о предметной области с помощью некоторой процедуры автоматического вывода без явного указания последовательности действий, которые необходимо выполнить вычислительной машине для получения результата.

В настоящее время ведутся активные исследования в области создания реляционных формализмов и языков, которые должны существенно расширить возможности представления и обработки данных и знаний. В работах Кутепова В П. и Фалька В.Н. : Направленные отношения: теория и применение // Изв. РАН, «Техническая кибернетика», 1994, №4, №5; Теория направленных отношений и логика // Изв. РАН, «Теория и системы управления», 2000, №5, разработана теория направленных отношений (НО), которая объединяет логический, реляционный и функциональный формализмы. Созданный на этой основе язык функционально-логического программирования РЬОООЬ (Фальк В.Н. Теория направленных отношений и ее приложения // Автореф. дис. ... докт. техн. наук.-М., 2001.) позволяет перейти к практической реализации высокоуровневых сред и систем программирования, отличающихся высоким уровнем автоматизации процессов разработки программ, широким использованием средств графического представления при построении и структурных преобразованиях программ. В рамках выполнения проекта РФФИ № 01-01-00690 «Разработка теоретических основ построения вычислительных сред и интеллектуальных систем, ориентированных на функционально-логический стиль программирования» была поставлена задача создания на базе языка РЬОООЬ системы функционально-логического программирования (СФЛП), решение которой рассматривается как цель проводимых в диссертации исследований.

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

- критический анализ известных моделей вычислений программ языков декларативного программирования и их реализаций с целью оценки возможности их применения при разработке СФЛП;

- разработка и исследование моделей вычислений на основе сетевого представления НО (СПНО);

- программная реализация подсистемы исполнения запросов СФЛП на основе разработанных моделей вычислений НО;

- разработка технологии корректного и комфортного для пользователя графического построения программ в сетевой форме;

- исследование и оптимизация метода автоматического построения графического изображения СПНО;

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

Методы исследования. При выполнении работы использованы методы теории направленных отношений, математической логики, теории формальных языков, теории алгоритмов, объектно-ориентированного программирования, тестирования программных продуктов.

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

Научная новизна. Научная новизна работы заключается в следующем:

1. Введено понятие размеченной сети на основе расширения понятия сети, определенного в теории НО. Предложены новые правила редукции для размеченных сетей и разработана сетевая модель вычисления НО.

2. Предложены модификации основных механизмов и стратегий вычисления НО, позволяющие повысить эффективность ПСИЗ, в частности, выполнения вычислительных операций подстановки и редукции сетей. Разработан алгоритм сетевой подстановки линейной сложности.

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

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

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

Апробация работы. Основные результаты диссертации докладывались и обсуждались на научно-технических конференциях МИРЭА (Москва, 2002, 2003, 2004), международных конференциях «Информационные средства и технологии» (Москва, 2003, 2004), всероссийской межвузовской научно-технической конференции «Микроэлектроника и информатика - 2004» (Зеленоград, 2004), международной научно-технической конференции «Информационные технологии в науке, образовании и производстве» (Орел, 2004), международной конференции «Континуальные алгебраические логики, исчисления и нейроинформатика в науке и технике» (Ульяновск, 2004), международной научно-технической конференции «Компьютерное моделирование 2004» (Санкт-Петербург, 2004) и «Девятой Национальной конференции по искусственному интеллекту с международным участием КИИ-2004» (Тверь, 2004).

Реализованная СФЛП демонстрировалась на выставке программных продуктов «Девятой Национальной конференции по искусственному интеллекту с международным участием КИИ-2004».

Публикации. Основные результаты, полученные при выполнении диссертационной работы, опубликованы в 9 печатных работах.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 94 наименования, и приложений. Диссертация содержит 152 страницы машинописного текста без учета приложений.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе приводится обзор современных подходов к декларативному программированию. Рассматриваются принципы построения декларативных программ, их теоретические основания и способы вычисления.

Функционально-логический стиль программирования сочетает преимущества функционального и логического программирования. Возможность явного задания функций в логической программе позволяет естественно представлять используемые в ней логические и функциональные определения, а также повышать эффективность процессов вычислений за счет использования особых процедур вычисления функций.

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

Обсуждаются известные методы реализации языков декларативного программирования и выделяется подход к реализации на базе абстрактных машин (АМ). Достоинствами АМ являются возможность строгого описания вычислительной семантики языка, построения на ее основе алгоритмов выполнения программ и достаточно простой перевод языка на различные платформы. Кроме того, при усовершенствовании реализации АМ можно без существенных затрат улучшить и построенную на ее основе подсистему вычислений. Рассмотрены ключевые аспекты реализации АМ SECD для функционального и WAM для логического программирования.

Анализируются известные способы графического построения программ и приводится обзор программных систем, поддерживающих графическое программирование. Графическое представление благодаря простоте и наглядности широко используется в различных формальных системах и языках программирования. В качестве примеров из области теории программирования можно привести граф-схемы программ, SADT-диаграммы, сети Петри, графы Ковальского, диаграммы классов и др. Однако в настоящее время существует небольшое число систем, позволяющих непосредственно строить программы графическим образом, например, LabView и Акторный Пролог. Обосновывается целесообразность графического построения программ в СФЛП.

Во второй главе рассматриваются основные понятия теории и вопросы вычисления НО. Подробно рассматривается сетевое представление, как естественная форма задания НО и основа для создания эффективных моделей их вычисления.

Направленным отношением арности (п',п"), п',п">0, на носителе D

называется график соответствия из D" в D" . Арность указывается в виде верхнего индекса имени НО. НО R называется функциональным, если а\/ 0V е R & (а,/?") = /?"); обратно функциональным, если

\/dVa"Vp{{d,p)<ER8í(a",p)е R а'-а"); тотальным, если Va3/?((a,/?)etf); обратно тотальным, если V/?3 а ((а,/?) е R).

Арность НО и наличие указанных свойств функциональности и тотальности позволяют определять в виде НО различные семантические объекты языков декларативного программирования. Так, например, для представления функций используются НО арности (л,1), обладающие свойством функциональности, а для всюду определенных функций эти НО обладают также и свойством тотальности; константы задаются в виде НО арности (ОД) со свойствами тотальности, прямой и обратной функциональности, а предикаты - в виде НО арности (и,0), обладающими только свойством функциональности.

Формально, языки НО строятся как индуктивно определяемые множества интерпретированных схем, причем основу каждого языка НО составляют в некотором смысле универсальное множество так называемых комбинаторных констант и операций композиции НО и множество исходных базисных НО, образующих область значений свободных переменных схем НО. Замыкание множества базисных НО и констант относительно множества операций композиции НО и определяет конкретный язык НО. В общем виде НО определяется через систему реляционных уравнений: (*) Л,'™""'' = г(, / = 1,2,...,п, где г, - (т:,я,)-арные термы, представляемые как конечные композиции базисных НО, комбинаторных констант и переменных НО /?,,/ = 1,2,...,п. В интерпретации система

уравнений (*) задает кортеж НО < Л™" ,...,Ялтт > - минимальное (относительно отношения включения НО) решение системы реляционных уравнений (*).

Более подробно рассматриваются вопросы сетевой интерпретации схем НО, как основа организации процессов вычислений НО. Базисом В называется тройка (X,//,//"), где X - конечное множество сортов элементов; ц',ц"\Х-¥ 0.. - функции, задающие арность (р'(х), /и"(х)) элементов каждого сорта хеХ ; //(х) называется количеством входов, а ,и"(х) - количеством выходов элементов сорта х. В дальнейшем, для краткости, базисы рассматриваются как множества сортов элементов с указанием в качестве верхних индексов их арностей. Размеченной сетью S арности (и',и"), п',п">0, в базисе элементов В называется шестерка <P,I,O,E,U,cr0>, где Р - конечное множество точек сети, а0 - частичное отображение точек сети на носитель D {начальнаяразметка точек сети); 1,ОеР* — кортежи входных и выходных точек сети, | /1= ri и [ О |= п"; Е с ВхР*хР* - множество элементов сети, такое, что для всех е =<x,Ie,Oe >еЕ \ /J = //(х), \Ое\ = р"(х); х = L;(е) - сорт элемента е сети S, 1г - кортеж его входных, а Ое - кортеж его выходных точек; U - граф семантического различия точек сети, сокращенно, dij —граф сети (точнее, U - множество ребер этого графа, а Р — множество его вершин). Подмножество точек сети - область определения сг0 - обозначим dom(a0). Иногда удобно считать, что отображение сг0 определено для каждой точки сети, полагая, что для неразмеченных точек p£dom(cr0) значением <т„(р) яв-

ляегся особый элемент О. Сети рассматриваются с точностью до изоморфизма относительно множества точек сети. Далее Р^Т^О^Е^и^а^ обозначают соответствующие компоненты сети 5,. На рис. 1 приведен пример графического изображения сети и ее компонентов (слева), а также возможной интерпретации ее элементов (справа).

конструктор предикат

функция

ребро dif-графа

точка сети

Рис. 1. Изображение и интерпретация компонентов сети.

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

В диссертации разработана базовая модель вычисления НО. Пусть КССГ задается четверкой <Bm,BH,a,R>, где Вт,Вн обозначают, соответственно, терминальный и нетерминальный базисы (BmnBH=0), аеВн - аксиому грамматики, a R - непустое множество правил вида b —»S, где be ВИ, a S -сеть в базисе (Вт и В J. Не ограничивая общности, можно считать, что в качестве аксиомы всегда используется специальный символ Query (запрос), а в R существует единственное правило вида Query —»Бй. Язык La, порождаемый грамматикой G, есть {S | G S & (Ve е E){q(e) еВт)\, где G => S обозначает выводимость сети S в грамматике G и определяется следующим образом: G^>S = S = S0v В S'(G => S' & (Зе е E')3S"(^(e) -» S" е R & S = [5"/е]5')), где [S"7e]S' есть, по определению, \ГО"Iq'q'yP'uP',Г,О',Е"uF\\e\,U"о£/') - результат подстановки сети S" в сеть S' вместо ее замещаемого элемента e=<x,q',q" >, арность сорта которого совпадает с арностью сети S". Будем говорить, что сеть S непосредственно выводима из сети S' применением правила r:£(e)—> S" и обозначать это как S'—»S. Переход от сети S' к сети S будем называть шагом вывода.

Дерево поиска определяет все возможные способы порождения сетей из языка Ьс. Пусть вершина дерева Ns представляет сеть S eLc. Тогда все вершины дерева поиска можно определить следующим образом: вершина Ns является корнем дерева; вершина N¿ является дочерней для Ns., если (3 reR)S'——>S. Листом дерева называется вершина Ns, такая что (Ve е Е)^(е) е Вт. Очевидно, что множество листьев дерева поиска определяет все сети, принадлежащие L0. Дерево вывода является поддеревом поиска и определяет те его вершины, сети которых порождены в процессе вывода. Вычисление завершается в том случае, если дерево вывода полностью совпадает с деревом поиска.

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

Рассматривается семантический компонент вычисления - редукция. Проводится классификация правил редукции. Предлагаются правила редукции для вычисления в размеченных сетях.

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

Правила редукции базируются на интерпретации сетей (S) и сетевых языков (2) в базисе В как НО на носителе D, которая индуцируется интерпретацией (р сортов элементов из В как НО на D:

{(«',c/)\(3cj-.P^D)((Vp еdom(<j0))(cr(p) = аь(р))& а' = а(Г)&а -а(О)& {V{Pi,p2} 6U)(a(Pl)* а(р2))&

(V < x,q',q" >е E){{a{q')Mq")) е ^*]))},%[2 ]= U% М•

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

Пример совмещения редукции по структуре с редукцией по разметке (аналог унификации термов Г (А, х) и Р{у, В)) приведен на рис. 2.

Рис. 2. Совмещение структурной редукции и редукции по разметке.

В главе рассмотрены способы выполнения логического вывода на основе теории НО. Обосновывается выбор грамматического подхода к организации логического вывода. Вводится понятие мультиправила. Одной из возможностей СФЛП является доказательство общезначимости формул логики предикатов первого порядка. Для выполнения логического вывода используется грамматический подход, который предполагает выполнение сетевой резолюции через подстановку. Недостатком грамматического подхода можно считать то, что одна формула, содержащая п элементов нетерминальных сортов, требует наличия в КССГ п соответствующих правил. Это значительно замедляет построение программы и приводит к неоправданным затратам оперативной памяти в процессе выполнения логического вывода. Для решения этой проблемы введено понятие мультиправила. Пусть сеть 5" арности (0,0) - правая часть мультиправила, определяющего некоторую логическую формулу, и Еп - подмножество ее элементов нетерминальных сортов. Тогда задает множество {х ^ | е =< х, 1е, Ос > £ ЕИ} из п = \ЕН | обычных правил, где правая часть Бс

каждого такого правила есть сеть <Р,1е,Ое,Е\{ё},и,а0>. Получение обычных правил из мультиправил выполняется непосредственно во время вычисления.

Исследуются методы оптимизации процессов вычислений. Предлагается использование как традиционных видов оптимизации, например, оптимизации последнего вызова, так и оригинальных видов - редукции «по фронт)'» и кольцевой подстановки. Для выполнения редукции необходимо определять совпадение фрагментов сетей с определениями левых частей правил редукции. Для сокращения рассматриваемой области сети использован тот факт, что однажды приведенная к нормальной форме (НФ) сеть может быть выведена из НФ только путем выполнения подстановки. Поэтому изначально все правила КССГ приводятся к НФ, после чего анализ на применимость правил редукции начинается с границы внесенных изменений («фронта» редукции), по мере необходимости продвигаясь внутрь и наружу образуемой этой границей внутренней области сети. Начальная граница изменений определяется множеством точек замещаемого элемента исходной сети.

Такой способ выполнения редукции можно назвать «ленивым» в том смысле, что анализ производится лишь для тех областей сети, где могла быть нарушена НФ. Выполнение редукции «по фронту» обеспечивает аналог применения сопоставления с образцом с целью выбора подходящего определения функции. Входы тела правила определяют условие его применимости, поэтому начало анализа от входов подставленной сети позволяет достаточно быстро исключать из рассмотрения неподходящие правила.

Суть кольцевой подстановки заключается в отказе от копирования элементов сетей до появления необходимости в таком копировании. Окружением точки называется множество элементов, входные или выходные кортежи которых содержат эту точку. Для выполнения подстановки требуется наличие замещаемого элемента, его входного и выходного кортежей точек и их окружения, а также входного и выходного кортежа точек тела правила и их окружения. После выполнения подстановки образуется кольцо, состоящее из внутреннего кольца (элементов тела правила) и внешнего кольца (элементов исходной сети). После этого вступает в действие механизм редукции «по фронту», расширенный таким образом, чтобы докопировать окружение фрагмента сети, для которого требуется выполнить анализ на применимость правил редукции. Если на определенном шаге редукции выясняется, что сеть интерпретируется как пустое НО, все скопированные элементы удаляются. Если же сеть приведена к НФ, выполняется копирование всех остальных, еще не скопированных элементов.

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

Оптимизация последнего вызова применяется для того, чтобы отказаться от копирования сети для выполнения подстановки в том случае, если для замещаемого элемента сети осталось применить только одно правило. Такая опти-

мизация имеет особое значение при работе с большими сетями, процесс копирования которых требует значительных вычислительных затрат.

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

Определяется базовый набор синтаксических операций, используемых в процессе вычисления для трансформации сетей. К таким операциям относятся добавление и удаление элементов сети, отождествление точек сети, разрушение связей заданной точки сети, добавление и удаление ребра dif -графа, добавление и удаление разметки для точки сети. Описывается изменение семантики сети при выполнении этих операций.

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

В соответствии с принятой моделью вычисления НО разработан набор команд АМНО и алгоритм ее работы. Основные команды относятся к осуществлению обхода дерева поиска и реализации базовых вычислительных механизмов - подстановки и редукции. Для работы АМНО вводится два списка сетей -список активных сетей AL и список сетей - результатов вычисления RL. Список AL содержит сети, для которых возможно применение правил КССГ. Изначально AL содержит только тело правила для аксиомы КССГ.

На каждом шаге вычисления в соответствии с принятой стратегией командой FindNet выбирается сеть S из AL, содержащая элемент е = FindElm(S) нетерминального сорта, после чего S копируется в S1 (в 5" элементу е соответствует е'), и командной Subst(S',e',e' —»S") строится сеть - результат подстановки [5"7е']5", где правило КССГ с правой частью S" определяется командой FindRule(S',е'). Производится редукция сети 5" командой Normalizeos'). В случае, если интерпретация сети S' отлична от 0, она добавляется либо в AL командой AddNet{AL,S'), если S' имеет элементы нетерминальных сортов, либо, в противном случае, командой AddNet(RL,S') в RL. Для элемента е примененное правило отмечается как использованное, и, если для этого элемента больше нет неиспользованных правил, то сеть S командой DelNet(AL,S) удаляется из AL, иначе она перемещается командой MoveNet(AL,S,Pos) в новое, определяемое принятой стратегией, место в AL.

В третьей главе уточняются задачи и рассматриваются основные вопросы реализации ПСИЗ. К основным задачам ПСИЗ можно отнести загрузку программ, статическую оптимизацию и вычисление программ, сбор статистической информации и выдачу результатов вычисления. В качестве отдельной задачи можно рассматривать поддержку вычислительного этапа компиляции запросов на языке 8-П.ОСОЬ, являющимся входным текстовым языком СФЛП.

Внутреннее представление КССГ формируется на основе особой, избыточной структуры данных, позволяющей повысить эффективность механизмов вычисления НО. Пример внутреннего представления сети показан на рис. 3.

(сеть) (внутреннее представление)

Рис. 3. Пример внутреннего представления сети.

Разработан алгоритм выполнения подстановки линейной сложности 0(п), где п - число связей входных и выходных точек замещаемого элемента исходной сети и тела правила. Алгоритм основан на попарном отождествлении точек кортежей замещаемого элемента и тела правила. Учет изменений, произведенных на предыдущих шагах алгоритма, производится по фактическому состоянию сети на основе особенностей ее внутреннего представления.

Описываются способы реализации оптимизационных преобразований основных вычислительных механизмов АМНО. Для реализации редукции «по фронту» вводится список точек редукции (СТР). Изначально СТР содержит точки кортежей замещаемого при подстановке элемента. На каждом шаге редукции выбирается одна точка из СТР и производится анализ ее окружения на применимость правил редукции. Если правило найдено, то производится его применение к соответствующему фрагменту сети, и те точки сети, в окружении которых произведены какие-либо изменения, вновь помещаются в СТР, иначе точка удаляется из СТР. Если список СТР пуст, то сеть находится в НФ.

Выполнение кольцевой подстановки осуществляется путем докопирова-ния сетевого контекста во время анализа точек из СТР. Для организации работы с контекстом каждый объект сети (элемент или точка) получает ссылки на свой родительский и (один) дочерний объекты. Установка этих свойств происходит при копировании объектов сети как для объекта-копии, так и для объекта-оригинала. Для каждого объекта также вводится флаг, показывающий, скопирован ли объект и все его окружение. Если при анализе точки из СТР этот флаг не установлен, то выполняется докопирование окружения этой точки (при этом все элементы родительской сети всегда копируются с точками их кортежей), после чего применимость правил редукции в этой точке анализируется

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

Применение кольцевой подстановки для решения таких задач как задача о Ханойских башнях, задача о ферзях, задачи обработки списков и др., позволило сократить среднее время выполнения шага вычисления в несколько раз.

Оптимизация последнего вызова выполняется следующим образом. Выделяется указатель ptr, определяющий сеть для выполнения подстановки и редукции. Если для замещаемого при подстановке элемента выбранной в соответствии с заданной стратегией сети S имеется более одного еще не примененного правила, то выполняется копирование сети S в S' и установка указателя ptr 5". Иначе указатель устанавливается на сеть 5 (ptr <- S ). После этого выполняется подстановка в определяемую ptr сеть и ее редукция.

Уточняются методы реализации стратегий вычисления. Стратегия определяется способом выбора тройки < S, е, г > для выполнения следующей подстановки, где S - исходная сеть, е - замещаемый элемент этой сети, а. г — правило КССГ для сорта элемента е. Для реализации поиска в ширину сеть S выбирается путем последовательного циклического просмотра AL, а новые сети добавляются в конец этого списка. Аналогичным образом ведется работа и со списком элементов сети для выполнения подстановки. Способ выбора правила КССГ при использовании такой стратегии значения не имеет.

При реализации поиска в глубину сеть S выбирается из начала списка AL; новые сети также помещаются в начало этого списка. Для реализации корректного выбора элементов сетей для выполнения подстановки все элементы нумеруются. При добавлении новых элементов в сеть во время выполнения подстановки все новые элементы должны помещаться в список элементов до собственных элементов сети с сохранением прежнего порядка. Для решения этой задачи строится специальный индекс, последовательность элементов которого определяет последовательность выбора элементов сети для выполнения подстановки, а значения элементов индекса указывают на соответствующие элементы сети. При выполнении подстановки индекс тела правила г помещается в начало индекса сети S. Использование индекса позволяет отказаться от сортировки часто изменяющегося списка элементов сети.

Рассматривается организация учета масок вычислимости при выборе элемента сети для выполнения подстановки.

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

кортежей элементов только в том случае, если такая разметка может быть однозначно определена. Например, при помощи системного НО сложения %Addi2'X) можно вычислить разметку любой точки входного или выходного кортежа по заданной разметке двух других точек.

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

Проводится анализ методов отладки в системах функционального и логического программирования. Разрабатываются методы отладки в СФЛП. Для отладки программ в СФЛП используется так называемое дерево отладки, которое представляет собой дерево вывода, дополненное особыми вершинами, содержащими информацию о способе формирования соответствующей сети. Кроме дерева отладки возможно использование специальных системных НО Swrite и Sshow, осуществляющих вывод текстового сообщения и изображения текущей вычисляемой сети, соответственно. Для отображения основных характеристик процесса вычисления используется подсистема сбора статистических данных.

Рассматриваются способы представления сетевых результатов вычисления в СФЛП. Выделяются случаи, допускающие текстовое представление результатов на основе разметки точек сети.

Описывается реализованный в СФЛП метод импорта программ, написанных на языке Пролог. Вводятся ограничения на вид таких программ, основными из которых являются запрет на использование отрицания и отсечения. Из системных предикатов поддерживаются =\=, ==, >=, is, write, fail, = и \=. Арифметические выражения преобразуются в древовидные сетевые фрагменты, вычисляемые системным НО $аг. Подсистема импорта также используется компилятором запросов СФЛП для преобразования промежуточного представления запроса на языке S-FLOGOL во внутренний формат ПСИЗ.

В четвертой главе исследуются вопросы графического построения программ. Предлагается технология графического построения программ (111111), обеспечивающая корректность формируемой программы на каждом шаге ее построения в сочетании с естественным и удобным подходом к конструированию сетей. Основой ТГПП является выделение набора операций, выполнение которых позволяет естественным образом формировать КССГ, в частности, графические изображения тел ее правил.

Для построения КССГ предложен набор операций, формально определенная семантика которых гарантирует, что выполнение операции не нарушит

корректность КССГ. Указанные операции приведены в табл. 1. Состояние КССГ после выполнения команды определяется как С =< В'т,В'и,а',Я' >.

Таблица 1.

Операция Команда К в;, а' Я' Условия

Добавление элемента Вт АсМТ(х) в„ а Я -

Удаление элемента Вт ЕХАТЬ) ' ВтЩ В„ а Я хеВт

Добавление элемента Вн Ас1с1М(х) \ Вт а Я -

Удаление элемента В., ОеШ(х) | Вт ВНЩ а Я хеВн,®

Выделение аксиомы ОгзЛхт(х) | Вт вн X Я хеВн

Удаление аксиомы Ое1Ахт(х) 1 Вт В„ 1 Я х = а

Добавление правила А<1йЯ{г) 1 Вт В„ а я^ и -

Удаление правила Ое№(г) | Вт ВИ а ; Я\{г} геЯ

Через символ ® обозначено ограничение на удаление сорта х из терминального и нетерминального базисов: (\/г е Я) -л5опи$ей{г,х~), где предикат 5опиае<1 определяет наличие элементов сорта х в теле правила г.

Правила КССГ задаются построением изображений тел правил. При добавлении правила в КССГ его тело изображается как пустая сеть (рис. 4 а), и далее осуществляется лишь редактирование этого изображения.

—• А<1<1

С) •— АсМ

Ф—

а) б) в)

Рис. 4. Пример добавления элемента и отождествления точек сети.

Графическое построение ведется по принципу «конструктора», когда сеть собирается из некоторых элементов путем применения несложных операций, таких как добавление и удаление объектов сети, связывание объектов между собой и разрушение таких связей. К объектам сети относятся элементы, точки и дуги. При добавлении элемента сети добавляются все точки, принадлежащие его входному и выходному кортежам, а также соединяющие их дуги (рис. 4 б). Удаление точки происходит в том случае, если после удаления некоторого элемента она становится изолированной, то есть не принадлежит входным или выходным кортежам элементов или сети. После того, как элементы сети с точками входных и выходных кортежей добавлены, следует отождествить те точки, интерпретация которых для определяемого НО должна совпадать (рис. 4 в).

Для разрушения связей точки используется специальная операция расщепления. Расщепление точки предполагает, что вместо одной точки, входящей п раз во входные и выходные кортежи элементов, создается п новых точек, ка-

ждая их которых имеет ровно одно вхождение в эти кортежи на одном из мест расщепляемой точки. Пример расщепления точки приведен на рис. 5.

Рис. 5. Пример разрушения связей («расщепления») точки сети.

Операция удаления элемента производится следующим образом. Удаляются элемент и все дуги между элементом и точками. Если после удаления некоторая точка оказалась изолированной, она также удаляется. Пример удаления элемента приведен на рис. 6.

висс

о

А(Ш

Бисс

с)

А<И

висс

Рис. 6. Пример удаления элемента сети.

К операциям над сетями можно отнести подстановку и абстракцию. Подстановка в ТГПП является аналогом подстановки в модели вычисления НО и предназначена для статического применения правила к элементу некоторой сети, что может использоваться для вставки отдельно созданного сетевого определения в отведенное для него место. Абстракция предназначена для упрощения сети (в смысле мощности множества ее элементов) за счет вынесения ее фрагмента в отдельное правило. Выполнение абстракции преследует те же цели, что и выделение подпрограмм в императивных языках программирования.

Сформулированы основные принципы построения и разработана архитектура графического редактора - инструментального средства поддержки ТГПП в СФЛП. Выделены основные задачи и требования к графическому редактору (далее - просто редактору). Задачами редактора являются: создание, редактирование, сохранение и загрузка графических программ, управление процессом вычисления и отладки. Редактор должен обеспечивать корректное отображение СПНО, приемлемую скорость прорисовки изображения и адекватное отображение процесса вычисления для отладки программ.

В архитектуре редактора можно выделить ядро, выполняющее основные функции редактора, интерфейс пользователя и подсистему передачи сообще-

ний, предназначенную как для обеспечения взаимодействия ядра и интерфейса редактора, так и для организации межсистемного взаимодействия с внешними по отношению к редактору подсистемами СФЛП — ПСИЗ и Центральным модулем. Вид окна редактора представлен на рис. 7.

т.,-* =_.УУ.Гг........л ,•■ ^ .;.'■!.......*_

Рис. 7. Вид окна графического редактора СФЛП.

Описывается решение тех задач, которые могут возникать и в других аналогичных системах графического программирования (методы оптимизации прорисовки изображения, построение дуг, огибающих элементы сети и др.).

Проводится анализ существующих методов автоматического построения изображений сетей. Необходимость отображения результатов вычисления в сетевом виде ставит задачу автоматического построения изображения сети по ее внутреннему представлению. Изображение сети должно быть построено таким образом, чтобы объекты находились на некотором небольшом удалении и были сгруппированы в соответствии с их связями. Эта задача решена на основе метода взаимных силовых воздействий объектов, согласно которому все объекты сети формируют силы отталкивания, а объекты, связанные дугами, формируют также группирующие сипы притягивания. Расстановка считается завершенной, если все силы уравновешены. Предлагается модификация метода, повышающая скорость построения изображения и улучшающая его качество.

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

В заключении приводятся основные результаты, полученные при выполнении диссертационной работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Предложена базовая модель вычисления НО и ее расширения. Разработаны алгоритмы линейной сложности для выполнения основных механизмов базовой модели вычисления - подстановки и редукции.

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

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

4. На основе предложенных методов и алгоритмов выполнения базовых механизмов вычисления НО разработана абстрактная машина, которая положена в основу реализации подсистемы исполнения запросов (ПСИЗ) СФЛП.

5. Разработана технология графического построения программ (111111) на основе сетевого представления НО, гарантирующая корректность формируемой программы на каждом шаге ее построения.

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

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

8. На основе полученных результатов реализованы и интегрированы в СФЛП графический редактор и ПСИЗ. Реализован импорт программ на языке Пролог.

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

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Бебчик Ан. М., Бебчик Ал. М. Особенности визуализации объектов графического интерфейса РЬОООЬ-системы функционально-логического программирования // Международный форум информатизации-2003. Информационные средства и технологии: Докл. междунар. конф. В 3-х т. - М.:Янус-К, 2003. - Т. 3,-С. 68-71.

2. Бебчик Ан. М. Реализация динамики при визуализации сетевого представления схем направленных отношений // Международный, форум информати-

зации-2003. Информационные средства и ттнотгии- ллтяп

конф. В 3-х т. - М.:Янус-К, 2003. - Т. 3. - С

3. Бебчик Ан. М. Проблемы реализации ядра

программирования на языке Я-РЬОвОЬ // РНБ Русский фонд

ка-2004: Тез. докл. 11-й Всероссийской л

студентов и аспирантов. - М.-.МИЭТ, 2004. АА/Г Д

4. Бебчик Ан. М. Технология графическс -

логических программ на языке Б-РЬСЮОЬ О О АЛ

науке, образовании и производстве: Мат ^^

конф. - Орел: ОрелГТУ, 2004. - Т. 5. - С. V.

5. Бебчик Ан. М. Принципы автоматического формирования графического изображения сетевого представления направленных отношений в системе функционально-логического программирования // Континуальные алгебраические логики и нейроинформатика в науке и технике - КЛИН-2004: Тр. междунар. конф. В 7-х т. Ульяновск:УлГТУ, 2004. - Т. 3. - С. 30-32.

6. Бебчик Ал. М., Бебчик Ан. М. Модель вычисления запроса языка функционально-логического программирования Б-РЬОООЬ // Компьютерное моделирование 2004: Тр. междунар. научно-техн. конф. - СПб.:Нестор, 2004. -С. 279-286.

7. Бебчик Ал. М., Бебчик Ан. М., Фальк В. Н. Система функционально-логического программирования Б-РЬОСЮЬ // Девятая Национальная конференция по искусственному интеллекту с международным участием КИИ-2004: Тр. конф. В 3-х т. - М.:Физматлит, 2004. - Т. 1. - С. 210-217.

8. Бебчик Ал. М., Бебчик Ан. М., Фальк В. Н. Инструментальные средства разработки и отладки программ системы функционально-логического программирования Б-РШООЬ // Девятая Национальная конференция по искусственному интеллекту с международным участием КИИ-2004: Тр. конф. В 3-х т. - М.:Физматлит, 2004. - Т. 3. - С. 896-901.

9. Бебчик Ал. М., Бебчик Ан. М. Особенности программирования на функционально-логическом языке 5-П.ОООЬ // Международный форум информати-зации-2004. Информационные средства и технологии: Докл. междунар. конф. В 3-х т. - М.:Янус-К, 2004. - Т. 3. - С. 88-91.

Подписано в печать Ц.С^ Г.// Зак. -Цд Тир. 1С{ П.л. /Д4 Полиграфический центр МЭИ (ТУ) Красноказарменная ул., д. 13

1. МЕТОДЫ РЕАЛИЗАЦИИ СИСТЕМ ДЕКЛАРАТИВНОГО

ПРОГРАММИРОВАНИЯ.

1.1 .Декларативная парадигма программирования.

1.1.1. Функциональное программирование.

1.1.2. Логическое программирование.

1.1.3. Функционально-логическое программирование.

1.1.4. Формализм направленных отношений.

1.2.Виды и модели вычисления декларативных программ.

1.2.1. Функциональные программы.

1.2.2. Логические программы.

1.2.3. Функционально-логические программы.

1.2.3.1. Спрямление.

1.2.3.2. Сужение.

1.2.3.3. Логика.

1.2.3.4. Декларации режимов вычислений.

1.3.Реализация моделей вычисления.

1.3.1. SECD-машина.

1.3.2. Виртуальная машина Уоррена (WAM).

1.4.Вычисление направленных отношений.

1.4.1. Вид программы.

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

1.4.3. Модели вычислений.

1.4.4. Задачи редукции сетей.

1.4.5. Реализация вычисления.

1.5.Визуальное программирование.

1.5.1. Логическое программирование на Акторном Прологе.

1.5.2. Функциональное программирование в Lab View.

1.5.3. Система программирования для языка СИПРОЛ.

1.5.4. Программирование на основе СПНО.

1.5.5. Вопросы автоматического построения изображения сетей.

Разработка языков и сред программирования, предназначенных для представления знаний, и лежащих в их основе формальных систем является актуальной задачей. Известные уже достаточно давно языки функционального программирования Лисп и логического программирования Пролог создавались на основе теории вычислимых функций и логики предикатов как средства программирования и эффективного решения задач искусственного интеллекта, обработки сложно организованных данных на основе формального, как правило, аксиоматического задания их свойств и взаимосвязи. В проектах создания вычислительных систем нового поколения автоматизация и эффективность логических доказательств были и остаются центральными проблемами.

Указанные языки легли в основу направления декларативного программирования, которое предполагает определение программы в виде совокупности формального описания объектов и зависимостей между ними, характеризующего некоторую предметную область, и запроса на нахождение (построение) объектов с конкретными заданными свойствами. Декларативный подход к построению программ позволяет получать интересующую пользователя информацию о предметной области с помощью некоторой процедуры автоматического вывода без явного указания последовательности действий, которые необходимо выполнить вычислительной машине для получения результата.

В настоящее время ведутся активные исследования в области создания реляционных формализмов и языков, которые должны существенно расширить возможности представления и обработки данных и знаний. В работах [35,36] разработана теория направленных отношений (НО), которая объединяет логический, реляционный и функциональный формализмы. Созданный на этой основе язык функционально-логического программирования [46] позволяет перейти к практической реализации высокоуровневых сред и систем программирования, отличающихся высоким уровнем автоматизации процессов разработки программ, широким использованием средств графического представления при построении и структурных преобразованиях программ. В рамках выполнения проекта РФФИ № 01-01-00690 «Разработка теоретических основ построения вычислительных сред и интеллектуальных систем, ориентированных на функционально-логический стиль программирования» была поставлена задача создания на базе языка FLOGOL системы функционально-логического программирования (СФЛП), решение которой рассматривается как цель проводимых в диссертации исследований.

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

- критический анализ известных моделей вычислений программ языков декларативного программирования и их реализаций с целью оценки возможности их применения при разработке СФЛП;

- разработка и исследование моделей вычислений на основе сетевого представления НО (СПНО);

- программная реализация подсистемы исполнения запросов СФЛП на основе разработанных моделей вычислений НО;

- разработка технологии корректного и комфортного для пользователя графического построения программ в сетевой форме;

- исследование и оптимизация метода автоматического построения графического изображения СПНО;

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

Методы исследования. При выполнении работы использованы методы теории направленных отношений, математической логики, теории формальных языков, теории алгоритмов, объектно-ориентированного программирования, тестирования программных продуктов.

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

Научная новизна. Научная новизна работы заключается в следующем:

1. Введено понятие размеченной сети на основе расширения понятия сети, определенного в теории НО. Предложены новые правила редукции для размеченных сетей и разработана сетевая модель вычисления НО.

2. Предложены модификации основных механизмов и стратегий вычисления НО, позволяющие повысить эффективность ПСИЗ, в частности, выполнения вычислительных операций подстановки и редукции сетей. Разработан алгоритм сетевой подстановки линейной сложности.

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

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

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

Апробация работы. Основные результаты диссертации докладывались и обсуждались на научно-технических конференциях МИРЭА (Москва, 2002, 2003, 2004), международных конференциях «Информационные средства и технологии» (Москва, 2003, 2004), всероссийской межвузовской научно-технической конференции «Микроэлектроника и информатика - 2004» (Зеленоград, 2004), международной научно-технической конференции «Информационные технологии в науке, образовании и производстве» (Орел, 2004), международной конференции «Континуальные алгебраические логики, исчисления и нейроинформатика в науке и технике» (Ульяновск, 2004), международной научно-технической конференции «Компьютерное моделирование 2004» (Санкт-Петербург, 2004) и «Девятой Национальной конференции по искусственному интеллекту с международным участием КИИ-2004» (Тверь, 2004).

Реализованная СФЛП демонстрировалась на выставке программных продуктов «Девятой Национальной конференции по искусственному интеллекту с международным участием КИИ-2004».

Публикации. Основные результаты, полученные при выполнении диссертационной работы, опубликованы в 9 печатных работах.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 94 наименования, и при

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

ЗАКЛЮЧЕНИЕ. ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ.

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

2. Предложена базовая модель вычисления НО и ее расширения. Разработаны алгоритмы линейной сложности для выполнения основных механизмов базовой модели вычисления - подстановки и редукции.

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

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

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

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

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

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

1. Агафонов В. Н., Борщев В. Б., Воронков А. А. Логическое программирование в широком смысле (обзор). Логическое программирование: Пер. с англ. и фр.-М.:Мир, 1988.

2. Ахо А. В., Хопкрофт Д. Э., Ульман Д. Д. Структуры данных и алгоритмы. -М.:Вильямс, 2001.

3. Бебчик Ан. М. Реализация динамики при визуализации сетевого представления схем направленных отношений // Междунар. форум информатизации-2003: Докл. междунар. конф. «Информационные средства и технологии». В 3-х т. М.:Янус-К, 2003. - Т. 3. - С. 65-67.

4. Бебчик Ал. М. Сетевой метод компиляции программ языка функционально-логического программирования S-FLOGOL // Информационные технологии в науке, образовании и производстве: Материалы междунар. научно-техн. конф. Орел: ОрелГТУ, 2004. - Т. 5. - С. 164-168.

5. Бебчик Ан. М. Технология графического построения функционально-логических программ на языке S-FLOGOL // Информационные технологии в науке, образовании и производстве: Материалы междунар. научно-техн. конф. Орел: ОрелГТУ, 2004. - Т. 5. - С. 175-179.

6. И.Бебчик Ал. М., Бебчик Ан. М. Модель вычисления запроса языка функционально-логического программирования S-FLOGOL // Компьютерное моделирование 2004: Тр. междунар. научно-техн. конф. СПб.:Нестор, 2004. -С. 279-286.

7. ХЪ.Бебчик Ал. М., Бебчик Ан. М. Особенности программирования на функционально-логическом языке S-FLOGOL // Междунар. форум информатизации-2004: Докл. междунар. конф. «Информационные средства и технологии». В 3-х т. М.:Янус-К, 2004. - Т. 3. - С. 88-91.

8. Белов В. Н., Брановский В. И., Вершинин К. П., Гецко JI.H. , Довгялло А. М., Ефименко С.Пп Колос В. В. ПРОЛОГ язык логического программирования- Прикладная информатика, 1986. - Вып. 1.

9. М.Бирюков А. А. Доказательство теорем в интерактивной флогол-системе. //Современные информационные технологии в управлении и образовании -новые возможности и перспективы использования: Сборник научных трудов. ФГУП НИИ «ВОСХОД», МИРЭА. М., 2001.

10. Борщев В. Б. Пролог основные идеи и конструкции. - Прикладная информатика, 1986. - Вып. 2.

11. Борщев В. Б. Семантика языков логического программирования и абстрактная машина для их реализации // автореферат дисс. . докт. физ.-мат. наук-М, 1992.

12. Вагин В.Н., Головина Е.Ю., Загорянская А.А. Достоверный и правдоподобный вывод в интеллектуальных системах./ Под ред. В.Н. Вагина, Д.А. Поспелова. М.:Физматлит, 2004.23 .Гросс М., Лантен А. Теория формальных грамматик. М.:Мир, 1971.

13. Элджер Д. С++: библиотека программиста. Спб: Издательство «Питер», 2000.

14. Дехтяренко И. А. Декларативное программирование. 2003. http://wvm.softcraft.ru/paradigm/dp/index.shtml

15. Ершов А. 77. Смешанные вычисления: потенциальные применения и методы использования. В кн.: Методы математической логики в проблемах искусственного интеллекта и систематическое программирование. - Вильнюс, 1980.

16. Иванов В. П., Батраков А. С. Трехмерная компьютерная графика/Под .ред. Г.М. Полищука. -М.: Радио и Связь, 1995.

17. Киммел П. и dp. Borland С++ 5: пер. с англ. СПб.: BHV - Санкт-Петербург, 1997.

18. Клоксин У., Меллиш К. Программирование на языке Пролог-М.: Мир, 1987.

19. Ковалев А. В. Коноплев Б. Г. Генетический алгоритм размещения разногабаритных блоков СБИС // Перспективные информационные технологии и интеллектуальные системы. Таганрог. :ТРГУ, 2001 -№ 1.31 .Ковалъски Р. Логика в решении проблем М.:Наука, 1990.

20. Ъ2.Ковальский Р. А. Логическое программирование.33 .Кораблин Ю. П. Кутепов В. П. Фальк В. Н. Исчисление функциональных схем.-В кн: Цифровая вычислительная техника и программирование. М.: Сов. радио, 1974. № 8.

21. Крюков В., Петренко А. Интегрированный подход к разработке крупных програмных систем реального времени //Индустрия программирования: Тр. конф.-М., 1996.

22. ЪЪ.Кутепов В. П., Фальк В. Н. Направленные отношения: теория и приложения // Изв. РАН. Техническая кибернетика, 1994. № 4,5.

23. Кутепов В. П., Фальк В. Н. Теория направленных отношений и логика // Изв. РАН. Теория и системы управления, 2000. №5.

24. Логическое программирование: Пер. с англ. И фр М.:Мир, 1988.

25. ЪЪ.Маклаков С. В. BPwin и ERwin. CASE-средства разработки информационных систем.-М.: ДИАЛОГ-МИФИ, 1999.

26. Морозов А. А., Обухов Ю. В. Акторный Пролог. Определение языка программирования / Препринт ИРЭ РАН 2(613). М., 1996.

27. Манна 3. Теория неподвижных точек программ. В кн.: Кибернетический сборник-М.: Мир, 1978. Вып. 15.

28. Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог-М.: Мир, 1990.

29. Соснин П. К, Кононенко А.И. Методы и средства образно-семантического сопровождения процессов принятия проектных решений // Интеллектуальные САПР-2002:Материалы XII междунар. конф. -Таганрог, 2002.

30. АЪ.Пратт Т., Зелковиц М. Языки программирования: разработка и реализация / Под общей ред. А. Матросова. СПб.: Питер, 2002.

31. Гей А., Гибомон П., Луи Ж. Логический подход к искусственному интеллекту: от классической логики к логическому программированию: Пер. с франц.-М. Мир, 1990.

32. Фальк В. Н. Бестиповые регулярные схемы направленных отношений // Изв. РАН. Теория и системы управления, 1998. №5.

33. Фальк В. Н. Теория направленных отношений и ее приложения // Дисс. . докт. техн. наук. М.: МЭИ, 2001.

34. А1.Филд А., Харрисон 77. Функциональное программирование: Пер. с англ-М.:Мир, 1993.

35. Хоггер К. Введение в логическое программирование М.: Мир, 1988.49Хювенен Э., Сеппянен Й. Мир Лиспа. В 2-х т. -М.: Мир, 1990.

36. Actor Prolog Report, http://www.ni.com/devzone/lvzone/viewarchivedl.htm

37. Albert E., Hanus M., Huch F., An operational semantics for declarative multi-paradigm languages // Proc. 11th International Workshop on Functional and (Constraint) Logic Programming. WFLP 2002, Grado, 2002. P. 7-20.

38. Antoy S., Echahed R., Hanus M. A needed narrowing strategy // JACM 47(4):776-822, 2000.

39. Burstall R. M., MacQueen D. В., Sanella D. T. Hope: an experimental applicative language: CSR-62-80. / Department of Computer Science, University of Edinburgh, 1980.

40. Colmerauer A. Prolog II Reference Manual and Theoretical Model: Internal Report/ GroupelA-U Aix-Marseille, 1982.

41. Curien P.-L. Categorical combinators, sequential algorithms and functional programming- Pitman/Wiley, 1986.

42. Hassan А. -К., Rouer N. Integration logic and functional programming // LISP Symbolic Computation, 1989-№ 2.

43. Hassan A.-K. Warren's Abstract Machine // MIT Press, Cambridge, 1991.

44. Hanus M. The Integration of Functions into Logic Programming: From Theory to Practice // Journal of Logic Programming, 1994- Vol. 19, Vol. 20.

45. Hanus M. (ed.). Curry: An Integrated Functional Logic Language // http://www.informatik.uni-kiel.de/~mh/curry/report.html, 2003.

46. Hanus M. A United Computation Model for Functional and Logic Programming // Proc. Of the 24th ACM Symposium on Principles of Programming Languages-Paris, 1997.

47. Hanus M., Prehofer C. Higher-Order Narrowing with Definitional Trees // Journal of Functional Programming, 1999-Vol. 9, № 1.

48. Hanus M., Sadre R. An Abstract Machine for Curry and its Concurrent Implementation in Java // Journal of Functional and Logic Programming, 1999.-N

49. Kowalski R. A. Predicate logic as a programming language // Information Processing'74 (IFIP Congress 74), 1974.

50. Kowalski R. A. Algorithm = logic + control // Comm. ACM, 1979 № 22.

51. Krukov V. A., Petrenko A. K., Trunov Yu. V., GRAPHIT-graphic integrated environment for real-time system development // Real-Time Data RTD- 94: Тез. межд. конф. - Дубна, 1994.

52. LabView Report. http://www.cplire.ru/Labl44/start/rcomp.html

53. Landin P. The Mechanical evaluation of Expressions // Computer Journal, 1964-Vol. 6.

54. Lloyd J. W. Combining Functional and Logic Programming Languages // Proc. of the International Logic Programming Symposium, 1994.

55. McCarthy J., Abrahams P.W., Edwards D.J. LISP 1.5 programmers manual-MIT Press, 1962.

56. SA.Reddy U. S. The relation between logic and functional languages: a survey. / Journal of Logic Programming, 1986 № 3.

57. Robinson J. A. A machine-oriented logic based on the resolution principle // Journal of the ACM, 1965.-№ 12(1).

58. Robinson J. A. LOGLISP: An Alternative to Prolog // Machine Intelligence, 1982.-№ 10.

59. SI .Robinson J. A. Logic programming past, present and future // New Generation Computing, 1983.-№ 1.

60. Somogyi Z, Henderson F., Conway T. The execution algorithm of Mercury: an efficient purely declarative logic programming language // Journal of Logic Programming, 1996.89 .Steele G. L. Jr. Common Lisp: The Language-Burlington :Digital Press, 1984.

61. Van Emden M. N., Kowalski R. A. The semantics of predicate logic as programming language // J. ACM, 1976. № 4.

62. Warren D. H. D. An Abstract Prolog Instruction Set: Technical Note 309 /Stanford.: SRI International, 1983.