Constraint Handling Rules

Constraint Handling Rules

Constraint Handling Rules (CHR) is a declarative programming language extension introduced in 1991[1][2] 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 systems, natural language processing, compilation, scheduling, spatial-temporal reasoning, testing and verification, and type systems.

Although CHR is Turing complete,[3] 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.

Contents

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 [2]

  • 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 equivalence, 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 A the 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.

See also

Related languages and paradigms

References

  1. ^ Thom Frühwirth. Introducing Simplification Rules. Internal Report ECRC-LP-63, ECRC Munich, Germany, October 1991, Presented at the Workshop Logisches Programmieren, Goosen/Berlin, Germany, October 1991 and the Workshop on Rewriting and Constraints, Dagstuhl, Germany, October 1991.
  2. ^ a b Thom Frühwirth. Theory and Practice of Constraint Handling Rules. Special Issue on Constraint Logic Programming (P. Stuckey and K. Marriott, Eds.), Journal of Logic Programming, Vol 37(1-3), October 1998. doi:10.1016/S0743-1066(98)10005-5
  3. ^ Jon Sneyers, Tom Schrijvers, Bart Demoen: The computational power and complexity of constraint handling rules. ACM Trans. Program. Lang. Syst. 31(2): (2009).

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. doi:10.1017/S1471068409990123

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Constraint logic programming — Programming paradigms Agent oriented Automata based Component based Flow based Pipelined Concatenative Concurrent computing …   Wikipedia

  • Constraint satisfaction — In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution to a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a vector of variables that… …   Wikipedia

  • Constraint-Programmierung — In diesem Artikel oder Abschnitt fehlen folgende wichtige Informationen: Es fehlen die Domains und Beispiele für Programmiersprachen, die constraintbasiertes Programmieren erleichern. Du kannst Wikipedia helfen, indem du sie recherchierst und… …   Deutsch Wikipedia

  • Concurrent constraint logic programming — is a version of constraint logic programming aimed primarily at programming concurrent processes rather than (or in addition to) solving constraint satisfaction problems. Goals in constraint logic programming are evaluated concurrently; a… …   Wikipedia

  • List of programming languages by category — Programming language lists Alphabetical Categorical Chronological Generational This is a list of programming languages grouped by category. Some languages are listed in multiple categories. Contents …   Wikipedia

  • Constraintprogrammierung — Die Constraintprogrammierung (engl.: Constraint Programming) ist ein Programmierparadigma, das seit Mitte der 1980er Jahre entwickelt wird und sich als natürliche Weiterentwicklung der logischen Programmierung versteht. Logische und… …   Deutsch Wikipedia

  • List of programming languages — Programming language lists Alphabetical Categorical Chronological Generational The aim of this list of programming languages is to include all notable programming languages in existence, both those in current use and historical ones, in… …   Wikipedia

  • CHR — can refer to*Chain Home Radar *Cherokee language *Contemporary hit radio *Constraint Handling Rules *Chatham House Rule *Châteauroux Déols Marcel Dassault Airport in France (IATA code: CHR) *In role playing games, chr refers to charisma.… …   Wikipedia

  • CHR — Die Abkürzung CHR steht für: Cherokee (Sprache), Code nach ISO 639 für die Indianersprache Commission on Human Rights, die UN Menschenrechtskommission Constraint Handling Rules, eine Erweiterung für deklarative Programmiersprachen Contemporary… …   Deutsch Wikipedia

  • Список языков программирования — Списки языков программирования Алфавитный По категориям Хронологический Генеалогический Цель этого алфавитного списка языков программирования состоит в том, чтобы дать полный перечень всех существующих языков программирования, как используемых в… …   Википедия

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”