Главные вехи в истории метавычислений

Занятно, что история метавычислений неплохо ложится на десятилетия.
 Или, быть может, я подгоняю задним числом?

1960-е годы

Первые попытки сделать преобразователи программ, отличные от оптимизирующих компиляторов. Еще в те времена появился термин «partial evaluation». Тогдашние подходы к проблеме теперь представляют лишь исторический интерес. Для «широкой публики» может быть интересно, что уже тогда было понято: программы надоспециализировать (определение см. ниже). Это видно по статьям, авторы которых пытались даже делать экспериментальные системы. Нетрудно догадаться, что при слабости компьютеров и программистских инструментов того времени все это осталось в области теории.

1970-е годы

Зарождение методов и понимания фундаментальной важности задачи глубокого преобразования программ - в частности специализации. Независимо друг от друга к этим идеям пришли Валентин Турчин, Андрей Ершов, Йошихико Футамура (Yoshihiko Futamura).

Футамура первым понял, как с помощью самоприменения специализатораможно преобразовать интерпретатор в компилятор. Дата публикации его статьи (1971 год) теперь считается днем рождения этого научного направления, которое в этом году может отметить 30-летний юбилей. Однако Футамура не смог тогда предложить работоспособного метода специализации. Статья содержит набросок, который так и не стал алгоритмом.

Специализация программ - это порождение по программе f(x,y) при известном x программы f_x, такой, что f_x(y) = f(x,y). Специализатор Spec - это программа, выдающая по f и x программу f_x = Spec(f,x).

Турчин в 1972-77 годах разработал основы метода суперкомпиляции, опираясь на понимание необходимости «совершения крупномасштабного метасистемного перехода (МСП) над алгоритмами, программами», после разработки концепции МСП, изложенной в книге «Феномен науки» (написана в 1970 году). Цель этого МСП он метафорически описывал так: «Нужно сделать программы таким же естественным объектом обработки, как числа на Фортране». Турчин показал, как суперкомпиляция может решать 1) обратную задачу (дана программа и ее результат, найти аргумент), 2) автоматизировать построение компиляторов из интерпретаторов. Он заметил, что двойное самоприменение (то есть МСП) суперкомпилятора (как специализатора) дает компилятор компиляторов (Футамура и Ершов остановились на однократном самоприменении).

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

Генерирующее расширение программы f(x,y) - это программа f^ge(x), которая по данному х порождает программу f_x, такую, что f_x(y) = f(x,y), то есть f(x,y) = f^ge(x)(y).

Пример: компилятор - это генерирующее расширение интерпретатора. Ершов разрабатывал метод под названием смешанные вычисления с целью автоматической генерации генерирующих расширений: Gen(f) = f^ge. Связь со специализацией: Gen(f) = Spec(Spec, f); здесь происходит однократное самоприменение специализатора.

1980-е годы

Появление экспериментальных суперкомпиляторов и специализаторов. Возникновение мирового научного сообщества Partial Evaluation and Semantic-based Program Manipulation (PEPM), которое включало в себя и суперкомпиляцию.

Валентин Турчин начал свою работу в США с написания монографии по суперкомпиляции, изданной как Technical Report of City University of New York (№20, 1980). В ней он систематизировал идеи 70-х годов и заложил основы дальнейших работ, которые «расхлебываются» до сих пор. В начале десятилетия он со своей группой провел эксперименты с первой версией суперкомпилятора, а в конце они уже располагали весьма развитым суперкомпилятором Рефала. В 1989-90-х годах произошло «воссоединение» Турчина с российской командой, которое было отмечено летом 1990 года двухнедельной школой-семинаром в Обнинске.

Нил Джоунс (Neil Jones) и его группа в Копенгагенском университете, «заразившись» от Андрея Ершова задачей специализации программ и ознакомившись с методами Турчина, изобрели новый метод, названный ими старым термином частичные вычисления (partial evaluation). С одной стороны, его можно считать частным, упрощенным случаем суперкомпиляции, с другой - он содержит дополнительные оригинальные идеи, которые позволили в 1985 году группе Джоунса впервые вычислить на компьютере формулы Футамуры-Турчина порождения компилятора компиляторов путем двукратного самоприменения специализатора. Интересно, что авторы специализатора не смогли разобраться в первом компиляторе компиляторов, порожденном машиной. (Машина оказалась «умнее»…) После шлифовки метода Сергеем Романенко и текст, и идея автоматически порожденного компилятора компиляторов стали понятны людям (теперь эту идею можно изложить на одной странице). Интересно, были ли еще случаи в истории программирования, когда машина «порождала» фундаментальные идеи?

1990-е годы

Проработка деталей теории суперкомпиляции и движение к практике.

К началу 90-х назрела необходимость в систематизации и «наведении порядка» в основаниях суперкомпиляции. Благодаря работам Сергея Абрамова, Роберта Глюка (Robert Glьck) и Андрея Климова суперкомпиляция была структурирована так, чтобы можно было использовать ядро методов для решения более простых задач и постепенно добавлять приемы для более сложных задач. Это позволило начать разработку суперкомпиляторов для сложных практических языков типа Java.

Одновременно, Турчин и Андрей Немытых продолжали развивать «продвинутые» (advanced) методы суперкомпиляции в процессе реализации нового суперкомпилятора для Рефала-5, который удалось использовать в некоторых практических задачах.

С 2000 года на мехмате МГУ Сергей Абрамов читает курс по теории метавычислений и суперкомпиляции.

2000-е годы (прогноз)

«Матерение» теории и методов. Использование суперкомпиляторов на практике. В частности, будут завершены ведущиеся с конца 90-х годов работы по метавычислениям языка Java (и суперкомпиляция, и частичные вычисления) и начнется их практическое применение.

Компьютерная и информационная революция 90-х годов создала реальную потребность в глубоких методах оптимизации программ и подготовила условия и технические средства для использования их на практике. Суперкомпиляция окажет революционизирующее влияние на методы программирования, дав инструменты для дальнейшего развития «компонентного программирования», декларативного программирования, разработки разнообразных специализированных языков и т. п.