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

[Fergus Henderson]

On 10-Mar-1998, Oliver Hutchison <ohutch at students.cs.mu.oz.au> wrote:
> 
> > > > > compiler/simplify.m:
> > > > > 	Only report infinite recursion warning if a procedure has
> > > > > 	normal evaluation.
> > > > 
> > > > I think it would probably still be useful to issue this warning at
> > > > compile time even if there is a `pragma loopcheck', because in general
> > > > compile-time warnings are better than run-time errors.
> > > 
> > > What about the case of memoing. It is then possible that the call will not
> > > lead to infinite recursion? 

Sorry, I should have said it will always lead to either infinite recursion
or a runtime error.

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

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.  

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?
Is it just `e(in, out)', or does there have to be a `e(out, in)' mode too?

If memoed evaluation delays `p(A, C)' and calls `e(C, B)' in the reverse
mode, then yes it could terminate.  And that is what memoing might well
do in a non-strongly-moded language.  But I don't think memoing in Mercury
can do that.  I think memoing has to just block the whole disjunct
(in this case the whole clause) until all answers for the recursive
call are found.  And if the recursive call has the same input arguments
as the head, this will never happen.

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

(P.S. It seems like this example would be a good one for the test suite ;-)

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