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

*To*: cl-cleanup@sail.stanford.edu*Subject*: Issue HASH-TABLE-TESTS*From*: Jon L White <jonl@lucid.com>*Date*: Mon, 26 Sep 88 22:59:40 PDT

Issue: HASH-TABLE-TESTS References: CLtL, p382 (third paragraph), and p383 Issue EQUAL-STRUCTURE Issue: CONTAGION-ON-NUMERICAL-COMPARISONS Category: Addition Edit history: 26-Sep-88 Version 1 by JonL Problem Description: A great many users try to coalesce two equivalent defstruct instances, or two equivalent pointer arrays, using hash tables; but they are rudely awakened when they find out that EQUAL is not an appropriate test for this case, and that there is no :test argument to MAKE-HASH-TABLE which will "hash on non-tree structures". Proposal: HASH-TABLE-TESTS:ADD-EQUALP With the advent of the issue CONTAGION-ON-NUMERICAL-COMPARISONS, we can expect EQUALP to be a true equivalence function, and thus a suitable candidate for the :test function to MAKE-HASH-TABLE. Hash-tables will come in four kinds, the difference being whether the keys are compared with EQ, EQL, EQUAL, or EQUALP. Examples: > (defstruct foo a b c) FOO > (setq x (make-foo :a 1 :b 'b :c '(1 . 2)) x-copy (make-foo :a 1 :b 'b :c '(1 . 2))) #S(FOO A 1 B B C (1 . 2)) > (setq y #(1 B (1 . 2)) y-copy (copy-seq y)) #(1 B (1 . 2)) > (setq ht-equal (make-hash-table :test 'equal) ht-equalp (make-hash-table :test 'equalp)) #<Hash-Table BB1F7B> > (progn (setf (gethash x ht-equal) t) (setf (gethash x ht-equalp) t) (setf (gethash y ht-equal) t) (setf (gethash y ht-equalp) t)) T > (gethash x-copy ht-equal) NIL NIL > (gethash x-copy ht-equalp) T T > (gethash y-copy ht-equal) NIL NIL > (gethash (copy-seq y) ht-equalp) T T > Rationale: Implementing hash-tables efficiently is not an easy task; it makes more sense for this to be standardly available (implemented by the wizards at the Lisp vendor companies) than for individual programmers to keep trying to re-invent this obscure part of technology. Current Practice: Lucid's release 3.0 implements this proposal [some 2.1-level release supported it "provisionally"]. Symbolics implementation is reputed to be robust enough to implement this proposal trivially. Cost to Implementors: Moderate. Implementors have already dealt with EQUAL; the only tricky part will be ensuring the implication: "If 'a' is EQUALP to 'b', then 'a' and 'b' must lie in the same collision chain in any given EQUALP hash table" It has been suggested that merely linear searching a table is an acceptable implementation technique for CL's hash-tables [although no serious implementation limits itself thus] and that such tables have no "collision chains"; but in fact, this is the degenerate case wherein all entries are in the same collision chain, so the implication is trivially satisfied. Some persons prefer to say that the "reprobe sequence will be the same for the two items", rather than using the term "collision chain"; the meaning is the same. Cost to Users: None. This is an entirely upwards-compatible addition. Cost of non-adoption: Continuing bug reports from CL vendors' customers about why "hashing doesn't work" when said customer tries entering pointer-containing objects other than cons cells into hash tables. Continuing delay in same customers work until they figure out a new strategy for identifying equivalent structures. More difficulty in debugging their alternatives. Benefits: Addresses one aspect of the difficult equivalence problem. Makes hash tables usable with the major, remaining equivalence predicate of CL. Also as a "side effect", permits case-insensitive hashing on strings [tables of type EQUAL are case-sensitive on strings]; another "side effect" is the abililty to use the CL numeric comparison "=" for numbers [tables of type EQUAL use EQL on numbers]. Aesthetics: Reduces the discontinuity between basic equivalence functions and those usable as equivalence relations in hash-tables. Discussion: With the rejection of all the issues related to EQUAL-STRUCTURE, there is little or no hope that EQUAL will be "beefed up" to meet the expectations of so many of the user community on compound structures. If one wants a hash-table with a :test function that has fewer equivalence classes (i.e., does more "coalescing"), then there is no alternative now except to use the function EQUALP.

**Follow-Ups**:**Issue HASH-TABLE-TESTS (Version 1)***From:*David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>

- Prev by Date:
**proposal LOAD-TIME-EVAL:REVISED-NEW-SPECIAL-FORM** - Next by Date:
**Moon@stony-brook.scrc.symbolics.com** - Previous by thread:
**away....** - Next by thread:
**Issue HASH-TABLE-TESTS (Version 1)** - Index(es):