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

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

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

В настоящее время ведутся активные исследования в области создания реляционных формализмов и языков, которые должны существенно расширить возможности представления и обработки данных и знаний. В работах [35,36] разработана теория направленных отношений (НО), которая объединяет логический, реляционный и функциональный формализмы. Созданный на этой основе язык функционально-логического программирования [46] позволяет перейти к практической реализации высокоуровневых сред и систем программирования, отличающихся высоким уровнем автоматизации процессов разработки программ, широким использованием средств графического представления при построении и структурных преобразованиях программ. В рамках выполнения проекта РФФИ № 01−01−690 «Разработка теоретических основ построения вычислительных сред и интеллектуальных систем, ориентированных на функционально-логический стиль программирования» была поставлена задача создания на базе языка 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. На основе полученных результатов реализованы ПСИЗ и графический редактор СФЛП. Указанные подсистемы интегрированы в СФЛП, созданную совместно с Бебчиком Ал. М.