A short introduction to CHR

Constraint Handling Rules (CHR) is a declarative language for solving constraint problems. It's mainly used in conjunction with Prolog, but implementations for Java and Haskell are also available. I am currently working on making a Ruby implementation (as a Ruby DSL of course).

What is interesting about CHR is that it can be used to express constraint problems in a concise manner. It has successfully been applied to a wide range of constraint problems such as planning and language processing.

The language is quite simple. It consists of three kinds of rules that modify a constraint store (a database of constraints). All the rule definitions have a similar syntax:
rule :- head, operator, body.
The head and the body is basically a list of constraints. A rule is used when the head of the rule is matched by existing constraints in the constraint store. The constraints specified in the body gets added to the constraint store.

Propagation rules

c1, ..., c ==> Guard | cn+1, ... , cm
Propagation rules create new rules in the constraint store. Thee rules in the body (cn+1 .. cm) are added to the constraint store given that the guard is true. The rules from the head (c1 ... cn) remains in the constraint store.

Simplification rules

c1, ..., cn <=> Guard | cn+1, ... , cm
Simplification rules, has purpose of simplifying constraints in a particular way.
Rules in head (c1 .. cn) are removed from constraint store and rules in the body (cn+1 ... cm) is added to the store, provided that the Guard is true.

Simpagation rules

c1, ..., ci \ ci+1, ..., cn <=> Guard | cn+1, ..., cm
Simpagation rules is a sort of combination of the two others. The head is separated by a backslash. The rules before the backslash (c1 .. ci) stays in constraint store, while the rules after (ci+1 .. cn) is removed. The rules in the body (cn+1 .. cm) is added, provided the guard is true.