Constraint Handling Rules

Constraint Handling Rules (CHR)
ParadigmsConstraint logic, declarative
Designed byThom Frühwirth
First appeared1991; 33 years ago (1991)
Websiteconstraint-handling-rules.org
Influenced by
Prolog

Constraint Handling Rules (CHR) is a declarative, rule-based programming language, introduced in 1991 by Thom Frühwirth at the time with European Computer-Industry Research Centre (ECRC) in Munich, Germany.[1][2] Originally intended for constraint programming, CHR finds applications in grammar induction,[3] type systems,[4] abductive reasoning, multi-agent systems, natural language processing, compilation, scheduling, spatial-temporal reasoning, testing, and 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,[5] according to its abstract semantics and deterministic (top-down rule application), according to its refined semantics.[6]

Although CHR is Turing complete,[7] 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,[8] Java, C,[9] SQL,[10] and JavaScript.[11] In contrast to Prolog, CHR rules are multi-headed and are executed in a committed-choice manner using a forward chaining algorithm.

  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. ^ 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. ^ Dahl, Veronica, and J. Emilio Miralles. "Womb grammars: Constraint solving for grammar induction." Proceedings of the 9th Workshop on Constraint Handling Rules. vol. Technical report CW. Vol. 624. 2012.
  4. ^ Alves, Sandra, and Mário Florido. "Type inference using constraint handling rules." Electronic Notes in Theoretical Computer Science 64 (2002): 56-72.
  5. ^ Sneyers, Jon; Van Weert, Peter; Schrijvers, Tom; De Koninck, Leslie (2009). "As time goes by: Constraint Handling Rules – A Survey of CHR Research between 1998 and 2007" (PDF). Theory and Practice of Logic Programming. 10: 1. arXiv:0906.4474. doi:10.1017/S1471068409990123. S2CID 11044594.
  6. ^ Frühwirth, Thom (2009). Constraint handling rules. Cambridge University Press. ISBN 978-0521877763.
  7. ^ Sneyers, Jon; Schrijvers, Tom; Demoen, Bart (2009). "The computational power and complexity of constraint handling rules" (PDF). ACM Transactions on Programming Languages and Systems. 31 (2): 1–42. doi:10.1145/1462166.1462169. S2CID 2691882.
  8. ^ "CHR: Constraint Handling Rules library". GitHub. 5 September 2021.
  9. ^ Peter Van Weert; Pieter Wuille; Tom Schrijvers; Bart Demoen. "CHR for imperative host languages". Constraint Handling Rules: Current Research Topics. Springer.
  10. ^ "CHR2 to SQL converter". GitHub. 15 March 2021.
  11. ^ CHR.js - A CHR Transpiler for JavaScript