Tabling in Prolog: When Memoizing a Recursive Predicate Is Worth It

The decision: memoize a recursive predicate, or leave it on plain SLD resolution

Tabling (also called memoization, or SLG resolution in the literature) records each subgoal a predicate is called with, together with the answers it produced, in a table. A later call equivalent to an earlier one reuses the stored answers instead of re-entering the clauses. The practical question is narrow: does your predicate re-enter the same subgoal during a single query, and does that re-entry cost you termination or exponential time? If yes, tabling is usually the cheapest fix. If no, it adds memory and bookkeeping for nothing.

Two constraints drive the decision. Tabling is not part of ISO Prolog, so the directive and its semantics are engine-specific. And tabling changes what cuts and side effects mean inside the tabled predicate. Both are reasons to scope tabling to a few pure, recursive predicates rather than enabling it globally.

What tabling actually changes

Under plain SLD resolution, a recursive predicate over cyclic data can re-enter the same subgoal indefinitely. Transitive closure over a graph containing a cycle is the standard example: the query never finishes, because the same call reappears on every trip around the loop. Tabling breaks the loop by recognising the repeated subgoal and returning the answers already found for it.

The same mechanism collapses many dynamic-programming shapes from exponential to polynomial behaviour, because overlapping subproblems are solved once. That benefit is independent of termination, and it is often the real reason to table a predicate.

Engine support and directive syntax

Engine	Typical enabling directive	Notes
XSB	:- table p/2.	SLG resolution with well-founded negation; the reference implementation for tabling semantics.
SWI-Prolog	:- table p/2.	Tabling shipped during the 7.x series; supports variant and subsumptive modes plus lattice-style aggregation options.
YAP	:- table p/2.	Similar directive; check the manual for the mode options your version accepts.
B-Prolog	Action rules / tabling	Different surface syntax; consult the manual.
Trealla Prolog	:- table p/2.	Smaller implementation; verify which modes are supported.
GNU Prolog, ECLiPSe without a tabling library	None	Tabled code will not load; needs conditional compilation or a different algorithm.

The directive shapes above are the common form. Option names differ between systems, so confirm against the manual for the version you are actually running rather than copying a directive from a tutorial.

Trade-offs against pure SLD resolution

• Memory. Tables persist for the life of the query or until abolished. A predicate with an infinite answer set grows without bound.
• Overhead. Deterministic, tail-recursive predicates generally run slower when tabled, because every call pays for table lookup and answer storage.
• Cuts. A cut inside a tabled predicate can prune answers globally, producing incomplete result sets. Prefer wrapping the call site in once/1 instead.
• Side effects. write/1, assert/1, retract/1 and random generators run only on the first evaluation of a subgoal; later calls reuse the stored answer without re-running them.
• Negation and aggregates. Semantics diverge between engines, and an implementation may approximate SLG in some cases. Verify on the target engine.

A concrete pattern: transitive closure over a cyclic graph

Put the following in a file and consult it from the toplevel. This is an in-memory computation; no special permissions are required.

:- table tc/2.

edge(a, b).
edge(b, c).
edge(c, a).

tc(X, Y) :- edge(X, Y).
tc(X, Y) :- edge(X, Z), tc(Z, Y).

Query tc(a, X). The expected result is that the query terminates and enumerates each node reachable from a — here b, c, and a again through the cycle. Remove the :- table tc/2. directive and the same query does not terminate, because the cycle re-enters the subgoal tc(a, _) forever. That contrast is the check: if the tabled version terminates and the untabled version does not, tabling is doing the work you expect.

Optimisation variants need care

It is tempting to reuse the same shape for shortest paths, keeping only the cheapest distance per node pair. Do not assume plain subsumptive tabling does this. In SWI-Prolog, subsumption compares answers by term generality, so two distinct ground answers such as sp(a, c, 3) and sp(a, c, 5) do not subsume one another and both remain in the table. Engines provide separate lattice or aggregation options for keeping a minimum, and the option names differ between systems. Confirm the exact form in your engine's manual before relying on it, and treat any shortest-path example that uses only as subsumptive as unverified.

Validating and clearing table state

Tables are engine state, so inspecting them and clearing them are the two operations you need.

• statistics/2 with the tables key reports table counts and memory in SWI-Prolog. Read it before and after a large tabled computation to see growth.
• abolish_all_tables/0 clears all tables; abolish_table_subgoals/1 clears one. These are reported for SWI-Prolog — verify the predicates exist in your version.
• Inspection helpers such as get_table/2 (SWI) and table_dump/1 (XSB) appear in the respective manuals; check availability before scripting against them.
• listing/1 shows the tabled predicate's clauses, not the table contents.

Clearing tables changes engine state, so plan the rollback: if you abolish tables between queries to free memory, any later query that depended on stored answers recomputes from scratch. In a multi-threaded program abolition is not instantaneous, because other threads may still hold references — join worker threads before clearing.

Portability and conditional compilation

Code that depends on tabling will not load in a Prolog without it. If the program must run on more than one system, guard the directive:

:- ( current_prolog_flag(tabling, true)
   -> table tc/2
   ;  true
   ).

This keeps the file loadable elsewhere, but it does not make the untabled fallback terminate on cyclic data. Where tabling is unavailable, the fallback needs a different algorithm — an explicit visited set, iterative deepening, or a depth bound — not just the same clauses without the directive.

Limitations and what to verify

The behaviour described here is well established, but the specifics are version-dependent and were not tested against a running system while writing this. Before adopting tabling:

1. Confirm the directive and mode options in the manual for the exact engine version you target.
2. Run the transitive closure example with and without the directive and confirm the termination difference.
3. Test cut interaction on a small predicate containing a cut, and check whether answers you expect are missing.
4. Check side-effect behaviour by placing a write/1 inside a tabled predicate that is called more than once.
5. Measure table memory with statistics/2 on a realistic workload, not a toy graph.
6. If answers can be infinite, add an application-level bound; tabling does not make an infinite answer set finite.