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

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

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

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. Разработанная СФЛП доведена до уровня законченного программного продукта и внедрена в учебный процесс МИРЭА, МЭИ и МАИ.

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

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