Метавычисления и их применение (слайды к циклу лекций) Абрамов С.М. Парменова Л.В. Университет города Переславля им. А. К. Айламазяна. - презентация

1 Метавычисления и их применение (слайды к циклу лекций) Абрамов С.М. Парменова Л.В. Университет города Переславля им. А. К. Айламазяна

2 Литература и ссылки µ µ ftp://ftp.botik.ru/rented/xsg/www/tsg_book ftp://ftp.botik.ru/rented/xsg/www/tsg_book [1] Абрамов С.М. «Метавычисления и их применение». M.: Наука-Физматлит, 1995, с (Базовый учебник.) [2] С.М.Абрамов и Л.В.Пармёнова "Метавычисления и их применение. Суперкомпиляция" Готовится к печати. (Дополнительный учебник.)

3 Литература и ссылки µ [3] Абрамов С.М. Метавычисления и их применение // Диссертация на соискание степени доктора физико-математических наук, ИПС РАН, декабрь с µ ftp://ftp.botik.ru/pub/local/Sergei.Abramo v/book.appndx/dissertation/ ftp://ftp.botik.ru/pub/local/Sergei.Abramo v/book.appndx/dissertation/

4 Литература и ссылки µ [4] SERGEI ABRAMOV, ROBERT GLUECK, «SEMANTICS MODIFIERS: AN APPROACH TO NON-STANDARD SEMANTICS OF PROGRAMMING LANGUAGES»//FLOPS98 ftp://ftp.botik.ru/pub/local/Sergei.Abram ov/FLOPS98.zip ftp://ftp.botik.ru/pub/local/Sergei.Abram ov/FLOPS98.zip

5 Литература и ссылки µ * Abstract: An approach for systematically modifying the semantics of programming languages by semantics modifiers is described. It allows the design of general and reusable «semantics components» without the penalty of being too inefficient. Inverse computation and neighborhood analysis are used to demonstrate the computational feasibility of the approach. Equivalence transformers are shown to fulfill the requirements of semantics modifiers. Finally, projections are given that allow the efficient implementation of non-standard interpreters and non- standard compilers using program specialization.

6 Литература и ссылки µ [5] SERGEI ABRAMOV, ROBERT GLUECK, FROM STANDARD TO NON-STANDARD SEMANTICS BY SEMANTICS MODIFIERS // International Journal of Foundations of Computer Science, Vol. 12. No. 2 (2001) pp. 171–211 World Scientific Publishing Company, 2001 (* ftp://ftp.botik.ru/pub/local/Sergei.Abramov/IJ FCS / *) ftp://ftp.botik.ru/pub/local/Sergei.Abramov/IJ FCS /

7 ВведениеВведение

8 В. Ф. Турчин основатель метавычислений

9 В. Ф. Турчин. Краткая биографическая справка µ физик-ядерщик µ философ: «Феномен науки» общая теория эволюции (обсуждается далее) µ классик в области теоретических основ информатики, основатель метавычислений, создатель языка рефал

10 В. Ф. Турчин. Краткая биографическая справка µ наставник молодых: Колмогоровский интернат, рефал- мальчики, рефал- семинары µ популяризатор науки (журнал «Знание сила», сборники «Физики шутят» и «Физики продолжают шутить»)

11 В. Ф. Турчин. Краткая биографическая справка µ человек высокой совести, гражданин, µ диссидент, правозащитник, лидер хельсинской группы в Москве µ Книга В.Ф.Турчина «Инерция страха» µ выдворение из СССР (1977) µ персональная «железная занавесь»

12 Теория метасистемных переходов (MST) µ «Общая теория эволюции» В.Ф.Турчина: квант эволюции метасистемный переход; эволюция цепочка метасистемных переходов общие черты метасистем и метасистемных переходов для метасистем объектами (анализа, преобразования, управления...) являются системы часто метасистемы работают с множествами (объектов) условия для метасистемного перехода предпосылки неограниченной эволюции системы с неограниченными возможностями развиваться системы, обреченные жить без развития

13 Метавычисления: применение MST к программированию µ Основная идея: чтобы обеспечить эволюцию в мире программ, используем в программировании теорию эволюции В. Ф. Турчина; результат этого: метавычисления. µ Метапрограммы конструктивные метасистемы над программами

14 Метавычисления: применение MST к программированию µ Общие черты метапрограмм заимствованы из MST повторяют общие черты метасистем: метапрограммы работают над программами: анализ, преобразование, (нестандартные) вычисления и т.п. метапрограммы работают с множествами (с их представлениями) можно реализовать условие «неограниченной цепочки метавычислений»: возможность совершения метасистемного перехода над метапрограммой применение метапрограммы к метапрограмме

