When to Reach for Tabling in Prolog Instead of Hand-Rolled Memoization

Write transitive closure over a cyclic graph in plain Prolog and you'll hit the wall every Prolog programmer hits: the natural, left-recursive formulation loops forever. The usual fixes — threading a visited list through every clause, switching to iterative deepening, or rewriting the recursion to be right-recursive — all work, but they obscure the logic you were trying to express. Tabling (SLG resolution) is the feature that lets you keep the clean formulation and get termination anyway. The thesis of this post: if your predicate is a recursive relation over a finite, possibly cyclic domain, declaring it tabled is usually a better engineering decision than hand-rolling memoization — provided you keep the predicate pure.

What tabling actually does

Tabling changes the evaluation strategy. Under plain SLD resolution, Prolog proves goals depth-first and re-derives everything from scratch each time. Under tabled evaluation, the engine records each subgoal it calls and the answers derived for it. When the same subgoal comes up again — including cyclically, as in left recursion — the stored answers are reused instead of re-derived. This is essentially memoization built into the engine, and it's what makes Datalog-style evaluation possible inside Prolog.

The surface syntax is a directive placed near the predicate definition:

:- table reachable/2.

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

XSB, SWI-Prolog, YAP and B-Prolog all support tabling in some form, but the directive, its options, and whether a library must be loaded explicitly differ between systems and versions. Check the tabling chapter of your system's manual before copying syntax — treat the snippet above as representative, not portable gospel.

The worked example: cyclic reachability

Take a small directed graph with a cycle:

edge(a, b).
edge(b, c).
edge(c, a).   % cycle back to a
edge(c, d).

With plain SLD resolution, the query ?- reachable(a, Y). loops: reachable(a, Z) eventually reduces to reachable(a, Z) again, and depth-first search never escapes. With :- table reachable/2. in place, the same query terminates and returns the full transitive closure — Y = b, c, a, d — because the engine recognizes the repeated subgoal and feeds back only answers it has already found.

To check this on your own system: load the program, run the query without the directive and interrupt it once it's clearly looping, then add the directive and re-run. Compare the answer sets. Then try an acyclic graph and a large one to feel the trade-off described below. This is worth doing in at least two Prolog systems, since the directive availability and default tabling variant differ.

Why this beats hand-rolled memoization

The manual alternatives all have real costs. A visited-list accumulator makes every clause carry bookkeeping that has nothing to do with the relation being defined, and it changes termination behavior in subtle ways (it prevents infinite loops but can also prune legitimate paths in dense graphs if written carelessly). Iterative deepening guarantees completeness but re-does work at every depth. Asserting results into the dynamic database as a cache mixes effectful code into what should be a pure relation, which bites you later during backtracking.

Tabling gives you the declarative program and completeness over finite domains in one directive. It also opens the door to variants that plain memoization can't easily replicate: subsumptive tabling, and answer subsumption with a lattice or partial order, which let you compute aggregates like shortest paths directly instead of enumerating all paths and post-processing. These options are system-specific, so again, consult your manual.

The trade-offs you actually sign up for

Tabling is not free speed. It trades memory for time: tables retain subgoals and their answers for the duration of the query, so memory grows with the explored search space. On shallow, acyclic queries, tabled evaluation can be slower than plain recursion because of the bookkeeping overhead. And tabling does not rescue predicates that generate unboundedly many distinct answers or terms of growing size — the termination guarantee is about finite domains.

The sharper constraint is purity. Cut, negation, and side effects (assert/retract, I/O) inside tabled predicates do not behave exactly as they do under SLD resolution, because answer reuse changes when and whether clauses execute. Treat this as a design rule rather than a defect: keep tabled predicates pure and declarative, and push effects to the caller. If you're unsure how your system handles a specific construct, probe it experimentally with a tiny tabled predicate before relying on it.

A decision rule you can apply

Table a predicate when the relation is naturally recursive over a finite, cyclic domain: graph reachability, grammar parsing, type hierarchies, ontology queries. Keep plain recursion — with explicit pruning or iterative deepening — when you need tight control over search order, when pruning is the point of the algorithm, or when the predicate must perform effects. The practical check is cheap: declare the table, run your real query, and compare termination, answer sets, and memory against the untabled version on both cyclic and acyclic inputs. Your own measurements on your own system beat any general claim, including this one.