---

5.1 Списки и ячейки cons

Списки в Лиспе не являются примитивным типом данных; они строятся из ячеек cons (см. Тип ячейки cons и списки). Ячейка cons — это объект данных, представляющий упорядоченную пару. То есть у неё есть два слота, и каждый слот содержит или ссылается на некоторый объект Лиспа. Один слот известен как 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 в качестве CDR (а также в качестве CAR) находится nil.

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

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

Для некоторых целей не имеет значения, является ли список правильным, циклическим или точечным. Если программа не заглядывает в список достаточно далеко, чтобы увидеть CDR последней ячейки cons, ей это безразлично. Однако некоторые функции, работающие со списками, требуют правильных списков и выдают ошибки, если получают точечный список. Большинство функций, которые пытаются найти конец списка, попадают в бесконечные циклы, если получают циклический список. Вы можете использовать функцию proper-list-p, описанную в следующем разделе (см. proper-list-p), чтобы определить, является ли список правильным.

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