Numerical Comparison: "required coercions"

[Scott Cyphers <Cyphers@YUKON.SCRC.Symbolics.COM>]

    Date: Thu, 26 Mar 87 13:34 EST
    From: 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.)

Leave things the way they are.  You're trying to give too much meaning
to something which only derives its meaning from the way it is being
used.  In normal situations, things behave about how you'd expect them
to.  It is only when you get into the noise that things fall apart,
because the multiple interpretations are no longer distinct.  In those
cases, I say it is an error to write something like (< x rational), and
that you have no right to expect something like transitivity to hold
because you're mixing definitions.  If you want to say <, then do the
coercions yourself in the way appropriate to what your working on.

Rationals aren't necessarily any more exact than floating point.  If
you're computing rationals, then they're exact, but if you're computing
reals, then they're no more exact than floating point.  What if someone
is trying to say (< x (sqrt 2))?  Unless they are doing their own
coercions (or squaring x) I think there's always going to be some form
of default coercion which will do the "unexpected" for them.