The Book: Whats the difference between the concept of NIL and NULL in Lisp vs. the definition of them in Chapter 6?

Hi everyone!

The following might be a bit nitpicky without a practical purpose. The Book states:

Each item in a cons list contains two elements: the value of the current item and the next item. The last item in the list contains only a value called Nil without a next item. A cons list is produced by recursively calling the cons function. The canonical name to denote the base case of the recursion is Nil . Note that this is not the same as the “null” or “nil” concept in Chapter 6, which is an invalid or absent value.

I don't quite get the last sentence. In this context, Nil pretty much sounds like an absent "next" value to me. Please note that this quote is also referring to Lisp, a programming language that I have never personally used. A quick search revealed that NULL is the type of NIL in Lisp.

So what does the last sentence in the quote mean?

The way I read it is that it saying "null" or "nil" are invalid or absent values.

By contrast the "Nil" is an empty list. That is not invalid. It's not missing either. It's just empty.

I'd interpret it as Nil being of value nothing, just like how one might say in colloquial English that the price of something is nil.

Nill/null on the other hand I'd interpret as the absence of a value as one would traditionally understand.

Nil is the equivalent to 0 for HLists.

The reference to chapter 6 is probably for the section The Option Enum and Its Advantages Over Null Values, which discusses implicit in null (or nill, etc) values in pointer / reference types, which does not exist in rust.

The Nil in the quoted paragraph is the lisp Nil, which is very similar or even the same thing when writing lisp code, but when implementing a cons list in rust (maybe as a part of implementing a lisp interpreter in rust), it is not the absense of a List value, but instead a specific value from the List enum.

Both are sentinel values, but with some differences. The most important difference is that lots languages with references or pointers allow putting in null as a reference or pointer value, so they can use the common null as a sentinel. The Rust example is typical of Rust - it uses a Nil that has a type specific to the list, not using a "common null".

So if you look at chapter 6.1, you'll see that this section quotes Tony Hoare's famous "Billion-dollar mistake" quote:

I call it my billion-dollar mistake. At that time, I was designing the first comprehensive type system for references in an object-oriented language. My goal was to ensure that all use of references should be absolutely safe, with checking performed automatically by the compiler. But I couldn’t resist the temptation to put in a null reference, simply because it was so easy to implement. This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years.

This is talking about null as a fundamental language concept: A value that is allowed to show up anywhere (or in the case of Java, mostly anywhere) to indicate a missing value. Rust doesn't have anything like this. Rust's fundamental pointer types are all non-null (both in the "nonzero" sense and in the "not billion-dollar mistake" sense), and we use types like Option<T> and Result<T, E> to explicitly denote values that may not be present.

This is different from the usage in chapter 15, which is using Nil specifically as a name for "the empty list."

That said, NIL in Lisp has many other uses, which causes it to some similarities to the concept of null (though they aren't as meaningful given that LISP is not statically-typed). I'm not sure why the text feels necessary to draw this comparison, and I don't feel like it really adds anything.

1 Like

Ah but... That wikipedia entry says this about sentinels :

The sentinel value is a form of in-band data that makes it possible to detect the end of the data when no out-of-band data (such as an explicit size indication) is provided. The value should be selected in such a way that it is guaranteed to be distinct from all legal data values since otherwise, the presence of such values would prematurely signal the end of the data (the semipredicate problem).

That is a special value of a type being used to indicate something other than a value of the type.

So a pointer of value zero in C does not mean there is data at address zero, but rather there is no data (Or you made a bug). Or MAX_INT might indicate "no data here" when used in some algorithm looking at an array of integers.

By contrast the the Nil being discussed in the book is defined with:

enum List {
    Cons(i32, List),
    Nil,
}

Clearly it is not just a special, "in-band", value of the Cons type, it is a out of band indication using a totally different type.

In short I would not describe that Nil as a sentinel.

Nil is a sentinel of the List type. (And Cons is a variant, not a type.)

In that example they are creating a list of integers. Clearly the Nil is not a special value, sentinel value, of those integers. That would be "in band".

That list is held together by Box<> pointers. The Nil is not a special value of those either. The Nil is a separate out of band indication.

As such I can't classify that Nil as a sentinel by the wikipedia definition and in in the sense of I have seen the term used since forever.

But never mind, terminology has a habit to adopt different meanings in different contexts. Everyone knows what you mean.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.