Структура списков и памяти
До этого момента списки рассматривались на уровне текстового диалога человека с Лисп-системой. В настоящем разделе рассматривается кодовое представление списков внутри памяти машины и механизм "сборки мусора", обеспечивающий повторное использование памяти.
В памяти машины списки хранятся не как последовательности символов, а в виде структурных форм, построенных из машинных слов как частей деревьев, подобно записям в Паскале при реализации односвязных списков. Адреса в таких записях сопровождаются так называемыми тегами, специфицирующими тип данного, расположенного по указателю. При схематичном изображении структуры списка в виде диаграммы машинное слово рисуется как прямоугольник, разделенный на две части: адрес и декремент.
Теперь можно дать правило представления S-выражений в машине. Представление атомов будет пояснено ниже.
Преимущества структур списков для хранения S -выражений в памяти:
- Размер и даже число выражений, с которыми программа будет иметь дело, можно не предсказывать. Кроме того, исключаются трудности размещения произвольных выражений в блоках памяти фиксированной длины.
- Ячейки можно переносить в список свободной памяти, как только исчезнет необходимость в них. Даже возврат одной ячейки в список свободной памяти имеет смысл. Но если бы выражения хранились линейно, то было бы труднее организовать использование лишнего или освободившегося пространства из разрозненных блоков ячеек.
- Выражения, являющиеся продолжением нескольких выражений, можно хранить только в одном экземпляре.
Для примера рассмотрим типичную двухуровневую структуру (A (B C)).
Она может быть построена из A, B и C с помощью
(cons 'A (cons (cons 'B(cons 'C NIL))NIL))
или, используя функцию list,1) можно то же самое записать как
(list 'A (list 'B 'C))
Если дан список x из трех атомов x = (A B C), то аргументы A, B и C, используемые в предыдущем построении, можно найти как
A = (car x) B = (cadr x) C = (caddr x)
Исходную структуру из такого списка можно получить функцией grp, строящей (X (Y Z)) из списка вида (X Y Z).
(grp x)=(list(car x)(list(cadr x)(caddr x)))
Здесь grp применяется к списку X в предположении, что он заданного вида.
