Constraint Handling Rules: Difference between revisions

Revision as of 11:57, 21 May 2022

Revision as of 18:11, 23 May 2022

Line 83:

== Execution of CHR programs ==

To decide which rule should "fire" on a given constraint store, a CHR implementation must use some [[pattern matching]] algorithm. Candidate algorithms include [[Rete algorithm|RETE]] and [[TREAT]],<ref>

{{cite conference

| url = https://www.aaai.org/Papers/AAAI/1987/AAAI87-008.pdf

Line 96:

| ___location = Seattle, Washington

| id = ISBN 978-0-262-51055-4

}}</ref>, but most implementation use a [[Lazy evaluation|lazy]] algorithm called [[LEAPS (algorithm)|LEAPS]].<ref>{{cite thesis |url=http://www.cs.kuleuven.be/publicaties/doctoraten/cw/CW2008_14.pdf |title=Execution Control for Constraint Handling Rules |author=Leslie De Koninck |year=2008 |publisher=[[Katholieke Universiteit Leuven]] |type=Ph.D. thesis |pages=12–14}}</ref>

The original specification of CHR's semantics was entirely non-deterministic, but the so-called "refined operation semantics" of Duck ''et al.'' removed much of the non-determinism so that application writers can rely on the order of execution for performance and correctness of their programs.<ref name="timegoesby"/><ref>{{cite journal |first1=Gregory J. |last1=Duck |first2=Peter J. |last2=Stuckey |first3=María |last3=García de la Banda |first4=Christian |last4=Holzbaur |title=The refined operational semantics of Constraint Handling Rules |journal=Logic Programming |series=Lecture Notes in Computer Science |year=2004 |volume=3132 |pages=90–104 |doi=10.1007/978-3-540-27775-0_7 |isbn=978-3-540-22671-0 |url=http://ww2.cs.mu.oz.au/~pjs/papers/refined.pdf |access-date=2014-12-23 |archive-url=https://web.archive.org/web/20110304133204/http://ww2.cs.mu.oz.au/~pjs/papers/refined.pdf |archive-date=2011-03-04 |url-status=dead }}</ref>