berlisp/spec.md

Язык Берлисп.

Берлисп - это очень простой Лисп. Он по сути своей похож на Лямбда-исчисление с let. Он использует лексическую область видимости. Есть сборщик мусора. Часть объектов передаётся по ссылке, а часть копируется. Думаю, что очень важно было бы добавить конструкцию match.

Окружение

Окружение - это объект, который связывает имена переменных с их значениями. Окружение может иметь предков. Если мы не нашли переменную в данном окружении, можно поискать её в предке.

Значения переменных ищутся по именам. Имена - это символы. Каждый символ всецело определяется его именем. Двух символов с одним именем не бывает в принципе.

Сборщик мусора

У меня язык интерпретируемый, динамический, а потому сборщик мусора просто необходим. В основе его будет лежать алгоритм mark and sweep. Как работает этот алгоритм. У нас есть объекты. Одни объекты ссылаются на другие. В процессе работы ссылки на объекты то появляются, то исчезают. Если на объект нет ссылок, значит он недостижим, и его можно удалять. Если ссылки ещё остаются, значит объект ещё может понадобиться.

Для того чтобы можно было собрать мусор, к каждому объекту прикладывается метка (достижим, или недостижим) и указатель на предыдущий выделенный объект. Благодаря такому указателю, у нас есть список вообще всех объектов, по которому мы можем пройтись. Впрочем, это список служебный, и не предназначен для того, чтобы им пользовались в прикладной программе.

Перед сборкой мусора мы проходимся по списку всех объектов, и отмечаем их как потенциально недостижимые. Дальше, мы берём те объекты, которые достижимы уж точно, и начиная с них, проходимся по всем остальным объектам, рекурсивно, и отмечаем встретившиеся нам объекты как достижимые.

Когда мы прошлись по графу объектов, мы проходимся по служебному списку объектов. Если текущий объект не помечен как достижимый, мы его удаляем. Если нет, то оставляем.

Когда мы удаляем какой-то объект, важно обновить ссылку, чтобы служебный список не обрывался.

Структуры

Структуры похожи на таковые в Zig. Отличие состоит в том, что у нас язык в первую очередь динамически типизированный.