Tabling in Prolog: Caching Results to Stop Infinite Recursion

Problem: Infinite recursion in plain Prolog

When a predicate calls itself without a terminating condition, Prolog will keep evaluating until the system runs out of stack space. This happens often when the recursion depends on a condition that never becomes false, such as a missing base case or a circular reference.

Why recursion can loop forever

The interpreter does not remember earlier results, so each recursive call is treated as a new computation. If the recursion can form a cycle, the same sub‑goal is generated repeatedly, leading to non‑termination.

Tabling: a built‑in memoization mechanism

Tabling stores the answer of a predicate the first time it is computed and reuses that answer on subsequent calls. In SWI‑Prolog the predicate is declared with the table directive.

How tabling works

When the :- table P/Arity. directive is present, SWI‑Prolog creates a table for P/Arity. The first evaluation computes the result, caches it, and returns it. Later calls with the same arguments fetch the cached value directly, avoiding recomputation and breaking cycles that would otherwise cause infinite recursion. For example, a call that would otherwise loop forever can finish instantly once the answer is cached.

Worked example

Consider a simple transitive‑closure predicate that should stop even if the graph contains cycles.

:- table reach/2.
reach(X, Y) :- edge(X, Y).
reach(X, Y) :- edge(X, Z), reach(Z, Y).

Here edge/2 is a base edge relation, and reach/2 is defined recursively. Without tabling, a query such as reach(1,5) could loop forever if the graph contains a cycle like 1→2→3→1.

Running the example

1. Start SWI‑Prolog in a terminal with normal user rights.
2. Load the program containing the directives above.
3. Enter the query reach(1,5).
4. Observe that the query terminates and returns the correct answer, even if a cycle exists.

If the :- table line is omitted, the same query may never finish.

Trade‑offs and limitations

Memory consumption

Each distinct argument combination stored in the table occupies memory. For large graphs with many vertices, the table can grow quickly and may exhaust available RAM. Monitoring with statistics/1 helps quantify the increase. For instance, run statistics(walltime) before and after enabling tabling to see the memory footprint.

Performance impact

For predicates with a small branching factor, tabling usually speeds up execution. For predicates that generate a huge number of intermediate states, the overhead of managing the table can outweigh the benefits. In extreme cases, excessive tabling may cause the process to slow down or crash due to memory pressure.

When to use tabling

Tabling is most useful for predicates that are purely relational and are called repeatedly with the same arguments, especially when recursion can create cycles. Typical cases include:

• Transitive closure or reachability queries.
• Parent/ancestor relationships in hierarchical data.
• Deductive database queries where the same sub‑goal appears many times.

If a predicate is deterministic and has a single base case with no cycles, tabling may add unnecessary memory overhead. In such situations, ordinary recursion without tabling is preferable.

Another example: parent/ancestor

Define a family tree relation and a parent/2 fact.

family(mary, john).   % Mary is parent of John
family(john, paul).   % John is parent of Paul
:- table ancestor/2.
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

Without tabling, a query like ancestor(mary, paul) would recursively walk the chain and could loop if the family facts contained a cycle (e.g., a self‑reference). With tabling, the intermediate result for ancestor(john, paul) is cached after the first call, so the second step reuses it and the query finishes quickly.

Verification steps

To verify that tabling is active, enable tracing with trace. Run the same query twice; the second call will show a “cache hit” message instead of a recursive call, confirming that the result was retrieved from the table. If memory becomes a concern, you can cap the table size using table_size/1. For example, :- table_size(10000). limits the number of entries; exceeding the limit causes older entries to be discarded, which may affect correctness for very large datasets. When a predicate is no longer needed, you can remove its table with abolish_table/1. This frees memory and is useful during experimentation.

Conclusion

Tabling gives Prolog programmers a practical way to eliminate infinite recursion and speed up pure‑logic definitions. By caching intermediate results, it turns exponential backtracking into linear‑time behavior for many recursive patterns. The main caution is memory usage; use tabling judiciously and verify its impact with simple measurements.