[m-dev.] proposed command set for the internal trace based debugger

[Fergus Henderson]

On 02-Jun-1998, Zoltan Somogyi <zs at cs.mu.OZ.AU> wrote:
> 
> Peter Schachte wrote:
> > Wouldn't it be possible to have a debug version of the library that
> > makes file opening and closing commands "trail" their effects so they
> > can be redone?  Ideally it would be possible for writers of libraries
> > containing destructive modes to also write mostly destructive versions and
> > have the debugger optionally use those instead in a systematic way, so they
> > could be retried.  Note that when code is being "skipped" over (in Prolog
> > terminology), you can just use the destructive version, for full speed and
> > lower memory usage.
> 
> In fact we have a better scheme in mind (based on *all* I/O actions
> generating a log record, and being able to roll the log forward/backward
> at will), but that requires a significant amount of extra work. For the
> time being, we won't change the I/O library. (You could also apply the
> logging technique to other libraries, but automating the technique
> does not look feasible.)

I think you can combine the advantages of these two approaches.

First, let me explain the logging approach in a bit more detail.

Logging
-------
Obviously I/O can't be undone in the general case.
However, by keeping a log of previous actions,
and with the constraint that the I/O action performed after
an undo must match the action that was undone,
it is possible to support undo/redo of arbitrary I/O actions.
Rather than actually undoing the I/O, the "undo"
operation just resets the "current event" pointer
in the I/O event log.

What Zoltan talked about, the stuff we discussed in the meeting,
was having all I/O actions do the following:

	(a) first check whether there are any pending I/O events
	    recorded in the "pending" part of the log,
	    and if so, use the first such event instead of
	    performing an I/O operation
	    (if the event's operation isn't the same as the
	    operation currently being attempted, that is an error)

	(b) otherwise, after performing the I/O action,
	    record the action performed and its results
	    in the log

The log is sequence (e.g. array or linked list) of actions.  There are
two pointers into it, a pointer to the current action and a pointer to
the end of the log.  Operation (a) checks if current == end and if not,
it returns the event and advances the "current" pointer to the next
event.  Operation (b) appends a new event and the end of the sequence
and advances the "end" pointer.

Now, doing all this stuff manually would be tedious, even if we just
for library/io.m (and there are many others that do I/O or destructive update,
e.g. extras/odbc/odbc.m, extras/graphics/mercury_opengl/*.m,
library/array.m, library/store.m, etc.).

But fortunately I have just thought of a very nifty way of automating much
of it.  The key observation is that

	(1) all the actual I/O is done via `pragma c_code' procedures,
and
	(2) it should be reasonably easy to automate the insertion of actions
	    (a) and (b) for all `pragma c_code' procedures whose arguments
	    include a pair with type `io__state' (or `odbc__state', or
	    `store__store') and mode `di, uo'.

Conceptually, this is very much like tabling your I/O.
In fact, if you actually just use sequence numbers
for io__states (and similar types), then I think
the current tabling code would do it!
The use of sequence numbers for io__states can be
automated with a few small changes to the code
we generate for the C interface glue.

Using tabling wouldn't be quite as efficient as is possible, though, because

	i)   tabling indexes on all the input arguments,
	     whereas for this purpose we know that the sequence
	     number uniquely identifies the call, so
	     we can index only on the sequence number

	ii)  tabling uses a hash table when hashing on ints,
	     whereas if we know that ints are going to be
	     sequentially allocated, we can use an array

These problems could be solved by building some knowledge about state types
such as `io__state' into tabling code (which already has knowledge about
string, int, float, etc.).

But in addition, tabling wouldn't do _quite_ the right thing:

	iii) if you undo an action and then try to perform a different
	     action, it would go ahead and perform the action
	     rather than reporting an error.

But for the purposes of debugging, this wouldn't matter too much,
since most of the time the debugger should only try to redo
the same actions that were undone.  Exceptions to this might
occur if you modify the program being debugged while it is
being debugged, or if you use some debugger command to modify
the value of a variable, or possibly if some committed choice
predicate returns a different answer when it is called again.
However, in those cases it might arguably be better in many
situations to go ahead and do the I/O rather than reporting
an error.  So (iii) could be considered a feature rather than a bug.

I'm still undecided about whether it would be better to
add compiler support specifically for logging I/O, or to
just implicitly add `pragma memo' declarations for I/O primitives
and then use the ordinary tabling support.

> > You seem to have omitted the REDO port.  That one's pretty important.
> 
> We did not omit it by oversight. The Mercury execution model does not
> permit a redo port without requiring the compiler to perform a pessimization.
> This pessimization is:
> 
> 	When compiling a nondet predicate, just before the code that
> 	performs a successful exit, insert code that creates a new nondet
> 	stack frame on top of the nondet stack. The redoip slot of this
> 	frame should point to a new code label in the runtime, say
> 	"simulate_redo", which would perform a failure.  This label
> 	would therefore have the exact same effect as the current label
> 	do_fail, but the debugger would know that any stack frame
> 	that has this redoip represents a redo port, not an ordinary
> 	disjunct (which may have a do_fail redoip).
>
> It also requires undoing the optimization that removes nondet stack frames
> on last success (roughly parallel to "trust" in the WAM), although this
> is not a big deal.

I think you want to keep that optimization.
The "simulate_redo" frame should be pushed only
when doing a `succeed()', not when doing a `succeed_discard()'.
Furthermore, it should only be pushed if maxfr != curfr.
That way, you avoid the unwanted REDO-FAIL chains.

The only catch I can is this: once you get to the simulate_redo label,
how do you know which predicate it is that you are redoing?
I think you would need to actually have a "redo" label
for each procedure, and have the redoip slot of the extra frame
that you push point to this label.  The code at this label
would just call MR_trace(REDO, ...) and then fail().

> How strongly do people feel a REDO port is needed? I myself expect using it 
> very rarely, or not at all.

I think it would be useful.

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