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 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 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 N00014-91-J-4038.

notion of extending a programming language to support constraint-based 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 make-variable 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 arguments|in addition to ground