hyln9 / ikarus

Optimizing incremental native-code compiler for R6RS scheme. This is a forked repository.
https://launchpad.net/ikarus
Other
5 stars 0 forks source link

string-hash not suitable as a hash function #215

Closed hyln9 closed 10 years ago

hyln9 commented 10 years ago

Ikarus's string-hash is not suitable as a hash function, because hash functions are required to return non-negative exact integers, and Ikarus's string-hash can return negative numbers.

I realize that you've made string-hash return numbers in the whole fixnum range on purpose, but please consider this repl session:

(let ((h (make-hashtable (lambda (x) (string-hash x)) string=?))) (hashtable-set! h "foo" #t)) Unhandled exception Condition components:

  1. &assertion
  2. &message: "invalid return value from hash function"
  3. &irritants: (-171070200)

If I want to use string-hash in my own hash functions, then I need to e.g. wrap it in (abs ...) if I want the code to run in Ikarus. If string-hash can return negative numbers, shouldn't the hashtables also accept hash functions that return negative numbers? But then you run the risk that people write code that will only run on Ikarus, so shouldn't string-hash return non-negative numbers after all?

Besides, returning non-negative fixnums only halves the number of possible hashes. Does it really make much difference?

Launchpad Details: #LP413809 Göran Weinholt - 2009-08-14 17:28:31 -0400

hyln9 commented 10 years ago

I recall this discussion from the past.

Ahh, and it was me, on the R6RS list :o)

http://lists.r6rs.org/pipermail/r6rs-discuss/2009-April/date.html

Launchpad Details: #LPC leppie - 2009-08-15 08:38:52 -0400

hyln9 commented 10 years ago

I "fixed" this in revision 1848 by allowing both negative and nonnegative integer results from hash functions.

Launchpad Details: #LPC Abdulaziz Ghuloum - 2009-08-26 11:32:20 -0400

hyln9 commented 10 years ago

Fixed string-hash and string-ci-hash in revision 1849. They now return only nonnegative fixnums.

Launchpad Details: #LPC Abdulaziz Ghuloum - 2009-08-26 11:48:21 -0400