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

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

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

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

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

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

Москва - 2005

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

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

Официальные оппоненты: доктор технических наук, доцент

Хорошевский Владимир Федорович

кандидат технических наук, доцент Мороховец Юрий Евгениевич

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

Защита состоится «ЯО» мая 2005 г в 16 час 00 мин на заседании диссертационного совета Д 212 157.01 при Московском энер!етическом инстите (техническом университете) по адресу. 111250, г Москва, Красноказарменная ул , д 17 (ауд Г-ЗОб)

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

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

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

диссертационного совета Д 212 157 01 кандидат технических на>к, профессор

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

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

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

Язык FLOGOL является современным языком декларативного программирования, предоставляющим средства компактного описания сложнооргани-зованных областей данных с использованием технологических принципов объектно-ориентированного программирования и средств схемной надстройки, характерных для языков высокого уровня. Сложность синтаксиса и семантики языка определяют важность создания специализированных средств как поддержки самого процесса программирования, так и выбора методов и алгоритмов компиляции программ к форме, непосредственно воспринимаемой вычислительным компонентом СФЛП. В диссертации решены следующие научные и прикладные задачи, связанные с указанными аспектами реализации системы программирования, осуществленной автором совместно с Бебчиком Ан.М.:

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

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

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

'Кутепов В П, Фальк В Н Направтенные отношения теория и прилоления ' Изв РАН Техническая кибернетика-1994 - №4-С 242-256-№5-С 114-123

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

3 Фальк В Н Теория направтенных отношений и ее приложения//Авторсф лис докт техн наук-М, 2001

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты диссертации докладывались и обсуждались на научно-технических конференциях МИРЭА (Москва, 2002,

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

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

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

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

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

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

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

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

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

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

Направленным отношением арности (п',п"),п\п"> 0, на носителе £> называется график соответствия из 3" в В" (арность НО указывается в виде верхнего индекса). НО Я'\ такое, что У«\/Д((а,Д) е Я «=(/?,«) £ Л-1), называется обратным НО Я. НО Я("' называется тотальным, если \/а(аеВ" гз ЗД(Де£>" л(а,Р)е Я)), и функциональным, если \faVpVp" ((а,р') е Я л (а,/?") е Л з Д' = Д"). Арность и наличие у НО и обратного ему НО свойств функциональности и тотальности называются спецификацией НО.

Язык рекурсивных схем НО основной универсальной сигнатуры строится из символов переменных НО, конечного числа символов базисных комбинаторных констант и трех символов операций композиции НО с применением оператора рекурсии. Операции композиции отражают отдельные аспекты НО, как формального объекта: объединение НО определяется как (Я <"'°") и )<"'"'' = {(а,р) | (а,Р) е Л, V (а, Д) еЯ2} и характеризует НО как множество; последовательная композиция НО определяется как (Л,'"'"' • Я^)1"'^ = {(а,Р)\Зу((а,у)е Л, л (у,р) еЯ2)\ и характеризует НО как соответствие, т.е. как множество упорядоченных пар элементов из области отправления (вход) и области прибытия (выход) соответствия; параллельная композиция НО определяется как ^

\(а]а2, ДР2) | (а,, Д) € Я1 л (а2, Р2) е Я2} и характеризует входы и выходы НО как кортежи элементов носителя. Указанные аспекты понятия НО обеспечивают возможность представления самых разных семантических объектов языков декларативного программирования (конкретных элементов и кортежей элементов носителя, множеств отдельных элементов и кортежей элементов носителя, функций и, в частности, конструкторов, предикатов, высказываний и т.д.) как конкретным образом специфицированных НО. Комбинаторные константы и операции композиции НО в определенном смысле универсальны: они являются неподвижными точками относительно любой перестановки на носителе, причем с помощью базисных комбинаторных констант и операций можно выразить любую комбинаторную константу. Задание интерпретации свободных переменных схемы как НО индуцирует и интерпретацию самой схемы как НО. Использование оператора рекурсии при построении схем позволяет строить НО, являющиеся компонентами минимальных решений любых конечных систем уравнений в описанной сигнатуре.

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

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

наличие соответствующего свойства у результата композиции (знаком «-» отмечено отсутствие жесткой зависимости наличия свойства от наличия этого свойства у операндов, знаком «2» отмечено, что свойство результата композиции однозначно определяется свойством второго операнда).

Таблица 1. Свойства операций композиции НО.

Операция композиции Знак Ф т оф от

Последовательная • AND AND AND AXD

Параллельная # AND AND AND AXD

Унификация V OR - AND AND

Конкатенация * AND AND OR -

Условная 2 AND 2 -

Пересечение п OR _ OR -

Объединение и - OR - OR

Сетевое представление рекурсивной схемы НО определено как множество специального вида сетей (сетевой язык), элементы которых соответствуют вхождениям свободных переменных в схему НО. Базисом элементов В называется конечное множество сортов X. Для каждого сорта хе X определена входная fj'(x) и выходная р"(х) арности. Сетью S арности (п',п"), п',п">0, в базисе элементов В называется пятерка <P,I,0,E,U>, где Р конечное множество точек сети; 1,0 еР* - кортежи входных и выходных точек сети, \l\-n и \0\~ п"Е q Хх Р*хР* - множество элементов сети, такое, что для всех e=<x,q',q" >еЕ \q'\=fi\x), \ q" |= р."(х), е называется элементом сети S сорта х, q- кортежем его входных, a q°- кортежем его выходных точек; U с Р'[2> - граф семантического различия на множестве точек сети. Сети рассматриваются с точностью до изоморфизма относительно множества точек сети. Интерпретация сети S и сетевого языка I в базисе В как НО на носителе D индуцируется интерпретацией (р сортов элементов как НО на D:

V, [ S ] = {(а', а")! (3 а-.Р^ D)(a' = ст(/) & а" = <т(0) л <У{р„р2} е U) Ш)*о(рг))л<У(х,д',д') 6 E){(o(q),CTlq"))zcp[x]))}, [i ] = s\

Se I

Иными словами, элементы графика отношения формируются как пары кортежей элементов носителя - значений разметки кортежей входных и выходных точек сети для всех возможных разметок точек сети (отображений 0".P—>D), удовлетворяющих требованиям интерпретации элементов сети и требованиям графа семантического различия.

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

Кроме того, в СФЛП предусмотрена возможность низкоуровневого задания запросов непосредственно в сетевой форме с использованием специального графического редактора. КССГ задается четверкой < Вт,Вн,а,Я>, где Вт и Вн, соответственно, терминальный и нетерминальный базисы (Вн г\Вт= 0), аеВи - аксиома, а /? - множество правил вида ¡5 —> 5, где р е В;. и 5 - сеть

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

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

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

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

В результате в работе определяется язык S-FLOGOL (Small FLOGOL), в котором введены следующие ограничения по отношению к базовому языку:

1) отказ от использования открытых интервалов при задании списков значений параметров сверток,

2) запрет транзитной передачи отдельных параметров при вызове НО в правых частях определений.

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

4) упрощенная внутренняя организация модуля,

5) запрет на использование произвольных реляционных выражений для задания параметров,

