What is the Definition of a Lisp Cons Cell?

Question

What exactly is the definition of a Common Lisp Cons Cell? How is a Cons Cell different than a standard linked list item? After all, both the cons cell and the linked list item have a value and a pointer to the next cell or item... or is this understanding wrong?

Answer 1

Cons cells in general hold two pointers that can point to anything. General usage of course is to point to a "value" with the left one, and to another Cons cell (or nil) with the "right" one.

Answer 2

A cons cell is closer to a binary tree node than a linked list node. car and cdr return the two children, which can be nil, atoms, or other cons cells.

Answer 3

In Lisp, a cons cell holds a pair of values. If the cons cell is in the variable c, then (car c) returns the first value and (cdr c) returns the second.

By convention, a list consists of cons cells where the car of the cell contains the node value and the cdr contains the reference to the next node or nil (the empty list) to indicate the end of the list. When the primitive functions return or accept lists, this is the format in which the list is presented.

Therefore, for the list l, (car l) gives the first element (the value in the first cons cell) and (cdr l) returns the tail of the list (the next cons cell in the list).

Answer 4

I think the other answers here, while accurate, aren't explicit about one thing.

In a traditional C++ linked list implementation, the two fields (val and next, say) are typed. next is defined as pointing to another node in the list, with null being the terminator. You can't point to anything but another node with next.

Lisps are dynamically typed, so either field in a cons cell can be anything (either an atom or a reference). You can implement a linked list with cons cells (that's all a Lisp list is: a chain of cons cells with a nil terminator), but you can also put arbitrary values in each field, using a cons cell as a coordinate pair, a tree node, etc.

You can even combine these; e.g., a list of x y coordinates:

;; (cons foo (cons bar nil)) == (list foo bar)    
(cons
  (cons 5 4)
  (cons (cons 9 10) nil))
=>
((5 . 4) (9 . 10))

A cons cell is thus strictly more general than a linked list node; it's closer to an "applied pair", so to speak. All of the standard list processing functions (map, dolist, etc.) are simply functions that assume you're putting values in car and another list in cdr.

All this means that — if you wished — you could define lists backwards, with car pointing to the next cons cell and cdr pointing to the value! To do that with a linked list node you'd have to redefine the class or data structure to alter the types.

Answer 5

A cons cell is one third of a contract consisting of cons, car, and cdr, with the requirement being that they behave as pairs, as others have mentioned.

The reason for leaving out the words "reference", "pointer", etc. from this definition is to recognize that those are implementation details. If you wanted to, you could build a cons out of thin air, as Abelson and Sussman did:

(define (cons a b) (lambda (x) (x a b)))
(define (car x) (x (lambda (a b) a)))
(define (cdr x) (x (lambda (a b) b)))

This definition lives entirely inside Lisp's world of definitions and functions, and doesn't even stop to consider whether the objects are stored as values or references; yet these can serve as a drop-in replacement for the primitive objects (not considering mutability or other special uses).