Description and Evaluation of a Generic Design to Integrate CLP and Tabled Execution
Modular TCLP
Abstract
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.
Previous implementations of TCLP systems which use entailment to determine call / answer subsumption did not provide a simple, uniform, and well-documented interface to facilitate the integration of additional constraint solvers in existing tabling systems, which would increase the application range of TCLP.
We present the design and an experimental evaluation of Mod~TCLP, a framework which eases this integration. Mod~TCLP views the constraints solver as a client of the tabling system. The tabling system is generic w.r.t. the constraint solver and only requires a clear, small interface from the latter.
We validate our design by integrating four constraint solvers: a re-engineered version of a previously existing constraint solver for difference constraints, written in C; the standard versions of Holzbauer'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. All the development work and evaluation was done in Ciao Prolog, a robust, mature, next-generation Prolog system.
Distribution
Ciao-1.15-3657-g2abfa1e.tar.gz
$ ./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
Distribution
CiaoDE-1.15-2373-gd8813ce.tar.gz
$ ./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:| LP | Tabling | CLP(DC) | OrigTCLP(DC) | ModTCLP(DC) | CLP(Q) | ModTCLP(Q) | ModTCLP(R) | ModTCLP(Latt) | |
| 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}_{lp,tab,clp,tclp} | |||||||||
| takeuchi{3,6,8}_{tab,tclp} | |||||||||
| sentinel{4,6,8}_{tab,tclp} |
Benchmarks
Benchmarks.tar.gz
- To execute all the programs:
$ ./go
- To specify some programs
$ ./go "step_10_t_dc"