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

• Карпова, Наталья Николаевна
• кандидат физико-математических наук
• 1998

Оглавление диссертации кандидат физико-математических наук Карпова, Наталья Николаевна

Введение.

1. Анализ языков и систем функционального, логического и реляционного программирования.

1.1. Анализ современных стилей программирования.

1.2. Анализ языков и систем функционального программирования.

1.2.1. Продукционные языки.

1.2.2. Лямбда-основанные языки

1.2.2.1. Lisp.

1.2.2.2. SML.

1.2.2.3. Норе.

1.2.2.4. Miranda.

1.2.3. Языки композиционного программирования

1.2.3.1. Переход к композиционному программированию, язык APL.

1.2.3.2. Язык функциональных схем.

1.2.3.3. FUN.

1.2.3.4. FP-система.

1.2.3.5. FP2.

1.2.4. Типизация в языках функционального программирования.

1.2.4.1. Теории типов.

1.2.4.2. Реализационный аспект типизации языков программирования.

1.3. Анализ языков и систем логического программирования.

1.3.1. Пролог.

1.3.2. Дейталог.

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

1.4.1. Выражение запросов реляционной алгебры с использованием языка Miranda

1.4.2. Libra.

1.5. Цель и задачи диссертационной работы.

Выводы.

2. Язык FLOGOL. Формализм направленных отношений как основа построения языка.

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

2.1.1. Направленное отношение как математический объект.

2.1.2. Основные понятия аппарата направленных отношений.

2.1.3. Языки схем d-отношений.

2.1.4. Композиция d-отношений.

2.1.5. Классы d-отношений.

2.1.6. Исчисления включения и эквивалентности схем d-отношений.

2.2. Синтаксис языка FLOGOL.

2.2.1. Задачи создания языка и требования к его реализации.

2.2.2. Базовые конструкции языка.

2.2.3. Операции композиции отношений.

2.2.4. Структура программы.

2.3. Программирование на языке FLOGOL.

2.4. Язык запросов как подмножество языка FLOGOL.

Выводы.

3. Структура программ и особенности программирования на языке FLOGOL.

3.1. Средства модульной организации программ.

3.2. Схемное задание отношений.

3.3. Механизм «видимости» имен.

3.4. Контроль типов.

Выводы.

4. Реализация языка программирования FLOGOL.

4.1. Архитектура интегрированной системы функционально-логического программирования и проектирования программ.

4.2. Разработка и исполнение программ с использованием интегрированной среды программирования.

4.3. Компиляция программ.

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

4.4. Исполнение функционально-логических программ.

4.5. Перспективы развития системы. Интеграция языка FLOGOL с языками процедурного программирования.

Выводы.

Введение диссертации (часть автореферата) на тему «Исследование и реализация функциональнологической парадигмы программирования с использованием формализма направленных отношений»

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

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

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

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

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

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

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

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

При создании большого количества языков были предприняты попытки объединить функциональное и логическое программирование, сохраняя преимущества обоих, при этом устранив некоторые их недостатки. Многие созданные системы не имели собственного интерфейса и непосредственно использовали интерпретаторы функциональных языков. Большинство реализаций языков и систем функционального программирования были выполнены для ЕС ЭВМ (языки АРЬ [52], Норе[40], Мп-апс1а[67], ЯФС[5], система БР[33] и др.). Распространение ПЭВМ, распределенных вычислительных систем и связанный с этим прогресс в развитии программного обеспечения существенно изменили критерии оценки реализаций языков. Системы программирования для ПЭВМ, как правило, представляют собой диалоговое окружение, включающее все необходимые средства для выполнения работ по разработке и отладке программ.

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

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

Поставленная цель требует решения следующих задач:

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

- исследования существующих подходов к типизации языков программирования, структурированию и модульной организации программ;

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

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

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

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

Научные результаты и положения, выносимые на защиту.

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

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

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

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

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

6. Выполнена реализация разработанного языка в виде системы программирования, функционирующей на ЭВМ IBM PC под управлением операционной системы Windows 95.

Практическая значимость и внедрение результатов работы.

Работа над диссертацией проводилась на кафедре Информатики и процессов управления МИФИ /ТУ/. Выполненная работа соответствует «Перечню технологий двойного назначения (двойных технологий федерального уровня)» (раздел В.4.2.1.3 «Языки программирования и компиляторы»).

Результаты исследований, изложенных в диссертационной работе, использованы при разработке программ в Государственном центре компьютерных технологий «СиликонТелекомСофт» при Министерстве общего и профессионального образования РФ, г. Москва. Разработанная система программирования внедрена в ЗАО «Фирма «АйТи». Информационные технологии», г. Зеленоград.

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

- на Всероссийской научно-технической конференции с участием зарубежных представителей "Интеллектуальные САПР-96" (Геленджик, 1996г.),

- на международной конференции "Информационные средства и технологии" (Москва, 1997г.),

