13.5 Implementing Rules

Now that we have some idea of how within should work, we discuss a way to implement it in JVM code. Because the JVM does not have a yield operation, we have to implement one ourselves. This is a simplified form of the technique used to compile Sather iterators in section 11.3.1.

The key to implementing yield is to create an object for each method. This object remembers the state of processing when the method was last called. The object has a single method, call, which contains the code for the method. Every time the code calls for a yield, the call method does a return. Before it returns, it sets a variable called state$, which indicates where in the body of the method it left off. The call method begins with a tableswitch, which is used to jump to the location right after the last return, as indicated by the state$ field.

The object must remember not only the last instruction the program was in but also what all of the variable bindings were. For this reason, everything that appeared in the pseudocode as a local variable is made a field of the class.

13.5.1 Implementing within

With these ideas in mind, here's how to implement within in Oolong:

 .class within .field state$ I            ; Remembers the state .field inside_1 Linside;   ; The inside for the first loop .field inside_2 Linside;   ; The inside for the second loop .field within_2 Lwithin;   ; The within used in the second loop .field Z LVar;             ; The variable Z .field stackTag Ljava/lang/Object;      ; The token 

This code declares the fields that will be needed to implement within. The variable state$ keeps track of the current location being executed within the code.

The fields inside_1, inside_2, and within_2 are used to implement the subgoals used in the rules. The fields are used to implement backtracking. While evaluating the first rule for within, the code creates an instance of inside and keeps it in inside_1. For the second rule, inside_2 and within_2 are used.

When within calls within recursively, each instance of within keeps its own copy of the within_2 field. This keeps the system from becoming confused while evaluating recursive rules.

The field Z is also used in evaluating the second rule. It holds the intermediate results of finding Z.

The field stackTag holds the token used for backtracking. Before each rule, the stack undoes all the bindings on the trail from the previous rule down to the current stackTag. Then it pushes a new token and remembers it in the stackTag.

This is the beginning of the call method:

 .method call(Ljava/lang/Object;Ljava/lang/Object;)Z .var 0 is this Lwithin; .var 1 is X Ljava/lang/Object; .var 2 is Y Ljava/lang/Object; aload_0 getfield within/state$ I        ; Get the state from this tableswitch 0                   ; Jump to the appropriate state:     state0                      ; The beginning     state1                      ; After the first yield     state2                      ; After the second yield     default: fail               ; All other cases 

The first thing the method does is to resume from its last location by checking the state$ field. There are four possible states: state0 (the initial state), state1 (right after the first yield), state2 (right after the second yield), and fail, the state that indicates that there are no more matches. The system always begins with state$ set to 0, so the code always begins at the next line (state0).

 rule1: state0:     aload_0                ; Undo bindings from prior calls     getfield within/stackTag Ljava/lang/Object;     invokestatic Prolog/undoBindings (Ljava/lang/Object;)V     aload_0                ; Mark the trail     invokestatic Prolog/marktrail ()Ljava/lang/Object;     putfield stackTag Ljava/lang/Object;     aload_0                ; Create a new inside object     new inside             ; Store it in inside_1     dup     invokespecial inside/<init>()V     putfield within/inside_1 Linside; loop0:                     ; Loop while inside yields true     aload_0                ; Call inside(X, Y)     getfield within/inside_1 Linside;     aload_1     aload_2     invokevirtual inside/call        (Ljava/lang/Object;Ljava/lang/Object;)Z     ifeq rule2             ; Go to the next rule                            ; if inside returns false     aload_0                ; Remember that the new state is 1     iconst_1     putfield within/state$ I     iconst_1               ; Yield true     ireturn state1:                    ; Pick up here when called again     goto loop0             ; See whether there are any more                            ; bindings for inside(X, Y) 

The above code implements the pseudocode

 while(inside(X, Y))     yield true; 

First, the code undoes any bindings from previous calls by calling undoBindings. Initially the stackTag is null, so no changes are made to the trail. Then the code pushes a new tag onto the trail with markTrail, and stores the resulting tag in stackTag.

