Исследование и реализация методов структурного синтеза программ тема автореферата и диссертации по математике, 01.01.10 ВАК РФ

ВВЕДЕНИЕ.

ГЛАВА I. ОБЗОР МЕТОДОВ СИНТЕЗА ПРОГРАММ

1.1. Дедуктивный подход к синтезу.

1.2. Индуктивный подход к синтезу

1.3. Трансформационный подход к синтезу.

1.'4. Автоматический синтез в пакетах црикладных программ.

ГЛАВА II. МЕТОД СТРУКТУРНОГО СИНТЕЗА ПРОГРАММ.

2.1. Язык условий задач.

2.2. Вычислимость объектов.

2.3. Форма аксиом

2.4. Правила вывода

2.5. Язык программ.

2.6. Синтез программ линейной структуры.

2.6.1. Построение доказательства теоремы

2.6.2. Алгоритм построения доказательства

2.6.3. Оценка сложности

2.7. Синтез ветвящихся программ

2.7.1. Алгоритм построения доказательства

2.7.2. Оценка сложности.

2.8. Синтез црограмм с подпрограммами (первый способ)

2.8.1. Алгоритм построения доказательства

2.8.2. Оценка сложности.

2.9. Синтез программ с подпрограммами (второй способ)

2.9.1. Оценка сложности

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

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

Основной целью настоящей работы является исследование методов автоматического синтеза программ, непосредственно пригодных для реализации в универсальных системах программирования. Разработаны алгоритмы структурного синтеза линейных и ветвящихся программ, а также программ с подпрограммами по непроцедурным описаниям условий задач. Разработанные алгоритмы реализованы в синтезаторе программ. Синтезатор включен в состав инструментальной системы программирования с автоматическим синтезом ПРИЗ ЕС [ I ], разработанной в Институте кибернетики АН ЭССР.

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

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

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

В четвертой главе приводится описание синтезатора программ, являющегося реализацией метода структурного синтеза. Описывается используемый в синтезаторе язык представления условий задач, внутренний язык представления структур данных и манипулирования данными, структура и компоненты синтезатора. Приводится краткое описание инструментальной системы ПРИЗ ЕС и место синтезатора в ней.

В приложении приводятся протоколы некоторых примеров синтеза программ.

ЗАКЛЮЧЕНИЕ

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

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

2. Разработаны алгоритмы оптимизации синтезируемых программ, обеспечивающие получение в результате структурного синтеза программ, близких к оптимальным.

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

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

1. Кахро М.И., Калья А.П., Тыугу Э.Х. Инструментальная система программирования ЕС ЭВМ (ПРИЗ). - М.: Финансы и статистика, 1981. - 158 с.

2. Slagle, J. Experiments with a deductive question answering system. Communications of the ACM, 1965, vol. 8, No. 9, pp. 792-798.

3. Waldinger, R. J., Lee, R. С. T. PROW: A step toward automatic program writing. In: Proc. of the 1st International Joint Conference on Artificial Intelligence, Bedford, 1969, pp. 241-253.

4. Manna, Z., Waldinger, R. J. Towards automatic program synthesis. Communications of the ACM, 1971, vol. 14, Ho. 3, pp. 151-164.

5. Constable, R. L. Constructive mathematics and automatic program writers. In: Proc. IFIP 1971, North-Holland, 1972, pp. 733-738.

6. Tyugu, E. H. Towards practical synthesis of programs. In: Information Processing-80, Amsterdam: North-Holland Publ. Co., 1980, pp. 207-220.

7. Непейвода H.H. О построении правильных программ. В кн.: Вопросы кибернетики, 1978, вып. 46, М., АН СССР, с. 88-122.

8. Непейвода Н.Н. Соотношение между правилами естественного вывода и операторами алгоритмических языков высокого уровня. -ДАН СССР, т. 239, 1978, № 3, с. 526-529.

9. Робинзон Дк. Машинно-ориентированная логика, основанная на принципе резолюции. В кн.: Кибернетический сборник, Новая серия, М.: Мир, 1970, вып. 7, с. 194-218.

10. Kowalski, R. Logic for Problem Solving AI series 7,

11. The Computer Science Library, Elsevier North-Holland, Inc., 1979.

12. Clocksin, W. P., Mellish, C.S'. Programming in Prolog. -Springer-Verlag, 1981*

13. Барздинь Я.М. Об индуктивных цравилах вывода для синтеза программ. В кн.: Синтез, тестирование, верификация и отладка программ. Тезисы докл. всесоюзн. научн. конференции, Рига, 1981, с. 25-26.

14. Hardy, S. Synthesis of LISP functions from examples. -In: Proc. 4th IJCAI, Tbilisi, 1975, pp. 240-245.

15. Zloof, M. M. Query by example. In: Proc. AFIPS National Computer Conference, May, 1975.

16. Biermann, A. W., Kirshnaswany, R. Constructing programs from example computations. IEEE Transactions on Software Engineering, 1976, vol. 2, pp. 141-153.

17. Burstall, R.M., Darlington, J. A system which automatically improves programs. In: Acta Informatica, 1976, vol. 6, pp. 41-60.