6) отказ от пользовательских реляционных инфиксных операций,

7) отказ от пользовательских (не встроенных в систему) внешних интерпретаций НО,

8) исключение виртуальных определений НО.

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

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

Формулируются принципы формального описания семантики. Семантика языка S-FLOGOL определена в форме описания преобразования программы в ее представление в виде конечной КССГ, индуцированной программой и запросом к ней. Для описания семантики введена функция обозначающая интерпретацию синтаксического правила языка для некоторого значения атрибута (р, который задает контекст определения синтаксической конструкции в виде пары <%,Name >, где £ - контекст свертки, a Name - имя НО, для которого выполняется построение множества сетевых определений (правил КССГ).

Контекст свертки содержит последовательность значе-

ний операторных переменных свертки v, в области действия которых находится описываемая конструкция, где / обозначает глубину структурной вложенности определения свертки по отношению к рассматриваемому

вызову переменной свертки. Имя НО задается пятеркой < Spec,IndList,Id,Cons,Prms>, где Spec - спецификатор НО, Id, IndList и Prms обозначают, соответственно, идентификатор, вычислимый список индексов и список параметров вызова НО, a Cons e {True, False) - признак интерпретации НО как конструктора на эрбрановском универсуме. Контекст и имя НО задаются в виде списков (в скобочной нотации), для работы с которыми применяются функция выборки элемента из списка elm, функция конкатенации списков append и др.

Основной конструкцией языка S-FLOGOL является универсальное синтаксическое понятие выражения. Для всех типов выражений вариантами его определения являются первичное выражение, результаты применения префиксных и инфиксных связок, условной конструкции IF и оператора свертки к выражениям того же типа (выражение обозначается как е(т), где г - тип выражения). Область интерпретации основных выражений отражена в табл. 2. Значение по умолчанию используется в случае, если выражение в программе определено не полностью.

Таблица 2. Интерпретация выражений.

Тип Область интерпретации Обозначение Значение по умолчанию

Дом | Мн-во правил R 0

Рел • Мп-во сетей, Мн-во правил S, R 0,0

СпПар \ Список имен НО Prms Г1

Терм Мн-во сетей, Мн-во правил S, R {5О<М,Ь0

Формула Мн-во сетей, Мн-во правил S, R ¡SO100'}, 0

Далее определяется и поясняется формальная семантика всех конструкций языка S-FLOGOL. В качестве примера приведем описание семантики некоторых основных конструкций. Доменное выражение задает: множество правил КССГ, правые части которых определяются реляционными выражениями (определения); множество правил КССГ без задания правой части (эрбрановские конструкторы); множество правил КССГ, представляющее собой объединение двух множеств правил, заданных двумя доменными выражениями. Семантическое правило для определения имеет вид:

Ф^ ^Спец et Ид е2 - е3^ = R, где е, е е(СпИнд), е2 ё е(СпПар), е} е е(Рел), Name0 = elm(<p,2), Namelall = [elm(Name0,\),elm(Name0,2),e}m(Name„,3)],

