NIL Considered Harmful

Drew McDermott

January 13, 2006

NIL plays at least four different roles in CL programming:

 

·         It's a symbol, the one with name "NIL"

 

·         It means "false"

 

·         It means "empty list"

 

·         It means "don't care"

 

(One could argue that there are others. For instance, in a pathname, NIL means "field absent.")

 

The "don't care" role may seem odd, but in fact it's fairly common to return nil in a context where the value will be ignored.  For instance, you might write a function 'look-it-up' that returns two values, a boolean and an S-expression.  If the first value is true, the second value has some useful meaning.  If the first value is false, er, I mean, NIL, then the second value has no meaning at all, and should be ignored by anyone who calls look-it-up.  I assume that in this case look-it-up returns something like (values nil nil). (You might make a case for writing (values nil) instead, but I dislike relying on Lisp's default behavior when returned multiple values disagree in number with what the caller expects.)  Perhaps there are people out there who write (values nil ':dontcare); even cooler might be to write (values nil <ub>), where <ub> causes a variable to become unbound if the variable gets it as a value, but I don't think there's a portable way to do that (but see below).

 

But I digress.  The point is that nil is over-overloaded in Common Lisp.  This probably doesn't matter to most people, but I am interested in the subject of type-checking CL code, and nil is almost un-type-checkable. 

 

Actually, perhaps it should matter even to the programmer-on-the-street.  I find it rather annoying that lists I type in like these:

   '((a) () (b c))
   '(t nil nil t)

 

simply cannot be printed in a consistent way.  By playing games with the pretty-printer (see below), you can choose either

 

   ((a) nil (b c))
   (t nil nil t)

or

   ((a) () (b c))
   (t () () t)

but doing better would require some hairy heuristics that looked at the context of each occurrence of nil. 

 

In the input direction, the problem is somewhat alleviated by being able to write #.'() and #.false  (see below), but this is pretty ugly.  We could also import Scheme's #t and #f, but they don't solve the underlying problem, which is that there simply is no unambiguous representation, readable or otherwise, of false that distinguishes it from the empty list.

The problem here is not just visual. The fact is that Lisp really has no consistent way of representing a tree of symbols, because the empty list is a symbol, so there is no way of knowing, independent of context, whether () is a leaf of the tree or a node with no children.

The same problem arises in connection with Lisp's "semipredicates," functions that return either "false" or some useful value. For instance, member and assoc return either NIL, indicating that they didn't find what they were looking for, or a piece of the list they were searching. The idea works in these two cases because the empty list can never be the kind of substructure that member or assoc returns. In other cases, one always has to think carefully about whether the empty list might be one of the "useful values" the semipredicate might return. If it is, then some further gimmick must be found to distinguish between false and the empty list, because, for no good reason, they are identical. Furthermore, it is all too easy to change the "useful domain" of the semipredicate and forget that it now includes the empty list or the symbol nil.

I will now describe the set of tricks I have adopted to work around these problems, to the extent they can be worked around.  If you don't like clever hacks that disturb the way Lisp normally works, this is another chance to stop reading.  But you really haven't proved yourself Lisp-enlightened until you start thinking of ways to disturb how it normally works.

 

First, of course, one never uses t and nil to mean true and false, when one can write

 

   (defconstant true t)
   (defconstant false nil)

 

And while we're at we can define

   (defconstant nil* 'nil)
for the rare occasions when we want to refer to the symbol nil.

 

And of course one never ever writes (if possibly-empty-list ...); writing

(if (not (null possibly-empty-list)) ...)

 

reminds the reader that possibly-empty-list is a list, not a Boolean.  (I assume every compiler in the world generates the same code in either case.)

Using the empty list as a constant in code is the next problem to address. All the best authorities recommend writing '() in code when the empty list is meant. That's fine, but you might as well write 'nil, because they look the same to Lisp, and hence to any type checker. Also, if you print the code, that 'NIL will appear again, and it gets to be irritating.

The solution is to define

  (defmacro empty-list ()
    ''())

So we can write (empty-list), except that it's way too long. I use #\! as a dispatch-macro-char with several subcases, so it's natural to choose !() as the read/printed form of (empty-list):

(make-dispatch-macro-character #\!)

(set-dispatch-macro-character #\! #\(
   (lambda (srm ch n)
      (declare (ignore n))
      (setq ch (peek-char t srm))
      (cond ((char= ch '#\) )
             (read-char srm)
             '(empty-list))
            (t
             (let ((thing (read srm)))
                (cerror "!(~s...) has too much stuff before close paren"
                        thing))))))

(set-pprint-dispatch
    '(cons (eql empty-list))
    (lambda (srm el)
       (cond ((null (cdr el))
              (format srm "!()"))
             (t
              (pprint-fill srm el true))))
    2)

Now we can write code that looks like this:

;; Compute a list of all combinations of elements of l taken
;; n at a time.
(defun combinations (l n)
   (cond ((> n (length l)) !())
         (t
          ;; From now on we know 0 =< n =< (length l)
          (labels ((proper-combos (l n)
                      (cond ((= n 0) (list !()))
                            ((= (length l) n)
                             (list l))
                            (t
                             (nconc
                                (proper-combos (cdr l) n)
                                (mapcar (lambda (c)
                                           (cons (car l) c))
                                        (proper-combos
                                           (cdr l) (- n 1))))))))
             (proper-combos l n)))))

In Allegro CL, if we macroexpand-1 this definition, we get:

(progn (eval-when (:compile-toplevel)
         (excl::check-lock-definitions-compile-time 'combinations 'function
           'defun (fboundp 'combinations))
         (push 'combinations excl::.functions-defined.))
       (progn (eval-when (:compile-toplevel)
                (excl::check-de-argdecl-change 'combinations 'nil))
              (declaim (excl::dynamic-extent-arguments () combinations)))
       (setf (fdefinition 'combinations)
             (let ((excl::f
                    (named-function combinations
                      (lambda (l n)
                        (block combinations
                          (cond ((> n (length l)) !())
                                (t
                                 (labels ((proper-combos
                                           (l n)
                                           (cond
                                            ((= n 0) (list !()))
                                            ((= (length l) n) (list l))
                                            (t
                                             (nconc
                                              (proper-combos (cdr l) n)
                                              (mapcar
                                               (lambda (c) (cons (car l) c))
                                               (proper-combos
                                                (cdr l)
                                                (- n 1))))))))
                                   (proper-combos l n)))))))))
               (excl::set-func_name excl::f 'combinations)
               excl::f))
       (remprop 'combinations 'excl::%fun-documentation)
       (record-source-file 'combinations) 'combinations)

Note that the occurrences of (empty-list) are printed correctly as !()

There's one more use of nil: as a "don't care" indicator. For this we use the symbol '_', in two roles. Although it goes beyond the scope of this note, we can change the definitions of defun and other variable-binding constructs so that an occurrence of '_' may be used wherever a variable is expected, and will be taken to mean that the variable is to be ignored. For example, (lambda (x _ y) ...) is equivalent to

   (lambda (x #:g9999 y)
      (declare (ignore #:g9999))
      ...)
This convention is implemented in the YTools system.

In harmony with that convention, we arrange that an occurrence of '_' in an evaluated context means that its value is irrelevant. All we have to do is define it as a constant or symbol macro. What should its value be? It's tempting to try something nontraditional (such as a random value, different every time the system is recompiled?), but the simplest thing is to let it have as value our good old friend, nil. So in the hypothetical function look-it-up I described above, we can write the returned expression as (values false _).

Finally, although there is no way to fix the printing problem described above, the following works as well as anything.  I arrange that nil prints as NIL unless it appears in a pretty-printed list.  That is, I alter the set-pprint-dispatch entry for type specifier cons thus:

(defvar save-system-pprint-tab* (copy-pprint-dispatch))

(defvar normal-cons-printer*
        (pprint-dispatch '(foo) save-system-pprint-tab*))

(defvar print-nil-as-nil* false)

(defun pprint-fill-tricky (srm list &optional (colon? t) atsign?)
  (declare (ignore atsign?))
  (multiple-value-bind (builtin-printer found)
                       (pprint-dispatch list save-system-pprint-tab*)
     (cond ((and found
                 (not (eq builtin-printer normal-cons-printer*)))
            (funcall builtin-printer srm list))
           (t
            (pprint-logical-block (srm list
                                     :prefix (if colon? "(" "")
                                     :suffix (if colon? ")" ""))
              (pprint-exit-if-list-exhausted)
              (loop as ele = (pprint-pop)
                  do (if (and (null ele)
                              (not print-nil-as-nil*))
                         (write-string "()" srm)
                       (write ele :stream srm))
                     (pprint-exit-if-list-exhausted)
                     (write-char #\space srm)
                     (pprint-newline :fill srm)))))))

(set-pprint-dispatch 'cons #'pprint-fill-tricky)

(Thanks to Steve Haflich for helping me debug an earlier version of this idea.)

Now that I think about it, this is pissing into the wind, but I'd rather die on my feet than be dry on my knees.