The empty list

It's a reference to the "Codeless Code" link I shared upthread: 'All nothings are not equal.' A language that supports null and empty list as separate things opens the risk "what happens when the user passes null to something expecting a list?"

It is, at least, something a language with good static typing can mitigate by disallowing null as a list argument. And then there's Java...

Technically not, because a cons of two objects is not eq to another cons of the same two objects.

  (eq (cons 1 2)
      (cons 1 2))
  ;; => nil

It's memory locations, after all.

I see, fair enough. I forgot to switch out of pure functional programming/referential transparency mode for this discussion. Fine, you can take NIL to be one particular (NIL . NIL) that's different from all other (NIL . NIL)s, the only particular (NIL . NIL) that is considered a list of length 0 while all other (NIL . NIL)s are lists of length 1.

Lists in python are what are called vectors in almost every other language.

You can make a resizable vector in CL and use vector-push-extend to do things just like python.

There's a huge amount of documentation telling you that NIL is an empty list.

It isn't. It has none of the mechanics of an empty list in Python etc.

It's more like a null link, and has quite a bit in common with /0 as a string terminator.

It does different things on its own and in the context of a list.

The key is that Lisp list items are stored as car (link/pointer to an item) and cdr (link to the next item/s in the list) pairs.

Lisp's dot notation makes this explicit, but it's hidden behind syntactic sugar because it's messy and hard to read.

     (a b c) is really (a . (b . (c . NIL)))

Each dot shows the cdr of the preceding car.

On its own NIL is just a constant. It has no listy features - specifically no slots for car or cdr values. Although you can do things like (length NIL) you can't change it. It's simply not a list.

You can add car/cdr pointers to it with cons. Now you can use NIL in a list.

You can use NIL as a cdr list terminator. (something . NIL) means the list is over. There are no more cdrs after it.

You can use NIL as an empty car placeholder. (NIL . something) means the car has no value, but the list continues onwards with a cdr link.

In your example (append NIL foo) actually returns (foo . NIL). NIL is being used as a cdr terminator. Lisp hides the ". NIL" because syntactic sugar.

If you (append NIL foo) again, you still get (foo) because NIL already terminates the list and there's no reason to add another NIL after it.

(push foo NIL) throws an error because push is destructive and is attempting to change NIL. Which isn't allowed.

(cons NIL a) gives you (NIL a) because NIL is being prepended as an empty car pointer. Which is how you get NILs into a list without it collapsing around itself. It's just like any other list item, except it has a null value. The list can continue past it into further cdrs in the usual way.

Anyway. This is confusing because you have a single symbol doing three different things in three different contexts. (Not even counting its use as a Boolean...) Worse, syntactic sugar and the various function internals hide this from you. And the documentation tells you something that isn't true.

So unless you look at the source and/or learn how the various functions understand and use NIL you will be confused.

The up side is a REPL is interactive and easy to play with, so it's not a huge effort to experiment and see what falls out.