How Generators Are Implemented in TAP Bindings.

version 0.1, August 2002

Alexander Kopilovitch
aek@acm.org,   aek@vib.usr.pu.ru

Table of Contents

The inner package Predicate_Services (of the main package Prolog) implements all supported kinds of predicates, including the generators.

Throught this text external predicates of the Generator_Shared kind are referenced as shared generators, and predicates of the Generator_Reenterable kind are referenced as reenterable generators.

1. General Scheme.

The general method of implementing the external predicates (of all kinds) in the TAP bindinds relies upon the 4th argument of the lsAddPred LS API call - a typeless pointer with no prescribed meaning. Here is the quotation from the Amzi! Logic Server User's Guide & Reference:

"The fourth argument is used in the callback. This argument is passed as the first argument to the extended predicate. This feature allows you to implement call backs to member functions of class. The extended predicate becomes a dispatch function, that uses the argument as a pointer to an object that is used to implement the extended predicate."

When the TAP bindings conveys an external predicate to the Logic Server, TAP always creates the predicate's descriptor (which contains the predicate's Prolog profile -- functor and arity, the predicate's kind, the pointer to the predicate's executable code, and some internal variables), and then submits that descriptor via 4th argument of the lsAddPred call, while the 3rd argument -- the pointer to the predicate's executable code -- points to the same function Mediator for all external predicates. So, when an external predicate is called, the Mediator receives control along with immediate access to the predicate's descriptor; therefore the Mediator is able to determine the predicate's kind and to act accordingly. The exact actions of the Mediator are described below, see Section 2.

For generators, that is, for external predicates of Generator_Shared or Generator_Reenterable kind, the TAP dealings are more complex. They involve several generator-specific variables: one common (that is, declared within the Prolog session descriptor) variable

   Generator_Recent_Result : Boolean;
and four variables within a predicate's descriptor:

---- used for all generators

   Continue_Flag     : Boolean;  -- temporary indicator for Guard
   Continuation_Call : Boolean;  -- source for Get_Call_Purpose function
   
---- used for reenterable generators only

   Instance_Counter  : Natural;   -- counts all alive instances of the predicate
   Current_Instance  : Positive;  -- source for Get_Instance_Id function
The rest of this section outlines TAP dealings for generators.

First, for all generators TAP changes the predicate's functor by prefixing it with ext_exec_ string; and for a reenterable generator it also increases the predicate's arity, adding an extra variable, which carries the predicate's instance number at the run-time.

Second, TAP submits to the Logic Server the ext_gate/0 external predicate, which controls the recursion within the additional rules -- wrappers for generators. The ext_gate/0 predicate is implemented by the Guard function. The workings of the Guard function are described below, see Section 3.

Third, TAP deals directly with the Prolog side, asserting additional rules (via lsAssertaStr LS API call), which act as wrappers for the predicates:

Fourth, when a query failed (that is, either Apply or Proceed function returns False), the Instance_Counter variable for all reenterable generators is reset to 0. This action has two consequences:

2. Mediator workings.

When the Mediator receives control, it immediately looks into the predicates descriptor (its single argument), and determines the kind of the predicate.

For a Pure_Predicate, the subsequent Mediator's dealings are fairly straightforward: it takes the address of predicate's executor function code and calls it; upon return from there, the Mediator simply returns the result of the predicate's executor.

For a shared generator, the Mediator sets the Continuation_Call variable (for future use of Get_Call_Purpose function) by copying the corresponding Continue_Flag Boolean variable (which is initialized to False, indicating first call); then the Mediator unconditionally sets that Continue_Flag variable to True for subsequent calls. Then the Mediator calls the predicate's executor; upon return from the predicate's executor, the Mediator stores its result internally, in the Generator_Recent_Result variable, for future retrieval by the Guard, and returns that result to the caller.

For reenterable generator, the Mediator first of all determines whether this call is for new instance initialization only or it is a call for already initialized instance. For that the Mediator looks into the last argument of the call (that is, the extra argument, provided by TAP bindings).

