Типы ячеек и списков конс

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

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

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

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

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

(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).

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

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