By default, SWI-Prolog (and other Prolog systems with tabling) create
a table per call variant. A call (term) is a variant of another
call (term) if there is a renaming of variables that makes the two terms
equal. See =@=/2 for
details. Consider the following program:
:- table p/1.
p(X) :- p(Y), Y < 10 000, X is Y+1.
p(1).
Calling p(X) creates a table for this variant with
10,000 answers. Calling p(42) creates a new table where the
recursive call (p(Y)) uses the previously created table to
enumerate all values 1 ... 41 before deriving p(42)
is true. Early completion (see section
7.4) in this case prevents enumerating all answers for p(Y)
(1 ... 10,000). As a result, the query below runs in
quadratic time and creates a 10,000 additional tables.
?- time(forall(between(1, 10 000, X), p(X))).
% 150,370,553 inferences, 13.256 CPU in 13.256 seconds
Subsumptive tabling answers a query using answers from a
more general table. In this case, this means it uses basically trie_gen/2
to get the answer p(42) from the table p(_).
This leads to the program and results shown below.
:- table p/1 as subsumptive.
p(X) :- p(Y), Y < 10 000, X is Y+1.
p(1).
?- time(p(_)).
% 140,066 inferences, 0.015 CPU in 0.015 seconds
?- time(t).
% 170,005 inferences, 0.016 CPU in 0.016 seconds
Subsumptive tabling can be activated in two ways. Per table
assign the ... as subsumptive option and globally by
setting the
table_subsumptive
flag to true.
One may wonder why subsumptive tabling is not the default. There are
also some drawbacks:
- Subsumptive tabling only provides correct support if instances (more
specific) queries indeed provides answers that are consistent with the
more general query. This is true for
pure programs, but not guaranteed for arbitrary Prolog
programs.
- Finding more generic tables is more complicated and expensive than
finding the call variant table and extracting the subset of answers that
match the more specific query can be expensive.
- Using subsumptive tables can create more dependencies in the call
graph which can slow down the table completion process. Larger dependent
components also negatively impact the issues discussed in section
7.4.
