Списки и конс-ячейки

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

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

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

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

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

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

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

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