Incremental Evaluation of Lattice-Based Aggregates in Logic Programming using Modular TCLP
ATCLP
Abstract
Aggregates are used to compute single items of information from separate pieces of data, such as answers to a query to a logic program. Some examples are the maximum / minimum or the set of answers.
The computation of aggregates in Prolog or variant-based tabling can infinitely loop even if the aggregate only requires a finite amount of computations / answers. When answer subsumption / mode-directed tabling is used, termination improves but its behavior is not consistent.
We present a framework to incrementally compute aggregates for elements in a lattice. We use the entailment and join relations of the lattice to define (and compute) aggregates and decide whether some atom is compatible with (entails) the aggregate. The semantics of the aggregates so defined is consistent with the LFP semantics of tabling.
Our implementation is based on the TCLP framework available in Ciao Prolog and improves its termination properties w.r.t. similar approaches. Users can define aggregation operators and how answers are aggregated. Describing aggregates that do not fit into the lattice structure is possible, but some properties guaranteed by the lattice may not hold. However, the flexibility provided by this possibility justifies its inclusion. We validate our design with several examples and we evaluate their performance.
Distribution
Ciao-distribution-padl.tar.gz
$ ./ciao-boot.sh configure
$ ./ciao-boot.sh build core.ciaobase
$ ./ciao-boot.sh build core
$ ./ciao-boot.sh install
$ source ~/.bashrc
NOTE: Read core/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
We will now evaluate the expressiveness and performance of ATCLP w.r.t. pure Prolog and tabling. The ATCLP framework presented in this paper is based on TCLP, in turn implemented Ciao Prolog. The examples, benchmarks, and a Ciao Prolog distribution including the libraries and frameworks presented in this paper are available at http://www.cliplab.org/papers/padl2019-atclp/. All the experiments were performed on a Mac OS X 10.13.6 laptop with a 2 GHz Intel Core i5. Times are given in milliseconds.Benchmarks
Benchmark-padl.tar.gz
- To evaluate the programs in each directory:
$ ./go
- To specify some programs (e.g., program01.pl and program02.pl)
$ ./go "program01 program02"