Logic programming systems featuring Constraint Logic Programming (Jaffar and Maher 1994) and tabled execution (Tamaki and Sato 1986; Warren 1992) have been shown to increase the declarativeness and efficiency of Prolog, while at the same time making it possible to write very expressive programs. Previous implementations fully integrating both capabilities (i.e., forcing suspension, answer subsumption, etc. where it is necessary in order to avoid recomputation and terminate whenever possible) did not have a simple, well-documented, easy-to-understand interface which made it possible to integrate arbitrary CLP solvers into existing tabling systems. This clearly hinders a more widespread usage of this combination.
In our work, we examine the requirements that a constraint solver must fulfill to be easily interfaced with a tabling system. We propose a minimal set of operations which the constraint solver has to provide to the tabling engine. These operations are based in only four objects (Vars, Dom, ProjStore and Store). Vars is a list with the constrained variables of a call. Dom and ProjStore are the representation of the projection of the constraint store of a call. Store is the representation of the constraint store of a generator and is used by the external constraint solver to reinstall it when the generator is complete.
The two main operations to be provided by the solver are: (i) entailment, entail(+Vars A, +Dom A, +DomB , +ProjStoreB ), which checks if the call/answer constraint store (VarsA and DomA) is entailed by the previous call/answer constraint store (DomB and ProjStoreB ) and (ii) projection, executed in two steps: project_domain(+Vars, -Dom) , that pre-computes an object (Dom) used during the entailment, and project_gen_store(+Vars, +Dom, -ProjStore) , which is executed when the entailment fails.
The compiler performs a shallow program transformation adding tabled_call/1 to control the tabled execution and new_answer/0 to collect the answers. These two predicates invoke the operations of the interface during tabled execution. Fig. 1 contains a Prolog version of tabled_call/1 which specifies its implementation and the control flow of the execution. This specification shows that when a new call is entailed by a previous generator, its execution is suspended, unlike in usual tabling, where suspension happens only when variant calls are found.
We validate experimentally our design with three use cases. First we re-engineer a
Joaquín Arias et al. previously existing tabled constrain domain (difference constraints (Chico de Guzmán et al. 2012)) in Ciao (Hermenegildo et al. 2012). This solver is implemented in C, so the arguments of the interface represent the memory address of C structures. Then we integrate Holzbauer’s CLP(Q) (Holzbaur 1995; Holzbaur 1992) implementation with Ciao Prolog’s tabling engine. In this case existing CLP(Q) predicates already provide the necessary functionality so we only need to write simple bridge predicates (see Fig. 2). project_domain(_, _). project_gen_store(V, _, (F, St)) : ¡
clpqr_dump_constraints(V, F, St). project_answer_store(V, _, (F, St)) : ¡
clpqr_dump_constraints(V, F, St). entail(V, _, _, (V, St)) : ¡ clpq_entailed(St).
current_store(_). reinstall_store(_, _, _). apply_answer(V, _, (V, St)) : ¡
clp_meta(St).
With these two constraints solvers we evaluate on one hand the cost of adopting a more modular framework versus the previous non-modular implementation of difference constraints, and on the other hand we highlight the benefits of being able to interface easily more constraint solvers: using TCLP(Q) gives more expressiveness and in some cases better performance that TCLP(Diff ) (see results of the reverse Fibonacci benchmarks in Table 1) since by using TCLP(Q) we can write programs in way which exploits better the advantages of constraint programming.
Last, we implement a constraint solver over (finite) lattices that is parametrized by the lattice domain. The lattice domain defines the elements and its operations, including at least join and meet, which define the partial order (v) relation used to check en
CLP 494 – – – – –
TCLP Mod TCLP 11 13 21 25 36 42 56 69 85 111 113 158
CLP 67 628 6001 153813 > 5 min. > 5 min.
CLP(Q)
Mod TCLP 12 20 30 40 53 64 tailment. To evaluate this constraint solver in the context of tabled execution, we implemented a simple abstract analyzer whose fix-point is reached by means of tabled execution. Its domain operations are implemented using the lattice domain and the constraint solver, which avoids recomputation of subsumed abstractions and attains better accuracy and considerable speedups. We evaluate its performance by comparing this implementation with an abstract interpreter without the constraint solver. Table 2 shows the results in terms of execution time of the analysis of a program which is parametrized by the number of arguments.
2788 563 112 21
3 2 2 1 CHICO DE GUZMÁN, P., CARRO, M., HERMENEGILDO, M., AND STUCKEY, P. 2012. A General Implementation Framework for Tabled CLP. In FLOPS’12, T. Schrijvers and P. Thiemann, Eds. Number 7294 in LNCS. Springer Verlag, 104–119.
HERMENEGILDO, M. V., BUENO, F., CARRO, M., LÓPEZ, P., MERA, E., MORALES, J., AND PUEBLA, G. 2012. An Overview of Ciao and its Design Philosophy. TPLP 12, 1–2, 219–252. http://arxiv.org/abs/1102.5497.
HOLZBAUR, C. 1992. Metastructures vs. Attributed Variables in the Context of Extensible Unification. In 1992 International Symposium on Programming Language Implementation and Logic Programming. LNCS 631, Springer Verlag, 260–268.
HOLZBAUR, C. 1995. OFAI clp(q,r) manual, edition 1.3.3. Tech. Rep. TR-95-09, Austrian Research
Institute for Artificial Intelligence, Vienna.
JAFFAR, J. AND MAHER, M. 1994. Constraint Logic Programming: A Survey. Journal of Logic Programming 19/20, 503–581.
TAMAKI, H. AND SATO, M. 1986. OLD Resolution with Tabulation. In Third International Conference on Logic Programming. Lecture Notes in Computer Science, Springer-Verlag, London, 84–98.