Tabled CLP: Description, Implementation and Evaluation of a Generic Design

Joaquin Arias - joaquin.arias@imdea.org
Manuel Carro - manuel.carro@imdea.org

Modular TCLP

Abstract

Logic programming with tabling and constraints (TCLP, tabled constraint logic programming) has been shown to be more expressive and in some cases more efficient than LP, CLP or LP + tabling.

Previous designs of TCLP systems did not fully use entailment to determine call / answer subsumption and did not provide a simple and well-documented interface to facilitate the integration of constraint solvers in existing tabling systems.

We study the role of entailment and projection in the design of a TCLP system, and present the design and an experimental evaluation of Mod TCLP, a framework which eases this integration. Mod TCLP views constraint solvers as clients of the tabling system, which is generic w.r.t. the solver and only requires a clear interface from the latter.

We validate our design by integrating four constraint solvers: a previously existing constraint solver for difference constraints, written in C; the standard versions of Holzbaur s CLP(Q) and CLP(R), written in Prolog; and a new constraint solver for equations over finite lattices.

We evaluate the performance of our framework in several benchmarks using the aforementioned constraint solvers. Mod TCLP was developed in Ciao Prolog, a robust, mature, next-generation Prolog system. Logic programming systems with tabling and constraints (TCLP, tabled constraint logic programming) have been shown to be more expressive and in some cases more efficient than those featuring only either tabling or constraints.

Distribution

 Ciao-distribution-tplp.tar.gz

- To install this distribution, descompress the file and compile with:
$ ./ciao-boot.sh configure --instype=local --core:m32=yes
$ ./ciao-boot.sh build_nodocs ciao
$ source core/etc/DOTprofile

NOTE: Read INSTALATION for required dependencies before build:
For Ubuntu: $ sudo apt-get install emacs build-essential texlive texinfo imagemagick gcc-multilib libc6-i386 libc6-dev-i386

Original TCLP

This is the implementation described in P. Chico de Guzmán, M. Carro, M. Hermenegildo and P. Stuckey. "A General Implementation Framework for Tabled CLP". In, FLOPS'12, May 2012.

Distribution

CiaoDE-1.15-2373-gd8813ce.tar.gz

- To install this distribution, descompress the file, compile and active:
$ ./ciaosetup user-install.
$ source ciao/etc/DOTprofile

NOTE: Read INSTALATION for required dependencies before build:
  • For Ubuntu:
    $ sudo apt-get install emacs build-essential texlive texinfo imagemagick gcc-multilib libc6-i386 libc6-dev-i386

Evaluation

The design we are presenting is likely to bring more flexibility to a system with tabled constraints at a reasonably price in implementation effort. We will support this claim with several examples. As it is usual with these cases, additional flexibility comes also with a performance price, which we will also evaluate. To perform this double validation, we have used four solvers with different characteristics in their implementation:


LPTablingCLP(DC)Original TCLP(DC)Mod TCLP(DC)CLP(Q)Mod TCLP(Q)Mod TCLP(R)Mod TCLP(Latt)
[original_]truckload{100,200,300}_{dc,t_dc}
step{10,20,30}_t_dc
fibonacci{89,610,28657,832040}_{dc,clpq,clpr}
{dist_cycles,dist_wo_cycles}_{left,right}_{lp,tab,clp,tclp}
takeuchi{3,6,8}_{tab,tclp}
sentinel{4,6,8}_{tab,tclp}
✓ = specify in which systems are written the programs

Benchmarks

Benchmark-tplp.tar.gz

To evaluate them, unzip the file and:
  • To execute all the programs:
    $ ./go
  • To specify some programs
    $ ./go "step_10_t_dc"
NOTE: active the correct distribution before the execution ( source [...]/DOTprofile )