Navegación

Búsqueda

Búsqueda avanzada

Description and Evaluation of a Generic Design to Integrate CLP and Tabled Execution (Trabajo de alto nivel)

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 General Implementation Framework for Tabled CLP

This is a summary of [PCHS12], where a framework to combine tabling evaluation [TS86, War92] and constraint logic programming [JM94] is described (TCLP). This combination has been studied previously from a theoretical point of view [Tom97, Cod95], where it is shown that the constraint domain needs to offer projection and entailment checking operations in order to ensure completeness w.r.t. the declarative semantics. However, existing TCLP frameworks and implementations lack a complete treatment of constraint projection and / or entailment. The novelty of our proposal is that we present a complete implementation framework for TCLP, independent from the constraint solver, which can use either precise or approximate projection and entailment, possibly with optimizations.