Arne Skjærholt

Backtracking is probably the defining feature of Prolog. Abstractly, the execution of a Prolog program can be seen as traversing a tree, looking for a path that fits certain criteria. Each node represents a choice between several options, and are usually referred to as choice points (for reasons that should be obvious). If at any time the path taken is found to be inconsistent with the constraints, execution goes back to the previous choice point and tries the next option. The search is depth-first, left-to-right.

Now, as I've mentioned before, in Parrotlog this is implemented using continuations, based on example code from Graham's On Lisp book (chapter 22). Simply put, continuations allow you to restore the execution of your program to a previous state. For the C programmers, this is simillar to setjmp(3) and longjmp(3), but returning from the originating function doesn't invalidate the saved state. On Lisp chapter 20 has more about continuations, and so do the Parrot docs.

This, then, is the core of our backtracking, and with continuations it's actually pretty simple. Each time we encounter a choice point, we just store a continuation which will try a different value from the one we're going with right now. Failure is then just a matter of popping the top continuation of the stack (since we want to backtrack to the last choice point encountered, the LIFO semantics of a stack is what we want) and invoke it, returning execution to the choice point.We do this until we find a match, or we backtrack out of the search entirely.

Then we have cuts. A cut can be seen as pruning the search tree, or committing to some of the choices that have been made. We implement this just like Graham's Scheme code does: we mark the limit of the cut with mark(), which stores a subroutine reference to fail() on the stack, so that failure still consists of popping the top element off the stack and invoking it. Popping the mark will just result in a recursive call to fail(). cut() simply pops items off the stack until it finds the mark.

The main difference between my code and Graham's (apart from the fact that my code is PIR and his is Scheme) is that I explicitly thread the stack of continuations through the various functions as their first argument. This is based primarily on a gut feeling that it might come in handy at some later point. Someone once told me that global variables were a bad idea, and I've found that to be right most of the time. Primarily I think it might be useful for the metalogical predicates like findall/3 where the code will have several nested backtracking searches. I think a single global stack might work, but I'm not sure, and I think an explicit stack would make that code clearer anyways.