- PVSM.RU - https://www.pvsm.ru -
Очень рад объявить о завершении моего первого компилятора для языка программирования! Malcc [1] — это инкрементальный AOT-компилятор Lisp, написанный на C.
Вкратце расскажу о его многолетней разработке и что я узнал в процессе. Альтернативное название статьи: «Как написать компилятор за десять лет или меньше».
(В конце есть TL;DR [2], если вас не волнует предыстория).
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, которая анализировала код и ходила по абстрактному синтаксическому дереву [3] (AST). Когда интерпретатор всё-таки заработал, я переименовал его в Lydia [4] и переписал на C, чтобы сделать быстрее.
Помню, синтаксис Lydia казался мне очень умным! До сих пор наслаждаюсь его простотой.
Хотя Lydia была далека от идеального компилятора, но она вдохновила меня продолжить эксперименты. Впрочем, меня по-прежнему мучили вопросы, как заставить компилятор работать: во что компилировать? нужно ли изучать ассемблер?
В качестве следующего шага в 2014 году я начал работу над scheme-vm [5] — виртуальной машиной [6] для Scheme, написанной на Ruby. Я думал, что виртуальная машина с собственным стеком и байт-кодом станет переходным этапом от интерпретатором с AST-проходами и полноценным компилятором. И поскольку Scheme формально определена [7], не придётся ничего изобретать.
Я возился со scheme-vm более трёх лет и многое узнал о компиляции. В конце концов, я понял, что не смогу закончить этот проект. Код превратился в настоящий хаос, а конца не было видно. Без наставника или опыта, я словно блуждал в темноте. Как выяснилось, спецификация языка — не то же самое, что руководство по нему. Урок усвоен!
К концу 2017 года я отложил scheme-vm в поисках чего-то лучшего.
Где-то в 2018 году мне попался Mal [9] — интерпретатор Lisp в духе Clojure.
Mal изобретён Джоэлом Мартином как учебный инструмент. С тех пор разработано более 75 реализаций на разных языках! Когда я смотрел на эти реализации, то понимал, что они очень помогают: если я застрял, то могу пойти поискать подсказки в версии Ruby или Python. Наконец хоть кто-то говорит на моём языке!
Я также подумал, что если смогу написать интерпретатор для Mal, то смогу повторить те же шаги — и сделать компилятор для Mal.
Сначала я приступил к разработке интерпретатора согласно пошаговому руководству [10]. В то время я активно изучал Rust (оставлю это для другой статьи), поэтому написал собственную реализацию Mal на Rust: mal-rust [11]. Подробнее об этом эксперименте см. здесь [12].
Это была совершенное наслаждение! Не знаю, как выразить благодарность или похвалить Джоэла за создание превосходного руководства по Mal. Каждый шаг описан детально, есть блок-схемы, псевдокод и тесты! Всё, что нужно разработчику, чтобы создать язык программирования от начала до конца.
К концу руководства я сумел запустить свою Mal-реализацию для Mal, написанную на Mal, поверх моей реализации на Rust. (два уровня глубины, ух). Когда она сработала в первый раз, я от волнения запрыгнул на стул!
Как только я доказал жизнеспособность mal-rust, то сразу начал исследовать, как написать компилятор. Компилировать в ассемблер? Смогу ли я компилировать непосредственно машинный код?
Я видел ассемблер x86, написанный на Ruby. Он меня заинтриговал, но мысль о работе с ассемблером заставила остановиться.
В какой-то момент я наткнулся на этот комментарий на Hacker News [13], где упоминался Tiny C Compiler [14] как «бэкенд компиляции». Это показалось отличной идеей!
У TinyCC есть тестовый файл, показывающий, как использовать libtcc [15] для компиляции кода C из программы C. Это стартовая точка для “hello world”.
Опять вернувшись к пошаговому руководству Mal, вспоминая свои знания C, за пару месяцев свободных вечеров и выходных я смог написать компилятор Mal. Это было сплошное удовольствие.
Если вы привыкли к разработке через тестирование, то оце́ните наличие предварительного набора тестов. Тесты ведут к рабочей реализации.
Не могу много сказать об этом процессе, разве что повторю: руководство по Mal — настоящее сокровище. На каждом шагу я точно знал, что нужно делать!
Оглядываясь назад, вот некоторые сложности при написании компилятора Mal, где пришлось повозиться:
top
: код верхнего уровня — здесь функцииdecl
: объявление и инициализация переменных, используемых в телеbody
: тело, где производится основная работаDEBUG
, он выдавал скомпилированный код C, где можно просмотреть ошибки.Мне нравится, что на компилятор ушло почти десятилетие. Нет, правда. Каждый шаг на пути — это приятное воспоминание, как я постепенно становился всё лучшим программистом.
Но это не значит, что я «закончил». Есть ещё много сотен методов и инструментов, которые нужно изучить, чтобы чувствовать себя настоящим автором компилятора. Но могу уверенно сказать: «Я сделал это».
Вот весь процесс в сжатом виде, как сделать собственный компилятор Lisp:
Я считаю, что этот метод можно использовать с любым языком программирования, который компилируется в исполняемый файл. Например, вы можете:
go build
.В идеале, лучше контролировать компилятор Go как библиотеку, но это тоже способ сделать компилятор!
С помощью руководства Mal и своей изобретательности вы можете всё это сделать. Если даже я смог, то и вы сможете!
Автор: m1rko
Источник [19]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/kompilyatory-2/313677
Ссылки в тексте:
[1] Malcc: https://git.sr.ht/~tim/malcc
[2] TL;DR: #1
[3] абстрактному синтаксическому дереву: https://en.wikipedia.org/wiki/Abstract_syntax_tree
[4] Lydia: https://github.com/seven1m/lydia
[5] scheme-vm: https://github.com/seven1m/scheme-vm
[6] виртуальной машиной: https://en.wikipedia.org/wiki/Virtual_machine#Process_virtual_machines
[7] формально определена: http://www.scheme-reports.org/
[8] Image: https://mpov.timmorgan.org/images/stepA_mal.png
[9] Mal: https://github.com/kanaka/mal
[10] пошаговому руководству: https://github.com/kanaka/mal/blob/master/process/guide.md
[11] mal-rust: https://github.com/seven1m/mal-rust
[12] здесь: http://seven1m.sdf.org/experiments/make_a_lisp_in_rust.html
[13] комментарий на Hacker News: https://news.ycombinator.com/item?id=13250722
[14] Tiny C Compiler: https://bellard.org/tcc/
[15] как использовать libtcc: https://github.com/TinyCC/tinycc/blob/mob/tests/libtcc_test.c
[16] Image: https://mpov.timmorgan.org/images/mal-tests.png
[17] сборщика мусора Boehm-Demers-Weiser: http://www.hboehm.info/gc/
[18] Go: https://golang.org/
[19] Источник: https://habr.com/ru/post/446808/?utm_source=habrahabr&utm_medium=rss&utm_campaign=446808
Нажмите здесь для печати.