[m-rev.] for review: rationalise hash functions across the standard library

Zoltan Somogyi zoltan.somogyi at runbox.com
Tue Feb 11 15:38:54 AEDT 2020



On Tue, 11 Feb 2020 14:19:22 +1100 (AEDT), Julien Fischer <jfischer at opturion.com> wrote:
> I don't have any objections to moving to unsigned integers.  I would
> like whatever we end up with to be a little more well thought out
> than what's currently present in the library. 

Agreed.

> Perhaps, we should move
> to have hashable type class?

Perhaps, but that should be a separate change.

Are you thinking of adding this as a typeclass constraint to the signature
of all the hash table operations, or just doing this to the init function,
and having it stash the hash function in the hash_table structure,
as we now do with the hash predicate? The former seems cleaner,
the latter has a simpler correctness argument for the proposition
that all call sites use the same typeclass instance and hence the same
hash function.

> > The original implementation required two hash values.
> 
> Ah, that explains it!

I was curious what the two hash values were, so I had a look. While doing
that, I found something else. This:

:- type hash_table_alist(K, V)
    --->    ht_nil
    ;       ht_single(K, V)
    ;       ht_cons(K, V, hash_table_alist(K, V)).

While having ht_single as a special case is justifiable at the top level,
it is *not* justifiable in the third arg of ht_cons, since (a) it allows
more than one representation of the same data, and (b) it requires
a three-way choice, not a two-way choice, at each element.
(I actually had a slide showing how to avoid this when I taught
logic programming.)

I would replace ht_cons with something like

ht_more(K, V, K, V, kvlist(K, V)),

where kvlist is defined by

:- type kvlist(K, V)
    --->    kv_nil
    ;    kv_cons(K, V, kv_list(K, V)).

> > When I changed it to require only one hash value, I didn't change the
> > hash predicates to functions.
> 
> I have no objection to changing it to a function; we should be able to
> add wrappers that also preserve the existing interface.

I don't see much point in changing to functions; predicates work just
as well.

I think that this switch should be done, if at all, when we also switch
to that hashable typeclass. Two improvements, with just one disruption.

Zoltan.


More information about the reviews mailing list