[m-dev.] hash consing

[Peter Schachte]

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.

I trust your implementation capitalizes on the fact that niladic
constructors don't need tabling.

> 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.

> 	The mode checker should record that the result of a construction
> 		unification creating a term of a hash-consed type
> 		is not unique.

Your terminology doesn't serve you well here.  A hash consed term *is*
unique:  it will be the only term in memory having that value.  It may
very well be *shared*, however.  But I suppose you're stuck with that
meaning of "unique" now.

> 	The mode checker should disallow creation of partially instantiated
> 		values for hash-cons types
> 		(Alternatively, it could allow them; but in that case, they
> 		should be canonicalized only at the point when the value
> 		becomes ground; even then, that could be confusing behaviour,
> 		so it's probably not worth supporting this.)

I don't think it would be so confusing, but it's probably not
important enough to bother with for now.  Still, I don't think it
should be precluded by the language specification.


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.


> 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?  It'd get pretty ugly if people, for some reason,
chose to name their own function hash_cons_C/N.



-- 
Peter Schachte                     What is the robbing of a bank compared to
mailto:schachte at cs.mu.OZ.AU        the founding of a bank?
http://www.cs.mu.oz.au/~schachte/      -- Bertold Brecht 
PGP: finger schachte at 128.250.37.3  
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------