Мусорщик: пометить и вычистить.

Вы не поверите, но я написал сборщик мусора! Это бесхитростный mark-and-sweep, идейно восходящий ещё к той самой первой системе Джона Маккарти.
Две маленьких оптимизашки: используются дополнительные биты для различения managed-ячеек (например, используются под дополнительное хранилище данных атома) и free-ячеек, которые можно смело пропускать в процессе маркировки. Второй бит может быть излишним, если ещё немного подумать, но и так тоже хорошо.

Пришлось переиначить формат ячеек - теперь тэг и прочие биты хранятся в отдельном байте, т.е. занимаемый системой объём ОЗУ чуточку вырос.


Работает (или должен работать) примерно так:

1. Проходим по всем ячейкам, у которых выставлен флаг USED (он выставляется при любой операции взятия ячейки из списка пустых). Если там не выставлен флаг MANAGED (свидетельствующий о том, что выделением-освобождением памяти тут занимается какой-то другой механизм, не garbage collector), то выставляем ещё флажок GARBAGE. То есть GARBAGE = USED & (!MANAGED), как-то так.
   
2. Затем запускаем процедуру обхода среды окружения (т.е. того грандиозного списка с заранее неизвестной глубиной вложенности) и во всех ячейках, до которых мы можем рекурсивно "дотянуться", флаг GARBAGE заменяем обратно на USED.
   
3. Заново проходим по всем ячейкам, если видим флаг GARBAGE, то вызываем процидурку удаления ячейки (причём если это атом, то попутно запускаем функцию удаления специфичных данных, и она уже управляет флажком MANAGED, если надо).
   

Итого, если был создан какой-то объект, но на него нет ссылок, то этот алгоритм корректно (надеюсь) высвободит занятую память.

Недостатки известны. Например, на момент прохода алгоритма по памяти все прочие процессы (которые могут менять содержимое памяти) должны быть приостановлены. Если памяти очень много, пауза может стать ощутимой и потребуются уже другие алгоритмы - но я целюсь в системы с памятью от нескольких десятков килобайт до первых единиц мегабайт (плюс-минус), для них скорость работы алгоритма вполне приемлема.

Момент запуска алгоритма в работу - наверное, когда свободной памяти уже нет (т.е. при попытке взять ячейку из списка пустых обнаруживаем, что он уже сам пуст).

First 32 cells, 6000 cell total (30000 bytes):
0000: [ 0009.0 : 8058 ] U SYMBOL:X
0001: [ FFFF.1 : 0028 ] F ->0028
0002: [ 0009.0 : 0003 ] U SYMBOL:ALPHA
0003: [ 1750.1 : 005B ] U RAW:005B1750 
0004: [ 0002.1 : FFFF ] U ->FFFF
0005: [ 0004.1 : FFFF ] U ->FFFF
0006: [ 0000.1 : 0014 ] U ->0014
0007: [ 0006.1 : 0005 ] U ->0005
0008: [ 0009.0 : 0009 ] U SYMBOL:PAPA
0009: [ 1770.1 : 005B ] U RAW:005B1770 
000A: [ 0008.1 : FFFF ] U ->FFFF
000B: [ 000A.1 : 0007 ] U ->0007
000C: [ 0009.0 : 000D ] U SYMBOL:OSCAR
000D: [ 1780.1 : 005B ] U RAW:005B1780 
000E: [ 000C.1 : FFFF ] U ->FFFF
000F: [ 000E.1 : 000B ] U ->000B
0010: [ 0000.1 : 001B ] U ->001B
0011: [ 0009.0 : 001A ] U SYMBOL:FOO
0012: [ 0009.0 : 8059 ] U SYMBOL:Y
0013: [ 0012.1 : 000F ] U ->000F
0014: [ 0007.0 : 0015 ] U STRING:"Test string"
0015: [ 17A0.1 : 005B ] U RAW:005B17A0 
0016: [ 0007.0 : 0017 ] U STRING:"Bullshit"
0017: [ 17B8.1 : 005B ] U RAW:005B17B8 
0018: [ 0009.0 : 0019 ] U SYMBOL:GARBAGE
0019: [ 1790.1 : 005B ] U RAW:005B1790 
001A: [ 17D0.1 : 005B ] U RAW:005B17D0 
001B: [ 0012.1 : 0021 ] U ->0021
001C: [ 0005.0 : 001D ] U INT32:102
001D: [ 0066.1 : 0000 ] U RAW:00000066 
001E: [ 0004.0 : 001F ] U UINT32:101
001F: [ 0065.1 : 0000 ] U RAW:00000065 
freeptr: 0001
environment: 000F
39 cells allocated, uclmem_free: 5961

( ( OSCAR ) ( PAPA ) ( X . "Test string" ) ( ALPHA ) )

Garbage collector: Ok

First 32 cells, 6000 cell total (30000 bytes):
0000: [ 0009.0 : 8058 ] U SYMBOL:X
0001: [ FFFF.1 : 0028 ] F ->0028
0002: [ 0009.0 : 0003 ] U SYMBOL:ALPHA
0003: [ 1750.1 : 005B ] U RAW:005B1750 
0004: [ 0002.1 : FFFF ] U ->FFFF
0005: [ 0004.1 : FFFF ] U ->FFFF
0006: [ 0000.1 : 0014 ] U ->0014
0007: [ 0006.1 : 0005 ] U ->0005
0008: [ 0009.0 : 0009 ] U SYMBOL:PAPA
0009: [ 1770.1 : 005B ] U RAW:005B1770 
000A: [ 0008.1 : FFFF ] U ->FFFF
000B: [ 000A.1 : 0007 ] U ->0007
000C: [ 0009.0 : 000D ] U SYMBOL:OSCAR
000D: [ 1780.1 : 005B ] U RAW:005B1780 
000E: [ 000C.1 : FFFF ] U ->FFFF
000F: [ 000E.1 : 000B ] U ->000B
0010: [ FFFF.1 : 0001 ] F ->0001
0011: [ FFFF.1 : 001A ] F ->001A
0012: [ FFFF.1 : 0011 ] F ->0011
0013: [ FFFF.1 : 0012 ] F ->0012
0014: [ 0007.0 : 0015 ] U STRING:"Test string"
0015: [ 17A0.1 : 005B ] U RAW:005B17A0 
0016: [ FFFF.1 : 0017 ] F ->0017
0017: [ FFFF.1 : 0013 ] F ->0013
0018: [ FFFF.1 : 0019 ] F ->0019
0019: [ FFFF.1 : 0016 ] F ->0016
001A: [ FFFF.1 : 0010 ] F ->0010
001B: [ FFFF.1 : 0018 ] F ->0018
001C: [ FFFF.1 : 001D ] F ->001D
001D: [ FFFF.1 : 001B ] F ->001B
001E: [ FFFF.1 : 001F ] F ->001F
001F: [ FFFF.1 : 001C ] F ->001C
freeptr: 0027
environment: 000F
17 cells allocated, uclmem_free: 5983