Nanopass или как я писал компилятор этой осенью

Сразу прошу прощения за несколько надоевший всем стиль «lytdybr», но уж очень хочется поделиться крайне приятным опытом и рассказать о по-своему замечательном компиляторном курсе. И это ещё хорошо, что я пишу сейчас, когда эмоции подугасли, а не когда я только закончил вторую главу курса и от эйфории чувствовал себя как «хомячок, которого капля никотина разрывает на части»! Сразу предупреждаю, наверняка для кого-то эта заметка — «ребёнок познаёт мир», тех прошу сразу закрыть вкладку и не судить строго. Здесь и далее, всегда и всюду, во всех четырёх сферах прошу учитывать, что я не только не создаю компиляторы, но даже и не обучаю этому и не пишу методички! ;-)

Как всем известно, типичный компилятор — это консольная программа, читающая текстовый файл на некотором языке и выплёвывающая либо поток ругательств в stdout, либо бинарный файл на другом языке в какой-нибудь файл. Опять-таки, не секрет, что внутри типичный современный компилятор разделён на части: если грубо, то frontend (парсер), middleend и backend (кодогенератор), каждая из которых обрабатывает информацию и передаёт дальше. То есть, обычно компилятор — это некоторая последовательность из процедур (на жаргоне «проходов»), преобразующих программу.

Обычно первый проход — это парсер, на вход он получает текст, а выдаёт «дерево». И с этого момента обрабатываемая программа хранится и передаётся между проходами, как правило, в виде деревьев или списков. Nanopass — это подход к проектированию компилятора, в котором архитектура компилятора базируется на идее последовательности чётко очерченных отдельных «проходов». То есть, компилятор явно представляется как последовательное применение к обрабатываемой программе большого числа проходов с чётко, даже формально, описанными интерфейсами. Такая архитектура уменьшает кол-во ошибок, упрощая (само)обучение, поэтому она особенно хорошо подходит для преподавания.

Помимо общего подхода есть ещё и одноимённый framework на Scheme, упрощающий построение компиляторов на базе этого подхода — https://nanopass.org/. Этот framework хвалят, но конкретно я им ещё пока не пользовался и сказать ничего по этому поводу не могу.

Этой осенью я писал компилятор по курсу «Essentials of Compilation» университета Индианы, о чём далее.

Nanopass

Откуда я вообще узнал про подход Nanopass? Тут я обязан поблагодарить Петра Советова (true-grue) за его работу по популяризации компиляторостроения, курирование телеграм-канала CompilerDevelopment и создание подборки курсов по компиляторам — https://github.com/true-grue/Compiler-Development (просьба профессионалам добавлять туда интересное и подходящее).

Подход Nanopass берёт своё начало со статьи «An Incremental Approach to Compiler Construction», https://raw.githubusercontent.com/namin/inc/master/docs/paper.pdf, развитой в «A nanopass framework for commercial compiler development» https://dl.acm.org/doi/10.1145/2500365.2500618. Насколько я понимаю, для коммерческого применения этот подход слегка хуже обычного, т.к. компилятор из-за огромного кол-ва проходов получается несколько медленнее. А вот для обучения, подход Nanopass, как мне кажется, прекрасен. Не забывайте, что я не профессионал ни в компиляторах, ни в обучении CS!

Немного повторюсь, в рамках Nanopass компилятор — это некоторое последовательное применение процедур-проходов к тексту программы. Первая процедура — это парсер, последняя — кодогенератор, на псевдокоде что-то вроде:

compiler = emit . add_prelude_conclusion . 
           patch_instruction . assign_homes . select_instructions .
           explicate_control . remove_complex_operands .
           uniquify_variables . parse

Nanopass — это старый добрый Unix-way, то есть, каждый проход делает лишь одну вещь и делает её хорошо. Каждый проход — это функция из одного промежуточного языка в другой, причём эти языки мало того, что описаны, в рамках подхода желательно написать интерпретатор для каждого языка. Так, чтобы можно было «запустить» каждое из промежуточных представлений компилируемой программы и сравнить с эталоном. Это жесткосердный подход, но от компиляторов и требуется очень высокая надёжность: падающий с SEGFAULT компилятор — это позор, а неправильная кодогенерация — это потерянные человеко-годы в отладке. Хотя SPJ рассказывал байку о том, что он как-то выпустил версию GHC, которая стирала исходник компилируемой программы, если тот содержал ошибку. И за это SPJ даже не обматерили — «святые люди, эти хаскелисты» заключил он.

В общем, как обычно в софтостроении: «тише едешь — дальше будешь», «quality is free», «чем позже найдена ошибка, тем она разорительнее» и прочие скучные мудрости ушедших веков.

Возвращаясь к примеру, проход explicate_control переводит код с LISP-подобного языка в трёхадресный код:

explicate_control :: RestrictedLISP -> ThreeAddressCode