If that argument contains an unbounded variable then this is a call for initialization only, and Mediator calls the Enumerator function (passing it the predicate's descriptor), and then assigns the result of that call to its last argument, and exits, indicating success. Note, that the predicate's executor is not called in this case.

Otherwise, the last argument contains proper instance number, and the Mediator copies it into Current_Instance variable in the predicate's descriptor; additionally, if that new Current_Instance value is less than the corresponding Instance_Counter variable then the latter is reduced to the former, thus preventing the Instance_Counter variable from an overflow (this reduction is possible because the instances of the same predicate, which numbers are higher than the current instance number, are necessarily ceased to exist, that is, already failed). Then the Mediator deals with the Continuation_Call variable exactly the same way as for shared generators (note, though, that for reenterable generators Enumerator function resets the corresponding Continue_Flag variable to False again, see Section 4). After all these preparations, the Mediator calls the predicates's executor; upon return from the predicate's executor, the Mediator stores its result internally, in the Generator_Recent_Result variable, for future retrieval by the Guard, and returns that result to the caller.

3. Guard workings.

When the Guard recieves control, it retrieves the value of the Generator_Recent_Result variable (which was set by the Mediator), then unconditionally sets this variable to True, and then return the original value to the caller.

4. Enumerator workings.

The Enumerator function is always called for new instance of a reenterable predicate, and never otherwise. It receives access to the predicate's descriptor as its single argument. The function resets to False the Continue_Flag variable in the predicate's descriptor, then increases the Instance_Counter variable in the predicate's descriptor by 1, and returns the resulting value.

5. How Generator's Backtracking Works.

Let us first consider a shared generator p/n. It is equipped with the following rules:

   p(X1, ..., Xn)  :-  ext_exec_p(X1, ..., Xn).    % Rule 1
   p(X1, ..., Xn)  :-  ext_gate, p(X1, ..., Xn).   % Rule 2
If Rule 1 fails then the Generator_Recent_Result variable must be set to False and therefore ext_gate/0 in Rule 2 will fail (as it enters immediately after the failure of Rule 1), and the whole predicate p/n will fail with it. Note, that after that failure of the whole predicate p/n, the variable Generator_Recent_Result is True again (because Guard always restores it).

If predicate ext_exec_p/n succeeds then the Prolog cursor points at the beginning of Rule 2. On backtracking, the Generator_Recent_Result variable is True because:

So, ext_gate/0 will succeed and backtracking will get its way to the Rule 1.

Now let's consider a reenterable generator p/n. It is equipped with the following rules:

   p(X1, ..., Xn)              :-  ext_exec_p(X1, ..., Xn, K),   % Rule 0
                                   ext_cont_p(X1, ..., Xn, K).
                                   
   ext_cont_p(X1, ..., Xn, K)  :-  ext_exec_p(X1, ..., Xn, K).   % Rule 1
   
   ext_cont_p(X1, ..., Xn, K)  :-  ext_gate,                     % Rule 2
                                   ext_cont_p(X1, ..., Xn, K).
The situation is much the same as for the previous case of a shared generator. The only significant difference is that the instance number must be taken into consideration in this case. But as Prolog retains the Prolog variable K -- the instance number holder -- for a backtracking call, and as we immediately proceed from the Rule 0 to the Rule 1 and never return to the Rule 0 for backtracking, so the instances will never be confused.

6. Note On Logical Extension Libraries.

As TAP bindings must submit the ext_gate predicate to the Logic Server, there is a ground for a collision between a Prolog session and Logical Extension Libraries, and/or between several Logical Extension Libraries. When the libraries are loaded by the TAP bindings themselves, there is no such danger because in this case the caller and the libraries use common ext_gate predicate, which is submitted only once (and accordingly, all generators in the caller and in the libraries use common Generator_Recent_Result variable because they share the Prolog session descriptor). Otherwise (that is, when the libraries are loaded outside of TAP bindings), for preventing such a collision, the suffix _LSXn (where n is the LSX number, in the loading order; a loading procedure provides it) is added to the predicate's functor. For example, for first loaded LSX the predicate's functor will be ext_gate_LSX1. This adjustment prevents the collision and changes nothing else.