Nondeterministic Lisp as a Substrate for Constraint Logic Programming

Abstract

We have implemented a comprehensive constraintbased programming language as an extension to Common Lisp. This constraint package provides a unified framework for solving both numeric and non-numeric systems of constraints using a combination of local propagation techniques including binding propagation, Boolean constraint propagation, generalized forward checking, propagation of bounds, and unification. The backtracking facility of the nondeterministic dialect of Common Lisp used to implement this constraint package acts as a general fallback constraint solving method mitigating the incompleteness of local propagation. Introduction Recent years have seen significant interest in constraint logic programming languages. Numerous implementations of such languages have been described in the literature, notably clp(!) (Jaffar and Lassez 1987) and CHiP (Van Hentenryck 1989). The point of departure leading to these systems is the observation that the unification operation at the core of lo...