The Easy Language

[vak]

Помните книжку Этюды для программистов? Там в предпоследней главе было крышесносное задание: построить компилятор для паскалеподобного языка.

Easy Does It
                   or...
A COMPILER FOR AN
ALGEBRAIC LANGUAGE

A compiler is always a large program. To write one from scratch, even in a pedagogical environment, is a major undertaking. Although Easy is designed to reduce the pain while providing as much enlightenment as possible, this still is the hardest problem in the book. Do not tackle it unless you (and some helpful friends) have plenty of time and energy.

THE EASY LANGUAGE

Easy is a general-purpose, procedural, algebraic programming language. Its roots lie in ALGOL, ALGOL 68, and PASCAL. Like them, it is designed to be compiled, loaded, and executed on a reasonably conventional computer (the EC-1 described in Chapter 25 is a good example). The syntax is described by a context-free grammar suitable for parsing by LR(1) techniques. The semantics are similar to the languages described above, and we will let an informal description suffice, trusting to the reader’s skill to fill any gaps. In the text below, logically connected portions of the grammar are described with the associated semantics.

Так вот, один гениальный человек (begoon) такой компилятор зафигачил. Исходники проекта: github.com/begoon/easy

Пример кода на языке Easy, игра Жизнь: life.easy

Компилируем, запускаем:

git clone https://github.com/begoon/easy.git
cd easy
node easyc.ts life.easy
cc life.c -o life -I.
./life

Получаем:

** [ EASY LIFE ] ***************************************************************** 
*                                                      xx                        *
*                                                    xx  xx                      *
*                                          x         x  xxx                      *
*                                        xx              x   xxx                 *
*                                                     x x   x  xx                *
*                                             xx       x   x x  xx               *
*                                             xxx          x    x                *
*                                         x  xxx             xxx                 *
*                                         xxxxx    xx       xx                   *
*                                       xx   x    x  x                           *
*                                          x x     xx                            *
*                                      x   xx                                    *
*                                       xxx                                      *
*                                 x                                              *
*                               x xx         x                                   *
*                             xxx  xxx      x x                                  *
*                                    x     x  x                                  *
*                                 x  x      xx                                   *
*                                 x x                                            *
*                                                                                *
*                                                                                *
*                                                                                *
*                            xx                                                  *
*                            xx   xx                                             *
*                                 xx                                             *
********************************************************************************** 
GENERATION: 104

Comments

[begoon]

Круг замкнулся :-) - "Жизнь" было одним из этюдов, поэтому написать ее на Мини/Easy было интересно. Но еще два этюда из книги, Quine and Mastermind, тоже написаны на Мини.

[spamsink]

Интересно, сколько времени заняло написание компилятора, по сравнению с отведённым на это в книге?

[begoon]

Время было очень нелинейно.

Самая первая версия (которая была еще на Питоне), которая успешно компилировала пример из книги, Решето Эратосфена, заняла дня 3-4. Но! Потом, как я продолжил допиливать грамматику, я переписывал все нуля несколько раз. А в конце и на Typescript перешел, чтоб можно было в браузере потом запускать. В общем, от самого начала до сегодня прошло около полутора месяцев.

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

Так что я не берусь сравнивать :-)

[juan_gandhi]

Прелесть.

[chaource]

Вотъ для того, чтобы разрабатывать новые языки было легко, придумано функцiональное программированiе. Начать съ простого нетипизированнаго лямбда-исчисленiя. Тамъ достаточно реализовать 2 языковые конструкцiи (лямбда и подстановку), это строкъ 100 кода всего, и будетъ уже можно программировать что угодно. Потомъ можно перейти къ типизированнымъ лямбда-исчисленiямъ, ихъ реализацiя займетъ уже около 500-1000 строкъ кода. И несравнимое удобство и мощь программированiя. Параметризованные типы, классы типовъ, функторы, монады. Архитектура программы, выражаемая въ типахъ и провѣряемая компиляторомъ.

А языкъ Еasy на самомъ дѣлѣ вѣдь совсѣмъ не "easy". Онъ опять заставляетъ программиста наступать на тѣ же самыя грабли, что и Algol, Pascal, С. Опять ошибки, которыя легко сдѣлать, но трудно потомъ найти. Опять x = x + 1, опять разница между "процедурами" и "функцiями", опять слишкомъ слабая система типовъ, опять 10 разныхъ нелогичныхъ языковыхъ конструкцiй, выражающихъ одно и то же, но разными несовмѣстимыми способами. Одинъ только парсеръ для Еasy уже 1000 строкъ, а вѣдь его еще и отлаживать надо, и поддерживать потомъ.

Книга "этюды для программистовъ" была для меня 15-лѣтняго - недостижимымъ идеаломъ. Казалось тогда волшебствомъ, что вообще можно компьютеръ заставить все это дѣлать. Но сейчасъ я даже не сталъ бы въ эту книгу смотрѣть, - оттуда ничему научиться нельзя, это тупикъ.

