- Documentation
- Reference manual
- Tabled execution (SLG resolution)
- Example 1: using tabling for memoizing
- Example 2: avoiding non-termination
- Answer subsumption or mode directed tabling
- Tabling for impure programs
- Variant and subsumptive tabling
- Well Founded Semantics
- Incremental tabling
- Monotonic tabling
- Shared tabling
- Tabling restraints: bounded rationality and tripwires
- Tabling predicate reference
- About the tabling implementation
- Tabled execution (SLG resolution)
- Packages
- Reference manual
7.5 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).
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.