Лаборатория языковых инструментов

Ведущий специалист: Илья Ключников, Институт прикладной математики им. М.В. Келдыша РАН, Москва, Россия.

Программа школы:

• Общее введение в символьные вычисления и метавычисления.
• Интерпретация. Дерево процессов. Прогонка (символьное исполнение программы).
• Использование дерева процессов.
  • Окрестностный анализ и окрестностное тестирование.
  • Инверсные вычисления. УРА (универсальный решающий алгоритм).
  • Связь с логическим и реляционным программированием.
• Методы суперкомпиляции.
  • Свертка дерева процессов.
  • Генерация остаточной программы.
  • Дефорестация (как частный случай суперкомпиляции).
  • Критерии завершаемости.
  • Алгоритмы обобщения.
  • Теорема о линейном ускорении.
  • Обзор методов доказательства корректности преобразований программ.
• Расширения методов суперкомпиляции.
  • Многорезультатная суперкомпиляция.
  • Многоуровневая суперкомпиляция.
• Обзор других методов метавычислений.
  • Частичные вычисления.
  • Метавычисления в логическом программировании (частичная дедукция).
  • Инструменты оптимизации и анализа программ, основанные на методах метавычислений.

Литература:

• Блог «Метавычисления и специализация программ».
• Видеокурс Сергея Абрамова «Основы метавычислений».
• С. М. Абрамов. Методы метавычислений и их применениеАбрамов. Методы метавычислений и их применение.
• С. М. Абрамов. Метавычисления и их применение. СуперкомпиляцияАбрамов. Метавычисления и их применение. Суперкомпиляция.
• Илья Ключников. Суперкомпиляция: идеи и методы. Практика функционального программирования, выпуск 7.
• Ilya Klyuchnikov and Sergei Romanenko. SPSC: a Simple Supercompiler in Scala (версия на русском).
• N. D. Jones, C. K. Gomard, and P. Sestoft, Partial Evaluation and Automatic Program Generation.
• Daniel P. Friedman, William E. Byrd and Oleg Kiselyov. The Reasoned Schemer — книга о реляционном программировании.

Требования к слушателям:

• Знание основ языка Haskell: algebraic data types, pattern matching, lazy evaluation, higher-order functions. Для ознакомления рекомендуется прочесть первые шесть глав книги Learn You a Haskell for Great Good! (переведена на русский).

Будет полезным:

• Знание основ языка Racket (достаточно глав 1-41/2 книги Realm of Racket).
• Представление о том, как пишутся интерпретаторы (Daniel P. Friedman and Mitchell Wand. Essentials of Programming Languages).
• Владение основами языка Scala.