[m-dev.] Tabling [1/3]

[Oliver Hutchison]

On Tue, 10 Mar 1998, Fergus Henderson wrote:

> > > I don't think so.  I think that a recursive call with the same input
> > > arguments will still always lead to infinite recursion, even with
> > > memoing.  Isn't that correct?
> > 
> > No. Memoing will suspend the recursive call and then feed answers back to
> > it through the resumption mechanism until there are no answers pending.
> 
> Does suspension suspend just a call, or does it suspend a whole disjunct?
> 

Memoing suspends just the call.

> If it suspends just a call, then later goals in this disjunct might fail,
> leading to termination.  But if it suspends the whole disjunct,
> I don't see how you can ever get to the situation where there are
> no answers pending -- surely you'd still have some pending answers for the
> predicate, namely the ones waiting for the answers for the recursive call.
> 
> What's the semantics of memoing?  I thought memoing wasn't supposed to
> affect the predicate's declarative semantics.  I thought that `minimal_model'
> was the only one that affects the semantics.  
> 

The semantics of memoing as I have implemented it matched that of SLG-d as
described in Kostis Sagonas' PhD theses.

> Note that the ordinary (completion) semantics say that for
> `p :- p.' it is unspecified whether `p' is true or not.
> Thus if `memo' is supposed to be using the ordinary semantics, as I
> think it is, then the only valid thing to do if you want all solutions
> for a memoed recursive call to `p' is to either loop or report a runtime
> error.  The case of `p(InArgs, OutArgs) :- ... p(InArgs, ...) ...'
> is similar.
> 
> > Given the predicates :
> > 
> > :- mode p(in, out) is nondet.
> >  
> > p(A, B) :- e(A, B).
> > p(A, B) :- p(A, C), e(C, B).
> >  
> > e(1, 2).
> > e(2, 3).
> 
> What's the mode(s) for e/2?

e(in, out)

> 
> > and the call : 
> > 
> > p(1, A).
> > 
> > The check in simplify will see the left recursive call and issue the
> > message but if the predicate p has memo or minimal evaluation it will
> > terminate. The memo version will return A = 2 ; 3
> 
> Shouldn't it return the answers `A = 2 ; A = 3; error_or_loop'?
> That is, on the first call it should return the answer `A = 2',
> on backtracking it should return `A = 3', and when you
> backtrack into it for the second time it should either loop
> or report a runtime error.
> 

No. Here is a run down of what will happen.

First we get the answer 2 from the first disjunct, then on backtracking we
detect the recursive call and suspend it. We then attempt to backtrack
again but find no more disjuncts. At this point we return the answer 2
through the suspended call and get the answer 3. We then return the
answer 3 through the suspended call but the call e(3, A) fails. We are
now in a situation where all the available answers to the subgoal p(1, A)
have been returned to all suspended calls to this subgoal, we can then say
that the subgoal is completely evaluated and therefore has no more answers.