Stack Frame Elimination

The Jekejeke Prolog system is capable of dropping stack frames for last call goals. We will describe in more detail the used technique. We have already seen the ingredients of a stack frame in the previous chapter. Among the fields of the stack frame we find the continuation. This field points to the old goal list skeleton and display. There are various options to implement this field. For the requirement of the resolution step it would be enough to point to the old goal list minus the old goal. For the purpose of obtaining a call chain it is more convenient to also include the old goal in the pointer.

When building the stack frame the Jekejeke Prolog interpreter includes the old goal skeleton and display in the continuation frame. There is a slight speed up by this method, since the access to the goal list succeeding the old goal is thus deferred to the new end body. Following this field from display to display the Jekejeke Prolog interpreter can generate a call chain at any time. This is for example used in the exception handling to generate a meaningful exception context. The call chain is available independent of some debugging mode. We use the following Prolog text as our first example to explain the stack frame:

?- set_prolog_flag(sys_stack_frame, on).
?- [user].
p :- q.
p.

q :- abc.
q.
^D

When the predicate p is invoked the Prolog interpreter will in turn invoke the predicate q, and subsequently the predicate r. There it will run into an undefined predicate exception. The exception will display the full call chain:

?- p.
Error: Undefined predicate abc / 0.
      abc / 0
      q / 0
      p / 0

The old goal skeleton and display is needed in a choice point to try further unifications. This gives us the idea that when there is no choice point that the old goal skeleton and display is not needed anymore. Unfortunately we cannot drop the old goal skeleton and display in all cases, since it serves us as the continuation. But there is one case where a drop of the old goal skeleton and display is feasible. We can drop it in case that the goal list succeeding the old goal is in itself an end body. We can then overwrite the continuation by the parent of the continuation, an early execution of the old end body.

The overwriting of the continuation by the parent continuation will shorten the call chain. That the goal list succeeding the old goal is an end body indicates that the old goal was a last call. Thus the call chain will be shortened when two conditions meet. An old last call and a new omitted choice point. We can make the two conditions visible by the following example.

p :- q.
p.

q :- abc.

The invocation of the predicate q is a last call. The predicate q itself will omit the choice point since there is no additional rule. Therefore when the optimization is in place, we should observe that the predicate q is not anymore part of the call chain:

?- p.
Error: Undefined predicate abc / 0.
      abc / 0
      p / 0

In the above example both conditions have met. In the first example the condition of an omitted choice point was not met. We will now produce an example where the condition of a last call is not met. The example is as follows:

p :- q, h.
p.

q :- abc.

The invocation of the predicate q is not a last call anymore since it is followed by call of the predicate h. But the predicate q itself will still omit the choice point. Nevertheless the optimization cannot take effect anymore and we will thus see the full call chain:

?- p.
Error: Undefined predicate abc / 0.
      abc / 0
      q / 0
      p / 0

The last call condition will be detected at runtime from the intermediate form. There is no special compile time instruction like “execute” in the intermediate form for the last call [4] of the parent frame. Instead we will simply detect that the goal call is followed by a continuation call. The goal call needs not to be a callable term at compile time it can also be a naked variable so that we will only know about the called predicate at runtime. Therefore the optimiza-tion applies also from within meta-predicates that have goal arguments. Among the meta-predicates that work with this optimization are call/1, (,)/2, (;)/2 and (->)/2.

The last call condition on the parent frame does not change at runtime since it depends on the compile time intermediate form. On the other hand the condition that a choice point has been omitted is not stable. When a clause matches we might detected that we cannot omit the choice point. But still at runtime the choice point can be removed later on by a cut. We have implemented the stack frame elimination in such a way that the omission of the choice point is constantly monitored. This is expressed by the new instructions “last_goal” and “last_cont”. This is seen in the intermediate form as follows.

?- friendly(p/0).
p :-
    q,
    h.
   0 init_display
   1 last_goal q
   2 last_goal h
   3 last_cont

[...]

As can be seen the monitoring is done on all goals and on the continuation. We will see in the next section about head variable elimination that under this optimization fewer goals will be monitored. The monitoring of all goals is necessary since any of the goals could be cut transparent and issue a cut. So particularly checking whether a goal has the form of the cut (!) would be of no avail. Since other meta-predicates such as (,)/2, (;)/2 and (->)/2 can issue a cut depending on the followed solution path during their execution.

That the cut can also provoke the shortening of the call chain as can be seen by the following example. The example is very similar to our first example where the optimization did not apply. The optimization did not apply since q had a second rule, and thus the choice point was not omitted. In the new example the cut will remove the choice point later on:

p :- q.
p.

q :- catch(abc, X, sys_print_exception(X)), !, abc.
q.

We use a catch/3 and sys_print_exception/1 to check the call chain of the first call of abc/0 before continuing with the cut and the second abc/0. The first call of abc/0 will show the full call chain. Whereas the second call of abc/0 will only show a shortened call chain:

?- p.
Error: Undefined predicate abc / 0.
      abc / 0
      catch/ 3
      q / 0
      p / 0
Error: Undefined predicate abc / 0.
      abc / 0
      p / 0

It should be noted that the optimization has also a positive effect on body variable elimination. Since we will simulate the end body of the last call, we will also invoke the “dispose_bind” instructions preceding the end body. As a result we will eliminate more body variables early on.

Comments