И проверяется с помощью двух интерпретаторов (один до, а второй — после прохода):

interp_ThreeAddressCode :: ThreeAddressCode -> ReturnCode
interp_RestrictedLISP :: RestrictedLISP -> ReturnCode

Естественно, если эти интерпретаторы кто-то другой уже написал, жизнь превращается просто в сказку.

Курс Essentials of Compilation

Хотя есть несколько разных курсов, построенных на этом подходе, я их не сравнивал, взяв курс со страницы true-grue, то есть https://github.com/IUCompilerCourse/Essentials-of-Compilation на языке Racket. У курса есть ещё официальная версия на Python'е и неофициальная версия на Ocaml. И хотя более-менее владею всеми тремя, я решил, возможно с наивной верой в людей, что курс на Racket будет содержать меньше косяков. Пётр Советов особенно подчёркивал, что в этом курсе парсер и кодогенератор (pretty-printer) уже написаны, поэтому с ними мороки и потери времени не будет (парсеры я писал, мне это скучно).

Основной автор курса, Prof. Jeremy G. Siek относительно недавно курс существенно переделал, и в нынешней редакции широко используется механизм структур Racket, который немного напоминает алгебраические типы данных. Кое-кто из моих знакомых, любителей Racket, от структур плюётся, но мне понравилось. Книга для старой версии курса доступна для скачивания в финальном виде — https://jeapostrophe.github.io/courses/2018/spring/406/notes/book.pdf, мне же пришлось скомпилировать тексты текущей редакции (ветка master).

К современной редакции курса идёт «обвязка» — https://github.com/IUCompilerCourse/public-student-support-code Она содержит код скриптов, запускающих тестирование, набор интерпретаторов и typechecker'ов для всех промежуточных языков, а также наброски структуры компилятора, чтобы начинать не совсем с чистого листа, чистый лист пугает.

Структура курса.

В рамках курса, опять-таки, архитектурно очень красиво с точки зрения «спиральной методологии» мы пишем скелет компилятора, на который позже навешиваем мясо. Мы расширяем компилятор как по количеству проходов, так и по языку обрабатываемых программ, который становится всё мощнее и сложнее от главы к главе.

Процесс обучения выглядит так:

1. Клонируем public-student-support-code куда-то на локальную машину.
   И, чтобы не гадить автору курса (ему же ещё домашку проверять), ни в коем случае
   не выкладываем свой код в публичный репозиторий.

Далее мы будем модифицировать файлы run-tests.rkt, compiler.rkt и файлы в каталоге tests.

Соответственно, в цикле по главам:

1. Читаем очередную главу из книги, может даже несколько раз.
2. Добавляем в каталог tests некоторое кол-во тестов для новых возможностей
   компилятора и языка.
3. Подправляем уже реализованные проходы и добавляем новые.
4. Пишем дополнительные тесты, убеждаемся, что всё, тем не менее, работает.
5. Следующая глава, goto пункт 1.

Это, в общем и целом стандартно. А вот что круто — это то, что поскольку все интерфейсы очень хорошо определены, для результата каждого прохода есть интерпретатор, уже написанный авторами курса. Ура, мы попали в сказку! И эта сказка добрая! То есть, после каждого прохода мы можем проверить операционную семантику программы и убедиться в том, что проход ничего не испортил — программы до какого-нибудь register_allocation и после него «эквивалентны», хотя и написаны на разных языках. Более того, прилагающаяся к курсу тестовая обвязка всё это делает — отлаживать легко и приятно (а не как всегда).

Но самое замечательное в этом курсе, то, что привело меня буквально в состояние эйфории — после каждой, даже «самой первой» главы, у нас в руках работающий компилятор. Причём не жульничество вроде компилятора с какого-то модельного языка на какой-то модельный язык. Нет, это компилятор пусть и с подмножества LISP в настоящий, абсолютно реальный, совершенно честный, без гвоздей, ассемблер x86-64. Причём код скриптами из public-student-support-code автоматически скармливается системному ассемблеру и ld, выдавая на выходе настоящий бинарник (в моём случае Mach-O). Представляете — настоящий бинарник, как у взрослых!

Поскольку я, как и многие «зрелые промышленные практики с ипотекой и детьми, пишущие на С++ уже лет 20» на самом деле являюсь «вайтишником», я на «кухню компиляторов хожу только кушать», и компиляция для меня всегда имела налёт магии. Да, парсеры я, разумеется, писал, даже недавно экспериментально выяснил, что парсер для LISP на Parsec у меня занимает 2 (два) часа (см известную книгу «Write Yourself a Scheme in 48 Hours»). Но компилятор — это не только парсер, вернее, в основном это совсем даже не парсер, а совершенно другое. И когда эти мои триста строк PLT Scheme получили на вход программу «калькулятора», а выплюнули рабочий ассемблер, тут же скомпилированный в работающий под OSX бинарник, моему восторгу не было предела. Я бегал кругами и пугал домашних воплями о том, что «у меня есть настоящий компилятор, который я понимаю от начала и до конца». И это была правда.

