Turn Prolog Recursion Into Fast, Terminating Queries with Tabling

Why Recursion Can Hang Your Prolog Query

When you model a graph in Prolog, a natural way to ask “is there a path from A to B?” is to write a recursive predicate. If the graph has cycles, that simple recursion can loop forever because the same sub‑goal is re‑invoked endlessly. The classic culprit is a left‑recursive definition of transitive closure:

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

With a graph that contains a cycle, the second clause keeps calling path(Z,Y) with the same arguments until the stack overflows or the query never returns.

Tabling to the Rescue: Memoizing Sub‑Goals

SWI‑Prolog’s tabling feature (also called SLG resolution) lets you declare a predicate as tabled. When a tabled predicate is called, the engine stores every distinct answer in a memo‑table and re‑uses it for subsequent calls. The declaration is simple:

:- table path/2.

Now the same path/2 definition will terminate on cyclic graphs, because the engine stops recomputing a sub‑goal once its answer is known. The result is that each unique answer is produced exactly once, even if the graph is large or contains many cycles.

Worked Example: Reachability on a Cyclic Graph

Suppose we have the following edges stored as facts:

edge(a,b).
edge(b,c).
edge(c,d).
edge(d,b).   % cycle: b → c → d → b
edge(d,e).

Without tabling, a query such as path(a,E) will never terminate because the recursion follows the cycle forever. Add the table declaration and run the query again:

?- :- table path/2.
?- path(a,E).
E = b ;
E = c ;
E = d ;
E = e.

Notice the query now returns four distinct answers and stops. The memo‑table contains the following entries after the query completes:

path(a,b)
path(b,c)
path(c,d)
path(d,e)

Each answer is produced once, and subsequent calls to path/2 reuse the table, making repeated reachability checks almost instant.

Performance Gains and Complexity

Without tabling, the left‑recursive transitive closure can have exponential recomputation: each call to path/2 may trigger many redundant sub‑calls. With tabling, the evaluation behaves like a bottom‑up fixpoint computation. For a graph with N nodes and E edges, the tabled version typically runs in O(N + E) time, whereas the untabled version may expand combinatorially on cyclic graphs.

SWI‑Prolog also offers answer subsumption to aggregate results directly in the table. For example, to compute the shortest distance between two nodes, you can declare:

:- table path(_,_,min).
path(X,Y,0) :- edge(X,Y).
path(X,Y,D) :- edge(X,Z), path(Z,Y,D1), D #= D1 + 1.

Here the engine keeps only the minimal distance for each path/3 pair, eliminating the need for a separate post‑processing step.

Trade‑offs and Caveats

• Memory consumption: The memo‑table grows with the number of distinct answers. On very large graphs, a tabled predicate can exhaust RAM before the query finishes. You can mitigate this with abolish_table_subgoals/1 to clear a table or by using incremental tabling (see below).
• Non‑logical side effects: If a tabled predicate contains I/O or dynamic database updates, the results may be inconsistent because the engine may skip re‑executing the side‑effecting goal for a cached answer.
• Portability: Tabling is not part of ISO Prolog. Code that relies on :- table may not run on systems like YAP or ECLiPSe without adaptation.
• Incremental tabling: SWI‑Prolog supports incremental tabling, which automatically recomputes tables when underlying dynamic facts change. This is useful for interactive knowledge‑base systems but adds overhead and complexity.

How to Verify Tabling Works in Your Environment

1. Load your graph facts into the Prolog REPL.
2. Run a query without the table declaration and confirm that the query either loops or times out.
3. Add :- table path/2. at the top of your file and reload.
4. Run the same query; it should terminate and return each distinct answer once.
5. Use statistics/2 to check table size: statistics(tables, Size). Verify that Size corresponds to the number of unique answers.

Actionable Takeaway

When you write recursive Prolog predicates that may traverse cyclic data, declare them as tabled immediately. This small change turns a potentially non‑terminating program into a sound, efficient query engine with minimal code changes. Just be mindful of memory usage and avoid side effects inside tabled predicates. If you need dynamic updates, consider incremental tabling or clear the table manually when facts change.