Abstract
We extend the rule-based, multiset rewriting language CHR with multiset comprehension patterns. Multiset comprehension provides the programmer with the ability to write multiset rewriting rules that can match a variable number of entities in the state. This enables implementing algorithms that coordinate large amounts of data or require aggregate operations in a declarative way, and results in code that is more concise and readable than with pure CHR. We call this extension CHR cp. In this paper, we formalize the operational semantics of CHR cp and define a low-level optimizing compilation scheme based on join ordering for the efficient execution of programs. We provide preliminary empirical results that demonstrate the scalability and effectiveness of this approach.
This paper was made possible by grant NPRP 09-667-1-100, Effective Programming for Large Distributed Ensembles, from the Qatar National Research Fund (a member of the Qatar Foundation). The statements made herein are solely the responsibility of the authors.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Batory, D.: The LEAPS Algorithm. Technical report, University of Texas at Austin (1994)
Cruz, F., Rocha, R., Copen Goldstein, S., Pfenning, F.: A linear logic programming language for concurrent programming over graph structures. CoRR, abs/1405.3556 (2014)
De Koninck, L., Schrijvers, T., Demoen, B.: User-definable rule priorities for chr. In: PPDP 2007, pp. 25–36. ACM, New York (2007)
De Koninck, L., Sneyers, J.: Join ordering for constraint handling rules. In: CHR (2007)
Duck, G.J., Stuckey, P.J., García de la Banda, M., Holzbaur, C.: The Refined Operational Semantics of Constraint Handling Rules. In: Demoen, B., Lifschitz, V. (eds.) ICLP 2004. LNCS, vol. 3132, pp. 90–104. Springer, Heidelberg (2004)
Holzbaur, C., de la Banda, M.G., Stuckey, P.J., Duck, G.J.: Optimizing compilation of constraint handling rules in HAL. CoRR, cs.PL/0408025 (2004)
Lam, E.S.L., Cervesato, I.: Constraint Handling Rules with Multiset Comprehension Patterns. In: CHR 2014 (2014)
Lam, E.S.L., Cervesato, I.: Optimized Compilation of Multiset Rewriting with Comprehensions (Full-Version). Technical Report CMU-CS-14-119, Carnegie Mellon (June 2014)
Lam, E.S.L., Cervesato, I.: Reasoning about Set Comprehension. In: SMT 2014 (2014)
Lam, E.S.L., Cervesato, I.: Decentralized Execution of Constraint Handling Rules for Ensembles. In: PPDP 2013, Madrid, Spain, pp. 205–216 (2013)
Sneyers, J., Van Weert, P., Schrijvers, T., Demoen, B.: Aggregates in Constraint Handling Rules. In: Dahl, V., Niemelä, I. (eds.) ICLP 2007. LNCS, vol. 4670, pp. 446–448. Springer, Heidelberg (2007)
Triossi, A., Orlando, S., Raffaetà, A., Frühwirth, T.W.: Compiling CHR to parallel hardware. In: PPDP 2012, pp. 173–184 (2012)
Van Weert, P., Schrijvers, T., Demoen, B., Leuven, K.U.: JCHR: A user-friendly, flexible and efficient CHR system for Java. In: CHR 2005, pp. 47–62 (2005)
Weert, P.V., Sneyers, J., Schrijvers, T., Demoen, B.: Extending CHR with Negation as Absence. In: CHR 2006, pp. 125–140 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Lam, E.S.L., Cervesato, I. (2014). Optimized Compilation of Multiset Rewriting with Comprehensions. In: Garrigue, J. (eds) Programming Languages and Systems. APLAS 2014. Lecture Notes in Computer Science, vol 8858. Springer, Cham. https://doi.org/10.1007/978-3-319-12736-1_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-12736-1_2
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-12735-4
Online ISBN: 978-3-319-12736-1
eBook Packages: Computer ScienceComputer Science (R0)