Why is the empty list used as the list terminator in Lisp?

Question

It seems to me that the list terminator in Lisp could be any arbitrary value. For example, the string terminator in C is the null pointer. Is there a philosophical reason why the empty list was chosen to terminate lists?

Answer 1

A Lisp list is not really terminated with an empty list -- it's terminated with a special value, traditionally called nil. As it happens, that also traditionally evaluates as false -- which makes it about as close to C's null pointer as you can get (in C, a null pointer constant is an integer constant equal to zero, which also evaluates to false).

An empty list is basically just a rather short-hand way of expressing NIL -- since you don't even have a single cons cell, all you're left with is the NIL that terminates the list. In other words, it's not that a list is terminated with an empty list -- it's that an empty list consists of only a terminator.

Using dot notation, it's possible to link cons cells together in other ways, but the result isn't a "list" as the term is normally used.

Answer 2

Lisp lists don't really have a 'terminating' value. Actually Lisp does not even have a primitive list data structure. Lists are built out of the empty list and a chain of linked cons cells pointing to list contents.

Lists are recursively defined:

• the empty list is ()
• a list newlist is the result of (CONS element list), where (FIRST newlist) is element and (REST newlist) is list.

A list is empty when it is the empty list or (NULL list) is true.

Because newlist is the result of (CONS element list) it is actually a cons cell object and `(CONSP newlist) is true.

In older times FIRST was called CAR and REST was CDR. Today it is good style to use in list operations FIRST and REST. CAR and CDR is better used when one exploits the feature that something (tree, queue, list, ...) is built out of cons cells.

Historically (and still in Common Lisp which aims to be backwards compatible), the empty list is also the unique symbol NIL. The empty list evaluates to itself and it is also the false value. In the Lisp-dialect Scheme, the empty list is NOT the false value.

CL-USER 12 > (setq l1 ())
NIL

CL-USER 13 > (setq l2 (cons 1 (cons 2 l1)))
(1 2)

CL-USER 14 > (consp l1)
NIL

CL-USER 15 > (consp l2)
T

CL-USER 16 > (null l1)
T

CL-USER 17 > (null l2)
NIL

CL-USER 18 > (first l2)
1

CL-USER 19 > (rest l2)
(2)

CL-USER 20 > (rest (rest l2))
NIL

CL-USER 21 > (consp (rest l2))
T

CL-USER 22 > (consp (rest (rest l2)))
NIL

Answer 3

I will give you the philosophical answer to your philosophical question:

It seems to me that the list terminator in Lisp could be any arbitrary value. [...] Is there a philosophical reason why the empty list was chosen to terminate lists?

The answer to your question is this: the list terminator is an arbitrary value. It is so arbitrary that different Lisp dialects use a different value for it and yet remain conceptually compatible.

Common Lisp uses a symbol object: the symbol nil. A symbol! What does a symbol have to do with lists? Nothing.

(Except that when we work with mathematical objects with pencil and paper, we use symbols. A circle with a dash through it or {} represent an empty set, etc. So why not use machine symbols similarly?)

Scheme uses an empty list, the object () which is not a symbol.

The Scheme () and the Common Lisp nil are quite different, yet they adequately terminate a list, exactly in line with your observation that it could be any arbitrary value!

So therefore, is there a philosophical reason why the empty list terminates lists? Yes! The reason is that any object which is understood to terminate a list is, by definition, the empty list. If you use the number 42 as the list terminator, then () means 42.

Mathematically, every list has the empty list as its suffix (just like every set has the empty set as a subset). Since the Lisp list representation is suffix-based (a non-empty list is an reference to an object holding the first element, and the suffix of that list), there has to be something to handle the case when a list has just one element, and its proper suffix is (mathematically) the empty list. Whatever object is installed as the suffix is then understood to be the empty list, and for the sake of consistency and unity, that object better be used as the representation of the stand-alone empty list also, not only as the representation of the empty suffix of the one-element list.

Answer 4

This may be not language specific and somewhat anti-scientific explanation, but may give you some thoughts.

You could think about the language as a set of all facts pertaining to the "world" or "universe" created by that language. As this is a set, you would need to have a complement set for all facts excluded from the language, i.e. something to mean "not in this set". In certain light nil (or false or other variants of "nothingness" may be understood as "not in this set"). Since cons is one of the basic building blocks of the language, the atom that is taken to mean nothingness is used for any not yet created value. So, you don't terminate the list with an empty list (how then do you terminate empty lists?), it's just at some point there is nothing the cons is pointing to and nil is the way to tell that.

Answer 5

As Rainer and Jerry explained, Lisp lists are built from cons cells so it's not really and empty list. Conceptually it's often helpful to think this way when defining recursive functions though. It's a bit more obvious if we look at List data type definition in (for example) Haskell.

data List a = Cons a (List a)
            | Empty <<== nil in Lisp

What this says is that either we have a Cons cell with an element followed by a tail or an Empty list. So a list of 1 element is (Cons 1 Empty). This is helpful for defining recursive functions such as map.

map f (Cons e tail) = Cons (f e) (map f tail)
map f Empty = Empty

Which in Lisp could be

(defmethod fmap (f (lst cons))
  (cons (funcall f (car lst))
        (fmap f (cdr lst))))

(defmethod fmap (f (lst null))
  nil)

So conceptually thinking of a list as being terminated by the empty list can be very helpful,