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

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

2 Литература и ссылки ftp://ftp.botik.ru/rented/xsg/www/tsg_book Абрамов С.М. ``Метавычисления и их применение''//M., Наука-Физматлит, 1995, с. 127 Позлевич Л.В., Федосова М.А. ``Метавычисления и их применение. Суперкомпиляция''//Выпускная работа на соискание степени бакалавра, Филиал Российского университета дружбы народов, Переславль--Залесский, с. 68

3 Литература и ссылки Абрамов С.М. Метавычисления и их применение//Диссертация на соискание степени доктора физико-математических наук, ИПС РАН, декабрь с. 287 Sergei Abramov, Robert Glück, Semantics Modifiers: An Approach To Non-standard Semantics of Programming Languages'//FLOPS98 (ftp://ftp.botik.ru/pub/local/Sergei.Abramov/FLOPS98.zip)ftp://ftp.botik.ru/pub/local/Sergei.Abramov/FLOPS98.zip

4 Контрольные мероприятия Написание тестов Задачи Рубежный контроль (1) Зачет (дифференцированный) Рубежный контроль (2) Экзамен Aссистент(ы) Работа в botik.edu Посещаемость: старосты

5 Глава 1. Введение

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

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

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

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

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

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

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

13 Простейшие примеры мета системных переходов Программа 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

14 Простейшие примеры мета системных переходов Даже простейшие метапрограммы позволяют достичь серьезных результатов Назовем (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 будет на следующем слайде

15 результат (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 для специализаторов.

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

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

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

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

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

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

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

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

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

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