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 this file into XSB and type the query

         ?- path(1,Y).

and continue typing ;<RETURN> until you have exhausted all answers. Type the query again. Can you guess why the order of answers is different? Now type

         ?- abolish_all_tables.

and retry the path/2 query.$\Box$

Exercise 5.2.2   If you are curious, 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.3   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$

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.

The above examples show how a variant-based tabled evaluation can reduce certain redundant subcomputations over SLD. However, even more redundancy can be eliminated, as the following example shows.

Exercise 5.2.4   Begin by abolishing all tables in XSB, and then type the following query

	 ?- abolish_all_tables.
         ?- path(X,Y), fail.

Notice that only a single table entry is created during the evaluation of this query. You can check that this is the case by invoking the following query

         ?- get_calls_for_table(path/2,Call).

Now evaluate the query

         ?- path(1,5), fail.

and again check the subgoals in the table. Notice that two more have been added. Further notice that these new subgoals are subsumed by that of the original entry. Correspondingly, the answers derived for these newer subgoals are already present in the original entry. You can check the answers contained in a table entry by invoking get_returns_for_call/2 on a tabled subgoal. For example:

         ?- get_returns_for_call(p(1,_),Answer).

Compare these answers to those of p(X,Y) and p(1,5). Notice that the same answer can, and in this case does, appear in multiple table entries.

Now, let's again abolish all the tables and change the evaluation strategy of path/2 to use subsumption.

	 ?- abolish_all_tables.
         ?- use_subsumptive_tabling path/2.

And re-perform the first few queries:

         ?- path(X,Y),fail.
	 ?- get_calls_for_table(path/2,Call).
	 ?- path(1,5).
	 ?- get_calls_for_table(path/2,Call).

Notice that this time the table has not changed! Only a single entry is present, that for the original query p(X,Y).

When using subsumption-based tabling, XSB is able to recognize a greater range of ``redundant'' queries and thereby make greater use of previously computed answers. The result is that less program resolution is performed and less redundancy is present in the table. However, subsumption is not a panacea. The elimination of redundant answers depends upon the presence of a subsuming subgoal in the table when the call to p(1,5) is made. If the order of these queries were reversed, one would find that the same entries would be present in this table as the one constructed under variant-based evaluation.

Exercise 5.2.5   The reader may have noted that the predicates table/1, use_variant_tabling/1, and use_subsumptive_tabling/1 were referred to as directives, while the predicates auto_table/0 and suppl_table/0 were referred to as declarations. The difference is that the user can execute a directive at the command line but not a compiler declaration. For instance, restart XSB and at the prompt type the directive

         ?- table(dyn_path/2).

and

         ?- load_dyn(dyn_examples).

Try the queries to path/2 of the previous examples. Note that it is important to dynamically load dyn_examples.P -- otherwise the code in the file will be compiled without knowledge of the tabling declaration.$\Box$