Пишем Lisp-интерпретатор на Java

[GlukKazan]

Выглядит интересно.
Продолжения делали?

[IIvana]

Вот как раз на продолжениях остановился. Есть мысль их сделать в перспективе. Изучив детальнее что это такое, для начала :) А вообще, можно развивать сахар (параметры функций по умолчанию и т.п.), фичи (те же продолжения, более полноценное interoperability с Java — создание экшенов по кнокпам или другим событиям) или что-то еще. Но продолжения в планах имеются, и с достаточным приоритетом.

[GlukKazan]

К сожалению, тема продолжений, а также макросов в SICP не освещена совершенно. Рекомендую почитать «Lisp in Small Pieces». На Хабре есть перевод.

[Mellkor]

Стоит упомянуть еще одну книгу www.buildyourownlisp.com.
Это небольшой туториал по реализации интерпретатора лиспа на си.

[IIvana]

Спасибо, я читал начало. Судя по всему, имеет смысл прочитать полностью. А макросы я по своим кустарным представлениям сделал, это потом я уже увидел заметку про фёст-класс рантайм-макросы и узнал много нового о себе после употребления этого словосочетания на ЛОРе :) Но они работают, и синтаксис проще стандартных Лисповых макросов. Но не имея опыта с последними, я не могу сказать, мои Уже или шире по возможностям.

[GlukKazan]

Я сам не бог весть какой специалист по лисповым макросам. Надо будет глянуть ваши исходники как будет время.
Всё еще не могу за вас проголосовать. Глупый баг.

[IIvana]

Я видел, что вы посмотрели на гитхабе и мой Haskell-проект реализации этого языка. В мелочах эти 2 реализации отличаются (автоматическое расширение чисел до типа double при арифметических операциях или разная арифметика для разных типов и т.п.), но в плане макросов они вроде эквивалентны. Можно конечно допилить Haskell-реализацию, если бы не лень (каламбурчик, внутренняя хаскельная лень как раз ничуть не мешает :)) Было бы интересно, если кто-нибудь ради забавы наваяет на Liscript решение какой-нибудь задачки, можно с блэкджеком и макросами :)

[GlukKazan]

Внимательно ещё не смотрел, пролистал по диагонали.
Очень радует подробное комментирование.

[GlukKazan]

Не совсем понял на счёт оптимизации хвостовой рекурсии. В readme к хаскельной реализации написано, что вы не стали её делать.
В Java-версии всё-таки решили сделать?

[IIvana]

Именно. Потому что хаскель сам отлично оптимизирует любые рекурсии, в том числе и хвостовые. А Java не оптимизирует даже хвостовые. И когда я перевел реализацию на Java, я сразу столкнулся с постоянными неприятными переполнениями стека при вычислениях — у меня же нет циклов (на самом деле есть, особая форма while, но это просто ради пробы, можно ее выпилить из языка), все делается через рекурсию, каждое вычисление идет в своем одном потоке, размер стека которого можно задать при старте приложения в параметре. Я потратил некоторое количество сил и времени для полного решения этого вопроса — вынос вычислений со стека в кучу, передача вычисления в дочерний поток и т.п. Но все эти варианты работали медленно и/или ненадежно, поэтому я остановился на общепринятой полумере — оптимизации только хвостовых вызовов, но автоматическом (программисту не надо явным образом указывать что это хвостовой вызов, как в некоторых других языках — интерпретатор определяет это сам). И в результате у меня библиотечная функция левой свертки списка foldl волшебным образом стала не переполнять стек на больших списках, а правая свертка foldr продолжает переполнять. Пришлось и некотороые другие (какие возможно) библиотечные функции переписать через хвостовую рекурсию. Как писал Норвиг в комментариях про lispy2:

there is a potential problem: if every recursive call grows the runtime stack, then the depth of recursion, and hence the ability to loop, will be limited. In some implementations the limit will be as small as a few hundred iterations. This limitation can be lifted by altering eval so that it does not grow the stack on all recursive calls--only when necessary.

http://norvig.com/lispy2.html
Вот и у меня — only when necessary, без лишних указаний со стороны программиста.
Но конечно есть задачи, которые трудно реализовать только через хвостовую рекурсию. В моих демо-примерах есть пример работы с бесконечными потоками (реализованными средствами исключительно самого языка, через макросы и мемоизацию), но они переполняют стек при относительно длинных запросах. Частичное решение — запускать интерпретатор с ключом — указанием размера стека потока побольше, при работе обычно используется максимум несколько потоков (в отдельных закладках), не считая потока событий GUI.

[GlukKazan]

Думаю, всё это вместе — хорошая тема для следующей статьи

[IIvana]

В свою очередь думаю, что по этой паре интерпретаторов можно написать не один десяток полноценных статей, каждая по своей отдельной тематике, где все расписывать уже в деталях. В личной переписке я просил вас (и здесь спрашиваю всех участников) — хотели бы вы видеть статьи, детальнее раскрывающие какие-либо отдельные вопросы, и если да — то какие? Насколько я понял, одно предложение уже есть — реализация TCO. Хорошо, попробую написать нескучно про это. Может кто что еще добавит (хотя обсуждаем тему только мы с вами, а после ухода статьи с первой страницы на второй день вряд-ли кто еще подключится).