Книга: Compiling with Continuations

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

Один из таких выдающихся авторов - Эндрю Аппель, специалист по компиляторам в целом и компиляторам функциональных языков в частности. Его книги и ключевые научные публикации по качеству прозы - и красоте идей! - можно сравнить только с интересным романом. Книгу Modern Compiler Implementation in ML ("тигровую книгу", по обложке), например, я читал раза три и, вероятно, еще не раз к ней вернусь.

Но Аппель прославился не только популярным учебником. Другая его книга, Compiling with Continuations, популяризовала и сделала стандартом в мире компиляторов функциональных языков внутреннее представление в стиле передачи продолжений (англ. continuation passing style). Ее я читал и перечитывал в последние недели.

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

Но в Compiling with Continuations на примере оптимизирующего компилятора языка Standard ML (SML/NJ, если говорить точно) раскрываются возможности явной передачи продолжений как внутреннего представления компилятора, аналогичного, например, SSA в императивных компиляторах. И, как и SSA, такое представление открывает возможности для удобного решения задач оптимизации кода, распределения регистров и так далее.

Книга вообще не занимается скучным вопросами синтаксического разбора, а сразу переходит к внутренним задачам функционального компилятора. Аппель поэтапно понижает уровень внутренних представлений от близкого к полному языку miniML и до вплоть до низкоуровневой абстрактной машины.

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

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

И все эти радости изложены в фирменном авторском стиле, очень понятном и доступном. Как мне кажется, лучше Аппеля объяснить суть подхода трудно. Книга стала классикой и закрепила успех явной передачи продолжений как одного из конкурентов SSA в роли внутреннего представления функциональных компиляторов на пару десятилетий вперед, и дискуссия вокруг темы продолжается до сих пор.

С момента публикации книги (1992) утекло много воды; как функциональные языки, так и их компиляторы с тех пор сильно изменились, но суть компиляции с продолжениями никуда от нас не ушла.