15

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.

Drew
  • 29,895
  • 7
  • 74
  • 104
Jan Wrobel
  • 6,969
  • 3
  • 37
  • 53
  • 4
    I edited your post to use `defun` and not `define`, which is from Scheme. I don't expect that you're talking about Scheme, since Scheme doesn't have `nil`, it doesn't allow you to pass in an empty list to `car` and `cdr`, and the use of direct list mutation is much more frowned-upon in the Scheme community. – C. K. Young May 17 '13 at 10:24
  • 2
    there's also the [*head sentinel* technique](http://stackoverflow.com/search?q=user%3A849891+head+sentinel), for your personal use: start with non-empty singleton list, say `(1)` or whatever; process it surgically in a uniform manner and return its `cdr` in the end. Allows for nice code simplification at a price of one extra cons cell allocation. – Will Ness May 17 '13 at 17:23

4 Answers4

17

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.

Kaz
  • 55,781
  • 9
  • 100
  • 149
  • I don't think people really try to pass Ruby off as a Lisp. Really?! Also, funny stab at Scheme in the last paragraph. ;-) – C. K. Young May 18 '13 at 16:09
16

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.

C. K. Young
  • 219,335
  • 46
  • 382
  • 435
4

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.

6502
  • 112,025
  • 15
  • 165
  • 265
  • And because of this Common Lisp lists are also somehow strange, because the answer to 'are lists mutable?' is 'sometimes'. – Jan Wrobel May 18 '13 at 08:59
  • 2
    @JanWrobel Lists are an illusion. The real data is in the conses and the `nil`. Conses are mutable. `nil` is not. That's all. – C. K. Young May 18 '13 at 15:54
  • @ChrisJester-Young: agree about the illusion; discussing mutability of list in CL is nonsense because lists are not objects. However much of the Lisp idea doesn't need to depend on this approach and you can build a lisp dialect where `list` is a first class object. For example I've built a lisp compiler targeting javascript that uses js array objects to represent lists (there's no `CAR` and no `CDR` and sharing is possible only at element level and not at tail level). So far I'm quite happy with this solution. – 6502 May 18 '13 at 19:06
  • Don't forget: And it's the logical false value! (That `nil` is so many things is the one CL feature I hate. Requires workaround code. All the other warts are so unimportant as to be not worth mentioning given CL's utility and (sometimes awkward) beauty.) – Mars May 29 '13 at 02:22
3

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

tripleee
  • 175,061
  • 34
  • 275
  • 318
  • Yes, I know about the identity, but I was wondering about the internal representation. So it is not possible to have an append-value function with consistent interface regarding its argument? – Jan Wrobel May 17 '13 at 10:15
  • 1
    @JanWrobel As I mentioned in my answer, your interface should be to return the new value, which may be the same list or not, depending on whether you were able to modify it in-place. Callers should use the return value, regardless, reassigning back to their variable if necessary. – C. K. Young May 17 '13 at 10:18