Theory and Practice of Constraint Handling Rules

Theory and Practice of Constraint Handling Rules, Thom Fruewirth, Journal of Logic Programming, 1994.

Constraint Handling Rules (CHR) are our proposal to allow more flexibility and application-oriented customization of constraint systems. CHR are a declarative language extension especially designed for writing user-defined constraints. CHR are essentially a committed-choice language consisting of multi-headed guarded rules that rewrite constraints into simpler ones until they are solved.

In this broad survey we cover all aspects of CHR as they currently present themselves. Going from theory to practice, we will define the syntax and semantics of CHR, introduce an important decidable property, confluence, of CHR programs and define a tight integration of CHR with constraint logic programming languages. This survey then describes implementations of the language before we review several constraint solvers -- both traditional and non-standard ones -- written in the CHR language. Finally we introduce two innovative applications that benefited from being written in CHR.

In the last post, we had some requests for constraint programming, so here you go. Constraint solving programs are often essentially stateful algorithms, and I see CHR as a particularly nice way of handling all that state in a declarative way. (They have a very pretty semantics as proof search in linear logic, too.)

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

CHR survey MkII

Tom Schrijvers announced a new survey of CHR, titled As Time Goes By: Constraint Hand ling Rules
A Survey of CHR Research from 1998 to 2007
, with coauthors Sneyers, Van Weert, and De Koninck.

As the title suggests, it is a sort of appendix to the Fruewirth survey, introducing the new work carried out since. The linear logic semantics neelk mentions above is sketched out, as are a successor semantics, transition logic.


Actually, it's Tom Schrijvers.


Fixed here and there.