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

*To*: Greenwald@stony-brook.scrc.symbolics.com*Subject*: EQUAL, and hash tables, and value/object distinctions*From*: Jon L White <edsel!jonl@labrea.stanford.edu>*Date*: Tue, 19 Jul 88 00:05:31 PDT*Cc*: jrose@sun.com, goldman@vaxa.isi.edu, common-lisp@sail.stanford.edu*In-reply-to*: Michael Greenwald's message of Thu, 30 Jun 88 16:36 EDT <19880630203650.3.GREENWALD@SWALLOW.SCRC.Symbolics.COM>

re: For example, one cannot construct a hash-function for #'= unless you limit the valid keys to not include both a floating point number and two integers that both coerce to that same float. You must be referring to the bug in CLtL, p194: "When rational and floating-point numbers are compared or combined by a numerical function, the rule of floating-point contagion is followed: ..." I believe that this should read: "When rational and floating-point numbers are combined by a numerical function, the rule of floating-point contagion is followed: ..." Float conversion is an inherently information-losing process; this is, of course, fine for situations where there will most likely be information loss anyway ,due to rounding and/or truncation [such as in "combination by a numerical function"]. But numerical equality and inequalities are not information losing, and should in fact be transitive relations. About one year ago, I pointed out this difficulty to Guy Steele with some well- chosen examples; and he was quite shocked -- indeed it was his intention that "=" be a true equivalence predicate. Lucid's 3.0 release performs "appropriate contagion" in the case of numerical comparisons, in order to preserve transitivity. re: Hash tables aren't so complicated that one can't construct them yourself. My guess (and only a guess) is that the only reason they're included in the language spec is to give a portable way of hashing on %pointer where that might be useful. SXHASH would have been enough, and that allows easy implementation of the common case of EQUAL hash tables, too. Efficient hash tables are! ["so complicated that one can't construct them ...]. Both Lucid and Symbolics hide a lot of implementation-dependent knowledge deep within the bowels of CL hash-tables; even if the average Lisp programmer were "smart enough" to defend his ego on hash-tables, he probably wouldn't have reasonable access to all the system internals that the vendor wizards do. In fact, I have heard some C programmers praise Common Lisp for it's inclusion of hash-tables. They complain and complain about having to reinvent the wheel (hash-tables) over and over again. re: Date: Thu, 30 Jun 88 12:40:54 PDT From: jrose@Sun.COM (John Rose) . . . Yuck. Who are these brilliant Implementors, that we may all worship at their feet? For they are the curators of such profound knowledge as (EQUALITY-PREDICATE X Y) ==> (= (HASH-FN X) (HASH-FN Y)) Yes, but the equality-predicate must be transitive over the domain of possible keys in order for a hash-function to work. This point that you [Greenwald] are making seems not to be generally appreciated. The fact that many many experts pored over the Common Lisp design, and still thought that numerical equality as defined by "=" was an equivalence relation shows how easy it is to miss closure on transitivity. -- JonL --

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

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

- Prev by Date:
**arithmeticprecision** - Next by Date:
**EQUAL, and hash tables, and value/object distinctions** - Previous by thread:
**What have hashing and equality to do with each other?** - Next by thread:
**EQUAL, and hash tables, and value/object distinctions** - Index(es):