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