Why do we need `nil`?

Question

I do not see why we need nil [1] when to cons a sequence (so-called proper list) of items. It seems to me we can achieve the same goal by using the so-called improper list (cons-ed pairs without an ending nil) alone. Since Lisps [2] have already provided a primitive procedure to distinguish between a pair? and an atom (some implementations even provide atom?), when defining a procedure on a list, e.g., length, I can do the same with just dotted-pairs, as shown below:

(define len
  (lambda (l)
    (cond ((pair? l) (+ 1 (len (cdr l))))
          (else 1) ) ) )

It is obvious that we can apply this procedure to an improper list like '(1 . (2 . 3)) to get the expected answer 3, in contrast to the traditional (length '(1 2 3)).

I'd like to hear any opinions in defense of the necessity of nil. Thanks in advance.

[1] Let's ignore the debate among nil/NIL, '() and ().

[2] Here it means the Lisp family of languages.

Answer 1

Working with lists without nil (or '()) would be like doing arithmetic without zero. Using only pairs without nil, how would we represent an empty list, or a singleton list '(1)?

It gets worse: since lists don't have to be lists of atoms, but can contain other lists, how would we represent the nested list '(1 2 (3 4))? If we do the following conversions:

'(3 4) => '(3 . 4)
'(1 2 x) => '(1 . (2 . x)) == '(1 2 . x)

we get:

'(1 2 (3 4)) => '(1 . (2 . (3 . 4))) == '(1 2 3 . 4)

But also:

'(1 2 3 4) => '(1 . (2 . (3 . 4))) == '(1 2 3 . 4)

So constructing lists only using pairs and no nil prevents us from distinguishing between a nested list structure and a flat list, at least at the end of the list. You can still include nested lists as any element except the last, so now there's a strange and arbitrary limitation on what the elements of a list can be.

More theoretically, proper lists are an inductively defined data type: a list is either the empty list, or it has a first element, which can be anything, and a rest, which is always another list defined in the same way. Take away the empty list, and now you have a data type where the rest might be another list, or it might be the last element of the list. We can't tell except by passing it to pair?, which leads to the problem with nested listing above. Keeping nil around lets us have whatever we like as list elements, and allows us to distinguish between 1, '(1), '((1)) and so on.

Answer 2

You need it to represent "Nothing".