Constraint Handling Rules
Encyclopedia
Constraint Handling Rules (CHR) is a declarative
programming language
extension
introduced in 1991 by Thom Frühwirth.
Originally designed for developing (prototypes of) constraint programming
systems, CHR is increasingly used
as a high-level
general-purpose programming language.
Typical application domains of CHR are abduction
, multi-agent system
s, natural language processing
,
compilation
, scheduling
, spatial-temporal reasoning
, testing
and verification
, and type system
s.
Although CHR is Turing complete, it is not commonly used as a programming language in its own right.
Rather, it is used to extend a host language with constraints.
Current host languages include Prolog
, Java
and Haskell
.
Prolog is by far the most popular host language and CHR is included in many Prolog implementations, including SICStus and SWI-Prolog
.
A CHR program, sometimes called a constraint handler, is a sequence of guarded
rules for simplification, propagation, and "simpagation" (a mix of simplification and propagation) of conjunctions of constraints. The CHR constraint store is a multi-set. In contrast to Prolog, the rules are multi-headed and are executed in a committed-choice manner using a forward chaining
algorithm.
:- use_module(library(chr)).
:- op(500, xfx, leq).
:- chr_constraint leq/2.
% X leq Y means variable X is less-or-equal to variable Y
reflexivity @ X leq X <=> true.
antisymmetry @ X leq Y , Y leq X <=> X=Y.
idempotence @ X leq Y \ X leq Y <=> true.
transitivity @ X leq Y , Y leq Z > X leq Z.
The first rule, which is called reflexivity (rule names are optional), is a single-headed simplification rule. It removes constraints of the form
, as the syntax suggests.
The third rule is a simpagation rule which removes redundant copies of the same constraint. Such rules are often needed because of the multi-set semantics of CHR. Finally, the last rule (transitivity) is a propagation rule that adds redundant constraints. Propagation rules correspond to logical implication.
Execution proceeds by exhaustively applying the rules to a given input query. For example, given the query
the transitivity rule adds
Declarative programming
In computer science, declarative programming is a programming paradigm that expresses the logic of a computation without describing its control flow. Many languages applying this style attempt to minimize or eliminate side effects by describing what the program should accomplish, rather than...
programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
extension
Extension (computing)
Software extension, is a file containing programming that serves to extend the capabilities of or data available to a more basic program. It is a kind of list of commands which are directly included in the program. This term often coincides with the plug-in...
introduced in 1991 by Thom Frühwirth.
Originally designed for developing (prototypes of) constraint programming
Constraint programming
Constraint programming is a programming paradigm wherein relations between variables are stated in the form of constraints. Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties...
systems, CHR is increasingly used
as a high-level
High-level programming language
A high-level programming language is a programming language with strong abstraction from the details of the computer. In comparison to low-level programming languages, it may use natural language elements, be easier to use, or be from the specification of the program, making the process of...
general-purpose programming language.
Typical application domains of CHR are abduction
Abductive reasoning
Abduction is a kind of logical inference described by Charles Sanders Peirce as "guessing". The term refers to the process of arriving at an explanatory hypothesis. Peirce said that to abduce a hypothetical explanation a from an observed surprising circumstance b is to surmise that a may be true...
, multi-agent system
Multi-agent system
A multi-agent system is a system composed of multiple interacting intelligent agents. Multi-agent systems can be used to solve problems that are difficult or impossible for an individual agent or a monolithic system to solve...
s, natural language processing
Natural language processing
Natural language processing is a field of computer science and linguistics concerned with the interactions between computers and human languages; it began as a branch of artificial intelligence....
,
compilation
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
, scheduling
Scheduling (production processes)
Scheduling is an important tool for manufacturing and engineering, where it can have a major impact on the productivity of a process. In manufacturing, the purpose of scheduling is to minimize the production time and costs, by telling a production facility when to make, with which staff, and on...
, spatial-temporal reasoning
Spatial-temporal reasoning
Spatial–temporal reasoning is used in both the fields of psychology and computer science.-Spatial–temporal reasoning in psychology:Spatial-temporal reasoning is the ability to visualize spatial patterns and mentally manipulate them over a time-ordered sequence of spatial transformations.This...
, testing
Software testing
Software testing is an investigation conducted to provide stakeholders with information about the quality of the product or service under test. Software testing can also provide an objective, independent view of the software to allow the business to appreciate and understand the risks of software...
and verification
Software verification
Software verification is a broader and more complex discipline of software engineering whose goal is to assure that software fully satisfies all the expected requirements.There are two fundamental approaches to verification:...
, and type system
Type system
A type system associates a type with each computed value. By examining the flow of these values, a type system attempts to ensure or prove that no type errors can occur...
s.
Although CHR is Turing complete, it is not commonly used as a programming language in its own right.
Rather, it is used to extend a host language with constraints.
Current host languages include Prolog
Prolog
Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
, Java
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
and Haskell
Haskell (programming language)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
.
Prolog is by far the most popular host language and CHR is included in many Prolog implementations, including SICStus and SWI-Prolog
SWI-Prolog
SWI-Prolog is an open source implementation of the programming language Prolog, commonly used for teaching and semantic web applications.It has a rich set of features, libraries forconstraint logic programming,multithreading,unit testing,GUI,...
.
A CHR program, sometimes called a constraint handler, is a sequence of guarded
Guard (computing)
In computer programming, a guard is a boolean expression that must evaluate to true if the program execution is to continue in the branch in question. The term is used at least in Haskell, Clean, Erlang, occam, Promela, OCaml and Scala programming languages. In Mathematica, guards are called...
rules for simplification, propagation, and "simpagation" (a mix of simplification and propagation) of conjunctions of constraints. The CHR constraint store is a multi-set. In contrast to Prolog, the rules are multi-headed and are executed in a committed-choice manner using a forward chaining
Forward chaining
Forward chaining is one of the two main methods of reasoning when using inference rules and can be described logically as repeated application of modus ponens. Forward chaining is a popular implementation strategy for expert systems, business and production rule systems...
algorithm.
Confluence
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. Establishing confluence is usually done by way of the following three properties- A CHR program is locally confluent if all its critical pairs are joinable
- A CHR program is called terminating if there are no infinite computations.
- A terminating CHR program is confluent if all its critical pairs are joinable.
Example program
The following SWI-Prolog program contains four CHR rules that implement a handler for the less-or-equal constraint::- use_module(library(chr)).
:- op(500, xfx, leq).
:- chr_constraint leq/2.
% X leq Y means variable X is less-or-equal to variable Y
reflexivity @ X leq X <=> true.
antisymmetry @ X leq Y , Y leq X <=> X=Y.
idempotence @ X leq Y \ X leq Y <=> true.
transitivity @ X leq Y , Y leq Z > X leq Z.
The first rule, which is called reflexivity (rule names are optional), is a single-headed simplification rule. It removes constraints of the form
A leq A from the constraint store. The second rule, antisymmetry, is a simplification rule with two heads. It replaces two symmetric leq constraints by an equality constraint (handled by Prolog unification). Simplification rules correspond to logical equivalenceLogical equivalence
In logic, statements p and q are logically equivalent if they have the same logical content.Syntactically, p and q are equivalent if each can be proved from the other...
, as the syntax suggests.
The third rule is a simpagation rule which removes redundant copies of the same constraint. Such rules are often needed because of the multi-set semantics of CHR. Finally, the last rule (transitivity) is a propagation rule that adds redundant constraints. Propagation rules correspond to logical implication.
Execution proceeds by exhaustively applying the rules to a given input query. For example, given the query
A leq B, B leq C, C leq Athe transitivity rule adds
A leq C. Then, by applying the antisymmetry rule, A leq C and C leq A are removed and replaced by A=C. Now the antisymmetry rule becomes applicable on the first two constraints of the original query. Now all CHR constraints are eliminated so no further rules can be applied, and the answer A=C, A=B is returned.Related languages and paradigms
- Constraint programmingConstraint programmingConstraint programming is a programming paradigm wherein relations between variables are stated in the form of constraints. Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties...
- Constraint logic programming
- Logic programmingLogic programmingLogic programming is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy's [1958] advice-taker proposal, logic is used as a purely declarative representation language, and a...
- Production rule systems
- Business rules engineBusiness rules engineA business rules engine is a software system that executes one or more business rules in a runtime production environment. The rules might come from legal regulation , company policy , or other sources...
s - Term Rewriting Systems
Further reading
- Jon Sneyers, Peter Van Weert, Tom Schrijvers and Leslie De Koninck: As Time Goes By: Constraint Handling Rules – A Survey of CHR Research between 1998 and 2007. Theory and Practice of Logic Programming, 10(1):1-47, 2010.