[Chicken-users] Hash table equality pitfall

[Peter Bex]

Hi all!

I ran into some very tricky behavior with hash tables that I'd like to
document for posterity.

Turns out that (equal? (make-hash-table) (make-hash-table)) no longer
always returns #t in the current master, but it did in Chicken 4.7.0.

This is because of obscure internal details: the hash table's internal
hashing function is a closure which contains the randomization fixnum,
which usually differs between tables.

In Chicken 4.7.0 and earlier, equal? only *appears* to work correctly for
hash tables.  In fact, it works if the table is filled such that buckets
contain at most one value, or if they were filled in the same order:

#;1> (use srfi-69)
; loading library srfi-69 ...
#;2> (define x (make-hash-table size: 2))
#;3> (define y (make-hash-table size: 2))
#;4> (equal? x y)
#t
#;5> (hash-table-set! x 'a 1)
#;6> (hash-table-set! x 'b 2)
#;7> (hash-table-set! x 'c 3)
#;8> (hash-table-set! y 'a 1)
#;9> (hash-table-set! y 'b 2)
#;10> (hash-table-set! y 'c 3)
#;11> (equal? x y)
#t

However, if we change the fill order, it no longer compares equal:

#;1> (use srfi-69)
; loading library srfi-69 ...
#;2> (define x (make-hash-table size: 2))
#;3> (define y (make-hash-table size: 2))
#;4> (hash-table-set! x 'a 1)
#;5> (hash-table-set! x 'a 2)
#;6> (hash-table-set! x 'b 2)
#;7> (hash-table-set! x 'c 3)
#;8> (hash-table-set! y 'c 3)
#;9> (hash-table-set! y 'b 2)
#;10> (hash-table-set! y 'a 1)
#;11> (equal? x y)
#f

The reason for this is that equal? is a very generic procedure, which
knows about core datatypes and compares record type values field by field.
A hash table is just a record type, and it contains some internal
slots with the configuration details as well as a vector which holds the
hash table's buckets.  The bucket contents themselves are alists, which
are filled simply using alist-cons when you use hash-table-set!.  That's
why the ordering differs.

Of course, from the end-user perspective this is *very* tricky behaviour,
so I've added a note to the manual about this.  I checked the SRFI, but
it doesn't mention anything about hash tables having to compare equal to
eachother so Chicken's behaviour is strictly not in violation of any
standard :)  The only other implementation I was able to test with was
Racket (why is SRFI-69 so uncommon in Schemes?) and there hash tables
also don't compare with equal?

Luckily, with the new version the mistake of thinking that equal? is
defined for hash-tables is a lot harder to make since the randomization
factor will ensure they are almost always different.

Cheers,
Peter
-- 
http://sjamaan.ath.cx
--
"The process of preparing programs for a digital computer
 is especially attractive, not only because it can be economically
 and scientifically rewarding, but also because it can be an aesthetic
 experience much like composing poetry or music."
                                                        -- Donald Knuth