[m-dev.] Trailing

[Fergus Henderson]

Peter Schachte wrote:
> 				Trailing in Mercury

This proposal looks good.

> A much better approach, I believe, would be for the Mercury system to
> provide a function to be called to push an entry on the trail, and not
> to do anything special when a choicepoint is created. 

Yes, this is a much better approach.

> [value trail + function trail]

Agreed.

> The obvious thing to do is to merge the two trails using a tag bit to
> distinguish the cases.

Yes, except that on x86, I think function pointers aren't guaranteed to
be aligned, so there's no spare bits (although in practice they _are_
usually aligned, so maybe we can count on that).

> However, Zoltan has pointed out that this will
> very significantly slow the simple (common) case, so it should be
> avoided.  This means there will have to be two trails, which isn't a
> big deal.

I think the common case will be backtracking to a choice point
after there have been _no_ trail entries added.  For this common
case, it is faster if you only have to check one trail.

> So this suggests the following interface:
> 
> 	void  MR_trail_value(Word *address, Word value);
> 		Make sure that when the current execution is
> 		backtracked over, value is placed in address.
> 	
> 	enum {undo,commit} untrail_reason;

s/undo/MR_undo/
s/commit/MR_commit/
s/untrail_reason/MR_untrail_reason/

Also you should add `MR_exception' to this enum now rather than later.

> 	void *MR_cut_to_choicepoint(Word cp);
> 		Assigns cur_fr = cp, but first traverses the function
> 		trail calling (*reset)(value,commit) for each entry.
> 		This is the deepest of voodoo, mainly intended for
> 		Mercury developers to use to make sure that the
> 		MR_trail_function() protocol is observed.

Would it be better to make that

 	void *MR_cut_to_choicepoint(Word cp, untrail_reason reason);
 		Assigns cur_fr = cp, but first traverses the function
 		trail calling (*reset)(value,reason) for each entry.
		...

?

> I know there are probably not many (any?) predicates in the current
> Mercury system or library that can commit to a choice, but they can be
> written using the C interface.  It is debatable whether or not the
> complication necessary to support this facility is worthwhile.

What complication is necessary?

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