Слайды к лекциям

Введение в Рефал и суперкомпиляцию

Политехнический музей, г. Москва, январь-февраль 2000 г.

Андрей Климов
Институт прикладной математики им. М.В.Келдыша РАН, г. Москва
klimov@keldysh.ru
 

Лекция № 1.  25 января 2000 г. (вторник), 12:00

• Введение
  • Метавычисления
  • Метаязык
  • Методы метавычислений
  • История 
• Рефал и метавычисления — основные понятия и примеры
  • Функциональные языки программирования
  • Рефал (базисный) — основные понятия
  • Пример Рефал-программы: факториал
  • Интерпретатор языка арифметических выражений
  • Выполнение интерпретатора арифметических выражений
  • "Неудачное" частичное вычисление
  • Частичное вычисление интерпретатора арифметических выражений 

Лекция № 2.  11 февраля 2000 г. (пятница), 13:00

• Рефал
  • Характеристика языка Рефал
  • Рефал (базисный) — основные понятия
• Первый пример на суперкомпиляцию:
  доказательство коммутативности сложения с 1
  (вариант, использованный на лекции):
  • Постановка задачи на суперкомпиляцию
  • Определение предиката
  • Суперкомпиляция предиката*
  • Построение остаточной программы*
  • Выдача суперкомпилятора
• Доказательство коммутативности сложения с 1   
  (усложненный вариант, не использованный на лекции; разница в функции Ad):
  • Постановка задачи на суперкомпиляцию
  • Определение предиката
  • Суперкомпиляция предиката*
  • Построение остаточной программы*
  • Выдача суперкомпилятора
• Второй пример на суперкомпиляцию:
  слияние двух проходов в один
  • Программа замены A на В, В на С
  • Суперкомпиляция: построение графа конфигураций*
  • Остаточный граф конфигураций, "наивная" остаточная программа*
  • Оптимальная остаточная программа*
  • Выдача суперкомпилятора

Лекция № 3.  17 февраля 2000 г. (четверг), 14:00

• Построение компилятора компиляторов
  • Формальная компиляция в Рефал по интерпретатору
  • Реальная компиляция в Рефал по интерпретатору
  • Построение компилятора в Рефал по интерпретатору
  • Компилятор компиляторов по интерпретаторам
  • Генерация эффективного компилятора компиляторов
• Построение компилятора компиляторов MST-схемами
  • Подробно
  • Сводка формул: "Проекции Футамуры-Турчина"
• Построение компилятора компиляторов специализатором
  • Специализация
  • Специализатор
  • Futamura-Turchin's Projections

Лекция № 4.  14 марта 2000 г. (вторник), 14:00

• Суперкомпиляция интерпретатора конечного автомата
  • Конечный автомат
  • Интерпретатор конечного автомата на Рефале
  • Суперкомпиляция конечного автомата* (при печати уменьшить)
  • Суперкомпиляция конечного автомата: упрощенный остаточный граф*
  • Остаточная программа на Рефале
• Простой интерпретируемый язык
  (Здесь все слайды "альбомные", "landscape". Синим цветом выделена разница с предыдущим слайдом.)
  • Пример описания языка на Рефале: интерпретатор арифметических выражений
  • Упрощенный интерпретатор: нет приоритетов операций
  • Результат суперкомпиляции
  • Однократное присваивание
  • Константы vs. данные
  • Константы vs. данные (с перекодировкой)
  • Условный оператор If-Then-Else
  • Оператор Prod (произведение): плохо суперкомпилируемый вариант
  • Оператор Prod (произведение): ручное кодирование Prod

* На слайдах, помеченных звездочкой, в графах конфигураций надо подрисовать дуги, идущие от нижних вершин наверх. Упражнение: Найдите эти вершины.