Potential Pitfalls in Tabling

While the judicious use of tabling can make some programs faster, its indiscriminate use can make other programs slower. Naively tabling append/3 is one case

append([],L,L).
append([H|T],L,[H|T1]) :- append(T,L,T1).

can, in the worst case, copy $N$ sublists of the first and third arguments into the table, transforming a linear algorithm into a quadratic one.

Exercise 5.2.5   If you need convincing that tabling can sometimes slow a query down, type the query:

         ?- genlist(1000,L),prolog_append(L,[a],Out).

and then type the query

         ?- genlist(1000,L),table_append(L,[a],Out).

append/3 is a particularly bad predicate to table. Type the query

         ?- table_append(L,[a],Out).

(i.e. with no genlist/2 and backtrack through a few answers. Will table_append/3 ever succeed for this predicate? Why not?

Suppose DCG predicates (Section 8) are defined to be tabled. How is this similar to tabling append?

Another issue to be aware of when using tabling in XSB is tracing. XSB's tracer is a standard 4-port tracer, that interacts with the engine at each call, exit, redo, and failure of a predicate (see Chapter 7). When tabled predicates are traced, these events may occur in unexpected ways, as the following example shows.

Exercise 5.2.6  

Consider a tabled evaluation when the query ?- a(0,X) is given to the following program

:- table mut_ret_a/2, mut_ret_b/2.
mut_ret_a(X,Y):- mut_ret_d(X,Y).
mut_ret_a(X,Y):- mut_ret_b(X,Z),mut_ret_c(Z,Y).

mut_ret_b(X,Y):- mut_ret_c(X,Y).
mut_ret_b(X,Y):- mut_ret_a(X,Z),mut_ret_d(Z,Y).

mut_ret_c(2,2).      mut_ret_c(3,3).

mut_ret_d(0,1).	     mut_ret_d(1,2).     mut_ret_d(2,3).

mut_ret_a(0,1) can be derived immediately from the first clause of mut_ret_a/2. All other answers to the query depend on answers to the subgoal mut_ret_b(0,X) which arises in the evaluation of the second clause of mut_ret_a/2. Each answer to mut_ret_b(0,X) in turn depends on an answer to mut_ret_a(0,X), so that the evaluation switches back and forth between deriving answers for mut_ret_a(0,X) and mut_ret_b(0,X).

Try tracing this evaluation, using creep and skip. Do you find the behavior intuitive or not?