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 _______________________________________________ Chicken-users mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/chicken-users
