cons cell

(programming)   /konz sel/ or /kons sel/ A Lisp pair object containing any two objects. In Lisp, "cons" (short for "construct") is the fundamental operation for building structures such as lists and other binary trees. The application of "cons" to objects H and T is written

	(cons H T)
and returns a pair object known as a "cons", "cons cell" or dotted pair.

Typically, a cons would be stored in memory as a two consecutive pointers.

The two objects in a cons, and the functions to extract them, are called "car" and "cdr" after two 15-bit fields of the machine code instruction format of the IBM 7090 that hosted the original LISP implementation. These fields were called the "address" and "decrement" parts so "car" stood for "Contents of Address part of Register" and "cdr" for "Contents of Decrement part of Register".

In the typical case where the cons holds one node of a list structure, the car is the head of the list (first element) and the cdr is the tail of the list (the rest). If the list had only one element then the tail would be an empty list, represented by the cdr containing the special value "nil".

To aid in working with nested structures such as lists of lists, Lisp provides functions to access the car of the car ("caar"), the car of the cdr ("cadr"), the cdr of the car ("cdar") and the cdr of the cdr ("cddr").

Last updated: 2014-11-09