Конечно, язык, с которой компилирует результат первой «реальной» главы (вообще-то второй после Preliminaries) — это язык арифметических выражений с + и * да скобками. Не поражает, если им пользоваться. Типичная программа:

(+ (+ 3 4) (+ 14 21))

Она же в оттранслированном виде:

    .align 16
_start:
    movq    $14, %rcx
    addq    $21, %rcx
    movq    $3, %rdx
    addq    $4, %rdx
    movq    %rdx, %rax
    addq    %rcx, %rax
    jmp _conclusion

    .globl _main
    .align 16
_main:
    pushq   %rbp
    movq    %rsp, %rbp
    subq    $0, %rsp
    movq    $65536, %rdi
    movq    $65536, %rsi
    callq   _initialize
    movq    _rootstack_begin(%rip), %r15
    movq    $0, 0(%r15)
    addq    $8, %r15
    subq    $256, %rsp
    jmp _start

    .align 16
_conclusion:
    subq    $8, %r15
    addq    $256, %rsp
    popq    %rbp
    retq

Поскольку я «зрелый практик с ипотекой и детьми», писать получается нечасто, одна глава у меня занимает примерно две недели, не сильно больше и не сильно меньше. То есть, через неделю-другую, у меня появляется очередное «разоблачение чёрной и белой компиляторной магии».

Разумеется, чем дальше, тем всё менее и менее поразительны обсуждаемые вещи. Например, глава про сборщик мусора по какой-то причине мне оказалась совсем неинтересна, хотя кое-что новое я почерпнул. Но это ожидаемо, что восторг первых глав уйдёт. В конце концов, тот же gradual typing, рассматриваемый в главе 10 — это вообще слишком близко к переднему краю исследований, чтобы рядовой программист был об этом наслышен и, следовательно, заинтересован.

Теперь о грустном, то есть, о косяках. Косяки есть, причём в количестве. Курс меняется, то тут, то там появляются какие-то недосказанности или вообще ошибки, но их лечат. Основной автор курса доступен по электронной почте, очень доброжелателен, но, увы, и очень занят. Опять-таки, как я понимаю, основной упор делается на версию для Python'а, что немного странно: все промежуточные языки там так или иначе LISP-подобны, поэтому оперировать со скобочками придётся. Но я же не преподаватель, им там виднее, в их Индианах.

Ещё, конечно, немножечко портит жизнь моё неважнецкое знание Racket'а: к примеру, я не знал, про pretty-print, аналогичный show из Haskell. Но, слава богу, Racket — это не C++, язык прост; большая часть необходимых библиотек содержится в стандартной поставке Racket; курс требует лишь небольшого подмножества языка (похожего на смесь SICP Scheme и «core» ML — ядра SML/Ocaml). Жить можно, в общем.

Заключение

Мне очень понравился курс построения компиляторов Essentials of Compilation в текущей редакции. Курс чудесно разоблачает «компиляторную магию», поскольку структура компилятора всегда под рукой, а все преобразования остаются понятными и логичными. Он очень, очень, очень подходит как курс повышения квалификации «вайтишникам с многолетним опытом», которые комплексуют, как я, от того, что не имеют полноценного профильного образования (я знаком с реальным хорошим CS PhD — это круто, совершенно другой уровень). Конечно, курс стал очень длинным, и, видимо, мало кто может себе позволить пройти его до конца. Да, пожалуй, и не надо. Но в любом случае не повредит пройти до главы 4 (Booleans and Conditionals).

Порядок глав, с моей точки зрения, довольно разумен, но лично я бы предпочёл, чтобы разговор о функциях шла перед реализацией сборки мусора. Тогда получился бы «расширенный язык C», а так после главы 6 получается странный язык, похожий по семантике на BASIC, но почему-то с кортежами и сборщиком мусора. Но, возможно, я что-то важное упускаю из вида.

Ещё не понравилась стандартная современная ошибка архитекторов систем, когда «ремонтопригодность» не принимается во внимание. К сожалению, есть только сложный «драйвер» компилятора, прогоняющий все имеющиеся тесты. Это замечательно, что он есть, но хотелось бы иметь и простой «драйвер», позволяющий оттранслировать одну и только одну программу до заданной стадии. Ещё хотелось бы разделить единый compiler.rkt на файлы по одному на проход.

Но это всё придирки — в остальном курс очень хороший, приятный, «структурирующий мир и делающий его понятнее». Я не знаю, как там для обучения индианских студентов, но как курс повышения квалификации он очень хорош. И даже некоторая недопиленность лишь делает курс более приближенным к реальной жизни, да и вообще «— Общение с девушками доставляет удовольствие лишь в тех случаях, когда достигается через преодоление препятствий…»