|Did you know ...||Search Documentation:|
|Variant and subsumptive tabling|
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).
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
is true. Early completion (see section
7.4) in this case prevents enumerating all answers for
(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
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
... as subsumptive option and globally by
One may wonder why subsumptive tabling is not the default. There are also some drawbacks: