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

[Mark Anthony BROWN]

> 
> You should mention "declarative debugger" somewhere in the first
> few lines, so that someone who is not interested in this stuff
> can figure it what it is for without having to read down that far.
> 
> For example, you could add something like
> 
> 	% Summary:
> 	%	This module defines an interface intended to be used by
> 	%	a (not yet implemented) declarative debugger for Mercury.
> 
> at the start.

Done.

> 
> > This is achieved with a two level
> > % 	architecture: a back end generates EDTs for a running program,
> > % 	and a front end searches them for errors.
> > %
> > %	To support this, the interface to an EDT is decoupled from its
> > %	implementation.  The front end of a declarative debugger should
> > %	use the interface provided for the type evaluation_tree/1 and the
> > %	typeclass evaluation_atom/1, and their associated access procedures,
> > %	to analyse the EDT.  The back end should provide an instance
> > %	of evaluation_atom (NB: this is the purpose of the compiler
> > %	module evaluation_tree_gen.m).
> > %
> > %	The chief advantage of this decoupling is that a debuggee module
> > %	(back end) is free to vary the implementation of atoms without
> > %	affecting the debugger (ie the compiled debugger does not depend
> > %	on the debuggee's representation of atoms).  In particular, this
> > %	allows a debugger to be written, compiled and distributed _before_
> > %	the debuggee is written, without resorting to the use of the
> > %	ground representation.
> 
> Huh?
> 
> You must still be using a ground representation.
> The typeclass interface specifies that the representation must be ground!
> 

My fault, my terminology is bad.  I am trying to say that I don't want
the front end to depend on how constructors are tagged in the back end.
There are two broad approaches:

    - Represent atoms uniformly across all back end modules.  When a
      back end module creates an atom, it must convert from the
      representation it uses to the uniform representation the front
      end expects.

    - Let back end modules use any representation, but when the front
      end wants to look at an atom it calls a procedure provided by the
      back end module to do so.

The first option is what I meant by "the use of the ground representation".
Perhaps instead s/the ground/a uniform/?

Even better, I could replace the last sentence of the comment by:

	In particular, this allows a module to represent data the same
	way inside atoms as out.  This is quicker and more compact than
	using a uniform representation, because no conversion is required
	while building the EDT.
	
> > % Design:
> > % 	The decoupling is achieved by parametrizing most of the types in
> > % 	this module with the type used to represent atoms, which must be
> > % 	an instance of the evaluation_atom typeclass.  This module uses
> > % 	one of the type variables 'A' or 'E' whenever such a type is
> > % 	expected.
> 
> What do `A' and `E' stand for?

Their upside-down, back-to-front counterparts.  Or: `Atom' and
`External Atom'.

> (It might be clearer to use `Atom' or `AtomType' instead of `A'.
> Then again, it might not.)

How about I change the end of the comment to

	% ...such a type is expected:
	%
	%	A	for the type of atoms that are local to the module
	%		that produced the root node; and
	%
	%	E	for a type of atoms that are external to the module
	%		that produced the root node.

Maybe it would be a good idea to use type variables longer than one
character, but this doesn't seem to be the usual practice ;-)

> 
> > 	%
> > 	% The front end can request an analysis of a particular atom.
> > 	% The back end should generate an element of the following type
> > 	% (and inst).
> > 	%
> > 	
> > :- type analysis(A)
> > 	--->	nondet_wrong(pred(evaluation_tree(A)))
> > 	;	multi_wrong(pred(evaluation_tree(A)))
> > 	;	semidet_wrong(pred(evaluation_tree(A)))
> > 	;	det_wrong(pred(evaluation_tree(A)))
> > 	;	wrong_io(pred(evaluation_tree(A), io__state, io__state))
> > 	;	miss(pred(evaluation_tree(A)))
> > 	;	miss_io(pred(evaluation_tree(A), io__state, io__state))
> > 	;	unavailable.
> 
> You should document the meanings of all of these.

Ok.

> 
> miss_io, in particular, is quite mysterious to me.
> 
> > %-----------------------------------------------------------------------------%
> > %
> > % This section contains the interface that the back end must
> > % conform to.
> > %
> 
> You separated this section from the "interface to the back end" section,
> but I think they should be together.
> 

They are separated because they will be used in different areas, which
is not clear because nothing uses it yet.

The first section (data common to both front and back) contains types
that the back end produces elements of for the front end to look at.
These declarations need to be visible to the front end as well as any
back end.

The third section (interface that the back end must conform to) contains
types that the back end will produce elements of, but which the front
end will not look at directly.

The middle section (interface to the front end) contains types used
by the front end only, and provides procedures to navigate the EDT.  This
means that a high level interface can be presented to the front end
(via root/3 and child/2), while the back end interface (the typeclass
methods) remains low-level.

This file could arguably be split into two:

library/evaluation_tree.m:

	Would contain the first and third sections of the original,
	and would be implicitly imported whenever a module is
	compiled to generate EDTs.

library/evaluation_tree_interface.m:

	Would contain the second section of the original, and import
	evaluation_tree.  This would not be imported into back end
	modules, but should be explicitly imported by a programmer
	writing a front end.

Do you think this is a better idea?

> In particular, it's hard to understand the `analysis' type unless you
> see how it is used.
> 

In order to start the computation of a goal, or restart an implicitly
stored computation, the front end supplies the call (which is an atom
in its initial state) to atom_to_{wrong, miss}_analysis, and gets an
element of type `analysis' back.

An `analysis' is a closure that returns an EDT.  For wrong answer analysis,
there will be as many solutions as in the original procedure, so we
have different functors for each determinism category (I guess there
should be something to handle cc_* detisms).

For missing answer analysis, however, there is exactly one EDT produced
for a particular call, so the closure is always det and we need not make
the distinction.

The functors ending in `_io' contain closures that produce EDTs for
procedures that can do IO.

So the question is, where should this be documented?  I could describe
the overall scene in something like compiler/notes/compiler_design.html
and make references to it from here.  Or, when a front end is written
I can point to it as an example of use.

> > 	%
> > 	% For wrong answer analysis, the goal justification is a
> > 	% proof_tree for a computed answer.
> > 	%
> > 	
> > :- type proof_tree(A)
> > 	--->	local_call(evaluation_tree(A))
> > %	;	some [E] external_call(evaluation_tree(E))
> > %			<= evaluation_atom(E)
> > 	;	conj(list(proof_tree(A)))
> > 	;	disj(int, proof_tree(A))
> > 	;	switch(int, proof_tree(A))
> > 	;	if_then(proof_tree(A), proof_tree(A))
> > 	;	else(miss_tree(A), proof_tree(A))
> > 	;	not(miss_tree(A))
> > 	;	trivial.
> 
> You should document what the `int's represent.
> 

Ok.

> > 	%
> > 	% For missing answer analysis also, the goal justification is a
> > 	% tree that corresponds to the structure of the program.  It is
> > 	% the dual of the above structure: it represents which atoms
> > 	% were _not_ computed answers.
> > 	%
> > 	
> > :- 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.

Was my reference to it being a dual structure confusing?  I could
change it to something like "Its purpose is the dual of the above
structure's purpose..."

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