22
$\begingroup$

In my Algorithms and Data Structures course, professors, slides and the book (Introduction to Algorithms, 3rd edition) have been using the word NIL to denote for example a child of a node (in a tree) that does not exist.

Once, during a lecture, instead of saying NIL, my classmate said null, and the professor corrected him, and I don't understand why professors emphasise this word.

Is there a reason why people use the word NIL instead of null, or none, or any other word? Does NIL have some particular meaning that the others do not have? Is there some historical reason?

Note that I have seen also a few places around the web where, e.g., the word null was used instead of NIL, but usually this last one is used.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
32
$\begingroup$

As far as I'm concerned, null, nil, none and nothing are common names for the same concept: a value which represents the “absence of a value”, and which is present in many different types (called nullable types). This value is typically used where a value is normally present, but may be omitted, for example an optional parameter. Different programming languages implement this differently, and some languages might not have any such concept. In languages with pointers, it's a null pointer. In many object-oriented languages, null is not an object: calling any method on it is an error. To give a few examples:

  • In Lisp, nil is commonly used to stand for the absence of a value. Unlike most other languages, nil has structure — it's a symbol whose name is "NIL". It's also the empty list (because a list should be a cons cell, but sometimes there is no cons cell because the list is empty). Whether it's implemented by a null pointer under the hood, or as a symbol like any other, is implementation-dependent.
  • In Pascal, nil is a pointer value (valid in any pointer type) that may not be dereferenced.
  • In C and C++, any pointer type includes a NULL value which is distinct from any pointer to a valid object.
  • In Smalltalk, nil is an object with no method defined.
  • In Java and in C#, null is a value of any object type. Any attempt to access a field or method of null triggers an exception.
  • In Perl, undef is distinct from any other scalar value and used throughout the language and library to indicate the absence of a “real” value.
  • In Python, None is distinct from any other value and used throughout the language and library to indicate the absence of a “real” value.
  • In ML (SML, OCaml), None is a value of the any type in the type scheme 'a option, which contains None and Some x for any x of type 'a.
  • In Haskell, the similar concept uses the names Nothing and Just x for the values and Maybe a for the type.

In algorithm presentations, which name is used tends to stem from the background of the presenter or the language that is used in code examples.

In semantics presentations, different names may be used to refer to e.g. the NULL identifier which denotes a pointer constant in the language, and the $\mathsf{nil}$ value in the semantics. I don't think there's any standard naming scheme, and some presentations leave it up to a font difference, or don't go into concrete syntax at all.

It's possible that your lecturer wants to use the word null for a null pointer constant in the programming language used in the course (Java or C#?), and NIL to denote the absence of a node in some data structures, which may or may not be implemented as a null pointer constant (for example, as seen above, in Lisp, NIL is often not implemented as a null pointer). This distinction would be relevant when discussing implementation techniques for data structures. When discussing the data structures themselves, the null-pointer-constant concept is irrelevant, only the not-equal-to-any-other-value concept matters.

There is no standard naming scheme. Another lecturer or textbook could use different names.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Two more examples. Objective C has both NULL (for C compatibility) and nil; calling methods on nil is a no-op. JavaScript has both null (a value representing nothing) and undefined (the value is not even set). $\endgroup$
    – 200_success
    Jul 15, 2015 at 19:42
  • 1
    $\begingroup$ "In object-oriented languages, null is not an object: calling any method on it is an error." – This is not true for all languages, including some of the languages you listed. In Ruby and Smalltalk, nil is an object like any other, it's an instance of NilClass, there is no other concept of "null-ness", and in particular, there is no null-pointer. In Scala, Nil is very much distinct from null, null is kinda-sorta like a null-pointer, however, it actually has a type (Null), Nil is a regular old object, the singleton instance of the EmptyList class if you will, and there is also … $\endgroup$
    – Jörg W Mittag
    Jul 15, 2015 at 21:07
  • 1
    $\begingroup$ … Nothing which is the bottom type and has no instance, and Unit which is the type of subroutines that don't return a value and has the singleton instance (). null somehow carrys with it the notion of "null pointer" or "null reference", not because that is somehow inherent in the term but simply because of the ubiquity of languages like C, C++, D, Java, C#, that use it in this manner. NIL does not carry this connotation, even though it is actually used that way e.g. in Pascal, Modula-2 and Oberon. In Ruby, nil has many useful methods: nil.to_i # => 0, nil.to_s # => '', … $\endgroup$
    – Jörg W Mittag
    Jul 15, 2015 at 21:12
  • 1
    $\begingroup$ … nil.to_a # => [], nil.to_h # => {}, nil.to_f # => 0.0, nil.inspect # => 'nil', and so on. You can see the full list here. $\endgroup$
    – Jörg W Mittag
    Jul 15, 2015 at 21:16
  • 1
    $\begingroup$ @alper No. 0 is a number, it is not “null” in the computer programming sense of the word. A few low-level languages (especially C and C++) use 0 in a pointer context to designate a null pointer, but outside of that using a number where a number is not expected is just confusing. $\endgroup$
    – Gilles 'SO- stop being evil'
    Aug 24, 2022 at 12:30
