Turning Recursive Ancestry Checks into a Linear Time Problem with SWI‑Prolog Tabling

Why a Simple Recursive Predicate Can Be a Performance Nightmare

When you first learn Prolog, the classic ancestor/2 predicate feels natural:

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

But as the family tree grows, the number of resolution steps explodes. Each call to ancestor/2 may re‑evaluate the same sub‑problems over and over, leading to exponential time or even infinite loops when cycles appear.

Enter Tabling: Memoizing Sub‑Goal Results

SWI‑Prolog’s tabling (SLG resolution) remembers the results of sub‑goals. When the same call is encountered again, the system simply looks up the answer in a table instead of recomputing it. This turns a potentially exponential algorithm into a linear‑time one.

Tabling is enabled with a declarative directive:

:- table ancestor/2.

After this, every call to ancestor/2 is automatically memoized.

Step‑by‑Step Example

Below is a complete SWI‑Prolog file that demonstrates the difference between non‑tabled and tabled execution.

% family.pl

% Base facts
parent(john, mary).
parent(mary, susan).
parent(susan, alice).
parent(alice, bob).

% Non‑tabled ancestor (commented out for clarity)
% ancestor(X, Y) :- parent(X, Y).
% ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

% Tabled ancestor
:- table ancestor/2.
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

% Simple query to force table construction
run_test :-
    time(ancestor(john, bob)).

Run the file with:
swipl -q -s family.pl -g "run_test, halt."

SWI‑Prolog will print the execution time and the number of resolution steps. On a typical machine you’ll see something like:
Time 0.000 seconds (1 CPU step, 5 resolution steps)

Without tabling, the same query would take many more steps and more time, especially if the tree were larger or had cycles.

Inspecting the Table

After running the query, you can inspect what the system stored:

?- listing(tabled(ancestor/2)).

This will print all the ancestor/2 answers that were memoized. It also shows the internal table structure, confirming that each distinct sub‑goal was evaluated only once.

Trade‑Offs and Practical Considerations

• Memory Usage: Every distinct sub‑goal and its answers stay in memory until the table is closed. On very large data sets, this can exhaust available RAM. Measure with memory/1 or the SWI‑Prolog profiler.
• Determinism: Tabled predicates are deterministic by default. If you need backtracking over multiple answers, use the tabled option det or explicitly ask for all solutions with findall/3.
• Compatibility: Tabling is a core feature of SWI‑Prolog, XSB, and YAP, but not all Prolog dialects support it. Verify the compiler flags and documentation for your environment.
• Loop Detection: The engine automatically detects ancestor loops and prevents infinite recursion. However, you must still be careful with predicates that modify the database during recursion, as this can invalidate memoized answers.

When to Use Tabling

Tabling shines for:

• Recursive definitions that revisit the same sub‑goal (e.g., transitive closure, reachability).
• Programs that need to avoid exponential blow‑up in the presence of cycles.
• Situations where determinism and repeatability of results are more important than minimal memory footprint.

Practical Checklist

1. Identify recursive predicates that may recompute the same sub‑goals.
2. Add :- table predicate/arity. before the definition.
3. Run the query with time/1 or the SWI‑Prolog profiler to confirm reduced steps.
4. Inspect the table with listing(tabled/1) to verify memoization.
5. Monitor memory usage; if it grows unacceptably, consider limiting the table scope or using table(ancestor/2, [det]). to force deterministic answers.

Conclusion

Tabling is a powerful, declarative tool that can turn a classic recursive Prolog pattern into an efficient, linear‑time algorithm. By simply adding a directive, you unlock memoization, loop detection, and deterministic behavior. Just remember the memory trade‑off and test your specific data set to ensure the benefits outweigh the costs.