[r6rs-discuss] Hash function return value constraints

[Lynn Winebarger]

On Fri, Apr 3, 2009 at 9:00 PM, Carl Eastlund <carl.eastlund at gmail.com>wrote:

> On Fri, Apr 3, 2009 at 8:43 PM, Lynn Winebarger <owinebar at gmail.com>
> wrote:
> > On Fri, Apr 3, 2009 at 5:16 PM, leppie <xacc.ide at gmail.com> wrote:
> >>
> >> ----- Original Message -----
> >> From: "Brian Harvey" <bh at eecs.berkeley.edu>
> >>
> >> > Okay, I'm confused,  A hash value is an index into an array.  If the
> >> > hash value doesn't fit in a fixnum, then the array doesn't fit in
> >> > memory,
> >> > or even in the virtual address space (by a factor of 4 on a 32-bit
> >> > machine).
> >> > What am I missing here?
> >>
> >>
> >> Something other than the most extreme naive implementation of a
> hashtable,
> >> ever.  :)
> >
> > I'm with Brian - I haven't been following the "hash table" literature,
> but
> > to the best of my knowledge its normal usage refers specifically to
> > associations recorded in an array.  Maybe the term has acquired a wider
> > meaning - certainly R6RS does not retain this standard meaning - but I
> think
> > it's hard to claim the standard definition of X is "the most extreme
> naive
> > implementation of " X.
>
> The problem with "the standard definition" is that it doesn't account
> for any kind of abstraction.  It describes hash functions from the
> perspective of a definition that "knows" about the array the hash
> table is stored in.  In a real library, that doesn't happen -- that
> array may get resized by the hash table implementation; you as a user
> do not know its capacity.  So any API that exposes the ability to
> write a "hash function" cannot ask you to produce an index into that
> array.  Instead, you must write the "first half" of the hash function:
> a function from elements to integers, or fixnums, or something of that
> sort.  The hash table library can then apply modulo or whatever other
> operation to go "the rest of the way" and narrow down the number to an
> index into a specific array size.
>
>
The problem is that the situation is actually reversed.  The user may be
writing the hash table implementation, but wants to use the Scheme
implementation's  hash functions to get hashes on arbitrary Scheme objects
for efficiency.  Obviously the tables the implementation provides can do
whatever they want under the hood, but the hash functions provided by the
implementation to the public should conform to the user's expectations.

If the implementation's make-hashtable accepts hash functions that yield
arbitrary fixnums, but it should work even if the hash function produces
positive bignums.  This question actually conforms to the "should" - it's
ridiculous to require that the implementation detect whether the
user-provided hash function always return a non-negative exact integer, so
the text says "should".

Lynn
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.r6rs.org/pipermail/r6rs-discuss/attachments/20090403/95614d76/attachment.htm