[spamsink]

Почему ничему научиться нельзя? Этюды же можно (и нужно) реализовывать на любом языке. Я, помнится, написал квайн на Рефале и был очень горд собой.

[chaource]

Задачи тамъ слишкомъ сложныя, чтобы правильно догадаться, какъ ихъ рѣшать. Книга должна объяснять, какъ ихъ рѣшать, хотя бы примѣрно, показывать кодъ и объяснять, какъ его лучше организовать. А не просто объяснять читателю, что онъ можетъ попробовать Сноболъ, а можетъ АПЛ...

Также, книга должна объяснять читателю концепцiи, помогающiя правильно программировать. Напримѣръ, если рѣчь идетъ о реализацiи системы регулярныхъ платежей съ бухгалтерскими провѣрками и отчетностью, то разумно было бы разработать domain-specific языкъ, позволяющiй быстро и декларативно запрограммировать требованiя задачи. Книга должна была бы показать, какъ это дѣлается, и лишь послѣ этого давать читателю завершить упражненiе. А не говорить, что "тутъ одними GOTO не обойтись" - и все. Дальше плыви, какъ знаешь. Я думаю, авторъ предполагалъ, что программистъ будетъ просто абы какъ, "на колѣнкѣ", писать длинный и трудно поддерживаемый императивный кодъ, реализующiй всѣ эти сложныя бухгалтерскiя правила съ помощью большого количества if/then/else, и что въ этой безсмысленной работѣ и заключается данный "этюдъ".

[vak]

Если нужен учебник - стоит поискать учебник. А тут этюдник. 😀

[chaource]

Насколько я понимаю, въ то время еще не было учебниковъ, гдѣ показывались бы cколько-либо адекватные способы рѣшать такого рода задачи. До опубликованiя SICP (1985) было еще долго.

Думается, авторъ книги предполагалъ, что программисты будутъ просто рѣшать эти задачи методомъ пробъ и ошибокъ, "пока не получится", - потому что книга дѣлаетъ видъ, что тамъ не нужно никакихъ особыхъ знанiй и методовъ, просто надо, молъ, наловчиться программировать, и это достигается простымъ упражненiемъ. Такимъ образомъ, книга поощряетъ читателя упражняться въ написанiи большой массы спагетти-кода съ трудно находимыми ошибками, - кода, который невозможно поддерживать и послѣ некотораго уровня сложности можно только выбрасывать и начинать снова. Книга помогла распространенiю этого метода, который собственно и привелъ къ постояннымъ жалобамъ на "кризисъ индустрiи программированiя" и къ попыткамъ (снова и снова негодными средствами, т.е. методомъ пробъ и ошибокъ) этотъ кризисъ рѣшать.

Для пiанистовъ, играющихъ этюды, методъ "учи, пока не выучишь" тоже невѣренъ и не приводитъ къ хорошимъ результатамъ.

[ichthuss]

Только єто же транспайлер, а не компилятор. Компилятор должен преобразовьівать из вьісокоуровневого язьіка в низкоуровневьій (ассемблер, байт-код, машинньій код). А назвать си менее вьісокоуровневьім, чем easy, можно разве что в каком-то очень єзотерическом смьісле.

[begoon]

Дело не в языке Easy как таковом. Естественно, ему уже много лет, ибо автор его придумал, а точнее, как сказал сам автор -- "немного переработал из XPL", когда до моего рождения оставалось еще несколько лет.

Дело в реализации компилятора. Сейчас, как ни странно, наблюдается ренессанс ручных рекурсивных парсеров (Jai, Zig, V, Odin, Nim etc.), или PEG, ибо памяти много, и смысла нет возиться с flex/bison и их табличным LR(k) подходом, отлаживать который не пожелаешь никому.

Ну а для реализации LSP (language server protocol), где парсерная часть компилятора вызывается практически при каждом нажатии клавиш в редакторе, recursive descent parser дает точнейшее место и причину ошибки.

Скажу так, если бы мне надо было писать настоящий компилятор С типа Кефира, даже со всеми плюшками стандарта С23, я б писал его также, как и этот компилятор Easy. Ну разве что в конце надо было б перевести все на нормальный компилируемый язык типа Go, Zig, V, да и сам С, почему нет.

[chaource]

А что вы думаете по поводу парсера treesitter, онъ какъ будто оптимизированъ какъ разъ для постояннаго повторнаго парсинга въ редакторахъ?

[begoon]

treesitter - штука модная и молодежная :-)

Как я понял про treesitter -- это фактически подход PEG, в котором грамматики описывается не по классике PEG/BNF, а в виде какого-то птичьего языка в форме Javascript/JSON.

И область применения treesitter'a - это не компиляторы, а именного языковой анализ для сред разработки, например, как LSP.

Но те языковые серверы (LSP конкретно), что я покопал, а именно Go (gopls) и Zig (zls), пользуются собственным парсерами, которые являются частью их компиляторов.