false

[willc%tekchips.CRL%tektronix.tek.com@RELAY.CS.NET]

I would like to request that the next revision of the Scheme
report not specify whether the empty list counts as true or
as false.

I think we all recognize that the empty list counts as false
only because Scheme came out of a Lisp tradition in which NIL
served as both the empty list and as the false value.  When
we decided to distinguish #f from the empty list, we felt
that we had to make allowances for existing implementations
that confuse the two.  Since such implementations could not
possibly have the empty list count as true, we made it count
as false.  This was a mistake; we should have left it
unspecified, just as it was unspecified whether the empty
list was distinct from #f.

The R3RS states quite explicitly that the reason the empty
list counts as false is "for compatibility with existing
programs and implementations that assume this to be the
case".  As I explain later in this message, compatibility
can be maintained without requiring that all implementations
perpetuate this mistake; we did not realize this at the time.

Existing implementations would not have to change.  They
could take advantage of the underspecification to have the
empty list continue to count as false, just as many
implementations take advantage of the loophole that lets
the empty list be identical to #f.

Five or ten years from now, after we've required the empty
list to be distinct from #f, perhaps we can require that the
empty list count as true.  Not now.

REASONS FOR CHANGE

If we are thinking of formal standardization, we should keep
things out of the standard that we might regret later.  The
fact that the empty list counts as false falls into that
category.

Having the empty list count as false makes it harder to do
type inference, because for example you can't tell whether
a procedure that returns the empty list is supposed to return
a boolean or a list.

That is why it is considered bad style for a programmer to
write '() when returning a boolean value, because this makes
it hard for human readers to do the "type inference".  The
existence of implementation modes that detect the use of the
empty list as a boolean would help programmers to develop
better style.  (For example, my translations of the Gabriel
benchmarks into Scheme have many such stylistic horrors,
but it was impractical for me to track them down because
I didn't have an implementation that would catch them for
me.)

The way that the R3RS is written encourages readers to believe
that the empty list is distinct from #f.  So far as I know, it
goes out of its way to allow them to be the same only in the
English description of NULL?.  This shows that we expected
future implementations of Scheme to distinguish #f from the
empty list.

People learning Scheme are confused if the empty list is the
same as #f (unless their brains have already been addled by
exposure to some other dialect of Lisp).  This shows that
future implementations of Scheme should distinguish #f from
the empty list.

One of the things that discourages implementors from making
the empty list distinct from #f is the fact that the empty
list counts as false.  On many architectures this makes it
slower to test a boolean value (unless the implementor
biases the representations to take this problem into account,
which would probably make other operations slower).  In
MacScheme, for example, testing a boolean return value
currently looks like

        cmp.l   #F,RESULT
        beq     ---

but would look like

        cmp.l   #NULL,RESULT
        beq     ---
        cmp.l   #F,RESULT
        beq     ---

if #f were different from the empty list.

So the change is useful to preserve our flexibility for the
future, for type inference/checking, to encourage good
style, and to prevent implementations that work the way we
intended and the way users expect from paying a (very small)
performance penalty.

COMPATIBILITY

Suppose I want to build an implementation in which the empty
list does not count as false.  (I do.)  Won't I be breaking
a lot of code?

Surprisingly not.  I can provide a compiler switch that
people can use to compile their code as though the empty
list counts as false.  That will keep users of old code
happy without penalizing writers of new code.

What about the procedure library?  The only standard Scheme
procedure affected by the change is the NOT procedure.  I
will thus have to provide two versions of NOT, one for
compatibility with old code and another for new code, and
have the compiler switch arrange to compile in an environment
which differs from the standard environment only for NOT.

Not all implementors will want to take even this minimal
trouble to support a compatibility mode, and that's fine.
All I'm asking is that Scheme let me and like-minded
implementors support a "progressive" mode in which the
empty list counts as true, and let me and like-minded users
write code using that mode.

What do you say?

BOOKS

>From glancing at S&ICP and TLL, I don't think they would be
significantly affected by this.  Both are written as though
(= 3 4) returns the symbol NIL, so they would be no less
accurate than before.  Abelson and Sussman early define
false as NIL and true as non-NIL, and use the terms "true"
and "false" throughout the rest of the book, so there are
only a couple of pages where a teacher would have to make
a correction, and teachers have to make a correction there
even now.

William Clinger