Status: Passed, Jan 89 X3J13
References: CLtL, p382 (third paragraph), and p383
Requires Issue: CONTAGION-ON-NUMERICAL-COMPARISONS
Edit history: 26-Sep-88 Version 1 by JonL
8-Dec-88 Version 2 by Masinter
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".
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.
> (defstruct foo a b c)
> (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))
> (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))
> (gethash x-copy ht-equal)
> (gethash x-copy ht-equalp)
> (gethash y-copy ht-equal)
> (gethash (copy-seq y) ht-equalp)
Implementing hash-tables efficiently is not an easy task; it makes more
sense for this to be standardly available than for individual programmers
to keep trying to re-invent this obscure part of technology.
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 users about why "hashing
doesn't work" when said user tries entering pointer-containing objects
other than cons cells into hash tables. Continuing delay in same
user's work until they figure out a new strategy for identifying
equivalent structures. More difficulty in debugging their alternatives.
Addresses one aspect of the difficult equivalence problem. Makes
hash tables more useful. Permits case-insensitive hashing
on strings [tables of type EQUAL are case-sensitive on strings];
another use is to allow = comparison for numbers
[tables of type EQUAL use EQL on numbers].
Reduces the discontinuity between basic equivalence functions and those
usable as equivalence relations in hash-tables.
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.
It would also be possible to extend hash tables to allow = or
STRING=, but those are not being proposed at this time.