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 WAM-based Prolog engine [2] 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

, the choice point stack looks like Figure 4(a): there are choice points for the activation of

, the disjunction itself,

and

. 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

and

have been exhausted, this second branch is entered and

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

is entered, the disjunction choice point is already popped.

**Figure 4:** Illustration of execution of disjunction in the WAM.
$\begin{figure}\begin{centering} \subfigure[Choice points just after entering {\e... ... e}.]{{\epsfig{file=wam1c.eps,width=.25\textwidth}}} \end{centering}\end{figure}$

When the goal

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 or-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

: it is similar to Figure 4(a). The or-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 the second branch. If the first branch has no solution, backtracking updates the alternative in the or-choice point, to point to the next branch in the pack table. The situation after the second branch is entered is shown in 5(b) and is again similar to 4(b). Suppose now that the branch with the goal

succeeds: the entry in the pack table with or-alternatives is now adapted by erasing the second alternative branch, backtracking occurs, and the next alternative branch of the or-choice point is taken. This is shown in 5(c).

When

produces a new solution and the or-disjunction is entered again, the pack table does no longer contain the second alternative branch and it is never re-entered. The pack table is actually arranged in such a way that entries are really removed instead of just erased so that they cause no overhead later.

**Figure 5:** Illustration of execution of pack disjunction on the WAM.
$\begin{figure}\begin{centering} \subfigure[The choice points just after entering... ....]{{\epsfig{file=packwam3.eps,width=.28\textwidth}}} \end{centering}\end{figure}$

Two more issues must be explained: first, the pack table with alternatives must be constructed at runtime every time the query pack is entered for evaluation. This is done by emitting the necessary instructions in the beginning of the code for the query pack. As an example, we show the code for the query pack a, (b,c or d or e) in Figure 6.

**Figure 6:** Abstract machine code for *a, (b,c or d or e)* .
$\begin{figure}\begin{tabbing} xxx \= xxx \= xxx \= xxx \= \kill \> \> construct\... ... \\ \> @3: \> call e \\ \> \> query\_pack\_prune \\ \end{tabbing}\end{figure}$

Finally, in the example it is clear that at the moment that all alternatives of an or-disjunction have succeeded,

can stop producing more solutions. So the computation can be stopped. In general - with nested query packs - it means that one pack table entry of the next higher or-node can be erased and this in a recursive way. The recursive removal of entries from the pack tables, is done by the instruction $query\_pack\_prune$ .

We have implemented this schema in ILPROLOG. Section 5 presents some measurements in ILPROLOG.