Очень рад объявить о завершении моего первого компилятора для языка программирования! Malcc — это инкрементальный AOT-компилятор Lisp, написанный на C.

Вкратце расскажу о его многолетней разработке и что я узнал в процессе. Альтернативное название статьи: «Как написать компилятор за десять лет или меньше».

(В конце есть TL;DR, если вас не волнует предыстория).

Демо компилятора

tim ~/pp/malcc master 0 > ./malcc                                                                   Mal [malcc]
user> (println "hello world")
hello world
nil
user> (+ 1 2)
3
user> (def! fib2 (fn* (n) (let* (f (fn* (n1 n2 c) (if (= c n) n2 (f n2 (+ n1 n2) (+ c 1))))) (f 0 1 1))))
<lambda>
user> (fib2 25)
75025
user> ^D%
tim ~/pp/malcc master 0 > ./malcc examples/hello.mal                                                                                         hello world
tim ~/pp/malcc master 0 > ./malcc --compile examples/hello.mal hello                                                                         gcc -g -I ./tinycc -I . -o hello hello.c ./reader.c ./printer.c ./hashmap.c ./types.c ./util.c ./env.c ./core.c ./tinycc/libtcc.a -ledit -lgc -lpcre
-ldl
tim ~/pp/malcc master 0 > ./hello                                                                                                            hello world
tim ~/pp/malcc master 0 >

Успешные неудачи

Почти десять лет я мечтал написать компилятор. Меня всегда очаровывала работа языков программирования, особенно компиляторов. Хотя я представлял компилятор как тёмную магию и понимал, что сделать его с нуля невозможно простому смертному вроде меня.

Но я всё равно попытался и учился по ходу!

Во-первых, интерпретатор

В 2011 году я начал работу над простым интерпретатором для вымышленного языка Airball (airball можно перевести как «мазила»). По названию можете оценить степень моей неуверенности, что он будет работать. Это была довольно простая программа на Ruby, которая анализировала код и ходила по абстрактному синтаксическому дереву (AST). Когда интерпретатор всё-таки заработал, я переименовал его в Lydia и переписал на C, чтобы сделать быстрее.



Помню, синтаксис Lydia казался мне очень умным! До сих пор наслаждаюсь его простотой.

Хотя Lydia была далека от идеального компилятора, но она вдохновила меня продолжить эксперименты. Впрочем, меня по-прежнему мучили вопросы, как заставить компилятор работать: во что компилировать? нужно ли изучать ассемблер?

Во-вторых, компилятор и интерпретатор байт-кода

В качестве следующего шага в 2014 году я начал работу над scheme-vm — виртуальной машиной для Scheme, написанной на Ruby. Я думал, что виртуальная машина с собственным стеком и байт-кодом станет переходным этапом от интерпретатором с AST-проходами и полноценным компилятором. И поскольку Scheme формально определена, не придётся ничего изобретать.

Я возился со scheme-vm более трёх лет и многое узнал о компиляции. В конце концов, я понял, что не смогу закончить этот проект. Код превратился в настоящий хаос, а конца не было видно. Без наставника или опыта, я словно блуждал в темноте. Как выяснилось, спецификация языка — не то же самое, что руководство по нему. Урок усвоен!

К концу 2017 года я отложил scheme-vm в поисках чего-то лучшего.

Встреча с Mal

Где-то в 2018 году мне попался Mal — интерпретатор Lisp в духе Clojure.

Mal изобретён Джоэлом Мартином как учебный инструмент. С тех пор разработано более 75 реализаций на разных языках! Когда я смотрел на эти реализации, то понимал, что они очень помогают: если я застрял, то могу пойти поискать подсказки в версии Ruby или Python. Наконец хоть кто-то говорит на моём языке!

Я также подумал, что если смогу написать интерпретатор для Mal, то смогу повторить те же шаги — и сделать компилятор для Mal.

Интерпретатор Mal на Rust

Сначала я приступил к разработке интерпретатора согласно пошаговому руководству. В то время я активно изучал Rust (оставлю это для другой статьи), поэтому написал собственную реализацию Mal на Rust: mal-rust. Подробнее об этом эксперименте см. здесь.

Это была совершенное наслаждение! Не знаю, как выразить благодарность или похвалить Джоэла за создание превосходного руководства по Mal. Каждый шаг описан детально, есть блок-схемы, псевдокод и тесты! Всё, что нужно разработчику, чтобы создать язык программирования от начала до конца.

