Numerical Comparison: "required coercions"

[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.

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.