asserts and retracts with Automatic Rollback

Lately I've been working on a paper about worlds—more on this soon—and while I was looking around for related work I came across something really interesting.

Consider the different ways of representing state in Prolog. First, there's the functional way, in which the state of the entire program is passed around from predicate to predicate in the form of additional arguments. Although burdensome, this approach interacts well with backtracking: when a failure occurs, changes to the program's state are automatically rolled back.

Another way to represent state in Prolog is to use the built-in database manipulation predicates assert and retract. This imperative approach has the advantage of not requiring predicates to take additional arguments, but it unfortunately does not interact well with backtracking. This is because assert and retract are destructive operations, i.e., they survive backtracking. So when a failure occurs, the programmer must make sure that each assert is retracted and vice versa, which is not easy to get right.

If only the programmer had access to special variants of assert and retract that automatically undo their side effects when backtracked over, the imperative approach would enable some really interesting programming styles that you could never get away with in a "real" imperative language. Interestingly, Tim Menzies shows us how to implement these variants in just a few lines of standard Prolog. (I had never come across this trick before, but Tim's nonchalance makes me think that it's well known in the Prolog community.)

Here is a variant of the assert predicate that automatically retracts itself upon backtracking:

  assert2(X) :- assert(X).
  assert2(X) :- retract(X), fail.

The first clause above makes assert2 behave like a regular assert if the query in which it is used succeeds. But if the query fails, the program will eventually backtrack to the point where assert2 was used and try the second clause, which retracts the fact asserted by the first clause.

Similarly, we might define retract2 as follows:

  retract2(X) :- retract(X).
  retract2(X) :- assert(X), fail.

But consider what happens if retract2's argument is not already in Prolog's database. The first clause (which uses retract) will fail, so the program will try the second clause, which will assert a fact that was never retracted in the first place! We can fix this problem by refactoring retract2 into two predicates, as shown below:

  retract2(X)       :- X, reallyRetract2(X).
  reallyRetract2(X) :- retract(X).
  reallyRetract2(X) :- assert(X), fail.

And that's that.