К концу руководства я сумел запустить свою Mal-реализацию для Mal, написанную на Mal, поверх моей реализации на Rust. (два уровня глубины, ух). Когда она сработала в первый раз, я от волнения запрыгнул на стул!

Компилятор Mal на C

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

Я видел ассемблер x86, написанный на Ruby. Он меня заинтриговал, но мысль о работе с ассемблером заставила остановиться.

В какой-то момент я наткнулся на этот комментарий на Hacker News, где упоминался Tiny C Compiler как «бэкенд компиляции». Это показалось отличной идеей!

У TinyCC есть тестовый файл, показывающий, как использовать libtcc для компиляции кода C из программы C. Это стартовая точка для “hello world”.

Опять вернувшись к пошаговому руководству Mal, вспоминая свои знания C, за пару месяцев свободных вечеров и выходных я смог написать компилятор Mal. Это было сплошное удовольствие.



Если вы привыкли к разработке через тестирование, то оце?ните наличие предварительного набора тестов. Тесты ведут к рабочей реализации.

Не могу много сказать об этом процессе, разве что повторю: руководство по Mal — настоящее сокровище. На каждом шагу я точно знал, что нужно делать!

Трудности

Оглядываясь назад, вот некоторые сложности при написании компилятора Mal, где пришлось повозиться:

1. Макросы должны компилироваться на лету и быть готовы к выполнению во время компиляции программы. Это слегка озадачивает.
   
2. Нужно обеспечить «окружение» (дерево хэшей / ассоциативных массивов / словарей с переменными и их значениями) как для кода компилятора, так и для итогового кода скомпилированной программы. Это позволяет определять макросы во время компиляции.
   
3. Поскольку среда доступна во время компиляции, изначально Malcc во время компиляции ловил неопределённые ошибки (доступ к переменной, которая не была определена), и в паре мест это нарушило ожидания набора тестов. В конце концов, чтобы пройти тесты, я отключил эту функцию. Было бы здорово добавить её обратно в качестве дополнительного флага компилятора, поскольку так можно заранее выловить много ошибок.
4. Я скомпилировал код C, записывая в три строки структуры:
   • top: код верхнего уровня — здесь функции
   • decl: объявление и инициализация переменных, используемых в теле
   • body: тело, где производится основная работа
5. Целый день я размышлял, не написать ли собственный сборщик мусора, но решил оставить это упражнение на потом. Библиотека сборщика мусора Boehm-Demers-Weiser легко подключается и доступна для многих платформ.
   
6. Важно просматривать код, который пишет ваш компилятор. Всякий раз, когда компилятор встречал переменную окружения DEBUG, он выдавал скомпилированный код C, где можно просмотреть ошибки.

Что я бы сделал иначе

1. Писать код C и пытаться сохранить отступы было непросто, тут я бы не отказался от автоматизации. Мне кажется, некоторые компиляторы пишут уродливый код, а затем специальная библиотека «украшает» его перед выдачей. Это нужно изучить!
   
2. Добавление в строки при генерации кода немного сумбурно. Можно было рассмотреть возможность создания AST, а затем преобразования в последнюю строку кода C. Это должно привести код в порядок и придать гармонии.

Теперь совет

Мне нравится, что на компилятор ушло почти десятилетие. Нет, правда. Каждый шаг на пути — это приятное воспоминание, как я постепенно становился всё лучшим программистом.

Но это не значит, что я «закончил». Есть ещё много сотен методов и инструментов, которые нужно изучить, чтобы чувствовать себя настоящим автором компилятора. Но могу уверенно сказать: «Я сделал это».

Вот весь процесс в сжатом виде, как сделать собственный компилятор Lisp:

1. Выберите язык, на котором вы чувствуете себя комфортно. Вы же не хотите одновременно изучать новый язык и то, как написать другой новый язык.
   
2. Следуя руководству Mal напишите интерпретатор.
   
3. Порадуйтесь!
   
4. Снова следуйте инструкциям, но вместо выполнения кода напишите код, который выполняет код. (Не просто «рефакторинг» существующего интерпретатора. Надо начать с нуля, хотя копипаст не запрещён).

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

1. Написать интерпретатор Mal на Go.
2. Модифицировать ваш код, чтобы:
   
   • создать строку кода Go и записать её в файл;
   • скомпилировать этот результирующий файл с помощью go build.

В идеале, лучше контролировать компилятор Go как библиотеку, но это тоже способ сделать компилятор!

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