☰

Tabling execution

Author(s): Pablo Chico de Guzmán Huerta, Joaquín Arias, The Ciao Development Team.

Stability: [beta] Most of the functionality is there but it is still missing some testing and/or verification.


This library package allows the evaluation of predicates using tabled resolution (tabling). Tabling is an alternative execution strategy for logic programs that records calls and their answers in order to reuse them in future calls. It improves Prolog declarativity and can improve efficiency by avoiding repeated computations [TS86,War92]. Tabling is guaranteed to terminate when Prolog programs have the bounded term-depth property. Some examples of the use of tabling can be found at the end of this section.

Tabling

Adding a table/1 declaration to a predicate makes the compiler and run-time system distinguish the first occurrence of a tabled goal (the generator) and subsequent calls which are identical up to variable renaming (the consumers). The generator applies resolution using the program clauses to derive answers for the goal. Consumers suspend the current execution path (using implementation-dependent means) and move to a different branch. When such an alternative branch finally succeeds, the answer generated for the initial query is inserted in a table associated with the original goal. This makes it possible to reactivate suspended calls and to continue execution at the point where it was stopped. Thus, consumers do not recompute those calls, but obtain instead the answers from the table where they have been previously inserted by the producer.

Predicates not marked as tabled are executed following standard SLD resolution, hopefully with (minimal or no) overhead due to the availability of tabling in the system.

Our current version of tabling only supports local evaluation and variant tabling [RRR96]. Local evaluation computes all the answers of a tabled predicate before returning any of them. Note that a call to a tabled predicate will never return if this call has infinite answers. Variant tabling considers two calls/answers to be the same only when they are identical under variable renaming.

By declaring a predicate as tabled, a program translation is performed to abstract the use of internal tabling primitives for the user. Our tabling implementation technique follows the -CHAT approach [DS99] which does not require major changes in the compiler or run-time system.

Tabled Constraint Logic Programming

The TCLP implementation allows the combination of tabling with constraints. The initial implementation described in [dGCHS12] has been modified by a modular implementation, called Mod TCLP, which is described in [AC19a]. By using the Mod TCLP interface of a constraint solver, e.g., :- use_package(t_clpq), the tabling engine uses the entailment check provided by the constraint solver to detect more particular calls / answers.

The TCLP interface of a constraint solver must implement the following interface:

call_domain_projection/2
answer_domain_projection/2
call_store_projection/3
answer_store_projection/3
call_entail/2
answer_check_entail/3
apply_answer/2

as an API for the tabling engine. Some examples of TCLP interfaces are different_constraints, t_clpq, and t_clpr libraries. Some examples of the use of TCLP can be found at the end of this section (with some examples of the TCLP interface).

Some TCLP applications

The current implementation of Mod TCLP has been used to develop more complex applications such as for implementing an Abstract Interpretation Algorithm [AC19b] or for Incremental Evaluation of Lattice-Based Aggregates in Logic Programming, described in [AC19c], and available as the Ciao :- use_package(tclp_aggregates) bundle.


Usage and interface

Documentation on new declarations

DECLARATIONtable/1
It declares a tabled predicate.

Other information

Some examples using Tabling

We now illustrate some of the uses of the package of tabling through examples. The following example defines a simple predicte path(X,Y) which returns the transitive closuer of edge/2 without entering loops:

:- use_package(tabling).
:- table path/2.

path(X,Y) :- path(X,Z), edge(Z,Y).
path(X,Y) :- edge(X,Y).

edge(a,b).
edge(b,a).

Other examples can be found in the source and library directories and in [dG12].

Some examples using Tabled Constraint Logic Programming

We now illustrate some of the uses of the package of t_clpq through examples. The following example defines a simple predicte fibonacci(N,F) which returns the fibonacci number F given the index N and returns the index N given the fibonacci number F:

:- use_package(tabling).
:- use_package(t_clpq).
:- table fibonacci/2.

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

Other examples can be found in the source and library directories and in [AC19a].

Some examples of TCLP interface

We now illustrate the implementation of a TCLP interface to link a constraint solver wiht the tabling engine through examples. The following example defines the interface of clpq wiht the tabling engine:

:- use_package(clpq).
:- use_module(library(clpq/clpq_dump), [clpqr_dump_constraints/3]).
:- active tclp.

call_domain_projection(Vars, st(Vars,_)).
call_entail(st(Vars,_), st(FGen-ProjGen)) :-
       Vars = FGen, clpq_entailed(ProjGen).
call_store_projection(_, st(Vars,_), st(F,Proj)) :-
       clpqr_dump_constraints(Vars, F , Proj).

answer_domain_projection(Vars, st(F,Proj)) :-
       clpqr_dump_constraints(Vars, F, Proj).
answer_check_entail(st(F,_), st(FAns,ProjAns), 1) :-
       F = FAns, clpq_entailed(ProjAns), !.
answer_check_entail(st(F,Proj), st(FAns,ProjAns), -1) :-
       F = FAns, clpq_meta(ProjAns), clpq_entailed(Proj).
answer_store_projection(_, St, St).

apply_answer(Vars, st(FAns,ProjAns)) :-  
       Vars = FAns, clpq_meta(ProjAns).

Other examples can be found in the source and library directories and in [AC19a].


Generated with LPdoc using Ciao