Ячейка cons — это объект, состоящий из двух полей, называемых полем CAR и полем CDR. Каждое поле может содержать любой объект Lisp. Мы также говорим, что CAR этой ячейки cons — это тот объект, который в данный момент содержится в её поле CAR, и аналогично для CDR.
Список — это последовательность ячеек cons, связанных между собой так, что поле CDR каждой ячейки cons содержит либо следующую ячейку cons, либо пустой список. Пустой список на самом деле является символом nil. См. Списки для подробностей. Поскольку большинство ячеек cons используются как часть списков, мы называем любую структуру, состоящую из ячеек cons, структурой списка.
Примечание для программистов на C: список Lisp, таким образом, работает как связный список, построенный из ячеек cons. Поскольку указатели в Lisp неявны, мы не различаем, хранит ли поле ячейки cons значение или указывает на него.
Поскольку ячейки cons настолько центральны для Lisp, у нас есть также слово для объекта, который не является ячейкой cons. Такие объекты называются атомами.
Синтаксис чтения и печатное представление списков совпадают и состоят из левой круглой скобки, произвольного числа элементов и правой круглой скобки. Вот примеры списков:
(A 2 "A") ; Список из трёх элементов. () ; Список без элементов (пустой список). nil ; Список без элементов (пустой список). ("A ()") ; Список из одного элемента: строка"A ()". (A ()) ; Список из двух элементов:Aи пустой список. (A nil) ; Эквивалентен предыдущему. ((A B C)) ; Список из одного элемента ; (который является списком из трёх элементов).
При чтении каждый объект внутри скобок становится элементом списка. То есть для каждого элемента создаётся ячейка cons. Поле CAR ячейки cons содержит элемент, а её поле CDR указывает на следующую ячейку cons списка, которая содержит следующий элемент в списке. Поле CDR последней ячейки cons устанавливается так, чтобы содержать nil.
Названия CAR и CDR происходят из истории Lisp. Первая реализация Lisp выполнялась на компьютере IBM 704, который разделял слова на две части: адрес и декремент; CAR была инструкцией для извлечения содержимого адресной части регистра, а CDR — инструкцией для извлечения содержимого декремента. В противоположность этому, ячейки cons названы в честь функции cons, которая их создаёт, а та, в свою очередь, была названа по своему назначению — построению (construction) ячеек.