The joys of backtracking

I'm pleased to say that Parrotlog is now at a point where it can actually do stuff. It can call predicates and backtrack (more on that in a moment). Unification probably works as well.

Now, backtracking is tricky to get right. Currently Parrotlog has a problem with cuts. A cut is supposed to remove all choice points encountered after the currently executing predicate was invoked. Parrotlog's cut prunes all choice points since the invocation of the last predicate that matched successfully. Close, but no cigar.

Graham's CL implementation (that Parrotlog owes quite a bit to) solves this by taking a reference to the choice point stack on invocation and just restoring that on cut. That works because Lisp lists are cons cells, but Parrot RPAs aren't, so I'll have to be a bit more clever. At the moment, I've two possible outs: 1) Copy the whole stack on invocation. Not very sophisticated, but it works. 2) Change the mark method to generate unique marks each time the stack is mark, so that cut can backtrack arbitrarily far into the stack, as long as you know the ID of the destination.

I think I'm gonna take a look at the materials I have on the WAM as well, see if I can't get some inspiration from how cuts are implemented there. But first, I have to decide if I want sushi or crêpes for dinner. Choices, choices...

Leave a comment

About Arne Skjærholt

user-pic Norwegian, computational linguistics student, classical philologer.