13.4 Rules as Programs

With the preliminaries out of the way, we can turn to compiling Prolog rules into bytecodes. We will turn each predicate into a class. The class has a method which, when you call it, has the semantics of the rules for the predicate.

13.4.1 inside

Think of inside as a method that takes two arguments, X and Y. It returns true when the arguments unify with one of the four definitions of inside shown in section 13. If either X or Y is a variable, then it is bound to a value such that one of the facts holds true. The definition of inside, written in pseudo-Java, is

 boolean inside(Object X, Object Y) {     if(unify(X, "baltimore") && unify(Y, "maryland"))          yield true;     if(unify(X, "maryland") && unify(Y, "united_states"))          yield true;     if(unify(X, "california") && unify(Y, "united_states"))          yield true;     if(unify(X, "san_francisco") && unify(Y, "california"))          yield true;     yield false; } 

Instead of returning true or false, the code instead performs a yield. The pseudo-instruction yield is like return, except that it remembers where it was when it returned. Each time you call inside, it picks up after the previous yield. Section 13.5 discusses how to implement yield using JVM instructions.

Consider the query

 ?- inside(X, united_states). 

It can be implemented using the inside method:

 Var X = new Var(); while(inside(X, "united_states"))     System.out.println("X = " + deref(X)); 

When run, this code prints

 X = maryland X = california 

The inside method is silent about its failures and yields true only on its successes until no more successes are possible. It fails to match inside(baltimore, maryland), but it finds a way to match inside(maryland, united_states), so it yields true with X set to maryland. The other two facts are checked similarly. After it has found that X = california is a successful substitution, inside does not find any more ways to unify the request with the rules it knows. Therefore, it yields false, which will terminate the loop.

It is necessary to call deref on X since we are interested in what X is bound to, not the variable X itself. Thus if X is bound to the string maryland, deref(X) will be maryland. In more complicated rules it is common to have one variable bound to another, and sometimes deref has to follow many links to get to the final value.

13.4.2 within

There are two different definitions for within:

 within(X, Y) :- inside(X, Y). within(X, Y) :- inside(X, Z), within(Z, Y). 

One way to look at within is as a function that takes two arguments, X and Y, and returns true if it was able to find bindings that satisfy either rule. This is an outline of these rules written in a pseudo-Java style:

 boolean within(X, Y) {    while(inside(X, Y))         yield true;    while(inside(X, Z))         while(within(Z, Y))              yield true;    yield false; } 

The yield instruction is used here to mean that the program signals that it has found a binding but that there may be more. The method returns its value, but when you call within again it picks up right after the most recent yield. This is much like the yield used in Sather iterators, as discussed in section 11.3.1.

13.4.3 yield and Backtracking

Defining yield this way implements backtracking. To compile within(X, Y), the program first tries all the ways it can to find inside(X, Y), which is the first definition of within. When that fails, it starts looking at the second definition of within, which first tries to find a Z such that inside(Z, Y) is true. Once it has found a value for Z, it tries to see if within(Z, Y) is true.

The question

 ?- within(X, united_states). 

can be answered by this method:

 test() {    Var X = new Var();    while(within(X, "united_states"))        System.out.println("X = " + deref(X)); } 

This code calls within to find out what's inside the United States.

First, within tries to find out what is immediately inside united_states by calling inside(X, "united_states"). The first thing inside finds is maryland, so it binds X to maryland.

The method inside yields true to within, which yields true. Although the method has yielded, it is still on the call stack, since it has not yet reached the end of the code. X is still bound to maryland. The call stack and variable bindings look like this:

The symbol indicates that the code is currently executing the method test, even though there are still two other calls on the stack. The program prints

 X = maryland 

Now test loops back and calls within again. The program picks up where it left off right after the yield in within. The variable X is made unbound so that the code can find new bindings for X. (The pseudocode shown does not show how variables become unbound. This will be discussed in greater detail in section 13.5.)

Next within loops back to call inside again, which continues after its first yield. The second test within inside fails, but the third test successfully binds X to california. Now inside and within yield again, and test prints

 X = california 

Going back into within, the program finds that inside has no more bindings for X, so it returns control to within. The binding of X to california is unbound. The Java stack now looks like this:

Now within has another rule to try: inside(X, Z), within(Z, Y). First within calls inside(X, Z). Z is a new variable, created just for the current code.

The method inside finds the first answer to this by binding X to baltimore and Z to maryland, and it yields true. The method within takes this binding of Z and recursively asks within(Z, Y). The call stack now looks like this:

The new within asks itself by its first rule if inside(maryland, united_states) is true. This is true, so inside yields true to the second call of within, which yields true to the first call of within, which yields true to the code shown. Now there is another binding for X, and the program prints

 X = baltimore 

Now the program returns to its original call of within, which loops back to see if it can prove within(maryland, united_states) again. It discovers that it cannot, and eventually it prints

 X = san_francisco 

Finally, the program is out of paths to follow, and it stops.