predicates and generalized booleans
Erik Naggum
I'm sorry to interrupt the Java discussions with a simple Lisp question.
I needed a form that is t if a segment of an input string is empty, the
expression read from the substring if it is a complete expression, or the
bounding positions of the substring if end of file was encountered in
reading it. I had this in mind (slightly simplified):
(or (= start end)
(read-from-string buffer nil nil
:start start
:end end)
(cons start end))
but then I remembered something about generalized booleans, and looked up
`=' in ANSI X3.226. it seems that an implementation is free to return any
non-nil value as the result of comparing two equal numbers. now, this is
probably an academic issue, since no Common Lisp implementation I have ever
seen returns anything but t for true in such cases, so my question is not
what to do in practice, but why so many predicates were specified to return
a "generalized boolean" instead of just a "boolean".
the relevant glossary entry for "t" reads:
t ... 1. ... b. the canonical generalized boolean representing
true. (Although any object other than nil is considered true as a
generalized boolean, t is generally used when there is no special
reason to prefer one such object over another.) ...
clearly, `=' and the like do not have any such special reasons, so what
motivated the use of "generalized boolean" instead of "boolean"?
#\Erik
--
I'm no longer young enough to know everything.
Barry Margolin
In article <30695283...@naggum.no>, Erik Naggum <er...@naggum.no> wrote:
>what to do in practice, but why so many predicates were specified to return
>a "generalized boolean" instead of just a "boolean".
To allow implementors the most freedom to optimize. If, in the course of
implementing a predicate, the value of the predicate is equivalent (as a
generalized boolean) to some intermediate value, that value can simply be
returned. Or the implementor could ensure that some predicate returns a
particular type of true value that optimizes other calling code (portable
code can't make use of these optimizations, but internal implementation
code needn't be portable).
>clearly, `=' and the like do not have any such special reasons, so what
>motivated the use of "generalized boolean" instead of "boolean"?
Rather than go through every predicate and decide whether we could imagine
an implementation that would be more efficient if it could return a
generalized boolean, most predicates were simply defined to return a
generalized boolean.
I could imagine an implementation of /= that returns the difference between
the two values when they're not equal, rather than simply returning T.
--
Barry Margolin
BBN Corporation, Cambridge, MA
bar...@bbnplanet.com
(BBN customers, call (800) 632-7638 option 1 for support)
Kent Pitman
In article <30695283...@naggum.no> Erik Naggum <er...@naggum.no> writes:
Erik> now, this is probably an academic issue, since no Common Lisp
Erik> implementation I have ever seen returns anything but t for true in such
Erik> cases, so my question is not what to do in practice,
You've chided me too much on SGML style issues for the HyperSpec for me to let
a comment like this pass without comment. ;-): You should do "in practice"
what will keep your programs from breaking if you meat a new implementation.
If the language doesn't define it, don't go depending on it. The felicity of
an implementation "happening to return T" is not a guarantee that it always
will; it's just the implementors being sensible and realizing that when
nothing better is at hand, T is probably as reasonable as anything. That's
not much of a guarantee.
Erik> but why so many predicates were specified to return
Erik> a "generalized boolean" instead of just a "boolean".
Heh. You had to ask... Well, it's good for people to see into the process
sometimes, and to understand that there isn't the tiniest corner of the
language that doesn't have a huge amount of history behind it...
It's easy for the academics to criticize CL because they may not realize how
many people have lived and breathed the language and how hard-fought every
little agreement on language definition really was.
Surprising fact to know and tell: This change was made by Steele and the
original CLTL book committee, not by X3J13, prior to the 1984 when the first
CLTL was published. Check CLTL if you don't believe me... but first, read
the rest of this message so you can understand what you're looking for.
Interestingly enough, this issue was among a few dozen items raised in public
review and extensively discussed by the committee, so it can be said
definitively not to have been a casual oversight.
The change *I* made in the ANSI spec was to clarify the WORDING in a way that
made Steele's change (long unnoticed by many in the community) more visible.
Indeed, the entire concept of the ANSI glossary and the using of italic to say
"we mean this word formally, go look it up" was a reaction to the ambiguous
prose style used in Steele's original book. People would see a word like
"filename" and wonder what it meant; then they would read in the middle of
some function or macro's definition that a "filename" meant some particular
thing and they would wonder what the scope of that explanation was. So we
decided to move all the definitions to a centralized place (I think it was my
Editor-predecessor, Kathy Chapman, that had this idea and began this process.)
[No slight to Steele meant--he's done much good work and I respect him
enormously, but he and I both know that there's much to criticize in our
works, and we both try to be honest about the flaws. Lack of wording
precision was definitely a flaw in his, not so much brought out by lack of
care as much as by his choice of book design and organization. Kathy's
decision to change that pretty much forced better care in that regard.]
At some point, because people complained about the large number of fonts
in the hardcopy (e.g., slant meant "parameter" but italic meant "glossary";
this distinction doesn't occur in the HyperSpec and is one reason to still
sometimes prefer the official hardcopy to resolve subtle questions), I
created certain rules of usage. One of them was that every glossary word
that was a type name would mean the same as that type. Boolean was the
notable exception, because \term{boolean} did not mean what \typeref{boolean}
meant; the former meant "any non-nil value" and the latter meant "T or NIL".
So I completely overhauled the entire spec and changed every reference to
\term{boolean} to \term{generalized boolean} and defined THAT to mean
"any non-nil value", and I then introduced a new \term{boolean} that meant
"\conref{t} or \conref{nil}". That change was semantics-preserving but
really surprised a lot of people. I took that surprise as approval (even
though they didn't) because I felt very strongly that if it exposed a
surprising fact that was already true before the change, then that was among
the strongest possible demonstrations that the old wording was deficient
and the new wording was not.
The complaint that came out in public review came from Kaufmann,
Boyer, and Moore. The CLHS dates the comment at Apr 94, citing
document X3J13/94-305. We had a bunch of conversations with these guys
(and John McCarthy, as I recall) about their desire to do (EQ (test1)
(test2)) rather than (let ((r1 (test1)) (r2 (test2))) (or (and r1 r2)
(and (not r1) (not r2)))) in what I assume are some sort of
theorem-prover-like situations. I'm sorry I didn't think to (and may
not have had the records adequate to) cross-reference public-review
comments in the HyperSpec. Maybe for a future version I'll be able to
correct that--we'll see. Anyway, my recollection is that since it's
easy to write a macro
(defmacro truth-value (x) (if x t nil))
so that you can do (eq (truth-value (test1)) (truth-value (test2))),
there was no compelling expressional reason to make a change. But moreover,
the reason the change had been made the first time was for speed reasons.
There might be times when the return-value register was already known to
have a valid true value in it at the time that a return value was going to
be generated; in that case, it would slow computations gratuitously to require
all predicates to move a different true value into place, since most
computations don't rely on the identity of truth values.
Note, btw, that NOT is required to return T/NIL, so the (NOT (NOT X)) trick
of turning an object to T/NIL will work. (PDP10 Maclisp used to have a special
internal routine called NOTNOT that the compiler could push to at any point
to do this coercion, as I recall.)
It is true that a lot of compilers don't make all the optimizations
that CL planned to let them make, so you might claim that this
optimization we planned on wasn't a good one to worry about. But we
were trying to design a language for the future, not just for the
moment. So we always presupposed compilers would get better and would
need neater tricks. (The CMU python compiler was one example that really
showed off some of the neat things one could do with CL compilation.)
Because these original reasons making the change seemed valid, and because
the change had stood unchallenged for ten years, X3J13 voted not to make
a change in response to this public review comment.
And, personally, I think relying on the identity of a truth value function as
being the arbitrarily chosen object T is stylistically poor. I would never
recommend to anyone to do this. The reason is that one might imagine a change
to some predicates in the future in which a "more interesting value" was
chosen (such as happens with string-inequality functions). This just puts
your programs at risk of breakage. In my personal theory of style, I
recommend relying on other-than-truth value of a predicate only when an
"interesting" value has been definitively named, since I don't expect the
language designers to incompatibly change that result nearly as easily as I
think they'd change "T". But by making all predicates return generalized
booleans (even if not called that at the time), note that Steele has in fact
secured the right of the language to "change" the value to something more
interesting as a "compatible change" (since the result would still be a
"generalized boolean" :-).
Erik> clearly, `=' and the like do not have any such special reasons, so what
Erik> motivated the use of "generalized boolean" instead of "boolean"?
In sum, clarity of presentation. Nothing more. ;-)
Barry Margolin
In article <riesbeck-090...@riesbeck.ils.nwu.edu>,
Riesbeck <ries...@ils.nwu.edu> wrote:
>In article <riesbeck-090...@riesbeck.ils.nwu.edu>,
>ries...@ils.nwu.edu (Riesbeck) bloopered:
>> (defun equiv (x y) (or (and x y) (and (not x) (not y))))
>>
>> or, more briefly,
>>
>> (defun equiv (x y) (if x y (not y)))
>>
>> I'm presuming Kaufmann et al may have had cases where this doesn't
>> work, but I wanted to make the point about not equating domain
>> semantics with language semantics for novice Lisp'ers.
>
>Or equating language semantics with domain semantics. The second
>DEFUN is bogus, of course.
They both look valid to me. Here's the results of my testing both of them
(they both return the same values in all cases I tried).
;;; First with real booleans
(equiv nil nil)
t
(equiv t t)
t
(equiv t nil)
nil
(equiv nil t)
nil
;;; Now with generalized booleans
(equiv 1 2)
2
(equiv nil 2)
nil
(equiv 2 nil)
nil
EQUIV takes generalized boolean arguments and returns a generalized
boolean.
By the way, those two definitions are examples of the types of functions
that Kent and I described: they return a generalized boolean because they
happen to have it in a register already; in the true case, they return the
value of Y.
Duncan Smith
Erik Naggum wrote:
> reading it. I had this in mind (slightly simplified):
>
>
> but then I remembered something about generalized booleans, and looked up
> `=' in ANSI X3.226. it seems that an implementation is free to return any
> non-nil value as the result of comparing two equal numbers. now, this is
I use:
(or (and (= start end) t) ...
in these cases, or where I need exactly T/NIL.
-Duncan
Riesbeck
In article <KMP.97Ap...@romulus.harlequin.com>, k...@harlequin.com
(Kent Pitman) wrote:
[ lots of lovely history ]
> The complaint that came out in public review came from Kaufmann,
> Boyer, and Moore. The CLHS dates the comment at Apr 94, citing
> document X3J13/94-305. We had a bunch of conversations with these guys
> (and John McCarthy, as I recall) about their desire to do (EQ (test1)
> (test2)) rather than (let ((r1 (test1)) (r2 (test2))) (or (and r1 r2)
> (and (not r1) (not r2)))) in what I assume are some sort of
> theorem-prover-like situations. I'm sorry I didn't think to (and may
> not have had the records adequate to) cross-reference public-review
> comments in the HyperSpec. Maybe for a future version I'll be able to
> correct that--we'll see. Anyway, my recollection is that since it's
> easy to write a macro
> (defmacro truth-value (x) (if x t nil))
> so that you can do (eq (truth-value (test1)) (truth-value (test2))),
Seems like the real flaw is equating EQ with logical equivalence.
Wouldn't it be better to define (and make inline)
(defun equiv (x y) (or (and x y) (and (not x) (not y))))
or, more briefly,
(defun equiv (x y) (if x y (not y)))
I'm presuming Kaufmann et al may have had cases where this doesn't
work, but I wanted to make the point about not equating domain
semantics with language semantics for novice Lisp'ers.
--
-- Chris
Riesbeck
> Seems like the real flaw is equating EQ with logical equivalence.
> Wouldn't it be better to define (and make inline)
>
> (defun equiv (x y) (or (and x y) (and (not x) (not y))))
>
> or, more briefly,
>
> (defun equiv (x y) (if x y (not y)))
>
> I'm presuming Kaufmann et al may have had cases where this doesn't
> work, but I wanted to make the point about not equating domain
> semantics with language semantics for novice Lisp'ers.
Or equating language semantics with domain semantics. The second
DEFUN is bogus, of course.
--
-- Chris
Erik Naggum
* Kent Pitman
| You've chided me too much on SGML style issues for the HyperSpec for me
| to let a comment like this pass without comment. ;-): You should do "in
| practice" what will keep your programs from breaking if you meat a new
| implementation.
(I deserved this.)
| Heh. You had to ask...
and I'm truly happy I did, too. thank you for a very informative answer.
| And, personally, I think relying on the identity of a truth value
| function as being the arbitrarily chosen object T is stylistically poor.
that was the weak hunch that prompted the question. I've cleaned it up,
and now it's a separate function with a slight change to the semantics (a
substring entirely without contents (i.e., empty or whitespace only) causes
the returned value to be t; a complete object if that object is readable;
otherwise, a cons of an error condition and the appropriate literal:
(flet ((parse-argument (start end)
(handler-case
(read-from-string buffer nil t
:start start
:end end)
(stream-error (eof)
(cons eof (make-array (- end start)
:element-type (array-element-type buffer)
:displaced-to buffer
:displaced-index-offset start)))))))
weird thing is, I think this has elegance, too.