No CrossRef data available.
Article contents
Unfolding for CHR programs
Published online by Cambridge University Press: 08 October 2013
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
Program transformation is an appealing technique which allows to improve run-time efficiency, space-consumption, and more generally to optimize a given program. Essentially, it consists of a sequence of syntactic program manipulations which preserves some kind of semantic equivalence. Unfolding is one of the basic operations used by most program transformation systems and consists of the replacement of a procedure call by its definition. While there is a large body of literature on the transformation and unfolding of sequential programs, very few papers have addressed this issue for concurrent languages. This paper defines an unfolding system for Constraint Handling Rules programs. We define an unfolding rule, show its correctness and discuss some conditions that can be used to delete an unfolded rule while preserving the program meaning. We also prove that, under some suitable conditions, confluence and termination are preserved by the above transformation.
Information
- Type
- Regular Papers
- Information
- Copyright
- Copyright © Cambridge University Press 2013
References
Abdennadher, S.
1997. Operational semantics and confluence of constraint propagation rules. In Principles and Practice of Constraint Programming (CP97), Smolka, G., Ed., Lecture Notes in Computer Science, vol. 1330. Springer, Berlin, Germany, 252–266.Google Scholar
Abdennadher, S. and Frühwirth, T.
2004. Integration and organization of rule-based constraint solvers. In Logic Based Program Synthesis and Transformation (LOPSTR 2003), Bruynooghe, M., Ed., Lecture Notes in Computer Science, vol. 3018/2004. Springer-Verlag, Berlin, Germany, 198–231.Google Scholar
Duck, G. J., Stuckey, P. J., Garca de la Banda, M. and Holzbaur, C.
2004. The refined operational semantics of constraint handling rules. In Logic Programming, Demoen, B. and Lifschitz, V., Eds., Lecture Notes in Computer Science, vol. 3132. Springer, Berlin, Germany, 269–304.Google Scholar
Etalle, S., Gabbrielli, M. and Meo, M. C.
2001. Transformations of CCP programs. ACM Transactions on Programming Languages and Systems (TOPLAS)
23, 3, 304–395.Google Scholar
Frühwirth, T.
1998. Theory and practice of constraint handling rules. Journal of Logic Programming
37, 1–3 (October), 95–138. (Special Issue on Constraint Logic Programming.)Google Scholar
Frühwirth, T.
2005. Specialization of concurrent guarded multi-set transformation rules. In Logic Based Program Synthesis and Transformation, Etalle, S., Ed., Lecture Notes in Computer Science, vol. 3573. Springer, Berlin, Germany, 133–148.CrossRefGoogle Scholar
Frühwirth, T.
2009. Constraint Handling Rules. Cambridge University Press, Cambridge, UK.CrossRefGoogle Scholar
Frühwirth, T. and Abdennadher, S.
2003. Essentials of Constraint Programming. Springer, Berlin, Germany.Google Scholar
Frühwirth, T., Di Pierro, A. and Wiklicky, H.
2002. Probabilistic constraint handling rules. In Selected Papers of WFLP'02 – 11th International Workshop on Functional and (Constraint) Logic Programming, Comini, M. and Falaschi, M., Eds., Electronic Notes in Theoretical Computer Science, vol. 76. Elsevier, Amsterdam, Netherlands, 115–130.Google Scholar
Frühwirth, T. and Holzbaur, C.
2003. Source-to-source transformation for a class of expressive rules. In APPIA-GULP-PRODE. Pub Zone, Reggio Calabria, Italy, 386–397.Google Scholar
Raiser, F., Betz, H. and Frühwirth, T.
2009. Equivalence of CHR states revisited. In Proceedings of the 6th International Workshop on Constraint Handling Rules (CHR), Kaiser, F. and Sneyers, J., Eds., Report CW555 of Katholieke Universiteit Leuven, Department of Computer Science, Heverlee, Belgium, 34–48.Google Scholar
Sarna-Starosta, B. and Schrijvers, T.
2009. Attributed Data for CHR Indexing. In Proceedings of the 25th International Conference on Logic Programming (ICLP 2009), Hill, P. M. and Warren, D. S., Eds., Lecture Notes in Computer Science, vol. 5649. Springer, Berlin, Germany, 357–371.Google Scholar
Schrijvers, T. and Sulzmann, M.
2008. Transactions in constraint handling rules. In Proceedings of the 24th International Conference on Logic Programming (ICLP 2008), de la Banda, M. G. and Pontelli, E., Eds., Lecture Notes in Computer Science, vol. 5366. Springer, Berlin, Germany, 516–530.Google Scholar
Sneyers, J., Meert, W., Vennekens, J., Kameya, Y. and Sato, T.
2010. CHR(PRISM)-based probabilistic logic learning. Theory and Practice of Logic Programming
10, 4–6, 433–447.Google Scholar
Sneyers, J., Schrijvers, T. and Demoen, B.
2005. Guard and continuation optimization for occurrence representations of CHR. In Proceedings of the 21st International Conference (ICLP 2005), Gabbrielli, M. and Gupta, G., Eds., Lecture Notes in Computer Science, vol. 3668. Springer, Berlin, Germany, 83–97.Google Scholar
Tacchella, P.
2008. Constraint Handling Rules. Compositional Semantics and Program Transformation, PhD thesis, Università di Bologna, Bologna, Italy.Google Scholar
Tacchella, P., Meo, M. C. and Gabbrielli, M.
2007. Unfolding in CHR. In Proceedings of the 9th ACM SIGPLAN International Symposium on Principles and Practice of Declarative Programming (PPDP '07), Leuschel, M. and Podelski, A., Eds., Heverlee, Belgium, 179–186.Google Scholar
Tamaki, H. and Sato, T.
1984. Unfold/fold transformations of logic programs. In Proceedings of the International Conference on Logic Programming, Tärnlund, Sten-Åke, Ed., Uppsala University, Uppsala, Sweden, 127–138.Google Scholar
Ueda, K. and Furukawa, K.
1988. Transformation rules for GHC programs. In Proceedings of the International Conference on Fifth Generation Computer Systems 1988 (FGCS'88). ICOT Press, Tokyo, Japan, 582–591.Google Scholar
You have
Access
- 1
- Cited by