Cons-ячейки: из чего на самом деле сделаны списки

Заглядываем под капот списков и обнаруживаем, что они собраны из крошечных двухполевых ячеек.

Cons-ячейка — элементарная структура из двух полей, car и cdr, каждое из которых хранит ссылку на любой объект. Список в Lisp — это не примитив, а цепочка cons-ячеек, где car хранит элемент, а cdr — ссылку на остаток списка.

До сих пор мы говорили о списках так, будто это монолитные объекты. На самом деле список в Lisp — иллюзия, удобная надстройка над куда более простой структурой: связными парами. Понять, что список «сделан из» cons-ячеек, — значит получить ключ ко всему: к тому, почему добавление в начало дёшево, а в конец дорого; почему два списка могут «делить» общий хвост; почему деструктивные операции опасны. Это, возможно, самый важный урок всего курса для практического программирования на Lisp.

Что такое cons-ячейка

Самая фундаментальная составная структура данных в Lisp — это cons-ячейка (от слова construct — «сконструировать»). Она устроена предельно просто: это ячейка памяти с двумя полями. Первое поле исторически называется car, второе — cdr (эти странные имена пришли из названий регистров машины IBM 704, на которой писался первый Lisp в 1958 году, и закрепились навсегда). В каждое поле можно положить ссылку на любой объект — число, символ, строку или другую cons-ячейку. Создаётся такая ячейка функцией cons, а извлекаются её поля функциями car и cdr.

;; cons создаёт ячейку из двух полей; car и cdr их читают:
(cons 1 2)         ; => (1 . 2)   ячейка: car=1, cdr=2
(car (cons 1 2))   ; => 1         первое поле
(cdr (cons 1 2))   ; => 2         второе поле

Запись (1 . 2) с точкой посередине называется точечной парой (dotted pair) и буквально изображает одну cons-ячейку: слева от точки — содержимое car, справа — содержимое cdr. Это самый честный способ увидеть ячейку «как она есть». Пока cdr содержит что-то, кроме другой ячейки или nil, мы имеем именно пару, а не список.

Как из пар получается список

Теперь главный фокус. Список — это не отдельный тип данных, а соглашение: цепочка cons-ячеек, в которой car каждой ячейки хранит очередной элемент, а cdr — ссылку на следующую ячейку. Последняя ячейка указывает своим cdr на nil, и этот nil служит признаком конца списка. То есть список (1 2 3) — это на самом деле три ячейки, связанные через cdr, и завершающий nil.

;; Список (1 2 3) — это вложенные cons-ячейки:
(cons 1 (cons 2 (cons 3 nil)))   ; => (1 2 3)

;; Это буквально означает цепочку:
;;  [1|*]-->[2|*]-->[3|nil]
;;   car cdr  car cdr  car  cdr

