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