- на Всероссийской научно-технической конференции с участием зарубежных представителей "Интеллектуальные САПР-97" (Геленджик, 1997г.),

- на Второй Всероссийской научно-технической конференции с международным участием "Электроника и информатика - 97" (Зеленоград, 1997г.),

- на научной сессии МИФИ (Москва, 1998г.),

- на ежегодной научно-технической конференции студентов и аспирантов ВУЗов России (Москва, 1998г.).

Публикации. Основные результаты работы отражены в 11 публикациях.

Структура и объем работы.

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

Заключение диссертации по теме «Теоретические основы информатики», Карпова, Наталья Николаевна

Выводы

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

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

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

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

5. Реализован модуль исполнения запросов к программам на языке FLOGOL.

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

ЗАКЛЮЧЕНИЕ

Главным итогом диссертационной работы является разработка и реализация на ПЭВМ ЕВМ РС языка функционально-логического программирования, обладающего неоспоримыми преимуществами по сравнению с языками функционального программирования и объединяющего в себе черты функционального композиционного и логического программирования. Данная реализация обладает удобным синтаксисом, возможностью создания различных структур данных и средствами контроля типов. В ходе работы были получены следующие результаты:

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

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

3. Разработано единообразное представление основополагающих математических понятий как подвидов направленных отношений.

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

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

6. Разработана архитектура интегрированной системы функционально-логического программирования и проектирования программ, ядром которой является язык РШСОЬ.

7. Разработано и реализовано внутреннее представление программ, позволяющее в 1,5 раза сократить время их исполнения по сравнению с языками функционального программирования.

Список литературы диссертационного исследования кандидат физико-математических наук Карпова, Наталья Николаевна, 1998 год

1. Амамия М., Танака Ю. Архитектура ЭВМ и искусственный интеллект: Пер. с японск. М, Мир, 1993. - 400 е., ил.

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

3. Борздова Т.В., Вахрушева М.Б., Кутепов В.П., Петцольд В. Полиязычная система параллельного программирования, основанная на одном семействе функциональных языков // Программирование, 1984, № 2, с. 31-45.

4. Борздова Т.В. Разработка структурно-функциональных методов в параллельном программировании // Дисс. к.т.н., М.: МЭИ, 1984.

5. Вирт Н. «Программирование на языке МОДУЛА-2», М., Мир, 1987.

6. Вирт Н. «Систематическое программирование», М., Мир, 1977.

7. Грызунов В.Б. Разработка и реализация системы функционального программирования для ПЭВМ // Дисс. к.т.н., М.: МЭИ, 1990.12. «Данные в языках программирования» под ред. Агафонова В.Н. М., Мир,1982.

8. Дейкстра Э. «Заметки по структурному программированию» в кн. «Структурное программирование», М., Мир, 1975.

9. Карпова H.H. Абстрактные типы данных в языках функционального программирования// Научная сессия МИФИ-98. Сб. науч. трудов. Часть 5, с. 51-52.

10. Карпова H.H. Средства модульной организации программ на языке FLOGOL // Сборник научных трудов к научно-технической конференции МИРЭА (ТУ). Кафедра МОВС. Москва: Изд-во ЭРЕБУС, 1998.

11. Карпова H.H. Теория направленных отношений как основа построения языка функционально-логического программирования FLOGOL. Международная конференция «Информационные средства и технологии». Тезисы докладов. Москва, 1997, с. 108-113.

12. Климов A.B., Романенко С.А. Система программирования РЕФАЛ-2 для ЕС ЭВМ: Описание входного языка. М., 1978, 52 с.

13. Кутепов В.П., Кораблин Ю.П. Язык граф-схем параллельных алгоритмов. -М.: Программирование, №1,1978, с. 5-11.

14. Кутепов В.П. Проблема функциональности в одном классе отношений // Кибернетика. 1981. № 3.

15. Кутепов В.П., Фальк В.Н. Модели асинхронных вычислений значений функций в языке функциональных схем. // Программирование, 1978, № 3, с. 3-15.

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

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

18. Кутепов В.П., Фальк В.Н. Функциональные системы: теоретический и практический аспекты. // Кибернетика, 1979 №1, с. 46-58.

19. Петцольд В. Построение системы параллельной обработки символьной информации на основе одного семейства функциональных моделей // Дисс. к.т.н., 1981.

20. Турчин В.Ф. Метаалгоритмический язык. Кибернетика № 4, 1968, с. 45-54.

21. Турчин В.Ф. Метаязык для формального описания алгоритмических языков. В сб. Цифровая вычислительная техника и программирование. Сов. Радио, 1966, с. 116124.

22. Фальк В.Н. Теоретические модели языков программирования и вопросы их структурной интерпретации //Дисс. к.т.н., М.: МЭИ, 1978.

23. Фальк В.Н. Языки схем отношений // Формальные модели параллельных вычислений. Новосибирск: ВЦ СО АН СССР, 1988.

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

