Constraint Handling Rules: Difference between revisions

Revision as of 22:27, 28 May 2021

Revision as of 03:45, 31 May 2021

Line 1:

{{Infobox programming language

| paradigm name = [[Constraint logicHandling Rules programming]](CHR)

| paradigms = [[Constraint logic programming|Constraint logic]], [[Declarative programming|declarative]]

| year = 1991

| year = {{Start date and age|1991}}

| designer = Thom Frühwirth

| implementations =

| dialects =

| influenced by = [[Prolog]]

| influenced =

| file_ext file ext =

| wikibooks =

}}

'''Constraint Handling Rules''' ('''CHR''') is a [[declarative programming|declarative]], rule-based [[programming language|language]], introduced in 1991 by Thom Frühwirth at the time with ECRC (European Computer-Industry Research Centre (ECRC) in Munich, Germany.<ref>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.</ref><ref name="chrtheorypractice">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}}</ref> Originally intended for [[constraint programming]], CHR finds applications in [[grammar induction]],<ref>Dahl, Veronica, and J. Emilio Miralles. "[https://lirias.kuleuven.be/bitstream/123456789/360286/1/CW624.pdf#page=40 Womb grammars: Constraint solving for grammar induction]." Proceedings of the 9th Workshop on Constraint Handling Rules. vol. Technical report CW. Vol. 624. 2012.</ref> [[type system]]s,<ref>Alves, Sandra, and Mário Florido. "[https://www.sciencedirect.com/science/article/pii/S1571066104803463/pdf?md5=86d0945f0ac4c840c07e43090600bd34&pid=1-s2.0-S1571066104803463-main.pdf Type inference using constraint handling rules]." Electronic Notes in Theoretical Computer Science 64 (2002): 56-72.</ref> [[abductive reasoning]], [[multi-agent system]]s, [[natural language processing]], [[Compiler|compilation]], [[Scheduling (production processes)|scheduling]], [[spatial-temporal reasoning]], [[Software testing|testing]], and [[Software verification|verification]].

A CHR program, sometimes called a ''constraint handler'', is a set of rules that maintain a ''constraint store'', a [[multi-set]] 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 [[non-deterministic programming|non-deterministic]],<ref name="timegoesby">{{Cite journal | doi = 10.1017/S1471068409990123 | title = As time goes by: Constraint Handling Rules – A Survey of CHR Research between 1998 and 2007 | journal = Theory and Practice of Logic Programming | volume =10 10| pages =1 1| year =2009 2009| last1 = Sneyers | first1 =Jon Jon| last2 = Van Weert | first2 =Peter Peter| last3 = Schrijvers | first3 =Tom Tom| last4 = De Koninck | first4 =Leslie Leslie| url = http://dtai.cs.kuleuven.be/projects/CHR/papers/draft_chr_survey.pdf | arxiv = 0906.4474}}</ref> according to its ''abstract [[Semantics_(computer_science)|semantics]]'' and deterministic (top-down rule application), according to its ''refined semantics''.<ref name="chrbook">{{cite book |last1=Frühwirth |first1=Thom |title=Constraint handling rules |date=2009 |publisher=Cambridge University Press |isbn=0521877768}}</ref>

Although CHR is [[Turing complete]],<ref name="complexity">{{cite journal |first1=Jon |last1=Sneyers |first2=Tom |last2=Schrijvers |first3=Bart |last3=Demoen |title=The computational power and complexity of constraint handling rules |journal=ACM Trans.Transactions Program.on Lang.Programming Syst.Languages and Systems (TOPLAS) |volume=31 |issue=2 |year=2009 |url=https://lirias.kuleuven.be/bitstream/123456789/218524/1/p1-sneyers.pdf}}</ref> it is not commonly used as a programming language in its own right. Rather, it is used to extend a ''host language'' with constraints. Prolog is by far the most popular host language and CHR is included in several Prolog implementations, including [[''SICStus Prolog|SICStus]]'' and ''[[SWI-Prolog]]'', although CHR implementations also exist for [[Haskell (programming language)|Haskell]], [[Java (programming language)|Java]], [[C (programming language)|C]],<ref name="imperative">{{cite encyclopedia |title=CHR for imperative host languages |author1=Peter Van Weert |author2=Pieter Wuille |author3=Tom Schrijvers |author4=Bart Demoen |encyclopedia=Constraint Handling Rules —: Current Research Topics |publisher=Springer |url=https://lirias.kuleuven.be/handle/123456789/197033}}</ref> [[SQL]],<ref>https://github.com/awto/chr2sql</ref> and JavaScript.<ref>[https://fnogatz.github.io/paper-now-chrjs/ CHR.js - A CHR Transpiler for JavaScript]</ref> In contrast to Prolog, CHR rules are multi-headed and are executed in a committed-choice manner using a [[forward chaining]] algorithm.

==Language overview==

Line 95 ⟶ 96:

*[[Constraint logic programming]]

*[[Logic programming]]

*[[Production system (computer science)|Production rule system]]s

*[[Business rules engine]]s

*[[Rewriting]]

Line 106 ⟶ 107:

==External links==

* [http://{{Official website|constraint-handling-rules.org/ The CHR Home Page]}}

* [http://dtai.cs.kuleuven.be/CHR/biblio/ CHR Bibliography]

* [http://listserv.cc.kuleuven.ac.be/archives/chr.html The CHR mailing list]

* [http://dtai.cs.kuleuven.be/CHR/ The K.U.Leuven CHR System]

* [http://chr.informatik.uni-ulm.de/~webchr/ WebCHR --: a CHR web interface]

[[Category:Constraint logic programming]]