15 Простейшие примеры метасистемных переходов µ Программа p из языка L (p P L ) на данных d D дает результат r D: p d * L r µ Что такое (L/R)-интерпретатор int языка L, написанный на языке R? Мнение? int P R : p P L d D int(p, d) * R r p d * L r µ Что такое (L1L2/R)-компилятор comp с языка L1 на язык L2, написанный на языке R? Мнение? comp P R : p1 P L1 comp p1 * R p2 P L2 d D p1 d * L1 r p2 d * L2 r

16 Простейшие примеры метасистемных переходов µ Даже простейшие метапрограммы позволяют достичь серьезных результатов µ Назовем (RR/R)-специализатором s P R : p P R d 1 D s(p, d 1 ) * R p 1 P R : d 2 D p (d 1, d 2 ) * R r p 1 d 2 * R r µ Коротко (основное свойство специализатора): p P R d 1, d 2 D p (d 1, d 2 ) = s(p, d 1 ) d 2 µ Тривиальный и нетривиальный специализатор: как отличить? Touch stone будет на следующем слайде

17 результат (LR)- компиляции p L (LR/R)- компилятор генератор компиляторов Простейшие примеры метасистемных переходов µ p (d 1, d 2 ) = s(p, d 1 ) d 2 µ p L d * L r R *int(p L, d) = s(int, p L ) d = s(s, int) p L d = s(s, s) int p L d µ Проекции Футамуры-Турчина µ Дистанция в ~15 лет между «это теоретически возможно (1971)» и «это сделано на практике (1985)». Touch stone для специализаторов.

18 История проекций Футамуры-Турчина µ Футамура открыл первые две проекции Y. Futamura: Partial Evaluation of Computation Process An approach to a Compiler-Compiler, 1971 µ Турчин независимо от Футамуры открыл ( ) все три проекции, опубликовать не мог Первое сообщение об этом: в работе академика Ершова µ Первая «неразборчивая» реализация: Neil D. Jones, DIKU, 1985 µ Более совершенная реализация: С.А.Романенко, 1987 µ Компьютерра «Турчин и другие...»

19 Другие примеры метасистемных переходов µ В нашем курсе мы рассмотрим более сложные метасистемы (многоуровневые метасистемы), более сложные примеры метасистемных переходов, более сложные проекции (например, для нестандартных семантик).

20 МетавычисленияМетавычисления µ Метавычисления: раздел программирования, посвященный разработке методов анализа и преобразования программ за счет реализации конструктивных метасистем (метапрограмм) над программами. µ Программы в метавычислениях рассматриваются как объект анализа и/или преобразования.

21 Базовые идеи µ применение теории метасистем и метасистемных переходов к программам µ процесс-ориентированный подход к построению методов анализа и преобразования программ разработка метапрограмм M, которые «наблюдают» за процессами вычисления исходной программы p (на одиночных данных d, на классах данных C ) и управляют этими процессами. µ фиксация языка реализации R на нем должны быть написаны все программы p, к которым будут применяться метапрограммы µ если некоторая метапрограмма M написана на R, то к ней применима она сама (самоприменимость) или другие метапрограммы (метасистемная лестница)

22 Цель исследований µ Реализация средств анализа программ и средств выполнения преобразований программ эквивалентных преобразований (например, оптимизаций) и построения новых программ, функции которых сложным образом определяются через функции исходных программ

23 МотивацияМотивация µ В.Ф.Турчин Феномен науки: µ «Метод современной науки по своему существу есть ничто иное, как построение формальных лингвистических моделей изучаемых явлений»... µ «Очередной шаг развития лингвистического моделирования, то есть очередной метасистемный переход в эволюции науки использование компьютеров в процессе построения формальных лингвистических моделей»... µ «И это может быть сделано при помощи использования методов метавычислений» µ Сегодняшние результаты убеждают, что данная роль метавычислений действительно может быть осуществлена на практике при условии дальнейшего развития методов метавычислений и методов их применения.

24 МотивацияМотивация µ В области программирования речь идет о создании мощных средств автоматического анализа и преобразований программ и методов применения этих средств Автоматизация программирования Обеспечение надежности ПО

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

26 МотивацияМотивация µ Близкие технологии (частичные вычисления, дефорестация, расширенная дефорестация, обобщенные частичные вычисления и т.д.) упрощения суперкомпиляции и метавычислений Исследователи, ранее занимающиеся данными направлениями, проявляют все больший интерес к метавычислениям

27 Супер- компиляция scp Специализация программ Приложения суперкомпиляции, в том числе Базовые понятия и методы метавычислений int, SR, ptr Инверсное вычисление ura Окрестностный анализ nan Приложения метавычислений Иные методы Иные приложения [2] Л.В. Парменова «Метавычисления и их применения. Суперкомпиляция» [1] С.М.Абрамов «Метавычисления и их применения» Область возможных новых исследований Окрестностное тестирование Реализация нестандартных семантик Инверсное программиро- вание Методы метавычислений Структура курса