Constraint Handling Rules (CHR) is a declarative, rule-based programming language, introduced in 1991 by Thom Frühwirth at the time with European Computer-Industry Research Centre (ECRC) in Munich, Germany.
[1][2] Originally intended for constraint programming, CHR finds applications in grammar induction,[3] type systems,[4] abductive reasoning, multi-agent systems, natural language processing, compilation, scheduling, spatial-temporal reasoning, testing, and verification.
Execution of rules may add or remove formulas from the store, thus changing the state of the program.
[11] In contrast to Prolog, CHR rules are multi-headed and are executed in a committed-choice manner using a forward chaining algorithm.
The host language supplies a data structure for representing terms, including logical variables.
A CHR program, then, consists of rules that manipulate a multi-set of these terms, called the constraint store.
The guards in rules are built-in constraints, so they effectively execute host language code.
In the former case, the constraint store can be read off by a host language program to look for facts of interest.
[9] The following CHR program, in Prolog syntax, contains four rules that implement a solver for a less-or-equal constraint.
To decide which rule should "fire" on a given constraint store, a CHR implementation must use some pattern matching algorithm.
[13] The original specification of CHR's semantics was entirely non-deterministic, but the so-called "refined operation semantics" of Duck et al. removed much of the non-determinism so that application writers can rely on the order of execution for performance and correctness of their programs.
[5][14] Most applications of CHRs require that the rewriting process be confluent; otherwise the results of searching for a satisfying assignment will be nondeterministic and unpredictable.