Списки и ячейки CONS

Списки в Lisp не являются примитивным типом данных; они строятся из ячеек CONS (см. Тип ячейки CONS). Ячейка CONS — это объект данных, представляющий упорядоченную пару. То есть, она имеет два поля, и каждое поле содержит или ссылается на какой-либо объект Lisp. Одно поле известно как CAR, а другое — как CDR. (Эти названия традиционные; см. Тип ячейки CONS.) CDR произносится как «ку-дэр».

Мы говорим, что «CAR этой ячейки CONS — это» тот объект, который в данный момент содержится в её поле CAR, и аналогично для CDR.

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

Также по соглашению, CDR последней ячейки CONS в списке является nil. Такую nil-завершённую структуру мы называем правильным списком⁴. В Emacs Lisp символ nil является одновременно символом и списком без элементов. Для удобства символ nil считается имеющим nil в качестве своего CDR (а также в качестве своего CAR).

Следовательно, CDR правильного списка всегда является правильным списком. CDR непустого правильного списка — это правильный список, содержащий все элементы, кроме первого.

Если CDR последней ячейки CONS списка — это какое-либо значение, отличное от nil, мы называем такую структуру точко-список, так как его печатное представление использует обозначение точечной пары (см. Обозначение точечных пар). Есть ещё одна возможность: CDR некоторой ячейки CONS может указывать на одну из предыдущих ячеек CONS в списке. Мы называем такую структуру циклическим списком.

Для некоторых целей не имеет значения, является ли список правильным, циклическим или точечным. Если программа не заходит достаточно глубоко в список, чтобы увидеть CDR конечной ячейки CONS, её это не волнует. Однако некоторые функции, работающие со списками, требуют правильных списков и сигнализируют об ошибках, если им передаётся точечный список. Большинство функций, пытающихся найти конец списка, попадают в бесконечные циклы при передаче циклического списка.

Поскольку большинство ячеек CONS используются как часть списков, мы называем любую структуру, созданную из ячеек CONS, структурой списка.