Resumen de Estrategias Avanzadas de Tabulación y Paralelismo en Programas Lógicos = Advanced Evaluation Strategies for Tabling and Parallelism in Logic Programs
Pablo Chico de Guzmán Huerta
Prolog is the main language inside the Logic Programming paradigm. A Prolog program is a set of predicates whose definition is based on a set of clauses which give a high-level of declarativeness and abstraction for the programmer. However, the standard evaluation of Prolog predicates frequently implies the recomputation of predicates and even worse, the generation of infinite loops for some programs which have a well-defined meaning from a declarative point of view. Tabled evaluation attacks these issues by remembering the solutions for tabled predicates and by suspending looping predicate calls until alternative execution paths compute solutions for them.
Tabled evaluation implementation is complex. It relies on three different operations which cannot be performed in constant time at the same time. These operations are: call suspension, call resumption and variable accesses. The first part of this thesis compares three different tabled evaluation implementations (implemented in Ciao), where each of these implementations penalizes one of these three operations. Each of these implementations have advantages and disadvantages depending on the behavior of a specific tabled evaluation application. The second part of this thesis improves the functionality of tabled evaluation in order to be combined with constraints and in order to avoid unneeded computations. Constraint Logic Programming (CLP) is a natural extension of Logic Programming which applies efficient, incremental constraint solving techniques which blend seamlessly with the characteristics of logical variables and which increase the expressive power and declarativeness of Logic Programming. We present a complete implementation framework for constraint tabled evaluation, independent from the constraint solver, which enlarges the application domain of tabled evaluation. On the other hand, a key decision of a tabled evaluation is related to the moment when answers are returned to the tabled call. Local evaluation returns solutions when all of them have been computed and behaves well on memory. Batch evaluation returns answers on-demand, which has a larger applicability, but its memory behavior is unacceptable for most of the applications. This thesis presents swapping evaluation, which returns answers on-demand but its memory behavior is much closer to the one of local evaluation. We also support pruning operators in order to prune the search when the desired solution is found.
Last but not least, Prolog adapts very well for parallelism due to the flexibility of its execution control and the use of logical assignments. The third part of this thesis extends the independent and-parallelism of Ciao to be working with non-determinism programs. Ones of the major issues of this problem is the trapped goal problem and the recomputation of goals. The classical solutions for the trapped goal problem break several invariants of the Prolog execution, affecting the implementation of the system everywhere. Consequently, they are difficult to maintain and to extend, and they tend not to be use. We propose a modular solution which does not break any invariant of the Prolog execution while keeping the same performance for the parallel execution (this solution is close related to swapping evaluation). Respect to the recomputation of goals, we have adapted techniques from tabled evaluation in order to remember previous computations.
