Основы функционального программирования


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


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

структура списка

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

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

схема

Рис. 1.2.  схема

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

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

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

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

обозначение NIL

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

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

(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, однако они могут возникнуть как результат вычисления некоторых функций, точнее, применения структуроразрушающих или деструктивных функций.


- Начало -  - Назад -  - Вперед -



Книжный магазин