Статья: ORBIT: An Optimizing Compiler for Scheme

Мир традиционных Лиспов делится на два больших семейства: родственники Common Lisp и многочисленные реализации Scheme. Common Lisp был разработан соответствующим комитетом как компромисс между многочисленными промышленными Лиспами 70-х и 80-х. И, как типичный управляемый комитетом стандарт, ANSI Common Lisp страдает многословностью и противоречивостью, что выражается в тысяче с лишним страниц определения языка.

Стандарты базовой Схемы занимают каждый порядка сотни страниц, определяя простое и легкое в реализации и понимании ядро языка. Но есть проблема: стандарт не очень практичен, и не включает в себя скучные частные вопросы. Ну, вроде стандартной библиотеки для работы с регулярными выражениями…

Тем не менее, лаконичность и простота Схемы привела к тому, что в среде академиков и энтузиастов создание эффективных интерпретаторов и компиляторов Схемы стало чем-то вроде спорта: мелких реализаций разве что не сотни, крупных — десятки. В них обкатываются новые техники компиляции функциональных и динамических языков, проверяются подходы к проблемам отрасли и просто развлекаются скучающие программисты.

Первая экспериментальная реализация компилятора Scheme была описана Гаем Стилом (англ. Guy Steele еще в конце семидесятых (см. публикацию Rabbit: A Compiler for Scheme, 1978 год). Но первым практичным компилятором стал Orbit, ключевая работа по которому была опубликована только в 1986 году.

Orbit оказал огромное влияние на все последующие компиляторы функциональных языков, в том числе Haskell, SML/NJ и многие другие, поэтому знакомство показалось мне обязательным. Во время двухдневного полета в Мюнхен у меня нашлось (много!) времени на чтение той самой первой публикации (ORBIT: An Optimizing Compiler for Scheme, длиной в 16 страниц), и получившиеся заметки хотелось бы сохранить в блоге.

Статья неожиданно начинается с оценки производительности получившегося кода, который практически на всех интересных бенчмарках опережает другие Лиспы. Авторы указывают ключевые техники, использованные в компиляторе: использование стиля с передачей продолжений (англ. continuation-passing style, или CPS) в качестве основного внутреннего представления компилятора, преобразование присваиваний (англ. assignment conversion) для упрощения оптимизаций на CPS и техник, использованных во встроенном ассемблере.

После предварительных расшаркиваний (и даже бахвальства) статья переходит к описанию фаз компилятора.

Первая фаза: \(\alpha\)-преобразование (в терминах лямбда-исчисления), в котором имена переменных меняются так, чтобы не пересекаться друг с другом во внутреннем представлении, что упрощает оптимизирующие преобразования на последующих фазах.

Вторая фаза: стандартный переход к внутреннему представлению в стиле явной передачи продолжений (англ. CPS transformation).

Третья фаза: преобразование присваиваний, где простые императивные изменения переменных (в случае Схемы это вызовы set!) заменяются на вызовы функций, меняющих ячейки (англ. cells) со ссылками на данные. Как и предыдущие фазы это позволяюет упростить работу последующих оптимизирующих фаз с внутренним представлением.

Четвертая фаза — оптимизирующие преобразования получившегося внутреннего представления. В простых случаях это частичное вычисление (англ. partial evaluation), например, арифметических и булевых выражений или применение к константным аргументам простых \(\lambda\)-выражений. Некоторые известные на тот момент в компиляторах императивных языков оптимизации (то же продвижение констант) не проводятся, так как требуют более сложный в функциональных языках анализ потоков данных.

В пятой фазе создаются файлы-объявления (англ. declarations) для модулей, что-то вроде заголовков в C, содержащие описания известных типов и так далее. Формат объявлений в стандарте Схемы не описывается, то есть это уже особенность именно Орбиты.

Шестая и седьмая фазы оптимизируют представление замыканий: принимаются решения о размежении окружения замыканий на стеке, в куче или регистрах; и ищутся возможности для совмещения окружений разных замыканий.

Восьмая и девятая фазы отвечают за распределение регистров и порождение кода сначала в терминах абстрактной машины языка, потом отображаемого двоичного кода конкретных физических машин.

Досадно, но в статье подробно не описываются представления типов времени исполнения программ (англ. run-time type presentation), и не описаны механизмы сборки мусора (англ. garbage collection), в которых, судя по другим описаниям компилятора, тоже впервые были использованы многие стандартные теперь техники. Подозреваю, что первые версии компилятора опирались на существующий более ранний компилятор или интерпретатор Схемы (верней, диалекта Схемы под неудобным названием T).

И хотя в конце статьи приводится пример цикла работы компилятора, но, повторюсь, деталей все же не хватает, а первое по-настоящему системное изложение этого подхода к компиляции составит только Аппель в знаменитой книге Compiling with Continuations.

Влияние Orbit, тем не менее, трудно недооценить, поэтому со статьей действительно стоит ознакомиться: написана она легко, без избытка специфичной терминологии, и общее представление об устройстве компиляторов получить позволяет.

Подробную историю разработки компилятора в изложении одного из создателей и другие материалы по теме, кстати, легко можно найти на сайте знаменитого Пола Грэма. Есть и другой изложение той же истории.

Комментарии

Comments powered by Disqus