Parallelism, concurrency and distribution in constraint handling rules: A survey
| Autor: | Thom Frühwirth |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Soundness
Constraint Handling Rules Correctness Semantics (computer science) Computer science Programming language Concurrency Computational logic 020207 software engineering 02 engineering and technology computer.software_genre Theoretical Computer Science TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Computational Theory and Mathematics Artificial Intelligence Hardware and Architecture TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Actor model computer Software Declarative programming |
| Zdroj: | Theory and Practice of Logic Programming. 18:759-805 |
| ISSN: | 1475-3081 1471-0684 |
| DOI: | 10.1017/s1471068418000078 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|