Prolog Tabling with Aggregate Functions

Prolog tabling is found among different Prolog systems. In our system we view Prolog tabling as memoization of a given aggregate. The aggregate is computed for a predicate with clauses that are preceeded by a table/1 directive. Lets consider again our primes example. We have a simple prime tester:

% prime(+Integer)
prime(N) :-
    M is floor(sqrt(N)),
    between(2, M, K),
    N mod K =:= 0, !, fail.
prime(_).

We can now define a predicate primes/1 and preceed it by a table/1 directive. If the table/1 directive is used with a predicate indicator the given aggregate will be the empty aggregate function. As a result the aggregate will only do grouping but not apply any aggregate functions.

% primes(-Integer)
:- table primes/1.
primes(X) :-
   between(1,1000000,X), prime(X).

The benefit of memoization is now that the first call of the tabled predicate will materialize the aggregate and store it. Recurrent calls will simply retrieve the materialized aggregate and list it. This is seen in that recurrent calls are much faster, on the other hand memory was used:

?- time((primes(X), X>100)).
% Up 7,374 ms, GC 52 ms, Threads 7,328 ms (Current 07/28/19 14:55:05)
X = 101
?- time((primes(X), X>100)).
% Up 1 ms, GC 0 ms, Threads 0 ms (Current 07/28/19 14:55:09)
X = 101

We can also define a predicate count/1 and preceed it by a different table/1 directive variant. If the table/1 directive is used with a callable the given aggregate is derived from the aggregate functions specified in the callable. These aggregate functions will then be applied in addition to the grouping:

% count(-Integer)
:- table count(sum).
count(1) :-
   between(1,1000000,X), prime(X).

The benefit of memoization is now again that recurrent calls can retrieve the stored materialization. The aditional benefit is now that the aggregate function result is also stored. The memory requirement is lower when storing results instead of all the elements for the aggregate function:

?- time(count(X)).
% Up 7,156 ms, GC 37 ms, Threads 7,141 ms (Current 07/28/19 14:55:47)
X = 78499
?- time(count(X)).
% Up 0 ms, GC 0 ms, Threads 0 ms (Current 07/28/19 14:55:49)
X = 78499

The memoization is organized as a map from call pattern variants to materialized aggregates. This allows different call patterns individually computed, store and listed. Our implementation also allows recursive calls. A recursive computation is stored as soon as it is completed.

The recursive calls must be well-founded, we have not yet some mechanism in place to automatically compute fixpoints. In as far we can nevertheless demonstrate the combination of aggregate functions and recursive calls in a shortest path computation of an acyclic graph.

% path(+Vertex, +Vertex, -Integer)
:- table path(_,_,min).
path(X, X, 0).
path(X, Y, N) :-
   edge(X, Z), path(Z, Y, M), N is M+1.

% edge(-Vertex, -Vertex)
edge(a, b).         edge(a, c).
edge(a, d).         edge(b, c).
edge(c, d).         edge(c, e).
edge(d, e).

The untabled predicate would compute paths and number of hops, leading non-deterministically to different results. The aggregation picks those paths that have the smallest number of hops. We can ask open queries listing the aggregate function result and we can also ask closed queries testing the result:

This is a preview of the upcoming release 1.4.0 of Jekejeke Prolog due in a few days. There are still different possible developments ahead. An attractive future development would be to introduce OR-parallelism so as to reach parallel tabling, comparable to memoized Java parallel streams.

Open Source: Module "tabling"
https://github.com/jburse/jekejeke-devel/blob/master/jekrun/headless/jekpro/frequent/advanced/tabling.p
User Manual: Module "tabling"
http://www.jekejeke.ch/idatab/doclet/prod/en/docs/05_run/10_docu/05_frequent/07_theories/10_advanced/06_tabling.html