Is an empty list in Lisp built from a cons cell?
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
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.