[m-dev.] hash consing

[Fergus Henderson]

On 12-Aug-1999, Peter Schachte <schachte at cs.mu.OZ.AU> wrote:
> Cool stuff!  This'll be a nice feature.
> 
> > 	:- pragma hash_cons(typector/arity)
> > 	:- pragma hash_cons(typector/arity, [ctor1/arity1, ctor2/arity2, ...])
> > 		(or perhaps some better name instead of `hash_cons',
> > 		e.g `canonical')
> 
> How about "table", or "memo", or maybe "table_type" or "memo_type"?
> After all, what you're really doing is tabling the constructor
> function (moving closer to conceiving of constructors as really just
> being automatically-generated functions).
> 
> Why is it important to be able to table only some constructors for a
> type?  It would be a lot simpler not to have this possibility, and it
> looks like it would make the implementation a lot easier, too.

It's not very important.  The main reason I included it is that I thought
it made sense and that I didn't think it would be that hard to implement.
Zoltan and I discussed this point, and I came up with the following
example where it might be useful. 

Suppose you are writing a program which displays twinkling stars.
As part of this program, you send messages from the star simulator
to the graphics engine.  These messages encode changes in the color
or position of a star:

	:- type color ---> red ; green ; blue.
	:- type change
		--->	new_color(color)
		;	new_position(float, float, float).

In your simulations you find that stars change color very often,
so you end up sending billions of `new_color' messages.
But you also find that they don't move very often.
Profiling also shows that the program is spending a lot of time
in the garbage collector, and that most of the memory allocation
is via this `new_color' constructor.  You realize that you could
dramatically reduce the rate at which the program creates garbage
by tabling the `new_color' constructor.  However, star positions are
sparse and so you don't want to memoize the `new_position' constructor;
indeed if the implementation doesn't do garbage collection of tables,
then tabling the `new_position' constructor would lead to an unbounded
memory leak.  Even if the implementation does do proper garbage collection
of tables, you'll still lose efficiency if you memoize `new_position'.

I admit this example is somewhat contrived and not compelling.

> > Semantic checking:
> > 		
> > 	The pragma must appear in same section (interface/implementation) as
> > 	the type declaration.
> 
> Tabling seems like an implementation detail; why should it be part of
> the interface for a module?  It seems like something that should only
> belong in the implementation section.

In Ada, this would belong in the "private" part of the module interface.
The reason it belongs in the interface for exported types is that
if you add or remove these declarations, then code using that type
must be recompiled.

> You also need to decide what to do about tabling types with
> user-defined equality.  As far as I can see, it's not possible, but
> maybe you can see a way.  Anyway, this should be documented.

The user could provide a user-defined predicates for doing the tabling.
But in order to make that respectable we'd need to clean up
the way table predicates work.  Currently it is done using `impure'
and without proper static typing, which is a bit of a hack.

Something like the following would  be better:

	:- import_module store.

	% init_table(DummyKey, Table, Store0, Store)
	%	Create an empty table, suitable for tabling values of
	%	the same type as `DummyKey', return it.
	%	(The value of `DummyKey' is ignored, only its type is used.)

	% table_lookup_insert(Key, TableRef, ValueRef, Store0, Store):
	%	If Key occurs in the value referred to by TableRef,
	%	then let ValueRef be the reference to the corresponding
	%	value.  Otherwise, allocate a fresh reference for
	%	ValueRef, and insert the Key into the table with
	%	this fresh reference as its corresponding data.

	:- typeclass tableable(Key) where [
		(some [Table]
		pred init_table(Key, Table, store, store) => table(Key, Table)),
		mode init_table(unused, in, di, uo) out is det
	].
	:- typeclass table(Key, Table) where [
		pred table_lookup_insert(Key, ref(Table(Value)), ref(Value),
				store, store),
		mode table_lookup_insert(in, in, out, in, di, uo) is det
	].

> > Implementation:
> > 
> > 	(1) Ensure that constructions are hash-consed
> > 
> > 	For each hash-consed constructor C/N, any unification which constructs
> > 	a ground value using that constructor will get transformed into
> > 	a call to a function hash_cons_C/N which is defined by
> > 
> > 		:- pragma memo(hash_cons_C/N).
> > 		hash_cons_C(X1, ..., XN) = C(X1, ..., XN).
> 
> Do you have a way to hide these functions so they don't pollute the
> user's namespace?

Yes, that can be arranged.

> It'd get pretty ugly if people, for some reason,
> chose to name their own function hash_cons_C/N.

Agreed.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------