[m-dev.] Trailing

[Peter Schachte]

On Tue, 12 Aug 1997, Fergus Henderson wrote:

> > But there's no nondet frame to tie the trail to!  I don't
> > know how to handle this one, other than to force the compiler to
> > create an artificial choicepoint before the call to mangle_array/2,
> > and have the call to test/1 either backtrack into it or cut it away.
> > Is there an better alternative I don't see?
> 
> Hmm.  The current implementation handles this by attaching trailing
> information to "tickets" (stored on a ticket stack) rather than to
> choice points.  Perhaps that is not such a bad design after all?

It's not the tickets that save the current implementation from this problem,
it's the fact that the solvers are notified every time a choicepoint is
created.  That would solve the problem for my approach too, but I still 
think the cost is much too high (assuming choicepoints are created
reasonably often and trailing isn't done terribly often).

But I have another idea.  For this source code

	p(A, Z) :-
		(   mangle_array(A, A1),
		    test(A1) ->
			q(A1, Z)
		;   q(A, Z)
		).

we generate code that looks like

	prev_trail = trail_pointer
	call mangle_array/2
	if (call test/1) {
	    notify trailed functions that they are being trimmed
	    trail_pointer = prev_trail
	    call q/2
	} else {
	    untrail back to prev_trail
	    trail_pointer = prev_trail
	    call q/2
	}

So we don't need a choicepoint to tie the trail to, as long as we know
that the call to test/1 will leave the stack and choicepoint pointers
as it found them.

The only catch is that we use values of max_fr to "segment" the trail,
ie to decide when we need to trail something and when we don't, but
max_fr doesn't change in this scheme.  So the hack to work around that
would be to simply do max_fr++ immediately before the call to test/1,
and max_fr-- immediately afterwards (anywhere up to the next call).


-Peter Schachte      URL:  http://www.cs.mu.oz.au/~pets/
pets at cs.mu.OZ.AU     PGP:  finger pets at 128.250.37.150 for key
    Do insects spend hours demammaling their programs?