|
|
Опубликовано в еженедельном журнале Компьютерра 29.06.2001 г. в статье Андрея Климова.
Занятно, что история метавычислений неплохо ложится на десятилетия. Или, быть может, я подгоняю задним числом?
1960-е годы
Первые попытки сделать преобразователи программ, отличные от оптимизирующих компиляторов. Еще в те времена появился термин «partial evaluation». Тогдашние подходы к проблеме теперь представляют лишь исторический интерес. Для «широкой публики» может быть интересно, что уже тогда было понято: программы надо специализировать (определение см. ниже). Это видно по статьям, авторы которых пытались даже делать экспериментальные системы. Нетрудно догадаться, что при слабости компьютеров и программистских инструментов того времени все это осталось в области теории.
1970-е годы
Зарождение методов и понимания фундаментальной важности задачи глубокого преобразования программ — в частности специализации. Независимо друг от друга к этим идеям пришли Валентин Турчин, Андрей Ершов, Йошихико Футамура (Yoshihiko Futamura).
Футамура первым понял, как с помощью самоприменения специализатора можно преобразовать интерпретатор в компилятор. Дата публикации его статьи (1971 год) теперь считается днем рождения этого научного направления, которое в этом году может отметить 30-летний юбилей. Однако Футамура не смог тогда предложить работоспособного метода специализации. Статья содержит набросок, который так и не стал алгоритмом.
Специализация программ — это порождение по программе f(x,y) при известном x программы fx, такой, что fx(y) = f (x,y). Специализатор Spec — это программа, выдающая по f и x программу fx = Spec(f,x).
Турчин в 1972–1977 годах разработал основы метода суперкомпиляции, опираясь на понимание необходимости «совершения крупномасштабного метасистемного перехода (МСП) над алгоритмами, программами», после разработки концепции МСП, изложенной в книге «Феномен науки» (написана в 1970 году). Цель этого МСП он метафорически описывал так: «Нужно сделать программы таким же естественным объектом обработки, как числа на Фортране». Турчин показал, как суперкомпиляция может решать 1) обратную задачу (дана программа и ее результат, найти аргумент), 2) автоматизировать построение компиляторов из интерпретаторов. Он заметил, что двойное самоприменение (то есть МСП) суперкомпилятора (как специализатора) дает компилятор компиляторов (Футамура и Ершов остановились на однократном самоприменении).
Андрей Ершов обнаружил (в процессе работы его коллектива над многоязыковым компилятором «Альфа»), что большое число разных с виду задач сводится к построению так называемого генерирующего расширения программ.
Генерирующее расширение программы f (x,y)
— это программа f ge(x), которая по данному х
порождает программу fx, такую, что fx(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–1990-х годах произошло «воссоединение» Турчина с российской командой, которое было отмечено летом 1990 года двухнедельной школой-семинаром в Обнинске.
Нил Джоунс (Neil Jones) и его группа в Копенгагенском университете, «заразившись» от Андрея Ершова задачей специализации программ и ознакомившись с методами Турчина, изобрели новый метод, названный ими старым термином частичные вычисления (partial evaluation). С одной стороны, его можно считать частным, упрощенным случаем суперкомпиляции, с другой — он содержит дополнительные оригинальные идеи, которые позволили в 1985 году группе Джоунса впервые вычислить на компьютере формулы Футамуры-Турчина порождения компилятора компиляторов путем двукратного самоприменения специализатора. Интересно, что авторы специализатора не смогли разобраться в первом компиляторе компиляторов, порожденном машиной (машина оказалась «умнее»…). После шлифовки метода Сергеем Романенко и текст, и идея автоматически порожденного компилятора компиляторов стали понятны людям (теперь эту идею можно изложить на одной странице). Интересно, были ли еще случаи в истории программирования, когда машина «порождала» фундаментальные идеи?
1990-е годы
Проработка деталей теории суперкомпиляции и движение к практике.
К началу 90-х назрела необходимость в систематизации и «наведении порядка» в основаниях суперкомпиляции. Благодаря работам Сергея Абрамова, Роберта Глюка и Андрея Климова суперкомпиляция была структурирована так, чтобы можно было использовать ядро методов для решения более простых задач и постепенно добавлять приемы для более сложных задач. Это позволило начать разработку суперкомпиляторов для сложных практических языков типа Java.
Одновременно, Турчин и Андрей Немытых продолжали развивать «продвинутые» (advanced) методы суперкомпиляции в процессе реализации нового суперкомпилятора для Рефала-5, который удалось использовать в некоторых практических задачах.
С 2000 года на мехмате МГУ Сергей Абрамов читает курс по теории метавычислений и суперкомпиляции.
2000-е годы (прогноз)
«Матерение» теории и методов. Использование суперкомпиляторов на практике. В частности, будут завершены ведущиеся с конца 90-х годов работы по метавычислениям языка Java (и суперкомпиляция, и частичные вычисления) и начнется их практическое применение.
Компьютерная и информационная революция 90-х годов создала реальную потребность в глубоких методах оптимизации программ и подготовила условия и технические средства для использования их на практике. Суперкомпиляция окажет революционизирующее влияние на методы программирования, дав инструменты для дальнейшего развития «компонентного программирования», декларативного программирования, разработки разнообразных специализированных языков и т.п.
Метавычисления — методы глобального анализа и оптимизации программ… позволяют решать задачи алгоритмического преобразования программ и автоматизации программирования; создания суперкомпиляторов для различных языков программирования, разработки эффективных реализаций нестандартных семантик, искусственного интеллекта.
Метавычисления — одно из самых перспективных направлений компьютерных технологий, которое начало оказывать большое влияние на информационные технологии и сыграет одну из ведущих ролей в продолжающейся компьютерной революции в XXI веке.
