5.2.4.0.1 Over-Tabling

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

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

is one such example. Doing so 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.7   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).

leaving off the call to genlist/2, and backtrack through a few answers. Will table_append/3 ever succeed for this predicate? Why not?

Suppose DCG predicates (Section 10) are defined to be tabled. How is this similar to tabling append?$\Box$

We note that XSB has special mechanisms for handling tabled DCGs. See Section 10 for details.