Hierarchical Constraint Logic Programming

Authors: Molly Wilson and Alan Borning

Published in The Journal of Logic Programming, special issue on Constraint Logic Programming, Vol. 16 Nos. 3 & 4, July-August 1993, pages 227-318. Preprint published as UW Tech Report 93-01-02a.


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. In many applications, such as interactive graphics, planning, document formatting, and decision support, one needs to express preferences as well as strict requirements. 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. An arbitrary number of strengths of preference are allowed. We present a theory of such 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 paper (compressed postscript)

Constraints home page