Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Constraint Handling Rules
open-in-new
<p>Constraint Handling Rules (CHR) is a <a href="/facts/Declarative_programming/gogtdzcJ">declarative</a>, rule-based <a href="/facts/Programming_language/cWTYbgWa">programming language</a>, introduced in 1991 by Thom Frühwirth at the time with European Computer-Industry Research Centre (ECRC) in Munich, Germany. Originally intended for <a href="/facts/Constraint_programming/rgkCK5bD">constraint programming</a>, CHR finds applications in <a href="/facts/Grammar_induction/Mx8ISTor">grammar induction</a>, <a href="/facts/Type_system/Tz0bAMS9">type systems</a>, <a href="/facts/Abductive_reasoning/QoHNqvKT">abductive reasoning</a>, <a href="/facts/Multi-agent_system/A85vt3UA">multi-agent systems</a>, <a href="/facts/Natural_language_processing/1hjMKsSN">natural language processing</a>, <a href="/facts/Compiler/WNfCDFJe">compilation</a>, <a href="/facts/Scheduling_(production_processes)/ChBw19Kb">scheduling</a>, <a href="/facts/Spatial-temporal_reasoning/5P0XlqC4">spatial-temporal reasoning</a>, <a href="/facts/Software_testing/VoXzG9Tb">testing</a>, and <a href="/facts/Software_verification/PczD7lsh">verification</a>. </p><p>A CHR program, sometimes called a <i>constraint handler</i>, is a set of rules that maintain a <i>constraint store</i>, a <a href="/facts/Multi-set/bPFJGMDo">multi-set</a> of logical formulas. Execution of rules may add or remove formulas from the store, thus changing the state of the program. The order in which rules "fire" on a given constraint store is <a href="/facts/Non-deterministic_programming/XRRlHhKn">non-deterministic</a>, according to its <i>abstract <a href="/facts/Semantics_(computer_science)/JEP1zyBv">semantics</a></i> and deterministic (top-down rule application), according to its <i>refined semantics</i>. </p><p>Although CHR is <a href="/facts/Turing_complete/73goop44">Turing complete</a>, it is not commonly used as a programming language in its own right. Rather, it is used to extend a <i>host language</i> with constraints. Prolog is by far the most popular host language and CHR is included in several Prolog implementations, including <i>SICStus</i> and <i><a href="/facts/SWI-Prolog/4krpcVnm">SWI-Prolog</a></i>, although CHR implementations also exist for <a href="/facts/Haskell_(programming_language)/4Htv9WLu">Haskell</a>, <a href="/facts/Java_(programming_language)/9ScgFyAL">Java</a>, <a href="/facts/C_(programming_language)/Ky2No763">C</a>, <a href="/facts/SQL/UjQLJcYm">SQL</a>, and JavaScript. In contrast to Prolog, CHR rules are multi-headed and are executed in a committed-choice manner using a <a href="/facts/Forward_chaining/FJjYIf6S">forward chaining</a> algorithm. </p>