[m-dev.] Tabling methods

[Fergus Henderson]

On 12-Mar-1998, Oliver Hutchison <ohutch at students.cs.mu.oz.au> wrote:
> 
> I'm not sure if anyone can remember this but why is it that we have both a
> memo and a memo+loop_check transformation.

Because memo alone should be more efficient that memo+loop_check.

> I really don't see the
> advantage of having memoing without the loop check. There is no extra
> overhead for the loop check and it gives a much better error message than
> heap overflow if an infinite loop is detected. 	

If there is really no extra overhead, then I agree --
unless the lack of overhead is just due to your implementation
of memo alone being unnecessarily inefficient.

If you are tabling a det predicate with one output argument
of type `T', then with memo alone the table entries need
contain only values of type `T'.  With loopcheck alone,
the table entries just contain a bool.  But with memo+loopcheck,
the table entries must effectively contain values of type `maybe(T)'.

The need to store values of type `maybe(T)' instead of `T'
may increase the storage requirements significantly.

> I suggest that we always do loop checking for the memo case and use the
> loop_check case to just do the loop check, no memoing of answers.
> 
> This would result it three types of tabling :
> 
> 	`loop_check' simply detect infinite looping and issue an error
> 		message if it is found. Valid in all dets.
> 	`memo' detect looping but also memo answers. This would
> 		primarily be used as an optimization. Valid in all dets.
> 	'minimal' implement the minimal model semantics. Valid in semidet
> 		and nondet dets. NOTE : This will change det procs to 
> 		semidet so it will still work with any piece of existing 
> 		code. Det code will just have to be declared semidet
> 		instead of det.

I agree with this except that `loop_check' should
be orthogonal with `memo' or `minimal_model'.

Note that if, in a particular implementation, loop checking
happens to be free, or very cheap, then the implementation is
always free to do loop checking even if the user doesn't specify
`pragma loop_check'.

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