Cons Cell

ConsCells are the building blocks of lists in LispLanguages.

A ConsCell can be thought of as a structure that can refer to two other things. The "other things" can be either a ConsCell or an atom. (In LispLanguages, anything that is not a ConsCell is an atom -- strings, numbers, symbols, etc.) For irrelevant historical reasons, the first of these two things is referred to as the CAR of the ConsCell, and the second is referred to as the CDR of the ConsCell.

The fundamental constructor is CONS. Thus, in typical LispNotation,

  (cons 1 2)

evaluates to

  (1 . 2)

which is the DottedPairNotation of a ConsCell containing the value 1 in its CAR and the value 2 in its CDR. (cons is a primitive built-in function of Lisp; it constructs ConsCells.)

The atom NIL has a special meaning when used in a ConsCell; it denotes "nothing". Lists can be built from ConsCells as follows:

  (cons a (cons b (cons c NIL)))  == (list a b c) == (a b c).

The form

  (a b c)

is just a pretty representation of

  (a . (b . (c . NIL)))

Such a list is known as a ProperList. The CAR of the first ConsCell in the list refers to the first element of the list. The CDR of the first ConsCell refers to the tail of the list, which, in a ProperList, is itself a list. When the CDR is NIL, then you've reached the end of the list.

This explains why CAR and CDR [Also knowns as FIRST and REST, in CommonLisp] behave as they do: they extract the first or second part of a ConsCell, respectively. If that cell happens to be the first cell of a list, the CDR extracts a whole sublist, which then is the REST of the original list.

This incredibly simple and ingenious representation is amazingly powerful. Lisp takes the idea to the extreme, by representing lisp programs themselves as lists, allowing Lisp to construct or analyze lisp statements very easily. This lends the language an amazing recursive, introspective flavour not duplicated in any other language.

They sound more like the building blocks of binary trees than lists. Is "ConsCell" another name for "node"?

Yes, it's just a funny name for a node of a binary tree. What's intriguing about LispLanguages is that everything can be built up from binary trees of atoms. That includes both data and code -- LispLanguages can treat code as data to an extent that you won't see in any other major branch of computer languages.

Or, another way to look at it is they are the nodes in a singly-linked list. I also want to point out that it's a bit of an overstatement to say that everything in Lisp is built out of cons cells. CommonLisp, supports a rich array of built in datatypes such as arbitrary magnitude integers, hash tables, multidimensional arrays, streams, etc. which are not built out of cons cells. Which is not to say that lists, trees, and other data structures built out of cons cells aren't quite convenient. And it is true that Lisp source code is parsed into lists built out of cons cells (which is important because LispMacros can then operate on those lists at compile time to generate new code which is then fed to the compiler.) -- PeterSeibel

---

CategoryLanguageFeature CategoryLisp