Choice Point Elimination

The Jekejeke Prolog system is capable of omitting choice points for deterministic predicates. We will describe in more detail the used technique. The point of departure for choice point elimination is a naïve implementation of Prolog with cut. In this implementation defined predicates always create choice points after success and the cut only removes choice points upon redo. Choice point elimination now implements the following optimizations to reduce the consumption of choice points:

  1. Exit from Call last Clause: When a defined predicate was invoked for the first time and the last clause was found then don’t create a choice point.
  1. Exit from Redo last Clause: When a defined predicate was invoked an additional time and the last clause was found then release the current choice point.
  1. Cut on Call: The cut will remove all choice points up to its own true frame before succeeding. In doing so it will not destroy the bindings from the intermediate goals.

To explain the optimizations 1) and 2) we can use the following example Prolog text:

p(a).
p(b).

We have two facts. When the first fact matches, we need a choice point so that we can go to the second fact. In the naïve implementation we keep the choice point even when the second fact matches. We can test this as follows:

?- set_prolog_flag(sys_choice_point, off).
Yes
?- p(b).
Yes ;
No
?- p(X).
X = a ;
X = b ;
No

The set_prolog_flag/2 system predicate allows us to switch off choice point elimination. When we invoke p(b), we see that after the success the system will prompt. This is an indicative that choice points are still around. Further when we invoke p(X), we see that after the first and the second solution the system will prompt. The prompt is again an indicative that choice points are still around. In both cases we quit the prompt with a redo request.

Now let’s run the example with choice point elimination enabled. We can use the directive set_prolog_flag/2 to switch on the choice point elimination optimization:

?- set_prolog_flag(sys_choice_point, on).
Yes
?- p(b).
Yes
?- p(X).
X = a ;
X = b

As could be seen, after the success of p(b) we will did not get a prompt anymore. This is now an indicative that the creation of choice point in situation 1) has been omitted. Further we also don’t get a prompt anymore after the last solution of p(X). Therefore the creation of choice point in situation 2) has been omitted.

To explain the optimizations 3) we can use the following example Prolog text:

p(X) :- q(X), !.
p(b).

q(a).

The predicate q has just one fact and is invoked by the predicate p. The predicate p has one rule and one fact. The rule that precedes the fact has a cut, so that when the first rule has passed its cut, the fact will not anymore be considered. In the naive implementation of the cut, the cut will only remove the choice point of the first rule in a redo. It will therefore automatically keep the bindings of the intermediate goals. We can test this as follows:

?- set_prolog_flag(sys_choice_point, off).
Yes
?- p(b).
Yes ;
No
?- p(X).
X = a ;
No

The cut works as expected. Procedurally we can derive p(b) since the cut was not passed as the q invocation failed. Procedurally we can derive for p(X) only one solution X=a, since this time the cut was passed. Both queries again result in a prompt which we quit with a redo request again. For the second query the prompt is an indicative that cut left the choice point untouched upon exit.

Now let’s run the example with choice point elimination enabled:

?- set_prolog_flag(sys_choice_point, on).
Yes
?- p(b).
Yes
?- p(X).
X = a

For both queries we do not get a prompt anymore. For the second query this means that in situation 3) the choice points where already removed when the cut was passed. This completes our exemplar exposition of the choice point elimination optimization for defined predicates and the cut.

The clean implementation of the choice point elimination optimization took us quite some time. Especially the cut was quite challenging. Because we want to keep the instantiations of the intermediate goals the trail of the eliminated choice points cannot be undone. On the other hand the trail of an eliminated choice point has to be merged with the other trails, so that upon an outer backtracking the instantiated variables are still correctly reset. The solution to this problem is a global trail with pointers into it.

The optimization is quite fundamental, since without the ability to eliminate choice points the head variable elimination and the stack frame elimination would not be possible. For more details on these two optimizations see some later sections. It should also be noted that choice point elimination and clause indexing have a synergetic effect, since optimization 1) and 2) might happen more often to smaller groups of clauses. For more details on the clause indexing optimization see the next sections.

Choice point elimination is also available for system and custom built-ins. System built-ins are free to create and destroy arbitrary choice points. System built-ins can thus follow choice point elimination strategies that even reach into optimization 3). For custom built-ins defined via Java methods there is a special protocol for the elimination of choice points. The Java foreign predicate can indicate via the try flag in the call out object whether they want to create respectively keep a choice point. This caters for the optimizations 1) and 2).

Comments