page 1  (43 pages)
2to next section

2.2 Constraint Hierarchies

Alan Borning, Bjorn Freeman-Benson, and Molly Wilson
Dept. of Computer Science & Engineering, FR-35
University of Washington
Seattle, Washington 98195

This paper was originally published in Lisp and Symbolic Computation, Vol. 5 No. 3, (September 1992), pages 223{270.


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 difierent 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.

2.2.1 Introduction

A constraint describes a relation that should be satisfled. Examples of constraints include:

? a constraint that a resistor in a circuit simulation obey Ohm's Law

? a constraint that two views of the same data remain consistent (for example, bar graph and pie chart views)

? a default constraint that parts of an object being edited remain flxed, unless there is some stronger constraint that forces them to change.