common-lisp Cons cells and lists Lists as a convention


Example

Some languages include a list data structure. Common Lisp, and other languages in the Lisp family, make extensive use of lists (and the name Lisp is based on the idea of a LISt Processor). However, Common Lisp doesn't actually include a primitive list datatype. Instead, lists exist by convention. The convention depends on two principles:

  1. The symbol nil is the empty list.
  2. A non empty list is a cons cell whose car is the first element of the list, and whose cdr is the rest of the list.

That's all that there is to lists. If you've read the example called What is a cons cell?, then you know that a cons cell whose car is X and whose cdr is Y can be written as (X . Y). That means that we can write some lists based on the principles above. The list of the elements 1, 2, and 3 is simply:

(1 . (2 . (3 . nil)))

However, because lists are so common in the Lisp family of languages, there are special printing conventions beyond the simple dotted pair notation for cons cells.

  1. The symbol nil can also be written as ().
  2. When the cdr of one cons cell is another list (either () or a cons cell), instead of writing the one cons cell with the dotted pair notation, the "list notation" is used.

The list notation is shown most clearly by several examples:

(x . (y . z))   === (x y . z)
(x . NIL)       === (x)
(1 . (2 . NIL)) === (1 2)
(1 . ())        === (1)

The idea is that the elements of the list are written in successive order within parenthesis until the final cdr in the list is reached. If the final cdr is nil (the empty list), then the final parenthesis is written. If the final cdr is not nil (in which case the list is called an improper list), then a dot is written, and then that final cdr is written.