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

[lisper]

> Strings aren't immutable in Lisp

Neither are lists. Only the empty list is immutable, and likewise empty strings. It really is a completely equivalent situation. There is no principled reason that the empty list should be unique and the empty string not.

[kazinator]

Yes there is a principled reason. If we accept that we have a list which is recursively defined using a binary cell aggregate structure, as a right-leaning tree shape, then it is advantageous to have an atomic, unique empty list at the bottom of the recursion. That atomic empty list can be represented as a machine word. We can perform a single comparison to detect the terminator: is it that object or not? Anything else, though workable, is a gratuitous complication.

The empty string is mutable. Even the literal one is potentially mutable: you can try it at your own risk. You ca make a mutable empty string with (make-string 0) or by mutating a non-empty string.

Any mutable string can be mutated to make it empty:

   (delete #\a (make-string 3 :initial-element #\a)) -> ""

Since strings aren't linked structures with a terminator, the comparison is moot.