Choosing and Using Prolog Tabling for Recursive Predicates

Decision and Constraints

Enable tabling when a predicate suffers from redundant recomputation, left‑recursion, or non‑termination under plain SLD resolution. The decision assumes you are working with a Prolog system that provides a tabling engine (e.g., XSB, SWI‑Prolog, YAP, B‑Prolog, Trealla, or Scryer). Enabling tabling introduces extra memory proportional to the number of distinct tabled subgoals and their answers, and it can change the semantics of cuts, assert/retract, I/O, and negation as failure.

Supported Systems Comparison

System	Tabling Support	Notable Features	Incremental Tabling	Answer Subsumption	Notes
XSB	Yes (core)	Well‑Founded Semantics, incremental tables, stratified negation	Yes	Yes (via table/2 with subsumption modes)	Mature, research‑oriented; good for logic programming with non‑monotonic constructs.
SWI‑Prolog	Yes (library(tabling))	table/1, mode‑directed tabling, answer subsumption, incremental options	Yes (incremental/2)	Yes (mode‑directed)	Widely used; documentation extensive; requires loading the tabling library.
YAP	Yes	XSB‑like tabling, mode‑directed, incremental	Yes	Yes	Performance close to XSB; compatible with many XSB programs.
B‑Prolog	Yes	Tabling + action rules, linear tabling	Limited	Basic	Optimizes for deterministic action rules; check incremental support.
Trealla	Partial	Basic table/1, goal‑wise tabling	No	No	Lightweight; verify that needed features (e.g., answer subsumption) are present.
Scryer	Partial	Experimental table/1, mode‑directed	No	No	Still evolving; consult release notes for current coverage.

Trade‑offs

• Performance: Tabling can turn exponential recursion (e.g., naïve Fibonacci or transitive closure) into polynomial or linear time by memoising subgoal answers.
• Memory: Each distinct tabled subgoal and its answer set consumes heap space; large search spaces may exhaust memory.
• Side effects: Cuts inside tabled predicates may prune answers unexpectedly; I/O and assert/retract assume a static predicate definition unless incremental tabling is used.
• Negation: Under tabling, negation follows Well‑Founded Semantics (XSB, SWI) so some goals may be undefined rather than simply true/false.
• Portability: The ISO standard does not define table/1/2; code must be guarded with conditional compilation or feature checks when targeting minimal Prolog systems.

Concrete Validation Example: Transitive Closure

Consider a directed graph defined by edge/2 facts. The transitive closure predicate tc/2 can be written as follows:

:- table tc/2.   % enable tabling for tc/2

% base case
 tc(X,Y) :- edge(X,Y).

% recursive step
 tc(X,Y) :- edge(X,Z), tc(Z,Y).

Without the table directive, a query such as ?- tc(a,X). may loop indefinitely on cyclic graphs (e.g., edge(a,b), edge(b,a)). With tabling, the engine stores each subgoal tc/2 call and its answers, guaranteeing termination and returning the set of reachable nodes without duplicate work.

How to Validate the Effect

1. Load your program into a tabling‑capable Prolog (e.g., SWI‑Prolog).
2. Run the query twice: once with the table directive present, once with it commented out.
3. Collect statistics before and after each run using statistics/2 (SWI‑Prolog) or the equivalent profiling predicate in your system.
4. Compare:
   • Number of logical inferences (inferences)
   • Global stack or table memory usage (globalused or similar)
   • Whether the query terminates and the answer set produced.
5. You should observe a drastic drop in inferences and memory usage when tabling is enabled, while the answer set (e.g., tc(a,b), tc(a,c)) remains the same.

Practical Checks and Limitations

• Memory growth: After a long‑running service, periodically invoke abolish_table/1 (or the system‑specific invalidation predicate) to free table space if the data set changes.
• Cut safety: Keep tabled predicates cut‑free when possible; if a cut is necessary, place it outside the tabled call and verify answer completeness with findall/3.
• Dynamic data: Use incremental tabling (e.g., table incremental/2 in SWI‑Prolog) or manually abolish and re‑assert tables after assertz/1 or retract/1 operations.
• Negation awareness: Test a simple self‑negating predicate like :- table p/0. p :- \+ p. and check whether the system reports undefined or flounders rather than looping.
• Mode‑directed tabling: When using answer subsumption (e.g., :- table fib(+,-).), confirm that the mode declarations match the intended aggregation (minimal, maximal, etc.) by inspecting the results with findall/3.