Tabling

Tabling (memoization of goals, SLG resolution) makes Prolog terminate on left-recursive and cyclic programs and avoids recomputation.

31.1 Basic tabling

:- table path/2.

edge(a, b). edge(b, c). edge(c, a). edge(c, d).

path(X, Y) :- path(X, Z), edge(Z, Y).    % left recursion — fine with tabling!
path(X, Y) :- edge(X, Y).

?- path(a, Who).                          % terminates: b, c, a, d

31.2 Dynamic programming for free

:- 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.

?- fib(1000, F).                          % instant

31.3 Answer subsumption (aggregation modes)

Modes: min, max, lattice(Pred/3), po(Pred/2), first, last, sum.

:- table shortest(_, _, min).

road(a, b, 4). road(a, c, 1). road(c, b, 2). road(b, d, 5).

shortest(X, Y, D) :- road(X, Y, D).
shortest(X, Y, D) :- shortest(X, Z, D0), road(Z, Y, D1), D is D0 + D1.

?- shortest(a, d, D).                     % D = 8 (a→c→b→d)

31.4 Well-founded semantics

Tabled negation tnot/1 handles programs with negation through recursion; answers can be true, false, or undefined (WFS).

:- table win/1.
win(X) :- move(X, Y), tnot(win(Y)).

31.5 Incremental tabling & more

:- table p/1 as incremental. + :- dynamic q/1 as incremental. — tables update automatically when dynamic facts change.

abolish_all_tables/0, shared tables across threads, subsumptive tabling, monotonic tabling.