Мате1Ьт=[Ф9{стц\ф\е^,к(Ид)\,

Name = unify (Name mB, Namedom), Prms = joinPrms(elm(<p,5), Ф Д e21), [S, й, ] = Ф^, |e3 j, (p = [elm((p,\\append (Name, Prms)],

R2 = makeR(Narne,S), R = Л, u R2.

Функция к отображает синтаксические константы в семантические. Функция unify определяется как унификация термов и позволяет сопоставить имена вызываемого (NamecaU) и описываемого (Namedm) НО. В случае, если унификация не успешна, то результатом вычисления доменного выражения является пустое множество правил. Функция makeR формирует множество правил КССГ в виде упорядоченных пар, где первым элементом является имя НО, а вторым - элемент множества сетевых определений НО. Функция joinPrms определяет слияние списка параметров вызова и списка значений по умолчанию таким образом, что пропуск каждого параметра заменяется на значение по умолчанию, если таковое определено. Считается, что параметры, для которых значение осталось не заданным, представляют собой пустые НО.

Конструктор определяется схожим образом, однако вместо реляционного выражения используется вызов функции makeS 1, формирующей представляющую конструктор одноэлементную сеть:

Ф^Спец е, Ид J= {[Name,makeSl(Name)]}, где e, ее(СпИнд), Name,, =elm(<p,2), NamecM =[elm(Namell,\),elm(Name0,2),elm(Name(1,3)],

Name40m = [ ф„ [ Спец ], Фр [e, ], к{Ид)}, Name = unify{NamecaSl,Narne(lom).

Единственной операцией для доменного выражения является инфиксная операция объединения, определяемая как:

ф„[ в, ;е2] = Ф,[е,]иФ,[е2],где е},е2 ее{Дом).

Реляционное выражение задает вызов НО в виде: одноэлементной сети и множества правил КССГ, индуцированных этим вызовом (то есть определяющих вызываемое НО); множества заданных графиком сетей, а также множества правил, индуцированных вложенными в график вызовами НО; множества сетей, полученных при помощи композиции сетей - интерпретантов реляционных выражений, а также объединения множеств правил, индуцированных сетями -операндами композиции. Семантическое правило для вызова НО имеет вид:

[ ИмяОтн ] = [5, Л], где S = {makeS\(Name)},Name = Ф^, [ ИмяОтн ],

я = ифДео1ео се(Дом), у! = [[],Name],Rprms = dejPrms{(p).

Функция defPrms задает множество правил для включенных в список параметров имен НО. Выражение е, представляет корневой домен модуля.

Семантическое правило для графика определено следующим образом:

| е,: е27е}J = [5",Л],где е,,е2 ее(Терм), е3 е е(Формулс), S = graphic (XДД),

Термы задают входной и выходной кортежи НО, а формула

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

Применение реляционных операций определяется следующим образом:

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

1) выполнить синтаксический и семантический анализ программы,

2) сформировать внутреннее представление программы,

3) на основании программы и запроса построить КССГ.

Решение задач 1) и 2) в целом обеспечивается применением технологии дедуктивного построения программ, однако ввиду наличия вычислимых имен семантический анализ выполняется также и на этапе построения КССГ.

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

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

логической программы-компилятора (ЛПК) можно условно разделить на две основные части, определяющие, что компилировать и как компилировать.

Первая часть правил, называемых также £7?-правилами трансляции (Special Rules), формируется следующим образом. Все узлы внутреннего древовидного представления компилируемой программы нумеруется. Каждому узлу, определяющему некоторое синтаксическое понятие, ставится в соответствие семантическая функция трансляции, синтаксические переменные которой конкретизируются ссылками на дочерние узлы. Полученные функции переводятся в правила логики предикатов и добавляются в БД SR-правил.

Приведем абстрактный пример формирования SR-правил программы для вычисления арифметического выражения вида е = 4 + 5 * 6 (рис. 1).

Рис. 1. Пример формирования 57?-правил.

На рис. 1 а) представлены правила грамматики и соответствующие им семантические функции. На рис. 1 б) показано внутреннее представление программы (подчеркиванием выделены номера узлов). На рис. 1 в) представлены сформированные для выражения SR -правила, в которых е(х) представляет собой SR -правило запроса. Конкретизация синтаксических переменных выполнена с помощью добавления номера узла (через символ «_») к имени определяемой узлом конструкции.

