Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question

migrated from stackoverflow.com Apr 16 '12 at 15:12

This question came from our site for professional and enthusiast programmers.

9  
"For example, the string terminator in C is the null pointer.", no, the string terminator in a C string is the character NUL, it just happens to share a numeric value with (most) NULL pointers (the integral value 0). –  Vatine Apr 16 '12 at 15:29
1  
The null pointer in C doesn't have a numeric value. Casting a null pointer to an integer type yields some unspecified value (not necessarily 0), and a literal 0 is a null pointer constant, but pointers are not numbers. –  Keith Thompson Apr 16 '12 at 19:33
    
As some answers note, Lisp is dynamically typed, and allows you to stick anything you want in the cdr cell -- but the resulting object is then known as an "improper list". This is arguably a philosophical distinction, but it has practical consequences, since an extra value must be handled differently from regular list elements. –  comingstorm Apr 16 '12 at 22:36
1  
Since nobody answered it and since I’m too lazy, I suspect the real reason is that it makes sense, mathematically: Peano’s axioms. –  Konrad Rudolph Apr 17 '12 at 1:00
    
Nobody answered what? I mentioned the mathematical slant in my response 3 hours earlier. Every list has an empty list as its suffix, similarly to how every set has the empty set as subset, or every sequence has the empty sequence as a subsequence. And since Lisp lists (the data structure) are suffix-based, ... –  Kaz Apr 17 '12 at 21:31

5 Answers 5

up vote 14 down vote accepted

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).

enter image description here

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.

share|improve this answer
    
I'm talking specifically about Scheme here, but I thought the same thing was true in all Lisps. In Scheme, nil is the same as (). –  Skilldrick Apr 16 '12 at 3:45
1  
Ok, according to both en.wikipedia.org/wiki/Cons and cs.cmu.edu/Groups/AI/html/cltl/clm/node9.html nil is the empty list. –  Skilldrick Apr 16 '12 at 3:47
2  
"Next, what about a representation for empty sequence? Looking at the representation of a non-empty sequence it appears natural to take NIL as R[()] (empty sequence - A.Y.) since after you have removed all the elements from the sequence NIL is all that is left in the representation" -- Anatomy of Lisp. –  Andrey Yazu Apr 16 '12 at 3:52
    
@Skilldrick In Scheme, nil is not the same as (). The symbol nil is not special in any way and has no predefined binding (does not evaluate to itself) and has nothing to do with the () object. The SICP book causes confusion about this because it uses nil in Scheme examples in early chapters, without making it clear that the student must define nil as a variable to make those examples work. –  Kaz Apr 16 '12 at 22:50
    
OK, that makes a lot of sense. I see now that the empty list is equivalent to the terminator, because the empty list consists of nothing but the terminator. Thanks! –  Skilldrick Apr 20 '12 at 5:37

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.

share|improve this answer

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,

share|improve this answer

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.

share|improve this answer

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.