Re: [Chicken-users] This may be a bug in chickens hash tables - or my bad

[Jörg F . Wittenberger]

Am 18.12.2015 um 18:35 schrieb John Cowan:
> Ivan Shmakov scripsit:
> 
>>      Given that the basic idea of hashing is to produce a key out of
>>      the object’s /value/, the change of the value – and mutation
>>      does just that – changes the hash.  
> 
> Well, yes and no.  SRFI 69 and other Scheme hash table frameworks
> support at least two kinds of hashing: hash by value and hash by
> identity.  If you have a large tree structure made with pairs, and
> you want to keep ancillary information about some but not all of
> the pairs, an identity-based hash table will let you keep the information
> associated with *a particular pair*.  Otherwise, if you had a tree like
> (a (b c) (b c)), then any information associated with the first (b c)
> would be overwritten if you associated information with the second (b c).
> This is quite independent of whether you ever mutate the tree or not.

Not necessarily.

Given the typical vector+alist implementation, this would still allow to
associate values to each particular pair.

The problem really arises only around the question what hash-by-identity
actually means.

I would understand the language as: "two objects comparing eq? will hash
to the same value".

This would imply that the hash value would have to be somehow
(implementation specific) being derived from a unique property of the
particular object.  (Easy if we'd assume malloc als allocator: just tag
the address bits as fixnum.  Harder for moving garbage collectors.)

So the question is kind of nitpicking: does the srfi-69 /mandate/ that
at least the hash-by-identity will produce the same value for the same
object over the livetime of the object even if the object is mutated?

If so, then we should change the chicken manual to document a deviation
from the standard.  Until we have a good idea how to fix it, that is.

Otherwise I'd still put a warning into the manual.  For boneheads like me.

I mean: the problem is trivial to work around, once you know what you're
dealing with.

/Jörg