{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T01:56:02Z","timestamp":1648518962124},"reference-count":51,"publisher":"Cambridge University Press (CUP)","issue":"5-6","license":[{"start":{"date-parts":[[2018,5,23]],"date-time":"2018-05-23T00:00:00Z","timestamp":1527033600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2018,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Constraint Handling Rules (CHR) is both an effective concurrent declarative programming language and a versatile computational logic formalism. In CHR, guarded reactive rules rewrite a multi-set of constraints. Concurrency is inherent, since rules can be applied to the constraints in parallel. In this comprehensive survey, we give an overview of the concurrent, parallel as well as distributed CHR semantics, standard and more exotic, that have been proposed over the years at various levels of refinement. These semantics range from the abstract to the concrete. They are related by formal soundness results. Their correctness is proven as a correspondence between parallel and sequential computations. On the more practical side, we present common concise example CHR programs that have been widely used in experiments and benchmarks. We review parallel and distributed CHR implementations in software as well as hardware. The experimental results obtained show a parallel speed-up for unmodified sequential CHR programs. The software implementations are available online for free download and we give the web links. Due to its high level of abstraction, the CHR formalism can also be used to implement and analyse models for concurrency. To this end, the Software Transaction Model, the Actor Model, Colored Petri Nets and the Join-Calculus have been faithfully encoded in CHR. Finally, we identify and discuss commonalities of the approaches surveyed and indicate what problems are left open for future research.<\/jats:p>","DOI":"10.1017\/s1471068418000078","type":"journal-article","created":{"date-parts":[[2018,5,23]],"date-time":"2018-05-23T08:20:07Z","timestamp":1527063607000},"page":"759-805","source":"Crossref","is-referenced-by-count":1,"title":["Parallelism, concurrency and distribution in constraint handling rules: A survey"],"prefix":"10.1017","volume":"18","author":[{"given":"THOM","family":"FR\u00dcHWIRTH","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,5,23]]},"reference":[{"key":"S1471068418000078_ref6","unstructured":"Betz H. 2007. Relating coloured Petri nets to Constraint Handling Rules. In Proc. 4th Workshop on Constraint Handling Rules, 33\u201347."},{"key":"S1471068418000078_ref10","doi-asserted-by":"crossref","unstructured":"Duck G. J. , Stuckey P. J. , Garc\u00eda de la Banda M. and Holzbaur C. 2004. The refined operational semantics of Constraint Handling Rules. In Proc. International Conference on Logic Programming, B. Demoen and V. Lifschitz , Eds. Lecture Notes in Computer Science, vol. 3132. Springer, 90\u2013104.","DOI":"10.1007\/978-3-540-27775-0_7"},{"key":"S1471068418000078_ref9","first-page":"113","volume-title":"Choreographic Compilation of Decentralized Comprehension Patterns","author":"Cervesato","year":"2016"},{"key":"S1471068418000078_ref42","first-page":"1","article-title":"As time goes by: Constraint Handling Rules \u2013 A survey of CHR research between 1998 and 2007","volume":"10","author":"Sneyers","year":"2010","journal-title":"TPLP"},{"key":"S1471068418000078_ref18","unstructured":"Fr\u00fchwirth T. and Holzbaur C. 2003. Source-to-source transformation for a class of expressive rules. In Proc. Joint Conf. Declarative Programming APPIA-GULP-PRODE, F. Buccafurri , Ed. 386\u2013397."},{"key":"S1471068418000078_ref49","doi-asserted-by":"crossref","unstructured":"Triossi A. , Orlando S. , Raffaet\u00e0 A. and Fr\u00fchwirth T. 2012. Compiling chr to parallel hardware. In Proc. 14th Symposium on Principles and Practice of Declarative Programming. ACM, 173\u2013184.","DOI":"10.1145\/2370776.2370798"},{"key":"S1471068418000078_ref7","volume-title":"A Unified Analytical Foundation for Constraint Handling Rules","author":"Betz","year":"2014"},{"key":"S1471068418000078_ref29","unstructured":"Lam E. S. L. 2011. Parallel execution of constraint handling rules \u2013 Theory, implementation and application. Ph.D. thesis, School of Computing, Department of Computing Science, National University of Singapore."},{"key":"S1471068418000078_ref35","volume-title":"Constraint-Based Analysis of Security Properties","author":"Sarna-Starosta","year":"2008"},{"key":"S1471068418000078_ref23","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068405002413"},{"key":"S1471068418000078_ref46","doi-asserted-by":"crossref","unstructured":"Sulzmann M. , Lam E. S. and Van Weert P. 2008. Actors with multi-headed message receive patterns. In Proc. 10th International Conference on Coordination Models and Languages, D. Lea and G. Zavattaro , Eds. Lecture Notes in Computer Science, vol. 5052. Springer, 315\u2013330.","DOI":"10.1007\/978-3-540-68265-3_20"},{"key":"S1471068418000078_ref30","unstructured":"Lam E. S. L. , Cervesato I. and Fatima N. 2015. Comingle: Distributed logic programming for decentralized mobile ensembles. In Coordination Models and Languages - 17th IFIP WG 6.1 International Conference, COORDINATION 2015, 51\u201366."},{"key":"S1471068418000078_ref17","unstructured":"Fr\u00fchwirth T. 2016. The CHR Web Site. Accessed May 2018 URL: www.constraint-handling-rules.org. Ulm University."},{"key":"S1471068418000078_ref38","doi-asserted-by":"crossref","unstructured":"Schrijvers T. and Sulzmann M. 2008. Transactions in constraint handling rules. In Proc. 24th International Conference on Logic Programming. Lecture Notes in Computer Science, vol. 5366. Springer, 516\u2013530.","DOI":"10.1007\/978-3-540-89982-2_44"},{"key":"S1471068418000078_ref11","first-page":"268","volume-title":"The Join Calculus: A Language for Distributed Mobile Programming","author":"Fournet","year":"2002"},{"key":"S1471068418000078_ref14","first-page":"49","volume-title":"CHR '06","author":"Fr\u00fchwirth","year":"2006"},{"key":"S1471068418000078_ref45","doi-asserted-by":"crossref","unstructured":"Sulzmann M. and Lam E. S. 2008. Parallel execution of multi-set constraint rewrite rules. In Proc. 10thInternational Conference on Principles of Practical Declarative Programming, S. Antoy , Ed. ACM Press, 20\u201331.","DOI":"10.1145\/1389449.1389453"},{"key":"S1471068418000078_ref31","unstructured":"Meister M. 2007. Concurrency of the preflow-push algorithm in constraint handling rules. In Proc. 12th International Workshop on Constraint Solving and Constraint Logic Programming, 160\u2013169."},{"key":"S1471068418000078_ref33","unstructured":"Raiser F. , Betz H. and Fr\u00fchwirth T. 2009. Equivalence of CHR states revisited. In Proc. Constraint Handling Rules, F. Raiser and J. Sneyers , Eds. K.U. Leuven, Dept. Comp. Sc., Technical report CW 555, 33\u201348."},{"key":"S1471068418000078_ref39","doi-asserted-by":"publisher","DOI":"10.1007\/s004460050028"},{"key":"S1471068418000078_ref41","doi-asserted-by":"publisher","DOI":"10.1145\/1462166.1462169"},{"key":"S1471068418000078_ref22","doi-asserted-by":"crossref","unstructured":"Guerraoui R. and Kapalka M. 2008. On the correctness of transactional memory. In Proc. 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. ACM, New York, NY, USA, 175\u2013184.","DOI":"10.1145\/1345206.1345233"},{"key":"S1471068418000078_ref36","doi-asserted-by":"crossref","unstructured":"Sarna-Starosta B. and Ramakrishnan C. 2007. Compiling constraint handling rules for efficient tabled evaluation. In Proc. 9th International Symposium on Practical Aspects of Declarative Languages, M. Hanus , Ed. Lecture Notes in Computer Science, vol. 4354. Springer, 170\u2013184.","DOI":"10.1007\/978-3-540-69611-7_11"},{"key":"S1471068418000078_ref51","unstructured":"Zaki A. , Fr\u00fchwirth T. and Geller I. 2012. Parallel execution of constraint handling rules on a graphical processing unit. In CHR '12, J. Sneyers and T. Fr\u00fchwirth , Eds. K.U. Leuven, Dept. Comp. Sc., Technical report CW 624, 82\u201390."},{"key":"S1471068418000078_ref34","unstructured":"Raiser F. and Fr\u00fchwirth T. 2010. Exhaustive parallel rewriting with multiple removals. In WLP '10, S. Abdennadher , Ed."},{"key":"S1471068418000078_ref3","doi-asserted-by":"crossref","unstructured":"Abdennadher S. and Fr\u00fchwirth T. 2004. Integration and optimization of rule-based constraint solvers. In Proc. International Symposium on Logic-Based Program Synthesis and Transformation, M. Bruynooghe , Ed. Lecture Notes in Computer Science, vol. 3018. Springer, 198\u2013213.","DOI":"10.1007\/978-3-540-25938-1_17"},{"key":"S1471068418000078_ref2","doi-asserted-by":"crossref","unstructured":"Abdennadher S. and Fr\u00fchwirth T. 1999. Operational equivalence of CHR programs and constraints. In Proc. International Conference on Principles and Practice of Constraint Programming, J. Jaffar , Ed. Lecture Notes in Computer Science, vol. 1713. Springer, 43\u201357.","DOI":"10.1007\/978-3-540-48085-3_4"},{"key":"S1471068418000078_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/S147106841000030X"},{"key":"S1471068418000078_ref27","doi-asserted-by":"crossref","unstructured":"Lam E. S. and Sulzmann M. 2007. A concurrent constraint handling rules semantics and its implementation with software transactional memory. In Proc. ACM SIGPLAN Workshop on Declarative Aspects of Multicore Programming. ACM Press.","DOI":"10.1145\/1248648.1248653"},{"key":"S1471068418000078_ref48","unstructured":"Triossi A. 2011. Hardware execution of constraint handling rules. PhD Thesis, Universita Ca Foscari di Venezia."},{"key":"S1471068418000078_ref47","doi-asserted-by":"publisher","DOI":"10.1145\/62.2160"},{"key":"S1471068418000078_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21542-6_2"},{"key":"S1471068418000078_ref28","doi-asserted-by":"publisher","DOI":"10.1017\/S147106841000044X"},{"key":"S1471068418000078_ref12","doi-asserted-by":"crossref","unstructured":"Fr\u00fchwirth T. 2005a. Parallelizing union-find in Constraint Handling Rules using confluence. In Proc. International Conference on Logic Programming, M. Gabbrielli and G. Gupta , Eds. Lecture Notes in Computer Science, vol. 3668. Springer, 113\u2013127.","DOI":"10.1007\/11562931_11"},{"key":"S1471068418000078_ref15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511609886"},{"key":"S1471068418000078_ref40","doi-asserted-by":"crossref","unstructured":"Sneyers J. 2008. Turing-complete subclasses of CHR. In Proc. 24th International Conference on Logic Programming. Lecture Notes in Computer Science, vol. 5366. Springer, 759\u2013763.","DOI":"10.1007\/978-3-540-89982-2_72"},{"key":"S1471068418000078_ref50","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2009.208"},{"key":"S1471068418000078_ref1","doi-asserted-by":"crossref","unstructured":"Abdennadher S. and Fr\u00fchwirth T. 1998. On completion of Constraint Handling Rules. In Proc. International Conference on Principles and Practice of Constraint Programming, M. J. Maher and J.-F. Puget , Eds. Lecture Notes in Computer Science, vol. 1520. Springer, 25\u201339.","DOI":"10.1007\/3-540-49481-2_4"},{"key":"S1471068418000078_ref24","first-page":"248","volume-title":"Coloured Petri Nets","author":"Jensen","year":"1987"},{"key":"S1471068418000078_ref37","doi-asserted-by":"publisher","DOI":"10.1142\/S0218194007003197"},{"key":"S1471068418000078_ref44","unstructured":"Sulzmann M. and Lam E. S. 2007. Compiling constraint handling rules with lazy and concurrent search techniques. In Proc. 4th Workshop on Constraint Handling Rules, 139\u2013149."},{"key":"S1471068418000078_ref20","first-page":"1","article-title":"Unfolding for CHR programs","volume":"15","author":"Gabbrielli","year":"2013","journal-title":"Theory and Practice of Logic Programming"},{"key":"S1471068418000078_ref43","unstructured":"Sulzmann M. and Chu D. H. 2008. A rule-based specification of Software Transactional Memory. In LOPSTR '08, Pre-proceedings, M. Hanus , Ed."},{"key":"S1471068418000078_ref32","unstructured":"Meister M. and Fr\u00fchwirth T. 2007. Reconstructing almost-linear tree equation solving algorithms in CHR. In Proc. Annual ERCIM Workshop on Constraint Solving and Constraint Logic Programming, 123."},{"key":"S1471068418000078_ref4","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009842826135"},{"key":"S1471068418000078_ref13","doi-asserted-by":"crossref","unstructured":"Fr\u00fchwirth T. 2005b. Specialization of concurrent guarded multi-set transformation rules. In Proc. International Symposium on Logic-Based Program Synthesis and Transformation, S. Etalle , Ed. Lecture Notes in Computer Science, vol. 3573. Springer, 133\u2013148.","DOI":"10.1007\/11506676_9"},{"key":"S1471068418000078_ref25","first-page":"121","volume-title":"Constraint Handling Rules: Compilation, Execution, and Analysis","author":"Lam","year":"2018"},{"key":"S1471068418000078_ref19","volume-title":"Constraint Handling Rules: Compilation, Execution, and Analysis","author":"Fr\u00fchwirth","year":"2011"},{"key":"S1471068418000078_ref5","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/1086.001.0001","volume-title":"Actors: A Model of Concurrent Computation in Distributed Systems","author":"Agha","year":"1986"},{"key":"S1471068418000078_ref26","doi-asserted-by":"crossref","unstructured":"Lam E. S. and Cervesato I. 2013. Decentralized execution of constraint handling rules for ensembles. In Proc. 15th Symposium on Principles and Practice of Declarative Programming. ACM, 205\u2013216.","DOI":"10.1145\/2505879.2505892"},{"key":"S1471068418000078_ref21","doi-asserted-by":"publisher","DOI":"10.1145\/48014.61051"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068418000078","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,2]],"date-time":"2020-11-02T09:06:56Z","timestamp":1604308016000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068418000078\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,23]]},"references-count":51,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["S1471068418000078"],"URL":"https:\/\/doi.org\/10.1017\/s1471068418000078","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,5,23]]}}}