Вторая часть правил, получивших название AR -правил (Additional Rules), задает схему и технологические средства компиляции программ и, следовательно, не зависит от вида конкретной компилируемой программы. AR-правила также реализуют вспомогательные операции, оптимизационные преобразования и механизмы межсистемного взаимодействия.

Для вычисления ЛПК используется ПСИЗ СФЛП, для чего записанные на языке Пролог SR -правила и AR -правила преобразуется в специальную КССГ GR\, результатом вычисления которой и является искомая КССГ запроса.

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

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

Формулируются принципы конструктивного построения КССГ. Рассматриваются реализующие эти принципы управляющие ЛЯ -правила ЛПК. Для конструктивного построения КССГ предлагается итерационный метод, реализуемый следующим алгоритмом:

1. Получить и добавить в КССГ сетевое определение вызова НО.

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

Для построения КССГ в множество ЛЯ -правил добавляются управляющие правила, реализующие следующую схему компиляции (рис. 2).

Рис. 2. Общая схема построения КССГ.

Построение КССГ начинается с выполнения шага 1 для НО с именем запроса и считается завершенным тогда, когда на очередном шаге в полученном сетевом определении НО присутствуют только элементы терминальных сортов. Имена определенных в программе НО, индуцированные вложенными вызовами полученного сетевого определения (шаг 1), записываются в так называемый список зависимостей и вновь направляются в БД для получения их сетевых определений (шаг 2). В силу введенных ограничений формирование КССГ для любой корректно заданной программы может быть выполнено за конечное число шагов.

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

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

ния SmpleNet. Определен метод преобразования КССГ из SmpleNet -описания в формат, используемый в ПСИЗ.

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

ресурсов может быть выражена как 0С , где О,- затраты на

формирование сети S вызываемого НО, п- количество элементов в 5, т- количество правил для г-го элемента, из них &,- с уникальной спецификацией, Ol/- затраты на формирование у-го правила для г-го элемента X Общая экономия определяется сетью S НО запроса.

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

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

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

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

Рассмотрим метод дедуктивного построения формального языка по его КС-грамматике. Пусть КС-грамматика б определена тройкой < У,Б,Р>, V -Т и N - объединенное множество терминальных и нетерминальных символов, 5 е N - начальный символ (аксиома) грамматики, Р - множество правил вида а Р, а <= ТУ, р еУ*. Цепочкой р называется последовательность символов а.1а2...а„, п > 0. Цепочка /? выводима в С? (обозначается (7 =>/?), если = 5 или Эр'зр"3р"3а(а^рт ¿РаС^ра/32лр--Р'/]"/]"). Во втором случае Р называется результатом применения правила а —> р" к некоторому вхождению нетерминального символа а в выводимую в С? цепочку р,ар2.

