Исследовательская группа
Лаборатория языковых инструментов
Зимняя школа по метавычислениям
3 февраля — 7 февраля 2014 г.
Ведущий специалист: Илья Ключников, Институт прикладной математики им. М.В. Келдыша РАН, Москва, Россия.
Программа школы:
- Общее введение в символьные вычисления и метавычисления.
- Интерпретация. Дерево процессов. Прогонка (символьное исполнение программы).
- Использование дерева процессов.
- Окрестностный анализ и окрестностное тестирование.
- Инверсные вычисления. УРА (универсальный решающий алгоритм).
- Связь с логическим и реляционным программированием.
- Методы суперкомпиляции.
- Свертка дерева процессов.
- Генерация остаточной программы.
- Дефорестация (как частный случай суперкомпиляции).
- Критерии завершаемости.
- Алгоритмы обобщения.
- Теорема о линейном ускорении.
- Обзор методов доказательства корректности преобразований программ.
- Расширения методов суперкомпиляции.
- Многорезультатная суперкомпиляция.
- Многоуровневая суперкомпиляция.
- Обзор других методов метавычислений.
- Частичные вычисления.
- Метавычисления в логическом программировании (частичная дедукция).
- Инструменты оптимизации и анализа программ, основанные на методах метавычислений.
Литература:
- Блог «Метавычисления и специализация программ».
- Видеокурс Сергея Абрамова «Основы метавычислений».
- С. М. Абрамов. Методы метавычислений и их применениеАбрамов. Методы метавычислений и их применение.
- С. М. Абрамов. Метавычисления и их применение. СуперкомпиляцияАбрамов. Метавычисления и их применение. Суперкомпиляция.
- Илья Ключников. Суперкомпиляция: идеи и методы. Практика функционального программирования, выпуск 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.