Constraint Handling Rules: Difference between revisions

Revision as of 10:30, 21 August 2021

Revision as of 14:44, 30 August 2021

Line 15:

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> 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 Transactions on Programming Languages and Systems |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'' and ''[[SWI-Prolog]]'', although CHR implementations also exist for [[Haskell (programming language)|Haskell]],<ref>https://github.com/atzedijkstra/chr</ref>, [[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==