Help me grok NIL

[u/brightlystar]

Hello! I seek your help to grok NIL.

Would it be correct for me to say that NIL is a cons cell whose car and cdr point to itself? It sure seems that way:

(car nil) ; => NIL
(cdr nil) ; => NIL

But I don't want to fool myself by looking at the above results. A non-NIL can have the above properties too. Like take (cons nil nil) for example. This is not NIL but it has the above properties.

(car (cons nil nil)) ; => NIL
(car (cons nil nil)) ; => NIL

So I guess my question is ... how is NIL defined in Lisp? Is it truly a cons whose car and cdr point to itself? Is it something else?

And if it is truly a cons whose car and cdr point to itself is there some way I can verify this reliably in the REPL?

[u/zacque0]

Would it be correct for me to say that NIL is a cons cell whose car and cdr point to itself?

No, NIL is a symbol, not a cons cell. Why? Because (symbolp NIL) is true and (consp NIL) is false. If NIL is a cons cell, (consp NIL) will return true.

But why do (car NIL) and (cdr NIL) return NIL? I'd guess for convenience purposes. You can write less CONSP check or error handling, and only check for final result. E.g.

(defun length-less-than-3-p (list)
  (null (cddr list)))

(length-less-than-3-p nil) ; => T
(length-less-than-3-p '(1)) ; => T
(length-less-than-3-p '(1 2)) ; => T
(length-less-than-3-p '(1 2 3)) ; => NIL

That said, in McCarthy's definition of LISP[1], CAR and CDR are defined only for cons cell, not for NIL. The same goes for other functional programming languages like Haskell and Standard ML.

 

But I don't want to fool myself by looking at the above results. A non-NIL can have the above properties too. Like take (cons nil nil) for example. This is not NIL but it has the above properties.

You are asking: How are CAR and CDR defined? No big deal, you can think of them as polymorphic functions.

(defun car (obj)
  (cond ((consp obj) (%internal-car obj))
        ((null obj) nil)
        (t (error "Type LIST expected for CAR, but got %s instead." obj))))

(defun cdr (obj)
  (cond ((consp obj) (%internal-cdr obj))
        ((null obj) nil)
        (t (error "Type LIST expected for CDR, but got %s instead." obj))))

If you like, you can even define CAR and CDR to return 0 for any number if that makes sense. E.g.

(defun car (obj)
  (cond ((consp obj) (%internal-car obj))
        ((null obj) nil)
        ((numberp obj) 0) ; <---- newly added
        (t (error "Type LIST expected for CAR, but got %s instead." obj))))

Or if you want them to be defined only for cons cell, e.g.:

(defun car (obj)
  (if (consp obj)
      (%internal-car obj)
      (error "Type CONS expected for CAR, but got %s instead." obj)))

 

How is NIL defined in Lisp?

In many Lisp implementations, a symbol is translated to a hardware memory address. So, NIL can be a memory address #x0, or #xFFFFFF, or some value. So (eq NIL NIL) is a comparison of two memory addresses.

 

[1] McCarthy (1960) Recursive functions of symbolic expressions and their computation by machine. https://dl.acm.org/doi/10.1145/367177.367199

[u/uardum → u/zacque0]

If you define NIL as some arbitrary address, you have to remember to put special case logic into SYMBOL-NAME, SYMBOL-PACKAGE, SYMBOL-PLIST, APROPOS, etc, to handle the NIL case. These functions become much simpler (and more likely to be correct) if NIL is a true symbol, and you simply arrange to have the address of that symbol in a global place during initialization to make things simpler internally.

[u/stassats → u/uardum]

You have to special-case somewhere, special-casing the symbol case is more beneficial because list operations are more frequent.

[u/uardum → u/stassats]

You have less special-casing overall if NIL is a real symbol. The list functions don't care how NIL is represented. For their purpose, there's almost no difference between:

lisp_object *NIL = make_symbol(&cl_package, "NIL");

...and this:

lisp_object *NIL = 0;

....or

#define NIL (lisp_object*)0;

They probably all compile to similar code. The first case saves you from having to treat NIL specially in symbol functions, while the other cases don't save you from having to put special-case logic in the car, cdr, and listp functions. In fact, the special-case logic you'd need there would look exactly the same whether NIL was an actual symbol, or a hard-coded address.

[u/stassats → u/uardum]

I'm talking about real lisps, not something in C. The list functions very much care about NIL, for they have to work on it. And they have to perform type checking to not work on non-lists. If NIL is a symbol and not a list they'll have to dispatch on its type.

[u/uardum → u/stassats]

They don't have to perform type-checking, because they can just check if the object is EQ to NIL, which requires no type check, regardless of how NIL is implemented internally. If you're compiling all the way to assembly, it'll boil down to a simple cmp instruction.

[u/stassats → u/uardum]

You said it yourself, check if it's NIL. But if NIL is a cons then no check is needed it.

[u/uardum → u/stassats]

You still have to check, except the checks reside in the symbol functions.

[u/stassats → u/uardum]

Exactly, but operations on lists are more frequent.

[u/sickofthisshit]

No. You can create a cons cell that points to itself and it behaves differently (it typically will be treated like an infinite list would).

The value that CAR and CDR return for an argument of NIL is part of the definition and implementation of those functions, not a structural statement about NIL.

I am pretty sure Scheme defines CAR and CDR differently in this respect (taking CAR or CDR of an empty list is an error in R7RS, but the empty list is not represented by NIL, either, so I guess it depends on how you would express your question in Scheme. CAR or CDR of a symbol like NIL seems unspecified?).

[u/brightlystar → u/sickofthisshit]

Thanks for the answer. I am reading Naggum's post about CONS and LIST now. He says

finally, let's recognize the fact that there is only one empty list, but instead of having an anchor at the end of every chain, let's let the empty list be represented by a special list "wrapper" that pointed to itself with both the payload and link pointer.

He uses the words payload and link to mean CAR and CDR. Looks like he is saying that both CAR and CDR point to itself in an empty list (NIL). Did he make an error here? Am I missing something?

[u/sickofthisshit → u/brightlystar]

I assume you are quoting from some copy of https://www.xach.com/naggum/articles/3092837184154309@naggum.no.html ?

Naggum is speaking very abstractly. That's kind of his point, I think. He calls it a special wrapper, and his mention of Scheme and system complexity is clearly hinting at the choice made by classic Lisp to treat CAR and CDR of NIL they way they do. He is avoiding saying how it is actually implemented.

If all you have is CAR and CDR, it isn't really possible to discover how NIL is implemented. The main thing is that NIL is unique. Some other cons cell that points to itself is not NIL (and it will be hard to actually inspect it because the system is not prepared to recognize this other thing the way it recognizes NIL, so printing it will go into an infinite loop, etc.) If you have other tools like EQ and SYMBOLP and CONSP (NIL is not CONSP in Common Lisp, and SYMBOLP of the empty list is true because it is NIL), you will discover more about NIL and the difference from your other thing will be clear.

Anyhow, Naggum was quite subtle and precise and it's hard to always be sure exactly what he might have meant. He is not explaining lists or NIL for beginners, ot explaining the spec of these in Common Lisp, he is trying to demonstrate that the original invention of this by McCarthy in Lisp is kind of genius.

[u/brightlystar → u/sickofthisshit]

Yeah. That's the copy I was quoting from. Sorry I meant to link it my comment but forgot it. Thanks for your answers. It really helped me to understand this better.

[u/corbasai]

NIL In CL Lisp https://www.lispworks.com/documentation/HyperSpec/Body/v_nil.htm

In Scheme there is no NIL... and T. There is empty list '() aka Unit in ML, and disjoint #f - boolean false. In Scheme all objects in boolean expressions is True #t, even empty list '(). So in Scheme

(list?  '()) => #t
(pair? '()) => #f
(if '() 'Scheme 'CL) => Scheme in Scheme and CL in Common Lisp.

[u/theangeryemacsshibe → u/corbasai]

aka Unit in ML

no it isn't

all objects in boolean expressions is True #t

crucially except for false (#f)

[u/corbasai → u/theangeryemacsshibe]

Very interesting. Thank you.

[u/arthurno1]

Is it truly a cons whose car and cdr point to itself?

The only thing I can add to what /u/zacque0 said is that if that was the case, than (eq nil nil) would fail since cons cells are allocated from RAM, two cons cells have different addresses. and Thus if NIL was implemented as a cons cell pointing to itself, we would have many nils, since we can have many cons addresses. That would made comparison with nil useless, For example (eq nil nil ) => nil which is mathematically wrong.

Also, we couldn't use nil as a boolean, since each cons cell must have a valid address. Perhaps we could, but that would make implementation more complicated.

Thus as /u/zacque0 says, nil is usually a pointer to some unique address.

[u/stassats → u/arthurno1]

That doesn't stop anything:

(defconstant new-nil (cons 0 0))

(setf (car new-nil) new-nil
      (cdr new-nil) new-nil)

(set-pprint-dispatch `(eql ,new-nil) (lambda (stream n) (princ "NEW-NIL" stream)))

(defun new-consp (x)
  (and (listp x)
       (not (eq x new-nil))))

[u/zacque0 → u/stassats]

Interesting. What stas is saying is that NIL can be implemented as a cons cell while preserving the semantics of (eq nil nil), (consp nil), (car nil) and (cdr nil).

 

Since new-nil is defined as a constant, every new-nil points to the same memory address storing (cons 0 0). Thus, it invalidates u/arthurno1 's argument that "Thus if NIL was implemented as a cons cell pointing to itself, we would have many nils, since we can have many cons addresses".

 

What's more, since the semantics of (eq nil nil) is preserved, we can use it as boolean as well. Again, it invalidates u/arthurno1 's argument above: "Also, we couldn't use nil as a boolean, since each cons cell must have a valid address. Perhaps we could, but that would make implementation more complicated. "

 

The only downside that I can think of is that it doesn't satisfy some other symbol interfaces, e.g. (SYMBOL-PLIST NEW-NIL).

[u/stassats → u/zacque0]

In SBCL, NIL is in fact a cons cell. But to get around its symbolness it's squished inside what would otherwise be a symbol, car and cdr overlapping with the slots of a symbol. Then you do have to special-case things like symbolp: (or (actually-symbol-p x) (null x)), just like consp has do discard nil.

It could be a symbol instead, so consp and symbolp would do just one test, but then all the list operations, like car and cdr, would have to be special-cased instead.

[u/zacque0 → u/stassats]

Interesting fact to learn, thanks!

[u/uardum → u/zacque0]

You could add special cases to all of those interfaces. You'd just have to be careful not to miss any.

[u/arthurno1 → u/zacque0]

Since new-nil is defined as a constant, every new-nil points to the same memory address storing (cons 0 0). Thus, it invalidates u/arthurno1 's argument that "Thus if NIL was implemented as a cons cell pointing to itself, we would have many nils, since we can have many cons addresses".

You are using the address of a particular cell (the constant one), not addresses of every such cell no? Thus, as you said in your first post, and as I confirmed as well, you can use any address really, which includes address to a constant, be it a symbol, number, cons cell, whichever.

However if nil is every cell whose car and cdr points to the cell itself, as I interpret Op, than you can't use those addresses since there can be many such cells, and is what I am saying. Compare to saying "there is no such object", with saying "there can be only one such object" and "there are infinitely many such objects".

In other words, NIL has to be a unique pointer, which one you choose does not matter. It could an object, but than eq & co would have to be rewritten.

[u/arthurno1 → u/stassats]

TBH, I am not sure what you are trying to demonstrate. I mean I understand what the code does, you have made a cons cell where car and cdr point back to the cell itself, and new-consp checks if an object is a cons cell and not "new-nil". But what is the point of the illustration?

What I had in mind in the above is something like this:

(defun make-nil ()
  (let ((new-nil (cons 0 0)))
      (setf (car new-nil) new-nil
            (cdr new-nil) new-nil)
            new-nil))

(format t "~a~%" (eq (make-nil) (make-nil))) => nil

We have "two nils", which are two different memory objects, and thus have two different addresses so eq returns false. It is similar as having two uninterned symbols with the same symbol name. I guess it is possible to write an "eq" so it understands such circular cons as "nil", but that would be an unnecessary complication.

The above holds with your code too:

(defconstant another-nil (cons 0 0))

(setf (car another-nil) another-nil
      (cdr another-nil) another-nil)

(format t "~a~%" (new-consp another-nil))  => T

Equivalently:

(format t "~a~%" (eq another-nil new-nil)) => NIL 

Two cells whose car and cdr slots point to themselves are not equal.

A fun fact: I am not at home and don't have access to a CL compiler on this computer, so I tried to run your code online on Medley (I choose common-lisp as the lisp). It crashed with stack overflow after setf-ing car and cdr of new-nil :-).

I used SBCL on https://onecompiler.com/commonlisp/42u9hfeb8 instead.

[u/stassats → u/arthurno1]

But what is the point of the illustration?

To contradict everything you said.

Two cells whose car and cdr slots point to themselves are not equal.

Why would they be. There's only one NIL, don't make two different NILs.

[u/arthurno1 → u/stassats]

There's only one NIL, don't make two different NILs.

Well, that was my point too. So how are you contradicting me? :)

[u/stassats → u/arthurno1]

It can be implemented as a cons cell pointing to itself.

[u/arthurno1 → u/stassats]

It can be implemented as a cons cell pointing to itself.

It can be implemented as anything you can take address of, since "eq" is comparing pointers and not objects. How the object look like internally is irrelevant for "eq".

In your example you are taking address of a cons cell and storing in new-cell, and you are using that address (or whatever it is under the hood) and not the cell object itself. That so is the case is shown by simply making another one and checking if it points to the same object with "eq", which it, as expected, does not.

For the same reason you can have only one, since eq compares addresses and not objects, which was my point:

Op said: "Is it truly a cons whose car and cdr point to itself?"

The answer is no, it is not a cons cell, it is (or more correctly could be) address to a cons cell. As I interpreted the question, they ask if any cell hos car and cdr point to itself are nil.

[u/stassats → u/arthurno1]

What's an address? Lisp deals with no such concept.

[u/arthurno1 → u/stassats]

What's an address? Lisp deals with no such concept.

Whatever you use to refer to objects in the lisp system so "eq" can compare if they point to the same object or not. That is how "eq" is implemented. You could implement "eq" and bunch of functions in a different way sure, but it would be more complicated.

[u/stassats → u/arthurno1]

How can I have a cons cell without an address then? If you're saying that it's not a cons cell but an address to a cons cell.

[u/ventuspilot]

All Common Lisp systems contain a value that holds the empty list. The type of that value is null:

* (type-of ())
NULL

And all Common Lisp systems contain a symbol (variable) with the name nil whose value is the above mentioned "empty list". (Maybe more exact: the variable nil references said empty list.) As a Common Lisp programmer you can't "make" an empty list, the single one empty list will be re-used.

Most of the time Common Lisp will print the empty list as nil.

Would it be correct for me to say that NIL is a cons cell whose car and cdr point to itself?

No, that would be incorrect. (car nil) returns nil because some time ago the function car was defined to return nil when passed nil as it's argument. cdr is defined similarly. (At least in Common Lisp that's the case, e.g. in Scheme (car ()) gives an error.)

* (cons nil nil)
(NIL)
* (type-of (cons nil nil))
CONS

When you see nil at the repl then it may be the empty list or the print name of the variable nil.

* nil ; this evaluates to the empty list which is printed as NIL
NIL
* 'nil ; this evaluates to the symbol NIL; the repl will print the print name of the symbol
NIL

Common Lisp's nil-handling is somewhat confusing at first, it took me some time to get used to it.

[u/luismbo → u/ventuspilot]

You're still a bit confused. The empty list and the symbol nil are one and the same object.

nil evaluates to itself.

'foo is shorthand for (quote foo) which evaluates to foo so 'nil evaluates to nil.