GNU Info

(elisp)Cons Cell Type

---

Next: Array Type Prev: Sequence Type Up: Programming Types

---

Enter node , (file) or (file)node

Cons Cell and List Types
------------------------

   A "cons cell" is an object that consists of two slots, called the
CAR slot and the CDR slot.  Each slot can "hold" or "refer to" any Lisp
object.  We also say that "the CAR of this cons cell is" whatever
object its CAR slot currently holds, and likewise for the CDR.

     A note to C programmers: in Lisp, we do not distinguish between
     "holding" a value and "pointing to" the value, because pointers in
     Lisp are implicit.

   A "list" is a series of cons cells, linked together so that the CDR
slot of each cons cell holds either the next cons cell or the empty
list.  Note: Lists, for functions that work on lists.  Because most
cons cells are used as part of lists, the phrase "list structure" has
come to refer to any structure made out of cons cells.

   The names CAR and CDR derive from the history of Lisp.  The original
Lisp implementation ran on an IBM 704 computer which divided words into
two parts, called the "address" part and the "decrement"; CAR was an
instruction to extract the contents of the address part of a register,
and CDR an instruction to extract the contents of the decrement.  By
contrast, "cons cells" are named for the function `cons' that creates
them, which in turn was named for its purpose, the construction of
cells.

   Because cons cells are so central to Lisp, we also have a word for
"an object which is not a cons cell".  These objects are called "atoms".

   The read syntax and printed representation for lists are identical,
and consist of a left parenthesis, an arbitrary number of elements, and
a right parenthesis.

   Upon reading, each object inside the parentheses becomes an element
of the list.  That is, a cons cell is made for each element.  The CAR
slot of the cons cell holds the element, and its CDR slot refers to the
next cons cell of the list, which holds the next element in the list.
The CDR slot of the last cons cell is set to hold `nil'.

   A list can be illustrated by a diagram in which the cons cells are
shown as pairs of boxes, like dominoes.  (The Lisp reader cannot read
such an illustration; unlike the textual notation, which can be
understood by both humans and computers, the box illustrations can be
understood only by humans.)  This picture represents the three-element
list `(rose violet buttercup)':

         --- ---      --- ---      --- ---
        |   |   |--> |   |   |--> |   |   |--> nil
         --- ---      --- ---      --- ---
          |            |            |
          |            |            |
           --> rose     --> violet   --> buttercup

   In this diagram, each box represents a slot that can hold or refer to
any Lisp object.  Each pair of boxes represents a cons cell.  Each arrow
represents a reference to a Lisp object, either an atom or another cons
cell.

   In this example, the first box, which holds the CAR of the first
cons cell, refers to or "holds" `rose' (a symbol).  The second box,
holding the CDR of the first cons cell, refers to the next pair of
boxes, the second cons cell.  The CAR of the second cons cell is
`violet', and its CDR is the third cons cell.  The CDR of the third
(and last) cons cell is `nil'.

   Here is another diagram of the same list, `(rose violet buttercup)',
sketched in a different manner:

      ---------------       ----------------       -------------------
     | car   | cdr   |     | car    | cdr   |     | car       | cdr   |
     | rose  |   o-------->| violet |   o-------->| buttercup |  nil  |
     |       |       |     |        |       |     |           |       |
      ---------------       ----------------       -------------------

   A list with no elements in it is the "empty list"; it is identical
to the symbol `nil'.  In other words, `nil' is both a symbol and a list.

   Here are examples of lists written in Lisp syntax:

     (A 2 "A")            ; A list of three elements.
     ()                   ; A list of no elements (the empty list).
     nil                  ; A list of no elements (the empty list).
     ("A ()")             ; A list of one element: the string `"A ()"'.
     (A ())               ; A list of two elements: `A' and the empty list.
     (A nil)              ; Equivalent to the previous.
     ((A B C))            ; A list of one element
                          ;   (which is a list of three elements).

   Here is the list `(A ())', or equivalently `(A nil)', depicted with
boxes and arrows:

         --- ---      --- ---
        |   |   |--> |   |   |--> nil
         --- ---      --- ---
          |            |
          |            |
           --> A        --> nil

Dotted Pair Notation

An alternative syntax for lists.

Association List Type

A specially constructed list.