Design and implementation of a finite domain constraint logic programming system based on PROLOG with coroutining

Abstract

Many problems in different areas such as Operations Research, Hardware Design, and Artificial Intelligence can be regarded as constraint solving problems (CSPs). Logic programming offers a convenient way of representing CSPs due to its relational, declarative and nondeterministic form. Unfortunately, standard logic programming languages such as PROLOG tend to be inefficient for solving CSPs, since what could be called constraints in PROLOG is used only in a passive a posteriori manner, leading to symptoms such as late recognition of failure, unnecessary and unintelligent backtracking and multiple computation of the same solutions. There have been intensive research efforts in order to remedy this. One of them, which has caught increasing attention over the past few years, is the Constraint Logic Programming approach: By integrating a domain concept for logic variables and consistency techniques such as forward-checking or looking-ahead into PROLOG, the search space can be restricted in an a priori manner. Thus, a more efficient control strategy can be achieved, preserving the 'clean' dual PROLOG semantics.

In this issue, I will present a horizontal compilation approach towards a CLP system maintaining constraints whose variables are ranging over finite domains. Horizontal compilations often referred to as optimizing transformation techniques in other context. A PROLOG system providing a delay mechanism is used in order to achieve the control behaviour described above. The major subtasks of my work are -Design and integration of a domain concept into logic programming, which allows direct access to and manipulation of possible values of logic variables. -Thorough implementation of a forward-checking control strategy in SEPIA. -Design and prototypical implementation of a looking-ahead algorithm. -Summary of the main theoretical results underlying to domains and consistency techniques in logic programming. -Consideration and prototypical implementation of first-fail heuristics. -Embedding these topics into a preprocessor, which transforms FIDO programs into SEPIA programs realizing the advanced control strategies. The general framework of this work is the FIDO lab within the ARC-TEC project, which explores several approaches towards integrating finite domain consistency techniques into logic programming.