|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
This may make you wonder why subsumptive tabling is not the default. There are also some drawbacks:
In the current implementation, SWI-Prolog only uses the more general table if this table is completed. This is likely to change in future versions.