Введение в программирование на Лиспе

         

Структура списков и памяти


До этого момента списки рассматривались на уровне текстового диалога человека с Лисп-системой. В настоящем разделе рассматривается кодовое представление списков внутри памяти машины и механизм "сборки мусора", обеспечивающий повторное использование памяти.

В памяти машины списки хранятся не как последовательности символов, а в виде структурных форм, построенных из машинных слов как частей деревьев, подобно записям в Паскале при реализации односвязных списков. Адреса в таких записях сопровождаются так называемыми тегами, специфицирующими тип данного, расположенного по указателю. При схематичном изображении структуры списка в виде диаграммы машинное слово рисуется как прямоугольник, разделенный на две части: адрес и декремент.

Теперь можно дать правило представления S-выражений в машине. Представление атомов будет пояснено ниже.

Преимущества структур списков для хранения S -выражений в памяти:

  1. Размер и даже число выражений, с которыми программа будет иметь дело, можно не предсказывать. Кроме того, исключаются трудности размещения произвольных выражений в блоках памяти фиксированной длины.
  2. Ячейки можно переносить в список свободной памяти, как только исчезнет необходимость в них. Даже возврат одной ячейки в список свободной памяти имеет смысл. Но если бы выражения хранились линейно, то было бы труднее организовать использование лишнего или освободившегося пространства из разрозненных блоков ячеек.
  3. Выражения, являющиеся продолжением нескольких выражений, можно хранить только в одном экземпляре.

Для примера рассмотрим типичную двухуровневую структуру (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 в предположении, что он заданного вида.



Содержание раздела