18. Burstall, R.M., Darlington, J. A Transformation system for developing Recursive Programs. In: Journal of the ACM, 1977, vol. 24, pp. 44-67.

19. Barstow, D. R., Knowledge-Based Program Construction. -Programming.Language Series 6, North-Holland, Inc., New York, 1979.

20. Касьянов B.H., Поттосин И.В. Системы конкретизации: подход и основные понятия. Препринт ВЦ СОАН СССР № 349, Новосибирск, 1982, - 22 с.

21. Загадский Б.А., Савочкина О.А., Темноева Т.А., Ярославцева JI.H. Организация вычислительного процесса в системе ФИХАР. ■ Препринт П-80, Диштровград: НШАР, 1974.

22. Бабаев И.О., Новиков Ф.А., Пеярушина Т.И. Язык Декарт -входной язык системы СПОРА. Прикладная информатика, 1981, № I, с. 27-76.

23. Корухова Л.С., Любимский Э.З. Система планирования действий, основанная на некоторых естественных цринципах,- ПЛАР. -Препринт ИПМ АН СССР, № 53, М., 1978.

24. Лавров С.С., Залогова Л.А., Петрушина Т.И. Принципы планирования решения задач в системе автоматического синтеза программ. Программирование, 1982, № 3, с. 35-43.

25. Бухштаб Ю.А., Горлин А.И., Камынин С.С., Корягин Д.А., Любимский Э.З. Интеллектуальный пакет, использующий при планировании вычислений знания о предметной области и функциональных модулях. Изв. АН СССР, Техническая кибернетика, 1981, № 5, с. 113-124.

26. Тыугу Э.Х., Харф М.Я. Алгоритмы структурного синтеза программ. Программирование, 1980, № 4, с. 3-13.

27. Минц Г.Е., Тыугу Э.Х. Обоснование структурного синтеза црограмм. В кн.: Автоматический синтез црограмм, Таллин, 1983, с. 5-40.

28. Минц Г.Е., Тыугу Э.Х. Полнота правил структурного синтеза. -ДАН СССР, т. 263, 1982, № 2, с. 291-294.

29. Плакс Т.П. Синтез параллельных црограмм на вычислительных моделях. Программирование, 1977, № 4, с. 55-63.

30. Малышкин В.Э. Основные принципы и этапы синтеза параллельных программ на вычислительных моделях с массивами. В кн.: Автоматический синтез црограмм, Таллин, 1983, с. 89-109.

31. Райков Л.Л. Построение оптимальных схем счета из модулей с именованными входами. УСиМ, 1982, № б, с. 115-119.

32. Вальковский В.А. 0 синтезе оптимальных программ на базе вычислительных моделей. Программирование, 1980, № б,с. 27г36.

33. Диковский А.Я. Оценки эффективности алгоритмов, связанных с вычислительными моделями. В кн.: Ш конф. "Применение методов математической логики" : Тезисы докл., Таллин, 1983, с. 42-51.

34. Минц Г.Е., Пеньям Я.Э., Тыугу Э.Х., Харф М.Я. Структурный синтез рекурсивных црограмм. В кн.: Автоматический синтез црограмм, Таллин, 1983, с. 58-70.

35. Харф М.Я. Оптимизация автоматически синтезируемых программ. -В кн.: Оптимизация и цреобразования программ, Новосибирск, 1983, ч. 2, с. 81-89.

36. Ершов А.П. Введение в теоретическое программирование. -М.: Наука, 1977. 288 с.

37. Кахро М.И., Мяннисалу М.А., Саан Ю.П., Тыугу Э.Х. Система программирования ПРИЗ. Программирование, 1976, № I,с. 38-46.

38. Казфо М.И., Тыугу Э.Х., Харф М.Я. Общие сведения о системе программирования ПРИЗ ЕС. В кн.: Технология црограммиро-вания: Тезисы докл. I Всесоюзн. конф. Секция И. Киев, 1979, с. 36-37.

39. Саан Ю.П., Унт М.И., Харф М.Я. Языковые средства пользователя в системе программирования ПРИЗ ЕС. В кн.: Технология программирования: Тезисы докл. I Всесоюзн. конф. Секция Н. Киев, 1979, с. 48-49.

40. Кабер M., Калья А., Кахро М., Лукаш Н., Лыугас Р., Мянни-салу М., Тыугу Э., Унт М., Харф М. Система программирования "ПРИЗ ЕС". Алгоритмы и программы (Информ. бюлл. ГФАП), М., ВНТИЦ, 1978, № 6(26), П003209, с. 23.

41. Тыугу Э.Х. Вычислительные фреймы и структурный синтез программ. Изв. АН СССР, Техническая кибернетика, 1982, № 6, с. 176-182.

42. Харф М.Я. Реализация синтезатора программ в системе прог-^чраммирования ПРИЗ. В кн.: Автоматический синтез программ,1. Таллин, 1983, с. II0-I4I.

43. Ломп A.A., Харф М.Я., Шмундак А.Л. Система МИС. В кн.: Автоматизация производства пакетов црикладных программ: Тезисы докл. Всесоюзн. семинара, Таллин, 1980, с. 187-188.

44. Пеньям Я.Э. Синтез семантического процессора по атрибутной грамматике. Программирования, 1983, № I, с. 50-60.