Is an empty list in Lisp built from a cons cell?

Question

I'm trying to emulate Lisp-like list in JavaScript (just an exercise with no practical reason), but I'm struggling to figure out how to best represent an empty list.

Is an empty list just a nil value or is it under the hood stored in a cons cell?

I can:

(car '())
NIL
(cdr '())
NIL

but an empty list for sure can not be (cons nil nil), because it would be indistinguishable from a list storing a single nil. It would need to store some other special value.

On the other hand, if an empty list is not built from a cons cell, it seems impossible to have a consistent high-level interface for appending a single value to an existing list. A function like:

(defun append-value (list value) ...

Would modify its argument, but only if it is not an empty list, which seems ugly.

Answer 1

An empty list is simply the nil symbol (and symbols, by definition, are not conses). car and cdr are defined to return nil if given nil.

As for list-mutation functions, they return a value that you are supposed to reassign to your variable. For example, look at the specification for the nreverse function: it may modify the given list, or not, and you are supposed to use the return value, and not rely on it to be modified in-place.

Even nconc, the quintessential destructive-append function, works that way: its return value is the appended list that you're supposed to use. It is specified to modify the given lists (except the last one) in-place, but if you give it nil as the first argument, it can't very well modify that, so you still have to use the return value.

Answer 2

Believe it or not, this is actually a religious question.

There are dialects that people dare to refer to as some kind of Lisp in which empty lists are conses or aggregate objects of some kind, rather than just an atom like nil.

For example, in "MatzLisp" (better known as Ruby) lists are actually arrays.

In NewLisp, lists are containers: objects of list type which contain a linked list of the items, so empty lists are empty containers. [Reference].

In Lisp languages that aren't spectacular cluster-fumbles of this sort, empty lists are atoms, and non-empty lists are binary cells with a field which holds the first item, and another field that holds the rest of the list. Lists can share suffixes. Given a list like (1 2 3) we can use cons to create (a 1 2 3) and (b c 1 2 3) both of which share the storage for (1 2 3).

(In ANSI Common Lisp, the empty list atom () is the same object as the symbol nil, which evaluates to itself and also serves as Boolean false. In Scheme, () isn't a symbol, and is distinct from the Boolean false #f object. However Scheme lists are still made up of pairs, and terminated by an atom.)

The ability to evaluate (car nil) does not automatically follow from the cons-and-nil representation of lists, and if we look at ancient Lisp documentation, such as the Lisp 1.5 manual from early 1960-something, we will find that this was absent. Initially, car was strictly a way to access a field of the cons cell, and required strictly a cons cell argument.

Good ideas like allowing (car nil) to Just Work (so that hackers could trim many useless lines of code from their programs) didn't appear overnight. The idea of allowing (car nil) may have appeared from InterLisp. In any case, Evolution Of Lisp paper claims that MacLisp (one of the important predecessors of Common Lisp, unrelated to the Apple Macintosh which came twenty years later), imitated this feature from InterLisp (another one of the significant predecessors).

Little details like this make the difference between pleasant programming and swearing at the monitor: see for instance A Short Ballad Dedicated to the Growth of Programs inspired by one Lisp programmer's struggle with a bletcherous dialect in which empty lists cannot be accessed with car, and do not serve as a boolean false.

Answer 3

NIL is somewhat a strange beast in Common Lisp because

• it's a symbol (meaning that symbolp returns T)
• is a list
• is NOT a cons cell (consp returns NIL)
• you can take CAR and CDR of it anyway

Note that the reasons behind this are probably also historical and you shouldn't think that this is the only reasonable solution. Other Lisp dialects made different choices.

Answer 4

Try it with your Lisp interpreter:

(eq nil '())
=> t

Several operations are special-cased to do unorthogonal (or even curious :-) things when operating on nil / an empty list. The behavior of car and cdr you were investigating is one of those things.

The idenity of nil as the empty list is one of the first things you learn about Lisp. I tried to come up with a good Google hit but I'll just pick one because there are so many: http://www.cs.sfu.ca/CourseCentral/310/pwfong/Lisp/1/tutorial1.html