25. Хоар К. «Иерархические структуры программ» в кн. «Структурное программирование», М., Мир, 1975.

26. Хоар К. «О структурной организации данных» в кн. «Структурное программирование», М., Мир, 1975.

27. Чери С., Готлоб Г., Танка JI. Логическое программирование и базы данных: Пер. с англ. М.: Мир, 1992. - 352 е., ил.

28. Apt K.R. and van Emden M.H. Contributions to the Theory of Logic Programming, Journal of the ACM 29:3,1982.

29. Backus J. Can programming be liberated from the fon Neuman style? A Functional style and its algebra of programs. CACM, vol. 128, no. 8, pp.613-641,1977.

30. Bowen K.A. and Kowalski R.A. «Amalgamating Language and Metalanguage in Logic Programming» in Logic Programming (K.L. Clark and S.A. Tarnlund, eds.), Academic Press, London, 1982, pp. 153-172.

31. Burstall R.M., MacQueen D.B., Sannella D.T. HOPE: An Experimental Applicative Language. 1st International LISP Conference, 1980.

32. Cardelli L. Amber. LNCS, mo. 242, pp. 21-47,1986.

33. Cardelli L. Compiling a functional language. Proc. 1984 ACM symp. in Lisp and Functional Programming. Austin, Texas, ACM, vol 8, pp. 208-217, 1984.

34. Chikayama T. ESP Extended Self-contained Prolog - as a Preliminary Kernel of Fifth Generation Computers, New Generation Computing 1:1,1983, pp. 11-24.

35. Church A. A formulation of the simple theory of types. The journal of symbolic logic, vol 5, pp. 56-68, 1940.

36. Church A. The calculi of lambda-conversion. Annals of Math. Studies, 6, 1951.

37. Clark K.L and Gregory S. Notes on the Implementation of Parlog, Journal of Logic Programming 2:1,1985, pp. 17-42.

38. De Bakker J.W. Recursive procedures // Mathematical centre tracts 24. Amsterdam: Mathematisch centrum, 1971.

39. Dwyer B. Libra: A Lazy Interpreter of Binary Relational Algebra, Computer Science Technical Report 95-10, Department of Computer Science University of Adelaide.

40. Gordon M., Milner R., Wadsworth C. Edinburg LCF: A Mechanised Logic of Computation. LNCS 78,1979.

41. Hammond P. and Sergot M. Apes: Augmented Prolog for Expert Systems Reference Manual, Logic Based Systems Richmond, Surrey, England, 1984.

42. Hitchcok P., Park D. Induction rules and termination proofs // Automata, Languages and Programming. Nivat. Ed. North-Holland, Amsterdam, 1973.

43. Iverson K.A. A Programming Language. Wiley. New York, 1962.

44. Kowalski R.A. Predicate Logic as a Programming Language. Proc. IFIP-74, North Holland, Amsterdam, 1974, pp. 569-574.

45. Kutepov V., Falk V. Integrated tools for functional, logical and data-flow parallel programming and controlling parallel computations on computeer systems // Proceed. Internat. Conf. «Parallel Computing technologies». Novosibirsk, 1991.

46. McDermott D. DUC: A Lisp-Based Deductive System, Technical Report, Department of Computer Science, Yale University, 1983.

47. Merritt D. Extending C with Prolog. Dr. Dobb's journal, #217, August, pp. 78-104,1994.

48. Milner R. Algebraic theory of computable polyadic functions // Computer Science memorandum № 22. University College of Swansea, 1970.

49. Milner R. A theory of type polimorphism in programming: J. Comp. System Sci., vol. 17, pp. 348-375, 1978.

50. Milner R. The Standard ML core language. Polimorphism: The ML/LCF/Hope Newsletter, vol. 2, no.2, October 1985.

51. Mitchel J. Coercion and type inference. Proc. of the fifth ACM symp. on principles of programming languages, 1983.

52. Saunders D. Databases: Models, Modelling and Languages, QMW, Computer Science Department, 1995.

53. Scott D. A Type-theoretical alternative to CUCH, OWNY, ISWIN. Oxford University, 1969.

54. Scott D., de Bakker J.W. A theory of programs // Unpublished notes. Vienna: IBM Seminar, 1969.

55. Shapiro E.Y. A Subset of Concurrent Prolog and its Interpreter, ICOT Technical Report TR-003, Institute for New Generation Computing, Tokyo, 1983.

56. Simmons R.F. Computations from the English, PrenticeHall, Englewood Cliffs,1984.

57. Strachey C. Fundamental concepts in programming languages, Notes for the International Summer School in Computer Programming, Copenhagen, 1967.

58. Turner D.A. Miranda: A non-strict functional language with polymorphic types. Functional Programming and Computer Architecture. LNCS № 201, pp.1-16,1985.

59. Welsh J. et. al. Ambiguities and Insecuruties in PASCAL. Software: Practice and Experience, No 7,1977.