;; Поэтому car даёт первый элемент, а cdr — весь остаток:
(car '(1 2 3))     ; => 1         (голова)
(cdr '(1 2 3))     ; => (2 3)     (хвост — это тоже список!)
(car (cdr '(1 2 3)))   ; => 2     (второй элемент)
(cdr (cdr '(1 2 3)))   ; => (3)   (остаток после двух)

Вглядитесь в эту структуру — она объясняет очень многое. car списка — это его первый элемент (голова). cdr списка — это весь остаток, и важно, что остаток сам является полноценным списком. Именно поэтому списки в Lisp так естественно обрабатываются рекурсией: «сделай что-то с головой (car), затем рекурсивно обработай хвост (cdr)» — и так до тех пор, пока хвост не станет nil. Эта пара «голова и хвост» — фундаментальный приём, на котором держится вся работа со списками.

Почему именно nil в конце

Теперь становится понятна особая роль nil, о которой мы говорили в прошлом разделе. nil — это и пустой список, и признак конца цепочки ячеек. Когда вы дошли по cdr до nil, список кончился. Это элегантно: не нужен отдельный «маркер конца», его роль играет тот же объект, что и «пустой список» и «ложь». Рекурсивный обход списка естественно завершается проверкой «а не nil ли хвост?» — то есть «не пуст ли оставшийся список?».

Список, у которого последний cdr указывает на nil, называют правильным (proper list). Если же где-то в цепочке cdr указывает не на ячейку и не на nil, а на произвольный атом, получается неправильный (точечный) список — он оканчивается точечной парой. Различие важно: большинство списочных функций рассчитаны на правильные списки, и неправильный список может привести к ошибке при обходе.

;; Правильный список оканчивается на nil:
(cons 1 (cons 2 nil))    ; => (1 2)         правильный
;; Неправильный (точечный) — последний cdr это атом:
(cons 1 (cons 2 3))      ; => (1 2 . 3)     точечный, оканчивается парой
;; Одиночная пара — частный случай:
(cons 1 2)               ; => (1 . 2)

car и cdr как навигация

Поскольку car берёт голову, а cdr — хвост, их комбинацией можно добраться до любого элемента. (car (cdr x)) — второй элемент, (car (cdr (cdr x))) — третий, и так далее. Эти комбинации настолько часты, что в Lisp есть сокращения: cadr (= car of cdr, второй элемент), caddr (третий), cddr (хвост после двух элементов). Буквы между c и r читаются справа налево как последовательность применений car/cdr.

;; Сокращения для навигации по списку:
(cadr  '(a b c d))   ; => B   ( = (car (cdr ...)),  2-й элемент)
(caddr '(a b c d))   ; => C   (3-й элемент)
(cddr  '(a b c d))   ; => (C D)   (хвост после двух)

;; На практике для ясности чаще пишут именованные функции:
(first  '(a b c d))  ; => A   (то же, что car)
(second '(a b c d))  ; => B   (то же, что cadr)
(third  '(a b c d))  ; => C   (то же, что caddr)
(rest   '(a b c d))  ; => (B C D)   (то же, что cdr)

В современном коде ради читаемости предпочитают именованные синонимы — first, second, rest — вместо загадочных cadr и cddr. Но знать сокращения нужно: они часто встречаются в старом коде и в учебниках, и понимание, что cadr — это просто «car от cdr», избавляет от расшифровки по справочнику.

Ячейки можно рисовать: box-and-pointer

Чтобы окончательно сжиться с cons-ячейками, полезно освоить классический способ их изображения — диаграммы «ящики и стрелки» (box-and-pointer), которыми пользуются во всех учебниках Lisp. Каждую ячейку рисуют как прямоугольник, разделённый на две половины: левая — car, правая — cdr. Если в поле лежит атом, его пишут прямо в половинке; если ссылка на другую ячейку — рисуют стрелку. Завершающий nil часто изображают перечёркнутой половинкой. Такая картинка делает структуру списка наглядной и сразу показывает, где разделяемые хвосты, а где независимые ветви.

;; Список (1 2 3) в виде box-and-pointer:
;;
;;   +---+---+    +---+---+    +---+---+
;;   | 1 | *-+-->| 2 | *-+-->| 3 |nil|
;;   +---+---+    +---+---+    +---+---+
;;    car cdr      car cdr      car cdr
;;
;; Точечная пара (1 . 2) — одна ячейка без продолжения:
;;   +---+---+
;;   | 1 | 2 |     (в cdr — атом, а не стрелка)
;;   +---+---+

Привычка мысленно рисовать такие диаграммы — лучший инструмент против путаницы. Когда вы не уверены, что вернёт cdr или почему два списка повлияли друг на друга, набросайте ячейки со стрелками — и ответ станет очевиден. Опытные лисперы держат эту картинку в голове постоянно, и именно поэтому им «очевидно» то, что новичку кажется загадкой.

Как это работает под капотом

На уровне памяти cons-ячейка — это два смежных машинных слова, каждое из которых хранит ссылку (указатель или непосредственно небольшое значение вроде fixnum). Список занимает в памяти ровно столько ячеек, сколько в нём элементов, плюс эти ячейки разбросаны по куче и связаны указателями — это классический связный список, а не непрерывный массив. Отсюда вытекают все его характеристики производительности, которые мы подробно разберём в уроке про обход: доступ к голове мгновенен, а к произвольному элементу — линеен, потому что приходится идти по цепочке указателей.

Важное следствие связной природы: добавить элемент в начало списка дёшево — достаточно создать одну новую ячейку, чей cdr указывает на старый список, и ничего не копировать. А вот добавить в конец дорого, потому что нужно пройти весь список до последней ячейки. Эта асимметрия — прямое следствие того, что cdr ведёт только вперёд, и она формирует все идиомы работы со списками в Lisp. Сборщик мусора, в свою очередь, автоматически освобождает ячейки, на которые больше никто не ссылается, так что вручную управлять их памятью не нужно.

Частые ошибки

Первая ошибка новичка — думать, что список это массив. Из-за похожей записи (1 2 3) легко решить, что доступ к n-му элементу мгновенен. Нет: список — связная цепочка, и добраться до середины можно только пройдя её с начала. Если нужен быстрый доступ по индексу, в Lisp есть отдельный тип — векторы (массивы), а списки оптимальны для последовательной обработки и роста с головы.

Вторая ошибка — путать (cons 1 2) и (list 1 2). (cons 1 2) создаёт одну ячейку — точечную пару (1 . 2), это не список из двух элементов. А (list 1 2) создаёт правильный список (1 2) из двух ячеек, оканчивающийся nil. Разница в том, что во втором случае cdr указывает на ячейку с nil, а в первом — прямо на число 2. Эту тонкость мы детально разберём в следующем уроке про построение списков.

Третья ошибка — брать car или cdr от того, что не является ячейкой. Применить car к числу или строке — ошибка типа. Особый случай: (car nil) и (cdr nil) в Common Lisp возвращают nil (это удобное соглашение для рекурсии), но это исключение касается только nil; для прочих не-ячеек будет ошибка. В Scheme же и (car '()) — ошибка, что снова напоминает о различиях диалектов.

Итоги

• Cons-ячейка — двухполевая структура (car и cdr), создаётся функцией cons; точечная пара (1 . 2) изображает одну ячейку.
• Список — это не примитив, а цепочка cons-ячеек: car хранит элемент, cdr — ссылку на остаток, а последний cdr указывает на nil.
• car даёт голову (первый элемент), cdr — хвост (весь остаток, тоже список); на этой паре держится рекурсивная обработка списков.
• Сокращения cadr, caddr, cddr читаются справа налево; в современном коде их заменяют на first, second, rest.
• Список — связная структура: добавление в начало дёшево, в конец дорого, а доступ по индексу линеен; (cons 1 2) — это пара, а не список из двух элементов.