Numerical Comparison: "required coercions"

[Michael Greenwald <Greenwald@STONY-BROOK.SCRC.Symbolics.COM>]

    Date: Thu, 26 Mar 87 10:47 EST
    From: David C. Plummer <DCP@QUABBIN.SCRC.Symbolics.COM>

	Date: Thu, 26 Mar 87 10:29 EST
	From: Guy Steele <gls@Think.COM>

	This issue makes me want to restate an earlier proposed model
	for the comparison functions:

		(? x1 x2 x3 x4 ... xn-1 xn) <=>
			(AND (? x1 x2) (? x1 x3) (? x1 x4) ... (? x1 xn-1) (? x1 xn)
				       (? x2 x3) (? x2 x4) ... (? x2 xn-1) (? x2 xn)
						 (? x3 x4) ... (? x3 xn-1) (? x3 xn)
								    .          .
								    .          .
									       .
									   (? xn-1 xn))
	where "?" may be =, /=, <, >, <=, or >=.
	That is, in principle every pair of arguments is compared.
	This is the model that justifies the "all different" interpretation for /=,
	and it is recognized that in practice the other five operations may
	be implemented cleverly through exploitation of transitivity.  Well,
	maybe such reliance on transitivity is wrong.

Why "maybe"?  (<= 1234d10 12340000000001 1234e10 12340000000000) => T
when you depend on transitivity, but should => NIL according to the
above model.

On the other hand, SORT clearly depends on transitivity, and one might
reasonably expect (APPLY '<= (SORT SEQUENCE '<=)) => T.

(Or even more reasonably (APPLY '< (SORT SEQUENCE '<)) => T, which
unfortunately isn't true since  
  (SORT '(1234d10 12340000000001 1234e10 12340000000000) '<) returns the
original sequence.)

    I'm a fan of transitivity and also recognize this problem.  If this is
    n^2 computation is to be the law-of-the-land for the non /= cases, I
    would suggest a declaration that tells the compiler that the user is
    guaranteeing transitivity so that only a linear number of comparisons is
    needed.

The declaration is unnecessary, (although might be useful), since the
check for whether transitivity will work can be done in linear time.
(This same strategy reduces /= to NlogN for cases where transitivity
holds, and all the elements are orderable by sorting the numbers and
then only comparing adjacent elements.  This doesn't work if any
coercions could lose precision.   (This works for complex numbers, too))

In practice, our implementation assumes transitivity holds, except in
/=, where we are more scrupulous.


All these anomolies are solved by coercing to the *most* exact
representation for comparisons.  I'm assuming that the floating-point
contagion rule was mandated for two reasons:

(1) It is misleading to *add* bits of precision during a computation.
(although this is belied by the single-to-double conversion rule)
(2) Floats put a stricter upper bound on the required storage than do
the corresponding rationals and bignums.

Both of these rules are more applicable for computations (+, -, etc.)
than for comparisons.

CLtL chose a single coercion rule ("WhenEVER a rational meets a floating
point number, the rational is first converted to a floating-point number
of the same format") rather than two coercion rules ("In computations
that produce new values, the arguments are first coerced to the least
precise representation of the two arguments, and the result has the
same, imprecise, representation.  In comparisons, arguments that differ
in type are first converted to the *most* precise representation of the
two arguments.").  

In some sense (although I don't believe this) you might be able to argue
that CLtL's decision made the language "simpler", (although it certainly
made the results of some of the numeric functions more "surprising").

If it isn't too late, maybe the coercion rule could be changed in the
"cleaned up Common Lisp".  (Unless someone knows of equally bizarre
results of *that* coercion rule.)