Head Variable Elimination

The Jekejeke Prolog system is capable of eliminating the need for some head variables. We will describe in more detail the used technique. Compared to the other optimizations, this optimization does not have the greatest gain in average. Nevertheless we have implemented it. Since it is a compile time optimization no bad cases are to be expected. The optimization technique introduces an improved unification instruction. Normally during head unification each goal argument is unified with the corresponding clause skeleton. The new unification instruction allows unification between goal arguments.

To detect the situation when the improved unification instruction is applicable we had to broaden our variable analysis. Based on the variable analysis for body variable elimination we added additional attributes to a variable:

The min goal field can be used whether a variable occurs in the head and is thus a head variable. If the value of the min goal field is -1 it is a head variable. The structure flag can be used to determine whether a head variable needs special treatment. If the structure flag is false then we do not perform the ordinary unification with the variable during head matching. We call such a variable a temporary variable.

The min argument field is used when a temporary variable occurs multiple times in a head in argument position. We then place a combined unification instruction to directly perform unifi-cation between the corresponding argument positions in the calling goal. This saves ordinary unification since the combined unification covers two ordinary unifications:

Ordinary Unifications
unify_term _1, X
unify_term _2, X
Combined Unification
unify_term _1, _2

The min body field is then used to determine when the place holder needs to be unified. We place corresponding specialized unification instruction “unify_var” before the goal indicated by the min body position. This instruction is aware that the second argument is a variable and takes a slightly faster path for unification:

Ordinary Unifications
unify_term _1, X
Specialized Unification
unify_var _1, X

Temporary variables that don’t have an occurrence in the body are called extra variables. These variables will never see a corresponding specialized unification instruction “unify_var” instruction in the body. Therefore we arrange that these variables are allocated at the end of the display. The clause is then invoked with a shortened display without these variables.

The maximum of the min body field has a further purpose. It indicates when stack frame elimination monitoring can be started. Before the maximum of this field there will be still specialized unification “unify_var” instructions for temporary variables. An early eliminating would prevent us from unifying the temporary variable with the corresponding argument in the calling goal since the calling goal is stored in the parent stack frame.

The effect of this optimization can be observed by listing the intermediate form. We will start with the head variable optimization switched off:

?- set_prolog_flag(sys_head_variable, off).

We will explain the effect by means of the following Prolog text. It is the Prolog code for the naïve reverse implementation:

rev([],[]).
rev([X|Rest],Ans) :- rev(Rest,L), concatenate(L,[X],Ans).

concatenate([],L,L).
concatenate([X|L1],L2,[X|L3]) :- concatenate(L1,L2,L3).

We can now list the intermediate form of the concatenate/3 and the rev/2 predicate via the built-in friendly/1. As can be seen the enhanced unification instruction “unify_term” with two goal arguments is not yet used. Only the ordinary unification instruction “unify_term” with one parameter argument and one skeleton argument is used. Also no specialized unification “unify_var” for non-extra temporary variables is not yet seen:

?- friendly(concatenate/3).
concatenate([], L, L).
0 unify_atomic _0, []
1 new_bind L
2 unify_term _1, L
3 unify_term _2, L
4 init_display
5 dispose_bind L
6 last_cont

[...]
?- friendly(rev/3).
[...]

rev([X | Rest], Ans) :-
rev(Rest, L),
concatenate(L, [X], Ans).
0 new_bind X, Rest
1 unify_compound _0, [X | Rest]
2 new_bind Ans
3 unify_term _1, Ans
4 init_display
5 new_bind L
6 last_goal rev(Rest, L)
7 dispose_bind Rest
8 last_goal concatenate(L, [X], Ans)
9 dispose_bind X, Ans, L
10 last_cont

The intermediate form also contains the results of the body variable elimination and the stack frame elimination from the previous sections. For the body variable elimination this means the intermediate code is scattered with “dispose_bind” instructions. For the stack frame elimination this means that “last_goal” and “last_cont” instructions are seen.

The predicate concatenate/3 works as expected:

?- concatenate(X,Y,[1,2,3]).
X = [],
Y = [1, 2, 3] ;
X = [1],
Y = [2, 3]
?- concatenate([1],[2,3],X).
X = [1, 2, 3]

We will now switch on the head variable elimination optimization. This is done as follows:

?- set_prolog_flag(sys_head_variable, on).

We can now re-consult the Prolog text for the naïve reverse implementation. When generating the intermediate form during consult, the Prolog interpreter will now apply the head variable elimination optimization. We can again list the intermediate form of the concatenate/3 predicate and the predicate rev/2 via the built-in friendly/1:

?- friendly(concatenate/3).
concatenate([], L, L).
0 unify_atomic _0, []
1 unify_term _1, _2
2 init_display
3 last_cont

[...]
?- friendly(rev/2).
[...]

rev([X | Rest], Ans) :-
rev(Rest, L),
concatenate(L, [X], Ans).
0 new_bind X, Rest
1 unify_compound _0, [X | Rest]
2 init_display
3 new_bind L
4 call_goal rev(Rest, L)
5 dispose_bind Rest
6 new_bind Ans
7 unify_var _1, Ans
8 last_goal concatenate(L, [X], Ans)
9 dispose_bind X, L, Ans
10 last_cont

In the first rule of the concatenate/3 predicate we see that the variable “L” has been judged as an extra variable. Therefore the two ordinary unification instructions in line 3 and 4 were replaced by one enhanced unification instruction in line 2. Subsequently the “new_bind” instruction for the variable “L” was not anymore needed.

In the second rule we see that the variable “Ans” has been judged as a non-extra temporary variable. Therefore the ordinary unification in line 5 was replaced by a specialized unification in line 8. The “new_bind” instruction for the variable “Ans” was moved as well.

Further the call of the rev/2 goal does not do stack frame monitoring anymore.

The predicate concatenate/3 still works as expected:

?- concatenate(X,Y,[1,2,3]).
X = [],
Y = [1, 2, 3] ;
X = [1],
Y = [2, 3]
?- concatenate([1],[2,3],X).
X = [1, 2, 3]

Prior to release 0.9.0 there was only the concept of an extra variable. The concept of a temporary variable has then been introduced. The movement of the “unify_term” instruction still put penalty for non-deterministic predicates since the instruction has to be repeated during backtracking. The reason is that the variable binding caused by this instruction is logged in the trail and thus automatically undone during backtracking.

On the other hand the optimization seems to be beneficial to deterministic predicates. Especially to pro-gramming patterns of the following form:

    P(X,Y) :- G(X), B(X,Y).

If G is a guard that might or might not succeed execution without temporary variables turns out costly. The variable Y would always be unified, even when the guard fails. With temporary variables the variable is only unified when we pass the guard.

Comments