Body Variable Elimination

The Jekejeke Prolog system is capable of reclaiming variables during its execution. We will describe in more detail the used technique. This optimization technique introduces reference counting for variable place holders. During unification when a variable is bound to a term, the reference count of all the variables in the term is incremented by one. When the variable instantiation is undone the reference count of the variables in the unbound term is decremented by one. Since variable place holders start with a reference count of one, the reference count of a variable place holder should never reach zero this way.

Now a new instruction comes into play. The new instruction will be “dispose_bind” and it allows the explicit decrementing of the reference count of a variable place holder in the body. This instruction will be idempotent and it will only be applied when no choice points are left for the given clause. This allows constantly reclaiming variable place holders and the term structures that are bound by the variable place holders.

The decrementing of the reference count of a variable place holder and its delay of the corresponding “dispose_bind” instruction pose some overhead not necessary for non-deterministic predicates. The overhead can be minimized to simple counter checks and some speed up structure in the terms, leading to a surprisingly low additional cost. The implementation itself is based on a liveliness analysis of the clause variables. For each variable we determine the following two attributes:

The new instruction is then placed according to the above value. The “dispose_bind” instruction will be found in front of a goal call or a body end for those variables with max goal + 1 = goal index respectively clause size. Thus the “dispose_bind” instructions are placed at the earliest moment possible moment.

The effect of this optimization can be observed by listing the intermediate form. We will start with the head variable, stack frame and body variable optimization switched off. These optimizations are explained in a later sections and its presence would only complicate the current explanations. The switching off is done as follows:

?- set_prolog_flag(sys_head_variable, off).
?- set_prolog_flag(sys_stack_frame, off).
?- set_prolog_flag(sys_body_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 rev/2 predicate via the built-in friendly/1. As can be seen the instruction “dispose_bind” is not yet used:

?- 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 new_bind Ans
3 unify_term _1, Ans
4 init_display
5 new_bind L
6 call_goal rev(Rest, L)
7 call_goal concatenate(L, [X], Ans)
8 call_cont

The rest of the intermediate form is practically a literal translation of the head and the body of the clause. The head results in unify term instructions for each argument. The body results in goal call instructions “call_goal” for each goal. The intermediate form ends with a continuation call instruction “call_cont”.

The predicate rev/2 works as expected:

?- rev([1,2,3],X).
X = [3, 2, 1]

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

?- set_prolog_flag(sys_body_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 body variable elimination optimization. We can again list the intermediate form of the rev/2 predicate via the built-in friendly/1. There is no change for the first fact of the predicate rev/2, since the fact does not make use of any variables:

?- 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 new_bind Ans
3 unify_term _1, Ans
4 init_display
5 new_bind L
6 call_goal rev(Rest, L)
7 dispose_bind Rest
8 call_goal concatenate(L, [X], Ans)
9 dispose_bind X, Ans, L
10 call_cont

In the second rule of the predicate rev/2 we find that the “dispose_bind” instructions have been placed. Not all “dispose_bind” instructions have been placed before the continuation call. The “dispose_bind” instruction for the variable “Rest” has been placed before the last goal call, since this is the only variable that is not anymore used in the clause after this point.

The predicate rev/2 still works as expected:

?- rev([1,2,3],X).
X = [3, 2, 1]

The current implementation of body variable elimination is not based on some mode analysis such as free or ground [6]. The decrementing instructions are placed independent of the mode of the arguments. Nevertheless the mode has an effect on the decrementing. For example if a head argument is ground then the term unification will not increase the reference count of a variable place holder since the clause variable will be instantiated with a part of the ground term and not vice versa. As a result decrementing will always immediately remove the variable from the display and the trail.

On the other if a head argument is non-ground then there are two possible situations. The first situation is similar to the ground case. It happens when a clause variable will be instantiated with a part of the non-ground term. Again as a result the decrementing will always remove the variable. It can even be arranged that this situation also applies in a variable to variable instantiation. The second situation is when a variable of the non-ground term unifies with a part of a clause term. The reference count of the clause variables in the clause term will then be increased and the clause variables survive as long as the non-ground term survives.

The delay of the decrementing of a variable place holder has been implemented in the spirit of [7, section 4.4.1]. Namely we also reorder the variables of a clause with respect to their max goal value and can then simply move an index. Further we also pose a choice point condition. But it seems that our solution is a little bit more flexible, since we can still move the index when the choice point is later removed. But our system might forget about the decrementing when an outer choice point removal happens. So there is room for implementation improvement and better coverage in the benchmarks.

Kommentare