5.2.0.0.1 Exercises

Unless otherwise noted, the file $XSB_DIR/examples/table_examples.P contains all the code for the running examples in this section. Invoke XSB with its default settings (i.e., don't supply additional options) when working through the following exercises.

Exercise 5.2.1   Consult $XSB_DIR/examples/table_examples.P into XSB and and try the goal

         ?- path(1,X).

and continue typing ;<RETURN> until you have exhausted all answers. Now, try rewriting the path/2 predicate as it would be written in Prolog -- and without a tabling declaration. Will it now terminate for the provided edge/2 relation? (Remember, in XSB you can always hit <ctrl>-C if you go into an infinite loop).$\Box$

The return of answers in tabling aids in filtering out redundant computations - indeed it is this property which makes tabling terminate for many classes of programs. The same generation program furnishes a case of the usefulness of tabling for optimizing a Prolog program.

Exercise 5.2.2   If you are still curious, load in the file cyl.P in the $XSB_DIR/examples directory using the command.

         ?- load_dync(cyl.P).

and then type the query

         ?- same_generation(X,X),fail.

Now rewrite the same_generation/2 program so that it does not use tabling and retry the same query. What happens? (Be patient -- or use <ctrl>-C).$\Box$

Exercise 5.2.3   The file table_examples.P contains a set of facts

         ordered_goal(one).
         ordered_goal(two).
         ordered_goal(three).
         ordered_goal(four).

Clearly, the query ?- ordered_goal(X) will return the answers in the expected order. table_examples.P also contains a predicate

         :- table table_ordered_goal/1.
         table_ordered_goal(X):- ordered_goal(X).

which simply calls ordered_goal/1 and tables its answers (tabling is unnecessary in this case, and is only used for illustration). Call the query ?- table_ordered_goal(X) and backtrack through the answers. In what order are the answers returned?

The examples stress two differences between tabling and SLD resolution beyond termination properties. First, that each solution to a tabled subgoal is returned only once -- a property that is helpful not only for path/2 but also for same_generation/2 which terminates in Prolog. Second, because answers are sometimes obtained using program clauses and sometimes using the table, answers may be returned in an unaccustomed order.