[kazinator]

> having CAR and CDR take lists instead of conses.

(car nil) and (cdr nil) safely returning nil was introduced in InterLisp, according to Gabriel's HOPL palper. At some big Lisp summit in the early 1970's, InterLisp decided to adopt MacLisp's readtables, and MacLisp adopted (car nil) -> nil.

Why the empty list is a symbol is natural: math uses symbols to refer to such things. For instance the empty set is notated both {} and ∅: empty braces or the special null set symbol.

I mean, why have symbols refer to things in a language that is consciously oriented toward symbolic processing, whose initial creators were people with math backgrounds? It's pretty much a forgone no-brainer.

[lisper]

Having a symbol DENOTE the empty list and having a symbol be THE SAME OBJECT as the empty list are two very different things. The former is perfectly reasonable. The latter causes no end of difficulties.

[kazinator]

The former is somewhat reasonable for having pi denote 3.14159... and such.

It brings in its own difficulties. If nil is a variable/constant which evaluates to some nil object, then to talk about nil itself, we have to quote it.

The object which it denotes doesn't print as nil; it has its own printed rep like () and we will end up seeing that printed rep and using it. So then we have two nil representations to deal with: the nil variable which we can use in evaluated contexts, and the literal nil like () that we use elsewhere.

If () isn't self-evaluating (like the criminally stupid design in Scheme), we have to quote it: '().

If we have additional semantic roles for () like it being Boolean false and the bottom of the type spindle, those uses are not nicely served by the () notation, from an esthetic point of view.

The list terminator is de facto a symbol because it's exploited for its identity: we care whether the cdr of a cons is or is not nil, and that's all. That's a symbolic behavior; we might as well complete things so that the symbol functions work with nil; it can have a property list, name and so on.

[lisper]

> to talk about nil itself, we have to quote it.

So? That's no different than if you want to talk about 'pi rather than pi a.k.a. 3.14159...

> So then we have two nil representations to deal with

No different than "pi" and "3.14159".

> If () isn't self-evaluating (like the criminally stupid design in Scheme), we have to quote it: '().

I agree, () should be self-evaluating just like numbers and vectors. The behavior of () should be analogous to the behavior of 0 or 0.0 or #() or "".

> If we have additional semantic roles for () like it being Boolean false

And why would you want to do a stupid thing like that?

> The list terminator is de facto a symbol because it's exploited for its identity

First, the list terminator need not be the same thing as the empty list. The list terminator is an implementation thing. The empty list is a language-semantics thing. These need not be the same.

Second, neither of these need to be unique. There can be multiple list terminators, and there can be multiple empty lists, just as there can be multiple empty vectors and multiple empty strings and even multiple instances of the same number (which actually happens with bignums).

> we care whether the cdr of a cons is or is not nil

No, what we care about -- or at least what we should care about -- is whether the CDR of a cons is an (n.b. not the) empty list. (eq #() #()) need not be true (in fact, generally isn't). Why should (eq () ()) be any different?

And BTW under no circumstances should taking the CAR or CDR of an empty list do anything other than signal an error.

[kazinator]

> First, the list terminator need not be the same thing as the empty list.

No it doesn't, but that choice happens to give us a compact recursive definition.

> There can be multiple list terminators ... multiple empty lists ...

Sure, and 2022 can be written MMXXII, and whatnot.

Mathematically, there is one empty list, so why proliferate it?

There can be multiple empty strings which is useful if strings are mutable. If strings are immutable, it's silly to have more than one empty string.

The empty list is immutable, so ...

> under no circumstances should taking the CAR or CDR of an empty list do anything other than signal an error.

Lisp 1 and 1.5 had it that way, certainly. It's mostly just inconvenient. A good mix is to have strict vectors and strings which signal on out-of-bounds, but lists which are forgiving. Forgiving lists allow good old Ashwin Ram to have:

  (cdr (assq key a-list))

rather than

  (let ((val (assq key a-list)))
     (cond ((not (null? val)) (cdr val))
          (else nil)))

[lisper]

> If strings are immutable, it's silly to have more than one empty string.

I guess Common Lisp is silly then.

    Clozure Common Lisp Version 1.12.1 (v1.12.1-10-gca107b94) DarwinX8664
    ? (eq "" "")
    NIL

> (cdr (assq key a-list))

Much better to have an abstract associative map (dictionary) type with an opaque implementation rather than punning cons cells (which locks you in to an O(n) implementation). ALists are interesting from a historical point of view but they should never be used in modern code without hiding them under a layer of abstraction.

And even if you are going to pun cons cells to build an associative map, alists are the wrong way to do it because it forces you to duplicate the keys for every frame. Much better to use D-lists ((key1 key2 ...) val1 val2 ...) because that lets you re-use the key list, which can cut your memory usage in half, and provides a much more straightforward path from interpreter to compiler for pedagogical purposes.

[kazinator]

Strings aren't immutable in Lisp, so there isn't a huge benefit to making (eq "" "").

It may be undefined behavior to modify "", but it's not the same thing. Suppose that mutating "" signals an error; that still leaves the problem that some other string which you are allowed to mutate can be mutated empty, yet is a distinct object from that empty string.

Moreover, though every string has "" as a suffix, it's not by way of pointing to a "" object. A unique "" wouldn't serve the role of terminator.

A language with immutable strings could intern all strings, so they are de facto symbol, and then exact string comparison is eq. That implies there is only one empty string object.