[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: CL-Cleanup@sail.stanford.edu*Subject*: Issue: CONTAGION-ON-NUMERICAL-COMPARISONS*From*: David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>*Date*: Wed, 14 Sep 88 16:27 EDT*References*: <8807200836.AA02976@bhopal.lucid.com>, <19880719152249.9.MOON@EUPHRATES.SCRC.Symbolics.COM>, <19880719213809.1.GREENWALD@SWALLOW.SCRC.Symbolics.COM>, <870402170955.6.MOON@EUPHRATES.SCRC.Symbolics.COM>

Issue: CONTAGION-ON-NUMERICAL-COMPARISONS References: CLtL p.194 Category: CHANGE Edit history: Version 1, 14-Sep-88, Moon Problem description: The numerical contagion rules specified on CLtL p.194 make it impossible for the numerical comparison functions to be transitive when given arguments of mixed floating and rational types (see example below). Proposal (CONTAGION-ON-NUMERICAL-COMPARISONS:TRANSITIVE): Instead of using the same contagion rule both for combining functions and for comparing functions, make the present rule apply only to combining functions and add the following rule: When rational and floating-point numbers are compared by a numerical function, the function RATIONAL is called to convert the floating-point number to a rational and then an exact comparison is performed. In the case of complex numbers (RATIONAL is for some unknown reason only allowed on reals), the real and imaginary parts are handled individually. It is of course valid to use a more efficient implementation than actually calling RATIONAL, as long as the result of the comparison is the same. Test Cases/Examples: (defvar a (/ 10.0 single-float-epsilon)) (= a (1+ (floor a))) should be NIL, since (= a (floor a)) is certainly T and (= (floor a) (1+ (floor a))) is certainly NIL. However, by the rule of floating-point contagion, (= a (1+ (floor a))) is the same as (= a (float (1+ (floor a)) a)) and the latter form is certainly T. To understand this example better, it helps to realize that (= a (+ a 1.0)) is always true, by the definition of single-float-epsilon. Here is a second example: (defvar i (floor a)) (<= a (+ i 1)) is T. (< (+ i 1) (+ i 2)) is T. (<= (+ i 2) a) is T by CLtL, NIL by this proposal. Thus CLtL requires a <= i+1 < i+2 <= a which ought to imply a < a which is absurd. Rationale: Transitivity of = and of < are important to many algorithms. What CLtL says now was probably not intentional, but just the result of thinking that comparing and combining could be lumped together without really thinking about it. Without this change, it is impossible to extend the :TEST argument to MAKE-HASH-TABLE to allow = or EQUALP, since there could be two table entries with rational keys that are not =, then GETHASH could be presented with a floating-point argument that is = to both keys. Current practice: Lucid is said to implement the proposal. As far as I know all other implementations do what CLtL currently says. Cost to Implementors: This requires a change in what is likely to be intricate and implementation-dependent code. However, the total effort should be small compared to the cost of writing that code originally. Cost to Users: This is an incompatible change. It's difficult to know if any users are depending on the current behavior. It seems likely that most users would expect the proposed behavior, and may be wondering why their programs don't quite work when the numbers get large. Cost of non-adoption: Comparison functions in Common Lisp will be non-transitive. Benefits: Comparison functions in Common Lisp will be transitive. Esthetics: Having two rules of floating-point contagion may seem less esthetic, but I'm certain that having the comparison functions behave in a more mathematically correct fashion outweighs that esthetically. Discussion: Everyone who has expressed an opinion has thought this was the right thing for years, but we never got around to writing it up as a cleanup proposal.

**Follow-Ups**:**Issue: CONTAGION-ON-NUMERICAL-COMPARISONS***From:*Jon L White <jonl@lucid.com>

**References**:**EQUAL, and hash tables, and value/object distinctions***From:*David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>

- Prev by Date:
**Re: issue TRUENAME-SYNTAX-ONLY** - Next by Date:
**Re: issue TRUENAME-SYNTAX-ONLY** - Previous by thread:
**EQUAL, and hash tables, and value/object distinctions** - Next by thread:
**Issue: CONTAGION-ON-NUMERICAL-COMPARISONS** - Index(es):