Lisp / Scheme : Evaluating nested empty list/cons : (())

Question

I'm using this Lisp compiler for testing

There is one things that I don't get it : If an empty list () evaluate to itself :

(format t "~:a" ())
;; => ()

why do evaluating several nested empty list () don't evaluate to an empty list ?

(format t "~:a" (()))
;; => EVAL: undefined function NIL
;; why not () ?

(format t "~:a" ((())))
;; => EVAL: (NIL) is not a function name; try using a symbol instead
;; why not () ?

From my point of view, () and NIL are the same, so the inner empty list should first evaluate to itself, then the outer list should "call" the newly inner evaluated empty list

I my head, I see it like this should happen when doing the calculation: (bold + italic = what is currently evaluated)

(()) => (()) => (()) => ()

Seem like Scheme also don't allow nested empty list call

Thank for reading

Answer 1

In Common Lisp and its ancestors, the empty list, (), is self evaluating by special dispensation: it's the only list which has this property. It's also the only list which is also a symbol, in this case the symbol nil (really NIL). It's tempting to think that, somewhere in the guts of the implementation something just said the equivalent of (defconstant nil ()), but it's much more magic than that:

> (eq () 'nil)
t

> (symbolp ())
t

> (symbol-name ())
"NIL"

It's not just the value of the symbol nil, it is the symbol nil. () is really very magic in CL. More magic than it is in Scheme, say: in Scheme it's still magic just rather less so. In Scheme, () is the only list which is not a pair (a cons), but it is not also a symbol and it is not self-evaluating.

So, OK, that explains why () evaluates to itself: it does so because it is magic.

So now consider trying to evaluate this form:

(())

Well, first of all this is not the empty list: its a list with one element, which is the empty list. From the point of view of evaluation it is a compound form. Well, as the empty list (the first element of this list) is also nil we can rewrite this compound form as

(nil)

This is the same thing: (equal '(nil) '(())) is true.

OK, well now what does the evaluator do with compound forms? It looks at their first element and decides what to do (see here.

• If it is a symbol, then the symbol should name one of

  • a special operator
  • or a (possibly local) function
  • or a (possibly local) macro

  and it will be processed accordingly.

• If it is not a symbol it may be a list beginning (lambda ...) which is turned into an anonymous function and called.

• There are no more cases.

Well, which is (()), or equivalently (nil)? It's a compound form, and the first element of it is the symbol nil. So

• does nil name a special operator? no -- (special-operator-p 'nil) is false;
• does nil name a macro? no -- (macro-function 'nil) is false;
• does nil name a function? No - (fboundp 'nil) is false.

So the evaluator can't process this form: it's not legal.

---

Note that in Scheme the same thing would also be not legal, but for slightly different reasons: for Scheme, the empty list is not self-evaluating, so the evaluator sees (()) and says (ignoring macros this time) that this is a procedure call, where the procedure is going to be the result of evaluating (), but that's an error. If I said (define nil '()) then (nil) would still be an error: it would evaluate nil and get (), but () is not a procedure.

---

A surprising thing about CL is that (()) can be given (local) meaning. This is, amazingly enough, conforming CL:

(flet ((() () ()))
  (()))

It's conforming because you're allowed to locally establish function definitions for symbols in CL if they do not have global function definitions:

If an external symbol of the COMMON-LISP package is not defined as a standardized function, macro, or special operator, it is allowed to lexically bind it as a function (e.g., with flet), to declare the ftype of that binding, and (in implementations which provide the ability to do so) to trace that binding. -- CLHS

And then () is the symbol nil which does not have a global function definition.