## Hierarchical Constraint Logic Programming

Author: Molly Ann Wilson

Ph.D. dissertation, Department of Computer Science and Engineering,
University of Washington, April 1993. Published as UW Tech Report 93-05-01.

### Abstract

A constraint describes a relation to be maintained; it states what the
relationship is as opposed to how to maintain it. In many applications,
such as interactive graphics, planning, document formatting, and decision
support, one needs to express *preferences* as well as strict
requirements. Such constraints are sometimes called *soft*
constraints; the required ones are called *hard* constraints. We
allow an arbitrary number of levels of preference, each successive level
being more weakly preferred than the previous one. A collection of
constraints at various levels of preference is known as a *constraint
hierarchy*. Constraint Logic Programming (CLP) is a general scheme for
extending logic programming to include constraints. It is parameterized by
D, the domain of the constraints. However, CLP(D) languages, as well as
most other constraint systems, only allow the programmer to specify
constraints that must hold. If we wish to make full use of the constraint
paradigm, we need ways to represent these defaults and preferences
declaratively, as constraints, rather than encoding them in the procedural
parts of the language. We describe a scheme for extending CLP(D) to
include both required and preferential constraints. We present a theory of
constraint hierarchies, and an extension, Hierarchical Constraint Logic
Programming, of the CLP scheme to include constraint hierarchies. We give
an operational, model theoretic and fixed-point semantics for the HCLP
scheme. Finally, we describe two interpreters we have written for
instances of the HCLP scheme, give example programs, and discuss related
work.

full version (compressed postscript)

Constraints home page