Tabling guarantees logically correct results and termination provided
the computation only involves terms of bounded size on pure
Prolog programs, i.e., Prolog programs without side effects or pruning
of choice points (cut, ->/2,
etc.). Notably pruning choice points of an incomplete tabled goal may
cause an incomplete table and thus cause subsequent queries for the same
goal to return an incomplete set of answers. The current SWI-Prolog
implementation provides several mechanisms to improve on this situation.
- Dynamic Strongly Connected Components (SCC)
Tabled goals are completed as soon as possible. Each fresh
tabled goal creates a scheduling component which the system attempts to
solve immediately. If a subgoal of the fresh goal refers to an
incomplete tabled goal the scheduling components for both goals are
merged such that the related goals are completed together. Dynamic
rather than static determination of strongly connected components
guarantees that the components are minimal because only actually reached
code needs to be considered rather than maximally reachable code.
Minimal SCCs imply that goals are completed as early as possible.
This implies that tabled goals may be embedded in e.g., findall/3
or be used as a condition as long as there is no dependency (loop)
with goals outside the findall/3
or condition. For example, the code below misbehaves when called as p(X)
because the argument of findall/3
calls a variant of the goal that initiated the findall goal. A
call p(1) however is ok as p(1) is not a
variant of
p(X).
p(X) :-
findall(Y, p(Y), Ys),
...
- Early completion
Ground goals, i.e., goals without variables, are subject to early
completion. This implies they are considered completed after the first
solution.
