proposed command set for the internal trace based debugger

[Lee Naish]

Peter Schachte <pets at students.cs.mu.oz.au> writes:

>On 5 Jun 1998, Lee Naish wrote:
> > Peter Schachte <pets at students.cs.mu.oz.au> writes:

> > >  EXIT	(correct solution)	|	(incorrect solution)
> > >		creep		|	     retry, creep
> > 
> > This is the best you can do for wrong answer diagnosis using the
> > standard Prolog commands.

> >  There can be multiple correct answers to q, r and s
> > which are irrelevant to the bug because don't lead to the instance of t
> > which has the wrong answer.  You still have to look at them all.  With
> > my method you look at (at most), one exit port for each of t, s, r and q
> > (in that order).

>This is a pretty convincing argument.

>My concern about this approach is that the code will, I expect, execute at
>"leap speed" at best, in order to keep enough information around to trace
>backward. This is quite slow.  With my approach, code executes at "skip
>speed," which can be pretty close to, if not equal to, full compiled speed. 

>Maybe the best approach would be a hybrid.  The computation could procede as
>you suggest to a certain depth, and just skip below that.  After the
>computation, tracing would procede as you suggest until you reach an
>erroneous computation that was skipped over.  Then recursively apply the
>hybrid approach.

I have not really thought about the low level details of how things are
implemented, and the difference between skip speed and leap speed (or
should that be creep speed).  Recomputation is generally the way to
avoid nasty constant factors and memory blowouts.  As long as
recomputation can be done (presumably its a bit tricky and brings up
issues related to destructive operations), then to achieve the better
search strategy for wrong answers you can expand the tree one level at a
time.  From an exit port (with a wrong answer), you want to recompute the
corresponding call until you get to *the same* exit in "skip things below
level N+1 mode" (where N is the current level).  To make things easier,
you only need to keep track of exit ports and don't need to keep
anything on backtracking (this is basically what declarative debuggers
like NUDE do).  This seems very complicated behaviour for a trace-based
debugger, but let me propose a couple of commands based on the trace
view to see if they seem reasonable (both are to be used a an exit port):

most_recent_exit_at_next_level
Goes to the most recent exit port at the next level (ie, the previous
line in the full trace, like prev).  Essentially moves down the proof
tree to the rightmost child.  This may require recomputation (which
should keep track of exit ports at the next level for all calls, not
just the last one, so we can implement prior_exit_at_this_level).

prior_exit_at_this_level
Goes to the most recent exit port of the previous call at this level
(like retry followed by prev; *not* the same as searching backwards for
an exit at this level since we want to ignore previous exits of this
call - perhaps a better name could be found).  Could give a warning if
the trace line before the corresponding call is not an exit.  Essentially
this jumps to the sibling to the left in the proof tree (if there is no
sibling then it jumps to the parent call and/or gives a warning).  This
command may not be possible without previously using last_exit_at_next_level.


Given that we will probably be doing recomputation anyway, the following
could be used in addition:

initial_exit_at_next_level
First exit *on current successful execution path* at next level.

subsequent_exit_at_this_level
Assuming we are currently at an exit on the right path, this will just
take ust to the next exit at this level.


	lee