LISP and Symbolic Computation, 5(3)223-270
Constraint HierarchiesAlan Borning, Department of Computer Science and Engineering, FR-35, University of Washington, Seattle, Washington 98195
Bjorn Freeman-Benson, University of Victoria, Department of Computer Science, Box 3055, Victoria, B.C. V8W 3P6 CANADA
Molly Wilson, Department of Computer Science and Engineering, FR-35, University of Washington, Seattle, Washington 98195
| Abstract: Constraints allow programmers and users to state declaratively a relation that should be maintained, rather than requiring them to write procedures to maintain the relation themselves. They are thus useful in such applications as programming languages, user interface toolkits, and simulation packages. In many situations, it is desirable to be able to state both required and preferential constraints. The required constraints must hold. Since the other constraints are merely preferences, the system should try to satisfy them if possible, but no error condition arises if it cannot. A constraint hierarchy consists of a set of constraints, each labeled as either required or preferred at some strength. An arbitrary number of different strengths is allowed. In the discussion of a theory of constraint hierarchies, we present alternate ways of selecting among competing possible solutions, and prove a number of propositions about the relations among these alternatives. We then outline algorithms for satisfying constraint hierarchies, and ways in which we have used constraint hierarchies in a number of programming languages and systems. |
[local copy]
![[picture of journal cover]](../LISP.JPG)