Набросал простенький лексический анализатор на Си, без использования сторонних утилит типа flex (они удобны, но хотелось попробовать сделать без них). Лексику чуть изменил под свои представления об удобстве, допилить-перепилить можно и потом.
Набросал так же системку управления памятью со сборкой мусора - простейший mark-and-sweep с одной маленькой оптимизацией, о которой чуть позже.
Так как я задумал не совсем лисп, а нечто чуть более близкое к железу (чтобы писать скрипты для Awesome Board, это будет главная цель), то система типов будет иной. В целях экономии и исходя из практических соображений.
Ясно, что система будет работать с данными типа "байты" чаще, чем с прочими, а многие практические значения легко уместятся в 16-битные переменные. Но выделять для хранения 16 или даже 8 бит целый атом (который есть ячейка размером 32 + 32 бита) как-то жырнавата будет. Но уменьшать гранулярность памяти тоже не хочу - 32 бита это натуральный размер данных для 32-битных ARMов. Поэтому сделаю так, что для некоторых типов данных указатель на ячейку будет на самом деле не указателем, а самим хранилищем этих данных. В указатель естественным образом помещается 32-битное число (теоретически, могут существовать 32-битные машины с 16-, 24-, 64- или какими-то ещё -битными указателями, но вряд ли я когда-нибудь с ними столкнусь), но отличить настоящий указатель от фиктивного будет невозможно. Если же данных всего 8 или 16 бит, то различить уже можно, если определить, что младшие биты такого регистра определяют вид хранимого значения: например, если младший бит равен 1 (и в система используется выравнивание по границе слов - это обязательное требование), то это уже не может быть указателем на 32-битное слово. Более того, раз у меня ячейки на самом деле 64-битные (из двух 32-битных полей), то реальные указатели на них имеют нулевых ТРИ младших бита, и их можно использовать под какие-то иные нужды.
А именно, эти три бита будут эмулировать мне тэгированую память.
Выстраивается такая система: бит 0 это маркер для сборщика мусора, бит 1 это маркер типа ячейки (атом/конс), бит 2 определяется по-разному для атомов и для консов - если атом, тогда это резерв (или, например, часть идентификатора типа данных); если конс, тогда по этому биту определяется, что лежит в данном поле: указатель или непосредственно данные (т.е. в случае конса бит 2 определён для обоих полей, ибо и там, и там может быть и указатель, и данные).
Но не могу пока сообразить, как по такой схеме реализовать двуликий NIL, который был бы и "пустым списком", и "логическим нулём" (как в большим Лиспе) одновременно: логическое значение, по-идее, должно быть атомом (чтобы быть самовычислимым), а пустой список это конс просто по определению.
В настоящем лиспе NIL имеет никакой тип (NULL), а T (которое есть не-NIL) имеет типа BOOLEAN. Это слегка бесит, поэтому я думаю, что сделаю boolean обычным типом и NIL не будет "пустым списком". Функции, подобные CAR и т.п. просто будут проверять аргумент на равенство NIL. Это, наверное, в каком-то аспекте снизит производительность, но вряд ли слишком сильно: проверять применимость функции к аргументу надо всё равно. Просто проверка будет двухступеньчатой - типа, если аргумент это список, то вернуть требуемое значение, а если не список, то убедиться, что это NIL и вернуть NIL, иначе просигналить ошибку.
Память организована пока что так: выделяется массив на несколько тыщ ячеек, все они формутируются так, словно это список (т.е. каждая ячейка указывает на следующую, при этом последняя указывает на NIL), заводится два указателя - freelst изначально указывает на первую ячейку, env указывает на NIL. Когда системе нужно взять новую ячейку, она берёт первую из списка freelst, а переставляя этот указатель на следующую. В список env заносятся создаваемые переменные и прочая такая фигня.
Высвобождение ячейки в простейшем случае выглядит так:
удаляем (обнуляем) её данные, а в указатель прописываем текущее значение freelst; затем в freelst прописываем адрес этой ячейки. Т.е. она становится головой списка пустых ячеек. Всё довольно просто.
Когда оказывается, что свободных ячеек больше нет (или, например, срабатывает некий таймер), то вызывается Сборщик Мусора. Он работает по известной схеме mark-and-sweep:
1) сначала все ячейки, весьм ассив, маркируется как мусор
2.1) затем обходится список env и с тех ячейеек, которые оказываются в нём, маркер мусора снимается
3) затем снова проходим по памяти, очищая ячейки, у которых всё ещё есть маркер мусора
Это описание алгоритма попадается очень часто, но в каждом таком описании пропущена одна мелочь: такой алгоритм будет тратить ресурсы на бессмысленное высвобождение и без того уже очищенных ячеек. Поэтому
2.2) проходим по списку freelst и снимаем маркер мусора с его ячеек - потому что мы знаем, что они и так уже пустые
Алгоритм с этой модификацией удаляет ТОЛЬКО выделенные, но "забытые" ячейки, на которые больше никто не ссылается.
Можно сделать его менее охочим до тактов процессора, если за один присест он будет обрабатывать не всю память целиком, а какую-то часть.