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 The solution is to define
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): Now we can write code that looks like
this: In Allegro CL, if we
macroexpand-1 this definition, we get: Note that the
occurrences of There's one more use of
(defmacro 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)
;; 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)))))
(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)
(empty-list)
are printed correctly as !()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.