Using SWI‑Prolog Tabling to Force Termination and Memoize Recursive Predicates

What Problem Are We Solving?

Recursive Prolog predicates that are left‑recursive or mutually recursive can easily get stuck in infinite loops. Even when they terminate, the same sub‑computations may be repeated many times, causing performance regressions in production code. SWI‑Prolog’s tabled/1 directive guarantees that such predicates terminate (if they are logically finite) and that each distinct set of arguments is computed only once, with the result cached for future calls.

Desired Outcome

After applying tabling you should be able to:

• Run previously non‑terminating queries without hanging.
• Observe that repeated calls to the same predicate return instantly from the cache.
• Verify that the table memory stays bounded for the input size you care about.

Prerequisites

1. SWI‑Prolog 8.0+ – Tabling is supported in the core distribution. Install via sudo apt install swi-prolog or download from swipl.org.
2. Pure logical predicates – No assert/1, retract/1, or side‑effectful calls inside the tabled predicate. Impure predicates break the tabling guarantees.
3. A module or file where you can place the :- table directive. Tabling is scoped to the module; other modules will not see the table unless you export the predicate.
4. Test data that previously caused non‑termination. For example, a simple ancestor graph that is left‑recursive.

Step‑by‑Step Procedure

1. Define the Predicate

Place the :- table directive before any clause of the predicate you want to memoize. The syntax is:

:- table ancestor/2.

ancestor(X, Y) :- person(X), parent(X, Y).
ancestor(X, Y) :- person(X), parent(X, Z), ancestor(Z, Y).

Here ancestor/2 is left‑recursive in the second clause, which would loop without tabling.

2. Load the Module

Run SWI‑Prolog and load your file:

% swipl
?- [my_ancestor].
% true.

Ensure you have the facts for person/1 and parent/2 available in the same module or imported.

3. Verify Tabling Is Active

Use predicate_property/2 to confirm the predicate is tabled:

?- predicate_property(ancestor/2, tabled).
true.

Alternatively, table_status/1 shows the current state of the table:

?- table_status(ancestor/2).
% Table: ancestor/2
% Status: empty
% Answers: 0
% Size: 0
true.

4. Execute the Query

Run a query that previously would hang. With tabling it will terminate and produce all answers:

?- ancestor(alice, Descendant).
Descendant = bob ;
Descendant = carol ;
Descendant = dave.

Notice that the query completes quickly even if the ancestor chain is long.

5. Check Memoization

Run the same query again and observe the execution time drop dramatically. You can use time/1 to measure:

?- time(ancestor(alice, X)).
% 0.001 CPU in 0.000 real seconds
X = bob.
% 0.000 CPU in 0.000 real seconds
X = carol.
% 0.000 CPU in 0.000 real seconds
X = dave.
% 0.000 CPU in 0.000 real seconds

The second run shows almost zero CPU time because the answers were fetched from the table.

6. Inspect Table Size (Optional)

SWI‑Prolog exposes table_size/3 to see how many answers are stored:

?- table_size(ancestor/2, Answers, Size).
Answers = 3,
Size = 42.

Size is in bytes; for large graphs this can grow, so monitor it in long‑running servers.

Expected Checks

• Termination: The query returns a finite answer set and does not hang. If it still loops, the predicate may contain side effects or be non‑logical.
• Memoization: Repeated calls return instantly. Use time/1 or compare execution traces.
• Memory boundedness: table_size/3 or table_status/1 shows a reasonable number of bytes for the input size. If the table grows unboundedly, consider splitting the predicate.
• Correctness: The answer set matches that of a hand‑crafted, non‑tabled version for a small test case.

Recovery Options

Tabling is powerful but not a silver bullet. If you encounter issues, try these strategies:

• Remove tabled/1 and revert to manual memoization. Use assertz/1 or a dictionary to cache results.
• Split the predicate. If the table grows too large, isolate the expensive part into a separate tabled predicate with a narrower argument list.
• Reset the table. Use table_clear(ancestor/2) or table_reset(ancestor/2) to free memory after a batch job.
• Use :- table ancestor/2 as memo. The memo strategy stores only the first answer for each call, reducing memory at the cost of recomputation for multiple answers.
• Switch to iterative deepening. For very deep recursions where tabling memory is prohibitive, an explicit depth‑controlled loop may be safer.

Limitations & Caveats

• Tabling is not portable across all Prolog systems; the syntax and semantics differ.
• It retains all answers for the lifetime of the session unless cleared. Long‑running servers should periodically reset tables or use table_clear/1.
• Impure predicates, cuts (!), and dynamic database updates inside a tabled predicate can produce incomplete or incorrect tables.
• Recursive calls that are not logically finite (e.g., infinite streams) will still consume memory, so tabling does not magically bound everything.

Practical Verification Checklist

1. Run the non‑tabled version and confirm it hangs.
2. Add :- table, reload, and run the same query – it should terminate.
3. Use predicate_property/2 to confirm tabled flag.
4. Measure execution time for first and second runs.
5. Inspect table_status/1 for size and answer count.
6. If memory grows beyond acceptable limits, apply a recovery strategy.

By following this guide you can confidently apply tabling to any recursive predicate that needs guaranteed termination and efficient memoization in SWI‑Prolog.