[R6RS] Hashing questions

dyb at cs.indiana.edu dyb at cs.indiana.edu
Tue Jun 13 15:38:35 EDT 2006

> Also, the Haskell folks use
> a more primitive abstraction (called stable names) on top of which they
> implement their equivalent of eq? hash tables.
> ...
> Would these make sense generally as a base abstraction to build eq? 
> hash tables or for R6RS?  I think someone mentioned that there were
> efficiency concerns---if so could somebody hint at them briefly?

MIT Scheme had/has something similar; I think it is called object-hash.  I
don't know about the MIT Scheme mechanism, but the Haskell mechanism is
implemented internally using---you guessed it---eq? hash tables.  So the
more primitive mechanism is actually the eq? hash table.

The efficiency issue arises because some collectors move objects,
so any hash code derived from the pointer changes over time.  In user
land, this means that some less efficient hashing algorithm must 
be used, e.g., one based on the structure of the object.  In system
land, the gc and hash table mechanism can cooperate to keep the hash
table up to date when objects move.


More information about the R6RS mailing list