Chapter 3 - Essential Lisp in Twelve Lessons

Lesson 4 - Putting things together, and taking them apart

CONS

CONS is the most basic constructor of lists. It is a function, so it evaluates both of its arguments. The second argument must be a list or NIL.

 (cons 1 nil)
 (1)

 (cons 2 (cons 1 nil))
 (2 1)

 (cons 3 (cons 2 (cons 1 nil)))
 (3 2 1)

CONS adds a new item to the beginning of a list. The empty list is equivalent to NIL,

()  NIL

so we could also have written:

 (cons 1 ())
 (1)

 (cons 2 (cons 1 ()))
 (2 1)

 (cons 3 (cons 2 (cons 1 ())))
 (3 2 1)

In case you're wondering, yes, there's something special about NIL. NIL is one of two symbols in Lisp that isn't a keyword but still has itself as its constant value. T is the other symbol that works like this.

The fact that NIL evaluates to itself, combined with () NIL, means that you can write () rather than (QUOTE ()). Otherwise, Lisp would have to make an exception to its evaluation rule to handle the empty list.

LIST

As you may have noticed, building a list out of nested CONS forms can be a bit tedious. The LIST form does the same thing in a more perspicuous manner:

 (list 1 2 3)
 (1 2 3)

LIST can take any number of arguments. Because LIST is a function, it evaluates its arguments:

 (list 1 2 :hello "there" 3)
 (1 2 :HELLO "there" 3)

 (let ((a :this)
        (b :and)
        (c :that))
     (list a 1 b c 2))
 (:THIS 1 :AND :THAT 2)

FIRST and REST

If you think of a list as being made up of two parts -- the first element and everything else -- then you can retrieve any individual element of a list using the two operations, FIRST and REST.

 (setq my-list (quote (1 2 3 4 5)))
 (1 2 3 4 5)

 (first my-list)
 1

 (rest my-list)
 (2 3 4 5)

 (first (rest my-list))
 2

 (rest (rest my-list))
 (3 4 5)

 (first (rest (rest my-list)))
 3

 (rest (rest (rest my-list)))
 (4 5)

 (first (rest (rest (rest my-list))))
 4

Clearly, chaining together FIRST and REST functions could become tedious. Also, the approach can't work when you need to select a particular element when the program runs, or when the list is of indeterminate length. We'll look at how to solve these problems in Chapter 4 by defining recursive functions. Later, in Chapter 13, we'll see the functions that Lisp provides to perform selection on the elements of lists and other sequences.

FIRST and REST are fairly recent additions to Lisp, renaming the equivalent functions CAR and CDR, respectively. CAR and CDR got their names from an implementation detail of one of the earliest Lisp implementations, and the names persisted for decades despite the fact that the underlying implementation had long since changed.