Constraint Handling Rules: Difference between revisions

Revision as of 20:20, 18 February 2018

Revision as of 21:54, 2 June 2018

Line 12:

'''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) 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> [[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]], and [[type system]]s.

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| pages = 1| year = 2009| last1 = Sneyers | first1 = Jon| last2 = Van Weert | first2 = Peter| last3 = Schrijvers | first3 = Tom| last4 = De Koninck | first4 = Leslie| url = http://dtai.cs.kuleuven.be/projects/CHR/papers/draft_chr_survey.pdf| arxiv = 0906.4474}}</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. Program. Lang. Syst. |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.