Представление структуры списка

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

Рис. 1.1.  структура списка

Каждая из частей занимает фиксированное число разрядов, представляющее тэг и адрес. Если декремент слова "x" указывает на слово "y", то это можно выразить стрелками на схеме:

Рис. 1.2.  схема

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

Рис. 1.3.  отображение атома в прямоугольнике

Правило представления неатомных S-выражений — начало со слова, содержащего указатель на car выражения в адресе иуказатель на cdr в декременте. Ниже нарисовано несколько схем S-выражений. По соглашению NIL обозначается как перечеркнутый по диагонали прямоугольник.

Рис. 1.4.  обозначение NIL

вместо (A . B).

Рис. 1.5.  (A . B)

Непосредственная польза от сопоставления графического вида с представлением списков в памяти поясняется при рассмотрении функций, работающих со списками, на следующем примере из [1]:

((M . N) X (M . N))

Рис. 1.8.  пример

Возможное для списков использование общих фрагментов ((M . N) X (M . N)) может быть представлено графически:

Рис. 1.9.  графическое представление

В точности такую структуру непосредственно текстом представить невозможно, но ее можно построить с помощью одного из выражений выражений:

(let ((a '(M . N))) (setq b (list a 'X a)) )

((lambda (a) (list a 'X a) )'(M . N))

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

Рис. 1.10.  структура

может распечатываться как ( A B C A B C ... ).

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

1. Размер и даже число выражений, с которыми программа будет иметь дело, можно не предсказывать. Кроме того, можно не организовать для размещения выражений блоки памяти фиксированной длины.

2. Ячейки можно переносить в список свободной памяти, как только исчезнет необходимость в них. Даже возврат одной ячейки в список имеет значение, но если выражения хранятся линейно, то организовать использование лишнего или освободившегося пространства из блоков ячеек трудно.

3. Выражения, являющиеся продолжением нескольких выражений, могут быть предоставлены только однажды.

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

Предполагается, что дан список вида

L1 = ((A B C)(D E F ) ... (X Y Z))

представленный как

Рис. 1.11.  точность построения структр списка

и нужно построить список вида

L2 = ((A (B C))(D (E F)) ... (X (Y Z)))

представленный как

Рис. 1.12.  список вида

Рассмотрим типичную подструктуру (A (B C)) второго списка.

Она может быть построена из A,B и C с помощью

(cons ‘A (cons (cons ‘B (cons ‘C NIL)) NIL))

или, используя функцию list, можно то же самое записать как

(list ‘A (list ‘B ‘C))

В любом случае дан список x из трех атомов x = (A B C), аргументы A, B и C, используемые в предыдущем построении, можно найти как

A = (car x)

B = (cadr x)

C = (caddr x)

Первый шаг в получении L2 из L1 — это определение функции grp, строящей (X (Y Z)) из списка вида (X Y Z).

(grp x) = (list (car x) (list (cadr x) (caddr x)))

Здесь grp применяется к списку L1 в предположении, что L1 заданного вида.

Для достижения цели новая функция mltgrp определяется как

(mltgrp L) = (COND ((null L) NIL)

(T (cons (grp (car L)) (mltgrp (cdr L)) )))

Итак, mltgrp, применяемая к списку L1, перебирает (X Y Z) по очереди и применяет к ним grp, чтобы установить их новую форму (X (Y Z)) до тех пор, пока не завершится список L1 и не построится новый список L2.

.

.