9. Как реализованы списки

В Лиспе атомы записывают в ясной манере; если реализация не ясна на практике, то она тем не менее ясна в теории. Атом `роза', например хранится, как четыре последовательные буквы `р', `о', `з', `а'. С другой стороны, список храниться по другому. Механизм достаточно простой, но надо чуть привыкнуть к идее. Список хранится используя набор сдвоенных указателей. В наборе, первый указатель каждой пары указывает на атом или другой список, а второй указатель каждой пары указывает на следующую пару указателей, или на символ nil, который означает конец списка.

Сам указатель --- это просто электронный адрес того, на что он указывает. Следовательно список хранится, как серия электронных адресов.

Например, в списке (роза фиалка лютик) --- три элемента, `роза', `фиалка' и `лютик'. В компьютере электронный адрес `роза' записывается в сегменте памяти компьютера вместе с адресом, который является электронным адресом размещения атома `фиалка'; а этот адрес (тот, который сообщает где размещается `фиалка') хранится вместе с адресом, который сообщает где размещен атом `лютик'.

Все это звучит сложнее, чем есть на самом деле, и это легко понять посмотрев на диаграмму:

___ ___ ___ ___ ___ ___ |___|___|--> |___|___|--> |___|___|--> nil | | | | | | --> роза --> фиалка --> лютик

На диаграмме, каждый прямоугольник представляет слово в памяти компьютера, которое содержит объект Лиспа, обычно в форме электронного адреса. Прямоугольники, то есть адреса расположены попарно. Каждая стрелка указывает туда, где хранится объект с этим адресом --- это или атом или пара адресов. Первый прямоугольник --- это электронный адрес атома `роза' и стрелка указывает на атом `роза'; второй прямоугольник это адрес следующей пары прямоугольников, первый из которых --- это адрес атома `фиалка', а второй --- это адрес следующей пары адресов. Самый последний прямоугольник указывает на символ nil, который означает конец списка.

Когда переменной присваивается список, например с помощью функции setq, на самом деле в этой переменной сохраняется адрес первого прямоугольника списка. Так вычисление следующего выражения

(setq букет '(роза фиалка лютик))

создаст следующую ситуацию:

букет | | ___ ___ ___ ___ ___ ___ --> |___|___|--> |___|___|--> |___|___|--> nil | | | | | | --> роза --> фиалка --> лютик

В этом случае, символ букет содержит адрес первой пары прямоугольников. В самом деле символ букет состоит из группы адресов-прямоугольников, один из которых --- адрес печатного слова `букет', второй --- это адрес определения функции прикрепленной к символу, если он конечно есть, а третий --- это адрес первой пары адресов-прямоугольников для списка (роза фиалка лютик), и т.д.

Тот же самый список можно проиллюстрировать и с помощью других прямоугольников:

букет | | -------------- --------------- ---------------- | | car | cdr | | car | cdr | | car | cdr | -->| роза | o------->| фиалка | o------->| лютик | nil | | | | | | | | | | -------------- --------------- ----------------

В прошлых разделах книги я предложил, что вы можете представить символ, как шкаф с полками. Определение функции хранится на одной полке, значение переменной на другой, и так далее. То, что мы положили на одну полку можно изменить, не задев содержимое другой полки и наоборот. Фактически то, что хранится на каждой полке --- это адрес значения или определения функции. Это похоже на старый сундук, где хранится карта захороненных сокровищ.

(Кроме имени, определения функции и значения переменной, у символа есть `полочка' для списка свойств в который можно записать другую информацию. Мы не будем обсуждать здесь списки свойств; смотрите section `Property Lists' in The GNU Emacs Lisp Reference Manual.)

Вот и честное представление:

Шкаф Содержимое Полок --------------------- | | | имя символа | букет | | --------------------- | | | определение функции | [нет] | | --------------------- | | | значение переменной | (роза фиалка лютик) | | --------------------- | | | список свойств | [не описан здесь] | | --------------------- |/ \|

Если символу присваивается CDR списка, то сам список не меняется; символу просто присваивается адрес другого элемента списка. (На жаргоне Лиспа CAR и CDR `не деструктивны'). Так вычисление следующего выражения

(setq цветы (cdr букет))

выдаст вот это:

букет цветы | | | ___ ___ | ___ ___ ___ ___ --> | | | --> | | | | | | |___|___|----> |___|___|--> |___|___|--> nil | | | | | | --> роза --> фиалка --> лютик

Значение цветы --- это (фиалка лютик), или можно сказать по другому, символ цветы содержит адрес пары адресов-прямоугольников, первый из которых содержит адрес атома фиалка, а второй содержит адрес атома лютик.

Пару адресов-прямоугольников называют списочной ячейкой (cons cell) или точечная пара. See section `List Type' in The GNU Emacs Lisp Reference Manual, и section `Dotted Pair Notation' in The GNU Emacs Lisp Reference Manual, за дополнительной информацией о списочных ячейках и точечных парах.

Функция cons добавляет новую пару адресов перед серией адресов, как это показано выше. Например, вычисление выражения

(setq букет (cons 'лилия букет))

выдаст:

букет цветы | | | ___ ___ ___ ___ | ___ ___ ___ ___ --> | | | | | | --> | | | | | | |___|___|----> |___|___|----> |___|___|---->|___|___|--> nil | | | | | | | | --> лилия --> роза --> фиалка --> лютик

Однако это не изменило значение символа цветы, как вы можете проверить вычислив следующее выражение,

(eq (cdr (cdr букет)) цветы)

это вернет t для true.

До тех пор, пока его не изменили, символ цветы все еще содержит значение (фиалка лютик) --- то есть адрес списочной ячейки, чей первый элемент является адресом атома фиалка. Также это не изменило никакую из других списочных ячеек --- они все еще там.

В Лиспе получая CDR списка, вы только получите адрес следующей списочной ячейки в группе; получив CAR списка, вы получите первый элемент списка; чтобы добавить новый элемент в список с помощью cons, вы добавляете новую списочную ячейку перед списком. Вот в принципе и все! Основы Лиспа гениально просты!

А на что указывает последний адрес в группе списочных ячеек? Он указывает на пустой список, nil.

В общем говоря, когда переменная Лисп устанавливается значение, то это делается через адрес списка, к которому относится эта переменная.

9.1 Упражнения

[ < ]

[ > ]

[ << ]

[ Up ]

[ >> ]

[Top]

[Contents]

[Index]

[ ? ]