Comments 28
Нет, не проще. Вполне очевидно, что в основной своей массе студенты местного вуза не будут писать компиляторов, и тот, что они напишут со мной, будет единственным в их жизни.
Моя задача не переизобрести LLVM, а просто объяснить людям, как работает машина. Моей самой базовой целью, которую должны достичь просто все студенты - понять, как работает стек. Вы удивитесь, но для очень большого числа людей стек вызовов функций - это очень размытая штука.
Идя дальше, я хочу, чтобы студенты поняли, как работают области видимости, что такое замыкание: подавляющее их большинство ключевого слова nonlocal в питоне не видело, например. А потом как работают таблицы виртуальных методов и тому подобное. А также какие это даёт накладные расходы, которые очень хорошо видно на маленькой кодовой базе компилятора.
В данном конкретном коде у меня нет замыканий, у меня статическое лексическое связывание переменных, но отдельно я покажу моим студентам, как реализовать динамическое связывание.
А потом я расскажу, что такое сборщик мусора, и покажу реализацию сборщика мусора. И это опять будет очень маленькая кодовая база, которая не опирается на большой чёрный ящик типа LLVM, который прячет слишком многое. Всё нужно делать руками, и раз сделав, понимаешь принцип.
Так что нет, сам компилятор меня не интересует, это просто очередной проект, который иллюстрирует интересующие меня аспекты крайне практического программирования.
главное - это дело не забросить ))) по моему много было уже подобного без продолжения или с продолжением, но не до конца
У нас это было на 2-м курсе в таком виде: сначала немного теории - грамматики Хомского, виды грамматик типа ГПП, LR(n)... потом задание - дан язык, написать грамматику, сгенерировать таблицу, готово. Первый язык - просто скобочные выражения, в качестве примера, можно скомпилировать без создания дерева, только стек. Очень интересная тема))) ждем рейтрейсинг)))
Подобное сделано на более высоком уровне с компилятором и виртуальной машиной на С++. См. си-подобный язык, Basheyev https://habr.com/ru/articles/560356/
Но это, конечно, не значит, что Вам не следует проделать это вновь.
Так устроен мир. Каждый живущий учится ходить - то есть "изобретает велосипед", "изобретёный" до него миллиадами живших. Собственно, через это учатся.
PS Где-то год назад заплюсовал Ваш tinyraycaster (хабр + отсылка к Ламоту) на Гитхабе (486 lines of C++: old-school FPS in a weekend). Поэтому не сомневаюсь, что и с данным компилятором у Вас получится.
PPS ИМХО интересней и полезней для сообщества было бы написать, например, короткий разборщик JS->AST на регулярках, чтобы цеплять к нему компиляторы на любых языках. Но это ИМХО.
Про разработку новых полезных инструментов - это не ко мне. Точнее, ко мне тоже, но не в данном контексте.
В моих tiny* репозиториях в принципе нет и не может быть ничего нового, добавленная стоимость в компактности каждого проекта и в формате подачи, я каждый раз показыаваю не конечный результат, но процесс. Компактность очень важна для того, чтобы было понятно, что ничего сложного в этом нет. На самом деле, тематика каждого из моих проектов вообще не важна, я лишь пытаюсь заинтересовать людей, чтобы они сами начали ковырять разные штуки, становясь через это лучше и лучше.
"Сложная это работа - из болота тащить бегемота." (с)
Мы все пытаемся. :)
PS Пользуясь случаем, тем кто захочет почитать на тему. Тоже когда-то заплюсовал там же. https://ps-group.github.io/compilers/ast
Я просто оставлю это здесь...
https://ppci.readthedocs.io/en/latest/howto/toy.html
Очень уж маленький язык, это просто калькулятор, и даже не очень программируемый :(
Оно хорошо, но нет того удовольствия от получения какого-то интересного результата малыми ресурасми. Вот прямо сейчас я готовлю пример программы на wend для следующих лекций, осторожно, спойлер:
Hidden text
,''''''''''''''''''''''''''''''''~~~~~~~~~~~~=====++:[<?[/<O +=~~~~~~~~~'''''''',
'''''''''''''''''''''''''''''~~~~~~~~~~~~~~=====++::;[&O &/;:++===~~~~~~~~~''''''
'''''''''''''''''''''''''~~~~~~~~~~~~~~=====+++:< XXO ? <;+======~~~~~~~''''
'''''''''''''''''''''~~~~~~~~~~~~~~===++++++:::;; <;::+++=======~~~~''
''''''''''''''''''~~~~~~~~~~~====+:o&/< /[[[&&?<&&oX O?&<//?/;:::::;/&+=~~~
'''''''''''''~~~~~~~~=========+++::[&o O x&<o xOO x:==~
'''''''''~~~~==============+++++:;[/<?X /:++==
''~~~~~=::+++++++====++++++:::;[O X [;:++=
~~====++:?&/[;;:;;x /;;::::;;;[ O?:=
=====++::;[<o x O O x&///<& ?[:+=
===++:::;&<o# xxO :+=
::;/ <<o&o x/:+==
/<<?x [;:++==
/<<?x [;:++==
::;/ <<o&o x/:+==
===++:::;&<o# xxO :+=
=====++::;[<o x O O x&///<& ?[:+=
~~====++:?&/[;;:;;x /;;::::;;;[ O?:=
''~~~~~=::+++++++====++++++:::;[O X [;:++=
'''''''''~~~~==============+++++:;[/<?X /:++==
'''''''''''''~~~~~~~~=========+++::[&o O x&<o xOO x:==~
''''''''''''''''''~~~~~~~~~~~====+:o&/< /[[[&&?<&&oX O?&<//?/;:::::;/&+=~~~
'''''''''''''''''''''~~~~~~~~~~~~~~===++++++:::;; <;::+++=======~~~~''
'''''''''''''''''''''''''~~~~~~~~~~~~~~=====+++:< XXO ? <;+======~~~~~~~''''
'''''''''''''''''''''''''''''~~~~~~~~~~~~~~=====++::;[&O &/;:++===~~~~~~~~~''''''
,''''''''''''''''''''''''''''''''~~~~~~~~~~~~=====++:[<?[/<O +=~~~~~~~~~'''''''',
Библиотека textx позволяет создавать практически любые языки. Библиотека ppci позволяет их компилировать, но возможно и интерпретировать или транслировать, например в С.
Библиотеки это хорошо, но толковые тексты - это ещё лучше. Они позволяют научиться создавать новые и улучшать старые библиотеки.
Ох,куда я попал...С моими 1,5 высшими тех.образованиями и далёким прошлым опытом первоначального программирования на низкоуровневых языках я здесь себя,похоже,чувствую как неандерталец на собрании лауреатов Нобелевских премий...
Если захочется разобраться поглубже, можно почитать эту книжку (на сайте есть бесплатная версия): https://craftinginterpreters.com/contents.html
Автор тот же, что и у Game Programming Patterns.
Я тоже как-то раз решил на выходных компилятор написать. "Выходные" длятся уже 7 с лишним лет.
Ну вот вам и отличный повод :)
Я, в принципе свой уже дописал, в выходные уложился. Теперь осталось отполировать и описать.
Вы видимо меня не допоняли. В те выходные я действительно кое-чего написал. А вот "отполировать и описать" длиться до сих пор - язык уж очень оброс фичами, был написан self-hosted компилятор, документация и примеры немаленькие и т. д. Короче - по-крупному в проект ввязался.
Здорово! Я вот думаю, стоит ли мне идти дальше и добавлять управление памятью, структуры-классы, или ну его на фиг, слишком сложно будет для объяснения...
В принципе, должно быть интересно писать компилятор языка на самом языке, постепенно его расширяя.
Было бы интересно почитать продолжение. Управление памятью, мне кажется, вообще мастхев. Классы, имхо, чуток оверкил. Можно, например, структуры с методами + интерфейсы. В этом случае будет охвачена довольно интересная тема про инкапсуляцию и таблицы виртуальных функций, но при этом вполне можно обойтись без наследования, полиморфизма и ограничений доступа (private/protected).
А не проще ли (и правильнее) идти не через велосипед, а через https://ru.m.wikipedia.org/wiki/LLVM ? Мировое сообщество уже давно делает компиляторы на базе стандартных проверенных временем решений. И какая задача стоит перед тобой - дать понимание студентам как делать компиляторы и как они работают или научить белое сложной работе с языком программирования?
Нет, не проще. Вполне очевидно, что в основной своей массе студенты местного вуза не будут писать компиляторов, и тот, что они напишут со мной, будет единственным в их жизни.
Моя задача не переизобрести LLVM, а просто объяснить людям, как работает машина. Моей самой базовой целью, которую должны достичь просто все студенты - понять, как работает стек. Вы удивитесь, но для очень большого числа людей стек вызовов функций - это очень размытая штука.
Идя дальше, я хочу, чтобы студенты поняли, как работают области видимости, что такое замыкание: подавляющее их большинство ключевого слова nonlocal в питоне не видело, например. А потом как работают таблицы виртуальных методов и тому подобное. А также какие это даёт накладные расходы, которые очень хорошо видно на маленькой кодовой базе компилятора.
В данном конкретном коде у меня нет замыканий, у меня статическое лексическое связывание переменных, но отдельно я покажу моим студентам, как реализовать динамическое связывание.
А потом я расскажу, что такое сборщик мусора, и покажу реализацию сборщика мусора. И это опять будет очень маленькая кодовая база, которая не опирается на большой чёрный ящик типа LLVM, который прячет слишком многое. Всё нужно делать руками, и раз сделав, понимаешь принцип.
Так что нет, сам компилятор меня не интересует, это просто очередной проект, который иллюстрирует интересующие меня аспекты крайне практического программирования.
Сборщик мусора будет покруче трассировки! Алгоритм Бейкера? Держите в курсе!
Я ж говорил, что я некомпетентный преподаватель, впервые слышу имя Бейкера, беру на заметку, спасибо!
У меня есть лишь отдалённое представление о предмете, но я точно знаю, что никакой магии там нет :)
Всё как обычно, жертвуем либо памятью, либо временем исполнения. Можно начать с чего-нибудь вообще тривиального типа линейного прохода по всем объектам, потом добавить каких-нибудь поколений, дефрагментацию. Фиг знает, я в этом не разбираюсь, надо будет поглядеть. Любые советы приветствуются!
Наверняка есть более подходящие книги, но я со сборкой мусора разбирался по старой как мир книге Джеффа Элджера с незатейливым названием "C++" (легко гуглится). Это учебник по C++ а не руководство по алгоритмам. С точки зрения C++ книга давно неактуальна, но идиомы умных указателей там очень хорошо разобраны. Уплотнение памяти и сборка мусора - 2 последние главы.
(прошу прощения-промахнулся с ответом)
Да, спасибо, посмотрю. В целом, насколько я понимаю, алгоритмов сбора мусора миллиард, всё зависит от паттернов доступа к памяти конкретного приложения.
Опять же, у меня нет желания показывать людям тонкости каждого алгоритма, я лишь хочу закрепить в мозгу основную идею: ничто не бесплатно, анализируем критические ресурсы. Из того, что в жаве не надо думать над утечками памяти, не следует то, что надо забывать про расположение объектов в памяти и про паттерны доступа к ним.
Я запрограммирую пару-тройку разных алгоритмов, и придумаю разные программы, на которых разные сборщики будут по-разному ломаться. Впрочем, это выходит за рамки данной серии текстов, сначала надо закончить её, а продолжать потом :)
Любопытный проект! Очень хорошо, что нацелились на простоту, минимализм и не используете LLVM.
От постоянных isinstance в коде можно было бы отказаться с помощью match/case (эту конструкцию для компиляторщиков и придумали, я почти не шучу). В этом докладе я агитирую за нее: https://github.com/true-grue/python-dsls
Компилятор за выходные: синтаксические деревья