Разработка и исследование подсистемы исполнения запросов и графического редактора системы функционально-логического программирования тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Бебчик, Антон Михайлович

• Бебчик, Антон Михайлович
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Бебчик, Антон Михайлович

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

Список литературы диссертационного исследования кандидат технических наук Бебчик, Антон Михайлович, 2005 год

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.