eq and hashing (was Re: [plt-scheme] How to make unit functors?)

At Wed, 28 May 2003 22:43:20 -0500, Robby Findler wrote:
> At Wed, 28 May 2003 16:38:22 -0600, Matthew Flatt wrote:
> > At Wed, 28 May 2003 17:19:18 -0500, Robby Findler wrote:
> > > Say that I'm implementing a finite mapping data structure that claims
> > > to map all values, but only creates the actual entries lazily (ie, when
> > > they are looked up or changed or something like that). If you ask me
> > > for 'l many times, but I only keep the hash code for 'l in my data
> > > structure, you may get different entries in the table at different
> > > times, as the symbol table is gc'd.
> > 
> > I don't quite follow. If you keep only the hash code, how do you know
> > that it has something to do with 'l (as opposed to, say, 'foo)?
> 
> You don't -- all you know is that next time you get a 'l passed into
> the data structure, you want the same answer to come out. Now you don't
> get that.
>
> Eg:
> 
>   (define m (make-mapping))
>   (bind 'l "l binding")
>   (lookup 'l) ==>(hopefully) "l binding"
> 
> If the internal structure of the table uses the hash codes to maintain
> the mapping and doesn't hold onto the values themselves the lookup
> might signal some kind of unknown entry.

Suppose that the only thing in `make-mapping' is the hash key of 'l and
the string "l binding".

Even if the hash key for 'l never changes, how does the implementation
of `make-mapping' know that the hash key it kept is for 'l, as opposed
to 'foo?

> I tried to test out this theory with mz's weak hash tables:
> 
>   Welcome to MzScheme version 204.3, Copyright (c) 1995-2003 PLT
>   > (define ht (make-hash-table 'weak))
>   > (hash-table-put! ht 'funnyhaha 1)
>   > (hash-table-get ht 'funnyhaha)
>   1
>   > (collect-garbage)
>   > (hash-table-get ht 'funnyhaha)
>   hash-table-get: no value found for key: funnyhaha
> 
> But of course I *have* mapped 'funnyhaha! I can see how you can argue
> operationally that this is just how it works, but I can't see how this
> is desirable behavior.

I'm not arguing that it's desirable. `eq?' often exposes implementation
issues that otherwise are hidden, and weak references expose even more.

Also, this is not the same example as above. Both examples expose the
GCing of symbols, but event if we disable GC of a symbol with a weak
reference, the hash key returned by `eq-hash-key' would still change.
That is, even a weak hash table needs to keep a (weak) reference to the
key symbol, which is the idea I'm trying to get at in the
`make-mapping' example.

Overall, I'm suggesting that it's difficult to construct a useful
program where a shift in hash key for a symbol matters. (I am also
unconcerned that weak hash tables can drop symbol mappings. Yes, it
exposes certain implementation details, but that's the nature of the
construct.)

Matthew