5
$\begingroup$

I believe the reason for the use of both nil and null is that the former is primarily a noun, and the latter primarily an adjective (I checked on the web and in my paper dictionnary: American Heritage 1992).

Regarding meaning and history, NIL is a contraction from Latin "nihil" which means "nothing".

To my knowledge, the use of the name nil to denote a null pointer was introduced with the programming language Lisp (1958).

A null pointer is a pointer value that is supposed to point to nothing, and should thus not be dereferenced. In most cases, pointers are simply memory addresses. Any variable (i.e., any location) that is intended to contain such a pointer will always contain some configuration of bits, and any such configuration can be read as a memory address. Hence it is often the case that the value nil will be the address of a memory area that is forbidden to the program, thus causing some form of failure (possibly interrupt) if the program attempts to dereference nil, which can only be an error.

Having a unique predefined standard value to play this role is essential in languages using pointers explicitly, since it is important to be able to test whether a pointer is atually pointing to some memory location, or not. Typically, in Lisp, a list was built as a succession of "cons" pairs containing a "car" pointer to a list element and a "cdr" pointer to the next pair. In the last pair of the list, the second pointer was nil.

This corresponds to the recursive definition of a list as either an empty list, or a list element concatenated to a list. Hence a list with no element was represented by nil. This empty list happens to be the identity of the list monoid.

Since lists can be used to represent sets, the empty set can in that case also be represented by nil.

Thus nil was historically a special pointer value, but came to be understood as a special identity value for other more abstract domains, such as lists or sets.

A pointer equal to nil was a null pointer, null being a adjective rather than a substantive (i.e. a noun).

The coordinated use of both word, as adjective and noun is quite consistent with other practice. The qualifier null is often used for the zero of an algebraic structure, such as the identity of a monoid: the null element. Lists form a monoid, where the value nil is the identity. The same is true of sets (though they form an algebra with many more properties). One says similarly that an integer is null when it is zero.

There are lots of variations on the use of these words an others, such as none, depending on authors and idiosyncrasies of programming languages.

The two major connotations are, as explained above

  • as a standard "undefined value", actually representing the absence of any usable value.

  • as identity value of some domain

This shows that it is not quite accurate to assert that NIL is "a value which represents the “absence of a value", as done by Gilles in the accepted answer. It depends on the language and its uses. The programming language LISP probably introduced NIL in the programming terminology 55 years ago. In LISP, NIL is the empty list, and can equivalently be noted () which is the natural representation of the empty list. It does not represent the absence of a value. It is sometimes used as place-holder for missing values, though that is often to be avoided precisely because the empty list is a value. What stands for a missing value in a structure in any arbitrary object, chosen by the programmer, that cannot be confused with acceptable values.

The two concepts are rather different, even though we have shown above that they can be related. It might be interesting to have a mode detailed taxonomie of the use of the terminology enumerated by Gilles'answer, to see whether the uses of each of these words are oriented more towards one connotation or the other.

Names are no more than what they are assigned to mean in a given context, by whoever is defining the discourse. Some uses are more common, more natural, or more consistent, but one should always check for definitions and make sure what meaning was intended in each context. And one should not always expect terminology to have been chosen with taste or consistency.

Improve this answer
$\endgroup$
1
$\begingroup$

NIL is an object with a value that tells the programmer the object is not valid. It's particularly useful in C++ where NULL is defined as 0. If you de-reference NULL in C++, you get undefined behavior. If you de-reference NIL (a pointer to an empty object that you defined), you get an object that you can tell is beyond the end of your data structure. It's great for preventing catastrophic program failures and detecting errors.

You can use NIL in cases like doubly-linked lists, having it be the beginning and end of the list to keep track of both the head and tail, and make sure that ->next and ->prev pointers never de-reference NULL.

Improve this answer
$\endgroup$
3
  • $\begingroup$ As far as I can see, this is simply incorrect. There is no "NIL" in C++. $\endgroup$
    – David Richerby
    Jul 15, 2015 at 17:54
  • 1
    $\begingroup$ I think you misinterpreted my answer. The link you provided has no correlation with my answer. I proposed that nil is a user-defined object, defined on a per-class basis, to point to an empty (but valid) object of that class. $\endgroup$
    – abastion
    Jul 15, 2015 at 18:02
  • $\begingroup$ The way you write "NIL is an object" (my emphasis) rather than, say "NIL can be defined as an object" makes it look like you're describing a language feature, rather than a style of programming. However, if your answer is purely about a programming style, it's not really on topic, here. $\endgroup$
    – David Richerby
    Jul 15, 2015 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.