Next, the code creates an instance of inside and stores it in inside_1. This allows the code to pick up using the same inside after the yield, which ensures that inside backtracks correctly. The method inside has its own state and may yield true more than once with different bindings. The code must ensure that all bindings are retrieved before going on to the second rule.

After initializing inside_1, the code goes into its while loop, beginning at loop0 and ending at the goto. On each pass through the loop, the field inside_1 is fetched and its call method invoked. The arguments are the X and Y passed to within.

When inside fails, within moves to the code at rule2, which implements the second rule. If inside succeeds, then within must yield true. It performs the yield by returning the constant 1. Before it can do that, it must set up state$ so that it picks up right after the return next time this method is called. This is done by storing 1 in state$.

The label state1 occurs right after the ireturn. This causes the system to loop back to find any more results from inside.

13.5.2 Implementing Conjunctions

Here is the code for rule2:

 rule2:     aload_0                ; Undo bindings down to the stack tag.     getfield within/stackTag Ljava/lang/Object;     invokestatic Prolog/undoBindings(Ljava/lang/Object;)V     aload_0                ; Mark the trail     invokestatic Prolog/markTrail()Ljava/lang/Object;     putfield stackTag Ljava/lang/Object;     aload_0                ; Create a new inside object     new inside             ; Store it in inside_2     dup     invokespecial inside/<init>()V     putfield within/inside_2 Linside;     aload_0                ; Create a new variable for Z     new Var                ; Store it in Z     dup     invokespecial Var/<init>()V     putfield within/Z LVar; loop2:                     ; While (inside(X, Z))     aload_0     getfield within/inside_2 Linside;     aload_1                ; Call inside(X, z)     aload_0     getfield within/Z LVar;     invokevirtual inside/call        (Ljava/lang/Object;Ljava/lang/Object;)Z    ifeq endloop2      ; Terminate the outer loop when                       ; inside fails     aload_0           ; Create a new within object     new within        ; Store it in within_2     dup     invokespecial within/<init>()V     putfield within/within_2 Lwithin; loop3:                ; While(inside(Z, Y))     aload_0     getfield within/within_2 Linside;     aload_1           ; Call inside(Z,Y)     aload_0     getfield within/Z LVar;     invokevirtual within/call        (Ljava/lang/Object;Ljava/lang/Object;)Z     ifeq endloop3     ; Terminate the inner loop if                       ; within fails     aload_0           ; Remember that the new state is 2     iconst_2     putfield within/state$ I     iconst_1           ; Yield true     ireturn state2:                ; Go here when     goto loop3 endloop3:     goto loop2 endloop2: 

This code is somewhat long, but it's constructed along the same lines as the code for rule1. The difference is that this time there are two subgoals that must be satisfied instead of one. This is called a conjunction.

The two subgoals share the intermediate variable Z. When this rule begins, it creates a new Variable and stores it in Z. That way the value of Z is remembered after control yields back to the calling method.

Where rule1 had one loop, rule2 has two loops, which are called loop2 and loop3; loop3 is nested with loop2. Loop loop2 loops over the results from inside(X, Z), and loop3 loops over the results of within(Z, Y). Before beginning loop3, a new instance of within is created. This resets within to handle a new binding of Z. (If we tried to use the old instance of within, its state would be incorrect.)

There is a new state associated with this code, state2, which occurs right after the ireturn instruction. This allows the code to return to the inner loop after true is yielded.

Here is the final bit of code for call:

 fail:            ; No more rules to try, so fail.    iconst_0      ; Return false, since there are    ireturn       ; no more bindings .end method 

This state is done when there are no more rules to apply. When the code from rule2 is done, it goes to endloop2. The labels endloop2 and fail refer to the same instruction, since the two labels occur right next to each other with no intervening code. The code here returns false. The caller should stop calling this object, since there are no more answers to be found.

13.5.3 Constructing within

Since instances of within are created, a constructor is required. A trivial one will do:

 .method <init>()V aload_0 invokespecial java/lang/Object()V return .end method