Пусть t - текст программы, в начальный момент t := 5". Шаг построения программы в ТДПП определяется как присваивание t результата применения к цепочке р - значению / некоторого правила грамматики. Для этого необходимо выделить вхождение нетерминального символа и выбрать одно из определенных для а правил грамматики. Построение программы осуществляется путем последовательного выполнения отдельных шагов и завершается тогда, когда полученная на очередном шаге цепочка не содержит нетерминальных символов. Такой метод очевидным образом гарантирует синтаксическую корректность формируемой программы на каждом шаге ее построения.

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

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

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

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

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

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

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

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

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

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

Для изменения уровня детализации отображения программы предусмотрена возможность свертывания и развертывания узлов РСД При этом, в зависимости от степени завершенности построения сворачиваемой синтаксической конструкции (не определена, определена частично, определена потностью), символ свернутого узла имеет различную цветовую раскраску

Формулируются принципы построения и требования к структурно-ориентированному редактору СФЛП, реализующему 1ДПП Описываются архитектура редактора и наиболее важные аспекты его программной реализации Общий вид окна редактора при комшляции запроса показан на рис 3

..«Ш1

э ШОЕ - [ОегмДО] - 1Ш1Л ■ 1*1М$ЛГИ

Щ-^йп вщ Действия- конпигя^ чОуак», _

№ «

@ 1 э «30 2 3 ЬепдЬ1 а 1впд»Ь 2 0 МетЬе

□ Мель« 2 0 О&ес! Е0 0 «12 Л Ре!иОП1

□ Раг оп2 5) Ра опЗ 3 Реггйо д Ре»гги1а ап.

□ Ре т/а «п 2 3 ОискЗа

О Ои к и О Ве е/ е 5 рр-« е2 0 ЭлЬс! 5 3 Эее г ^ Осемнье

П.£ то е»нье ^ Запросы 3 ОАрре А О ОСиск ч Рм ¿льтаг ~г

ъва^гье и-

X))))

Длина л ка ЬепдЫМЫи Ьи1 } Ьег^ оп«(х хз) ис ( (х">)) /Т наахлелность эл»нрнтй слит^ ГепЬес»^ Сопз<х хз) ) КепЬег-{ с з( / 73) { уз))

» е %новг<а л е »нт в пи >.а Р*глисвлгсг»{.< С г 4 г

Ресшисв ют» (411 )

ЦРегиш^юп ^РегяшеатЧЦт^ 1 3 5 ^,2])-}

/ Об^аллние п>ска Веу<» 96-

