[m-dev.] Tabling methods

[Oliver Hutchison]

On Thu, 12 Mar 1998, Fergus Henderson 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.
> 

Well there is the extra overhead so I will do it.

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

Yes, but with the current implementation this is not as easy as it sounds 
so I don't do it. I currently reserve the value 0 in a table leaf to
indicate that the leaf has just been created.

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

Ok so you want :
	
	`loop_check'
	`memo_loop_check'
	`memo'
	`minimal'

It doesn't make sense to loop check the minimal type.