Cons Cell and List Types — Elisp

Типы cons-ячеек и списков

Cons-ячейка — это объект, состоящий из двух слотов, называемых слотом CAR и слотом CDR. Каждый слот может содержать любой объект Lisp. Также мы говорим, что CAR этой cons-ячейки — это объект, который в данный момент содержится в её слоте CAR, и аналогично для CDR.

Список — это последовательность cons-ячеек, связанных между собой так, что слот CDR каждой cons-ячейки содержит либо следующую cons-ячейку, либо пустой список. Пустой список на самом деле является символом nil. Подробнее см. Списки. Поскольку большинство cons-ячеек используется как часть списков, любую структуру, состоящую из cons-ячеек, мы называем структурой списка.

Примечание для программистов на C: список Lisp работает как связный список, построенный из cons-ячеек. Поскольку указатели в Lisp неявные, мы не различаем ситуации, когда слот cons-ячейки содержит значение и когда он указывает на это значение.

Поскольку cons-ячейки играют столь важную роль в Lisp, у нас есть также слово для объекта, который не является cons-ячейкой. Такие объекты называются атомами.

Синтаксис чтения и печатное представление списков совпадают и состоят из открывающей скобки, произвольного числа элементов и закрывающей скобки. Вот примеры списков:

(A 2 "A")            ; A list of three elements.
()                   ; A list of no elements (the empty list).
nil                  ; A list of no elements (the empty list).
("A ()")             ; A list of one element: the string "A ()".
(A ())               ; A list of two elements: A and the empty list.
(A nil)              ; Equivalent to the previous.
((A B C))            ; A list of one element
                     ;   (which is a list of three elements).

При чтении каждый объект внутри скобок становится элементом списка. То есть для каждого элемента создаётся cons-ячейка. Слот CAR cons-ячейки содержит этот элемент, а её слот CDR ссылается на следующую cons-ячейку списка, содержащую следующий элемент списка. Слот CDR последней cons-ячейки устанавливается так, чтобы содержать nil.

Названия CAR и CDR связаны с историей Lisp. Первоначальная реализация Lisp работала на компьютере IBM 704, который делил слова на две части: адрес и декремент; CAR была инструкцией для извлечения содержимого адресной части регистра, а CDR — инструкцией для извлечения содержимого декремента. Название cons-ячеек, напротив, происходит от функции cons, которая их создаёт; имя этой функции, в свою очередь, связано с её назначением — построением ячеек.