{Сопз(х хз) АррегсЦ (*з> Соаз(х Г»1 ))> Реуесзе-(Ы11 VI | Бь трая с ртировк%

{С п-( хз)

8» вето

^ Сгеевемоаули

Д Намгммцня з*пмс * 'ОЙегтий*

_3 А*!""1 @ Нагл

@ Слеп {£? *огд Э ^ Дадук ивные модк Текстовыенсдуи

□ АН»« Ц СотЬСоп$ И СепТ ее

□ Напо

□

П ка в.

)

»г'а« иоп(хз х) =«>. 1 х2) кЗ {Г 1 N ) НаГВКаЯ ОрТИр Fвr г: (х /??ег а о < )

Сорт «ро«ка в т*вк г ТпзЭосг {Согэ(х хз) 1»эег (X

V.

Э КфпиыямзМрЬса + Псг^вио* I 4

г

Теотиши?1|е*М4т Ред ¡Пр Р?ляиийь*1Ср Пробел Ре 1 о

.4' '■'*. - - Ч

Рис 3 Общий вид окна структурно-ориентированного редактора

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

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

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

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

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

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

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

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

5. Разработаны архитектура и интерфейсные средства структурно-ориентированного редактора, реализующего построение S-FLOGOL-программ по предложенной технологии.

6. Разработан алгоритм автоматического структурирования текста программ языка S-FLOGOL на основе их внутреннего древовидного представления.

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

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

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

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

05Л-0£Ъ

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

3. Бебчик Ал. М. Алгоритм автоматического структурирования текста программ языка программирования 8-РЬОООЬ // Микроэлектроника и инфор-матика-2004: Тез. докл. 11-й Всероссийской межвузовской научно-техн. конф. студентов и аспирантов. - М.:МИЭТ, 2004. - С. 253.

4. Бебчик Ал. М. Альтернативно-списковая грамматика как основа технологии автоматизированного построения программ языка функционально-логического программирования 8-РЬОООЬ // Континуальные алгебраические логики и нейроинформатика в науке и технике - КЛИН-2004: Тр. междунар. конф. В 7-х т. Ульяновск:УлГТУ, 2004. - Т. 3. - С. 27-29.

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

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

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

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

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

Подписано в печать /4,£ Ч Тир. 1С1' П.л.

Полиграфический центр МЭИ (ТУ) Красноказарменная ул., д. 13

/ I >

(

( _

- 965

19

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

1.1. Основные парадигмы программирования.

1.1.1. Императивная парадигма.

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

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

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

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

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

1.2.1. Описание синтаксиса языков программирования.

1.2.1.1. Форма Бэкуса-Наура.

1.2.1.2. Синтаксические диаграммы.

1.2.1.3. Синтаксический анализ.

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

1.2.2.1. Статическая семантика.

1.2.2.2. Динамическая семантика.

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

1.3.1. Средства текстового построения программ.

1.3.2. Графическое программирование.

1.4.Основные формы реализации языков программирования.

1.4.1. Компиляция.

1.4.2. Интерпретация.

1.4.3. Смешанная форма.

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

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

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

Язык FLOGOL является современным языком декларативного программирования, предоставляющим средства компактного описания сложнооргани-зованных областей данных с использованием технологических принципов объектно-ориентированного программирования и средств схемной надстройки, характерных для языков высокого уровня. Сложность синтаксиса и семантики языка определяют важность создания специализированных средств как поддержки самого процесса программирования, так и выбора методов и алгоритмов компиляции программ к форме, непосредственно воспринимаемой вычислительным компонентом СФЛП. В диссертации решены следующие научные и прикладные задачи, связанные с указанными аспектами реализации системы программирования, осуществленной автором совместно с Бебчиком Ан.М.: -проанализированы методы реализации современных языков и систем декларативного программирования с целью определения возможности их применения при реализации СФЛП; -выполнен анализ методов описания семантики языков функционального и логического программирования; -уточнены принципы построения языка FLOGOL, определено его представительное подмножество S-FLOGOL и осуществлено формальное описание его синтаксиса и семантики; -разработаны принципы и методы обработки S-FLOGOL-запросов на вычисления;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. На основе предложенных ограничений разработан язык S-FLOGOL, являющийся диалектом языка FLOGOL, выполнено формальное описание его синтаксиса и семантики. В язык S-FLOGOL введены средства поддержки системных типов данных, обеспечиваемые подсистемой исполнения запросов СФЛП.

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

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

5. Разработаны архитектура и интерфейсные средства структурно-ориентированного редактора, обеспечивающего возможность программирования на языке S-FLOGOL по предложенной технологии.

6. Разработан алгоритм автоматического структурирования текста программ языка S-FLOGOL на основе их внутреннего древовидного представления.

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

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

1. Агафонов В.Н. Логическое программирование / Пер. с англ. и фр. М.:Мир, 1988.

2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и трансляции. М.:Мир, 1978.

3. Барендрегт X. Лямбда-исчисление, его синтаксис и семантика. М.: Мир, 1985.

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

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

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

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

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

9. Борщев В. Б. Семантика параметрических конструкций в логическом программировании // Тезисы докладов школы-семинара «Синтез программ», Устинов, 1985.

10. Борщев В. Б. Логическое программирование // Известия АН СССР, Техническая кибернетика, 2, 1986.

11. Ю.Братко И. Программирование на языке Пролог для искусственного интеллекта. М.: Мир, 1990.21 .Братчиков И. Л. Синтаксис языков программирования. М.:Наука. Физмат-лит, 1975.

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

13. Гросс М., ЛантенА. Теория формальных грамматик. М.:Мир, 1971.

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

15. Зевина С. Г. Использование логического программирования в системах построения компиляторов. Препринт. М:ВИНИНТИ, 1991.2в.Клоксин У., МеллишК. Программирование на языке Пролог. М.:Мир, 1987.

16. Ковалъски Р. Логика в решении проблем. М.:Наука,1990.

17. Котляров А.В. Построение интерпретаторов и компиляторов. СПб.: Наука и техника. 2001.

18. Кораблин Ю.П. Семантика языков программирования. Учебное пособие. М.:МЭИ, 1992.

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

20. Костельцев А.В. Построение интерпретаторов и компиляторов. Спб.:Наука и техника, 2001.

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

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

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

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

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

26. Себеста, Р. Основные концепции языков программирования, 5-е изд.:Пер. с англ. М.: «Вильяме», 2001.

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

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

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

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

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

32. Филд А., Харрисон П. Функциональное программирование / Пер. с англ. М.:Мир, 1993.45Хоггер К. Введение в логическое программирование. М.: Мир, 1988.4в.Actor Prolog Report. http://vAvw.ni.com/devzone/lvzone/viewarchivedl .htm.

33. Backus J. Can programming be liberated from von Neumann style? A functional style and its algebra of programs // Comm. ACM, 21, 1978.

34. Backus J. W., Williams J.H., Wimmers E.L. FL language manual (preliminary version) // IBM research report number RJ 5339 (54809), 1987.

35. Bellegrade F. Rewriting system on FP expressions that reduce the number of sequences they yield // Proc. Conference of LISP and Functional programming, 1984.

36. Bird R. Introduction to Functional Programming using Haskell // Prentice Hall, New York, 1998.51 .Bowen K.A. A meta-level programming and knowledge representation // New Generation Computing, 3, No. 4, 1985.

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

38. Chomsky N. Reflections on language //N. Y.: Pantheon, 1975.

39. Church A. The calculi of lambda conversion // Princeton University Press, 1941

40. Clark К. L. Negation as failure // Logic and data bases, N. Y. Plenum Press, 1978.5e.Colmerauer A. An interesting subset of a natural language. In Logic Programming //N.Y.: Academic Press, 1982.

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

42. Darlington J., Field A. J., Pull H. The unification of functional and logic languages, towards Constraint Functional Programming // Technical Report, Imperial College, London, U.K., 1979.

43. Dybvig R.K. The Scheme Programming Language // Prentice-Hall, Englewood Cliffs, NJ, 1987.

44. Jones Simon Peyton (editor). Report on the Programming Language Haskell 98, A Non-strict Purely Functional Language // Yale University, Department of Computer Science Tech Report YALEU/DCS/RR-1106, Feb 1999.

45. Kieburtz R.B., Shltis J. Transformation of FP program schemes // Proc. ACM Conference on Function Languages and Computer Architecture, Portsmouth, New Hampshire, 1981.

46. Knuth D. Semantics of context-free languages // Mathematical Systems Theory 2, 1968.

47. Knuth D. The genesis of attribute grammars I I Lecture Notes in Computer Science 461, 1990.

48. Kowalski R. A. Predicate logic as a programming language I I Information Processing'74 (IFIP Congress 74), 1974ll.Kowalski R. A. Algorithm = logic + control // Comm. ACM, 22, 1979.

49. Lab View Report, http://www.ni.com/devzone/lvzone/view archived 1 .htm

50. Mantsivoda A.V. Flang: a functional-logic language // Proc. Int. Workshop on

51. Processing Declarative Knowledge. Springer LNAI 567, 1991.

52. Mantsivoda A.V. Flang and its Implementation // Proc. of the 5th International Symposium on Programming Language Implementation and Logic Programming. Springer LNCS 714, 1993.

53. Naish L. Adding equations to NU-Prolog // Proc. of the 3rd Int. Symposium on Programming Language Implementation and Logic Programming, Springer LNCS 528, 1991.

54. Kl.Reddy U.S. The relation between logic and functional languages: a survey. // J. Logic Programming, 3 , No. 3, 1986.83 .Robinson J. A. A machine-oriented logic based on the resolution principle I I Journal of the ACM, 12(1), 1965.

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

56. Somogyi Zoltan, Henderson Fergus. The design and implementation of Mercury. // Joint International Conference and Symposium on Logic Programming. Bonn, Germany, September, 1996.

57. Steele G.L. Jr. Common Lisp: The Language // Digital Press, Burlington, Mass., 1984.

58. StoyJ.E. Denotational semantics: the Scott-Starchy approach to programming languages theory // MIT Press, 1977.

59. SS.Turchin V. F. REFAL-5 programming guide and reference manual // New England Publishig Co., Holyoke, 1989

60. Wegner P. The Vienna Definition Language // ACM Computing surveys, Vol.4, No. 1., 1972

61. Wolz D. Design of a Compiler for Lazy Pattern Driven Narrowing // Recent Trends in Data Type Specification. Springer LNCS 534, 1990.155