Turning Recursive Prolog into a Memoized Powerhouse with Tabling

Why the Classic Fibonacci Query Still Feels Like a Time Sink

Ask SWI‑Prolog to calculate fib(35,F) with the textbook recursive rule:

fib(0,0).
fib(1,1).
fib(N,F) :- N>1, N1 is N-1, N2 is N-2, fib(N1,F1), fib(N2,F2), F is F1+F2.

You’ll notice the query takes a few seconds. That’s because each call recomputes the same sub‑subproblems over and over again. The naive algorithm is exponential in N.

Enter Tabling – The Prolog Memoizer

Tabling, also called SLG resolution, is a built‑in mechanism in modern Prolog systems (SWI, YAP, SICStus) that caches the answers of a predicate the first time it is computed. Subsequent identical subgoals are answered from the cache, eliminating redundant work and guaranteeing termination for many left‑recursive or cyclic definitions.

In SWI‑Prolog you enable it with a simple directive:

:- table fib/2.

After adding that line, the same fib(35,F) query returns in milliseconds. The runtime automatically switches the predicate into tabling mode; you don’t need to rewrite the rule.

How Tabling Works Under the Hood

• When a subgoal fib(N,F) is first encountered, the interpreter stores the goal in a table and begins evaluating it.
• If the same goal is requested again before the first evaluation finishes, the interpreter suspends the new call and links it to the original. When the answer is finally found, all waiting callers receive it.
• Answers are stored forever (until the table is cleared or the predicate is redefined), so repeated queries are instant.

Practical Steps for SWI‑Prolog Users

1. Create a file fib.pl:

   :- table fib/2.
   
   fib(0,0).
   fib(1,1).
   fib(N,F) :- N>1, N1 is N-1, N2 is N-2, fib(N1,F1), fib(N2,F2), F is F1+F2.

2. Load the file in the REPL:

   ?- [fib].

3. Run a timed query:

   ?- time(fib(35,F)).

   You’ll see a result like F = 9227465 in milliseconds.
4. Compare with the naive version (fib0/2) to observe the difference in speed.

Inspecting the Table

SWI‑Prolog offers table_statistics/1 to see how many answers have been stored and how much memory they consume:

?- table_statistics(fib/2, Stats).
Stats = [answers(36), memory(1234)].

Replace 1234 with the actual memory figure returned by your interpreter. This helps you gauge whether tabling is blowing up memory for large problems.

Beyond Fibonacci – Real‑World Use Cases

• Graph reachability: tabling turns a depth‑first search into a linear‑time algorithm over the number of reachable nodes.
• Parsing: context‑free grammars can be parsed efficiently when left recursion is present.
• Dynamic programming: problems like the knapsack or edit distance become trivial when the subproblem results are cached.
• Constraint programming: tabling can be combined with CLP(FD) to prune large search spaces.

Trade‑offs and Caveats

• Memory consumption: each distinct subgoal and its answers remain in memory until the table is cleared. For problems with thousands or millions of unique subgoals, tabling can exhaust available RAM.
• Not universal: only predicates declared with :- table are memoized. Forgetting to add the directive means you’ll still pay the recursive cost.
• Dialect support: while SWI, YAP, and SICStus support tabling, some older or specialized Prolog systems may lack it or require a compile‑time flag.
• Debugging complexity: because answers are cached, debugging subtle bugs that depend on re‑evaluation can be trickier. Clearing a table with retractall/1 or retractall/2 may be necessary during development.

Actionable Takeaway

If you’re tackling a problem that involves repeated recursive calls—whether it’s a classic algorithm, a graph traversal, or a constraint‑laden search—try tabling first. Add the :- table directive, run time/1 to benchmark, and inspect table_statistics/1 to keep an eye on memory. For large data sets, consider clearing tables after each major phase or limiting the depth of recursion to avoid runaway memory usage.

With tabling, Prolog can turn an exponential nightmare into a linear‑time, memoized delight—without rewriting your logic.