[m-dev.] For review: declarative debugging back end (3/3)

[Mark Anthony BROWN]

> 
> On 16-Jul-1998, Mark Anthony BROWN <dougl at cs.mu.OZ.AU> wrote:
>
> > > > :- type miss_tree(A)
> > > > 	--->	local_call(evaluation_tree(A))
> > > > %	;	some [E] external_call(evaluation_tree(E))
> > > > %			<= evaluation_atom(E)
> > > > 	;	conj(list(miss_tree(A)))
> > > 
> > > Shouldn't that be `conj(int)'?
> > 
> > I don't think so.  In Lee's declarative debugging scheme, the children
> > of an `mp' node include `mp' nodes for each conjunct.  A miss_tree
> > holds the children of (the Mercury equivalent of) an `mp' node.
> 
> If a conjunction has a missing answer, it is not necessarily
> the case that all conjuncts will have a missing answer;
> only one conjunct need have a missing answer.
> 

Yes, but which one?  It is the purpose of the front end to prune away
subtrees based on the intended interpretation.  For example, given:

	p(X) :- q(Y), r(Y, X).
	q(1).
	q(3).
	r(1, 10).
	r(2, 30).

the success set of p is { p(10) }.  If the oracle (ie user) tells the
debugger that the intended success set was { p(10), p(30) }, then we
have a missing answer.  But we don't know what caused the problem, so
we must ask the oracle further questions.

If the intended success set of r is { r(1, 10), r(2, 30) }, then
r misses no answers and its subtree can be pruned.

If the intended success set of q is (say) { q(1), q(2), q(3) }, then
q has a missing answer -- we keep searching in this subtree.  In this
case q has no children, so we can't blame them for the missing q(2).
So we say q(2) is an uncovered atom.

Come to think of it, it's not true that only one conjunct _need_ have
a missing answer -- if the oracle says that q didn't have any missing
answers, then we should conclude that p(30) is the uncovered atom.

> I thought miss_trees represented missing answers.
> Is that not always the case? 

My comments were probably misleading.  I should have said that miss_trees
represent a justification for a missing answer.

More generally, an EDT represents some behaviour along with its
justification.  When analysing for missing answers, the behaviour that
is most useful is the success set for each given call.  The
justification is always just the behaviour of the children.

> (What does a `trivial' miss_tree mean?)

It means the _justification_ is trivial.  Eg, facts have trivial
justifications.

I think the best way to document this is in compiler/notes somewhere,
which will give an overview of the scheme and point to Lee's paper(s).
Any module that uses this scheme should give its own specific details
in comment, but refer to this central location for an overview.

Cheers,
Mark
-- 
Mark Brown  (dougl at cs.mu.oz.au)             |  Any technology that is
MEngSc student,                             |  distinguishable from magic
Dept of Computer Science, Melbourne Uni     |  is insufficiently advanced