Список свободной памяти и сборщик мусора
В любой момент времени только часть памяти, отведенной для структур списков, действительно используется для хранения S-выражений. Остальные ячейки организованы в простой список, называемый списком свободной памяти.
Первые реализации действовали по следующей схеме [1 (не найдено)].
Определенный регистр FREE содержит информацию о первой ячейке этого списка. Когда требуется слово для формирования дополнительной структуры списка, берется первое слово списка свободной памяти, а код в регистре FREE заменяется на информацию о втором слове списка свободной памяти. Не требуется никаких программных средств для того, чтобы пользователь программировал возврат ячеек в список свободной памяти. Этот возврат происходит автоматически при пропуске программы, где бы ни исчерпался список свободной памяти. Программа, восстанавливающая память, называется "мусорщик". Любая часть структуры списка, доступная программе, рассматривается как активный список и не затрагивается мусорщиком. Активные списки доступны программе через некоторые фиксированные наборы базисных ячеек, таких как ячейки списка атомов и ячейки, вмещающие частичные результаты Лисп-выражений. Сложные структуры списков могут быть произвольной длины, но каждое активное слово должно быть подведено к базисной ячейке цепью car-cdr.
Любая ячейка, не достижимая таким образом, недоступна для программы и не активна, поэтому ее содержимое не представляет интереса. Неактивные, то есть недоступные программе ячейки восстанавливаются мусорщиком в списке свободной памяти следующим образом. Во-первых, каждая ячейка, к которой можно получить доступ через цепь car-cdr, метится установлением отрицательного знака. Где бы ни выявилось отрицательное слово в цепи во время процесса пометки, мусорщик знает, что остаток раскручиваемого списка содержит уже помеченные ячейки. Затем мусорщик предпринимает линейное выметание осовободившегося пространства, собирая ячейки с положительным знаком в новый список свободной памяти и восстанавливая исходный знак активных ячеек.
