
Nondeterministic Lisp as a Substrate for Constraint
Logic Programming
Jeffrey Mark Siskind?
University of Pennsylvania IRCS
3401 Walnut Street Room 407C
Philadelphia PA 19104
215/898{0367
internet: Qobi@CIS.UPenn.EDU
David Allen McAllestery
M. I. T. Artificial Intelligence Laboratory
545 Technology Square Room NE43{412
Cambridge MA 02139
617/253{6599
internet: dam@AI.MIT.EDU
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 nonnumeric 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 logic programming can be viewed as a method for solving equational constraints between logic variables which range over the universe of Herbrand terms. A natural extension of such a view is to allow variables to range over other domains and augment the programming language to support the formulation and solution of systems of constraints appropriate to these new domains. The
?Supported in part by a Presidential Young Investigator
Award to Professor Robert C. Berwick under National
Science Foundation Grant DCR{85552543, by a grant from
the Siemens Corporation, by the Kapor Family Foundation,
by ARO grant DAAL 03{89{C{0031, by DARPA grant
N00014{90{J{1863, by NSF grant IRI 90{16592, and by
Ben Franklin grant 91S.3078C{1
y Supported in part by the Advanced Research Projects
Agency of the Department of Defense under Office of Naval
Research contract N0001491J4038.
notion of extending a programming language to support constraintbased programmingneed not be unique to logic programming. In this paper we present the constraint package included with Screamer, a nondeterministic dialect of Common Lisp described by Siskind and McAllester (1993). This package provides functionality analogous to clp(<) and CHiP in a Common Lisp framework instead of a Prolog one. Screamer augments Common Lisp with the capacity for writing nondeterministic functions and expressions. Nondeterministic functions and expressions can return multiple values upon backtracking initiated by failure. Screamer also provides the ability to perform local side effects, ones which are undone upon backtracking. Nondeterminism and local side effects form the substrate on top of which the Screamer constraint package is constructed.
Variables and Constraints
Screamer includes the function makevariable which returns a data structure called a variable. Screamer variables are a generalization of Prolog logic variables. Initially, new variables are unbound and unconstrained. Variables may be bound to values by the process of solving constraints asserted between sets of variables. Both the assertion of constraints and the ensuing binding of variables is done with local side effects. Thus constraints are removed and variables become unbound again upon backtracking.
Screamer provides a variety of primitives for constraining variables. Each constraint primitive is a constraint version" of a corresponding Common Lisp primitive. For example, the constraint primitive +v is a constraint version of +. An expression of the form (+v x y) returns a new variable z, which it constrains to be the sum of x and y by adding the constraint z = (+ x y). By convention, a Screamer primitive ending in the letter v is a constraint version of a corresponding Common Lisp primitive. Table 1 lists the constraint primitives provided by Screamer. All of these primitives have the property that they accept variables as argumentsin addition to ground