The empty list

My friend Zyni pointed out that someone has been getting really impressively confused and cross on reddit about empty lists, booleans and so on in Common Lisp, which led us to a discussion about what the differences between CL and Scheme really are here. Here’s a summary which we think is correct.

A peculiar object in Common Lisp¹

In Common Lisp there is a single special object, nil.

• This represents both the empty list, and the special false value, all other objects being true.
• This object is a list and is the only list object which is not a cons.
• As such this object is an atom, and again it is the only list object which is an atom.
• You can take the car and cdr of this object: both of these operations return the object itself.
• This object is also a symbol, and it is the only object which is both a list and a symbol.
• The empty list when written as an empty list, (), is self-evaluating.

Some comments.

• It is necessary that there be a special empty-list object which is a list but not a cons: the things which are not necessary are that it be a symbol, and that it represent falsity.
• Combining the empty list and the special false object can lead to particularly good implementations perhaps.
• The implementation of this object is always going to be a bit weird.
• It is clear that the empty list cannot be any kind of compound form so requiring it to be quoted — requiring you to write '() really — serves no useful purpose. Nevertheless I (Tim) would probably rather CL did that.
• Not having to quote nil on the other hand is not at all strange: any symbol can be made self-evaluating simply by (defconstant s 's), for instance.
• The graph of types in CL is a DAG, not a tree: it is not at all strange that there is an object whose type is both list and symbol.

Some entirely mundane things in Common Lisp

• There is a symbol, t which represents the canonical true value. Nothing is magic about this symbol in any way: it could be defined by (defconstant t 't).
• There is a type, boolean which could be defined by (deftype boolean () '(member nil t)), except that it is required that boolean be a recognisable subtype of symbol. All implementations we have tried recognise (member nil t) as a subtype of symbol, but the standard does not require them to do so. Additionally (type-of 't) must return boolean we think.
• There is a type, null, which could be defined by (deftype null () '(member nil)) or (deftype null () '(eql nil)), with the same caveats as above, and (type-of nil) should return null.
• There are types named t (top of the type graph) and nil (bottom of type graph).

These mundane things are just that: they don’t require implementational magic at all.

Three peculiar objects in Scheme

In Scheme there is an object, ().

• () is the special object that represents the empty list.
• It does not represent false.
• It is not a symbol.
• It is the only list object which is not a pair (cons): list? is true of it but pair? is false.
• You can’t take the car or cdr of it.
• It is not self-evaluatiing.

There is another object, #f.

• #f is the distinguished false value and is the only false value in Scheme, all other objects being true.
• It is not a symbol or a list but satisfies the boolean? predicate.
• It is self-evaluating.

There is another object, #t.

• #t represents the canonical true value, but all objects other than #f are true.
• It is not a symbol or a list but satisfies the boolean? predicate.
• It is self-evaluating.

Some comments. - Scheme does not have such an elaborate type system as CL and, apart from numbers, doesn’t really have subtype relations the way CL does.

A summary

CL’s treatment of nil clearly makes some people very unhappy indeed. In particular they seem to think CL is somehow inconsistent, which it clearly is not. Generally this is either because they don’t understand how it works, because it doesn’t work the way they want it to work, or (usually) both. Scheme’s treatment is often cited by these people as being better. But CL requires precisely one implementationally-weird object, while Scheme requires two, or three if you count #t which you probably should. Both languages have idiosyncratic evaluation rules around these objects. Additionally it’s worth understanding that things like CL’s boolean type mean essentially nothing implementationally: boolean is just a name for a set of symbols. The only thing preventing you from defining a type like this yourself is the requirement for type-of to return the type.

Is one better than the other? No: they’re just not the same. Certainly the CL approach carries more historical baggage. Equally certainly it is perfectly consistent, and changing it would break essentially all CL programs that exist.

Thanks to Zyni for most of this: I’m really writing it up just so we can remember it. We’re pretty confident about the CL part, less so about the Scheme bit.