
## 3.1.3 Wam Extensions

To fully exploit the potential of a query pack (shared computation and avoidance of unnecessary backtracking) changes have to be made at the level of the Prolog engine itself. The explanation assumes a WA M-based Prolog engine (Aït-Kaci, 1991) but a short explanation of the execution of disjunction in Prolog is given first, so that it becomes more easy to see what was newly introduced in the WAM.

Assume that the body of a clause to be executed is a, (b,c ; d ; e). Assume also that all predicates have several clauses. At the moment that execution has reached the first clause of c, the choice point stack looks like Figure 4(a): there are choice points for the activation of a , the disjunction itself, b and c .  The choice points are linked together so that backtracking can easily pop the top most one. Each choice point contains a pointer to the next alternative to be tried: only for the disjunction choice point, this alternative pointer is shown. It points to the beginning of the second branch of the disjunction. After all alternatives for b and c have been exhausted, this second branch is entered and d becomes active: this is the situation shown in Figure 4(b). At that point, the alternative of the disjunction choice point refers to the last alternative branch of the disjunction. Finally, once e is entered, the disjunction choice point is already popped.

![0_image_0.png](0_image_0.png)

When the goal a produces a new solution, all branches of the disjunction must be tried again. It is exactly this we want to avoid for query packs: a branch that has succeeded once, should never be re-entered. We therefore adapt the disjunction choice point to become an o-choice point which is set up to point into a data structure that contains references to each alternative in the or disjunction. This data structure is named the pack table. Figure 5(a) shows the state of the execution when it has reached c : it is similar to Figure 4(a). The o-choice point now contains the information that the first branch is being executed. As the execution proceeds, there are two possibilities: either this first branch succeeds or it fails.

We describe the failing situation for the first branch and explain what happens on success of