Sandro Etalle
Abstract
We introduce a transformation system for concurrent constraint programming (CCP). We define suitable applicability conditions for the transformations that guarantee the input/output CCP semantics is also preserved when distinguishing deadlocked computations from successful ones and when considering intermediate results of (possibly) nonterminating computations.The system allows us to optimize CCP programs while preserving their intended meaning: In addition to the usual benefits for sequential declarative languages, the transformation of concurrent programs can also lead to the elimination of communication channels and of synchronization points, to the transformation of nondeterministic computations into deterministic ones, and to the crucial saving of computational space. Furthermore, since the transformation system preserves the deadlock behavior of programs, it can be used for proving deadlock-freeness of a given program with respect to a class of queries. To this aim, it is sometimes sufficient to apply our transformations and to specialize the resulting program with respect to the given queries in such a way that the obtained program is trivially deadlock-free.
- BENSAOU,N.AND GUESSARIAN, I. 1998. Transforming constraint logic programs. Theor. Comput. Sci. 206, 1-2, 81-125. Google Scholar
- BOER,F.S.D.,GABBRIELLI, M., MARCHIORI, E., AND PALAMIDESSI, C. 1997. Proving concurrent constraint programs correct. ACM Trans. Program. Lang. Syst. 19, 5, 685-725. Google Scholar
- BURSTALL,R.AND DARLINGTON, J. 1977. A transformation system for developing recursive programs. J. ACM 24, 1 (Jan.), 44-67. Google Scholar
- CLARK,K.AND SICKEL, S. 1977. Predicate logic: a calculus for deriving programs. In Proceedings of IJCAI'77. 419-120.Google Scholar
- CODISH, M., FALASCHI, M., AND MARRIOTT, K. 1994. Suspension analyses for concurrent logic programs. ACM Trans. Program. Lang. Syst. 16, 3, 649-686. Google Scholar
- DE BOER,F.AND PALAMIDESSI, C. 1991. A fully abstract model for concurrent constraint programming. In TAPSOFT/CAAP. S. Abramsky and T. Maibaum, eds. LNCS 493, Springer Verlag. Google Scholar
- DE BOER,F.AND PALAMIDESSI, C. 1992. On the semantics of concurrent constraint programming. In ALPUK 92, Workshops in Computing, Springer-Verlag, 145-173.Google Scholar
- ETALLE,S.AND GABBRIELI, M. 1998. Partial evaluation of concurrent constraint languages. ACM Comput. Surv. 30, (Sept.). Google Scholar
- ETALLE,S.AND GABBRIELLI, M. 1996. Transformations of CLP modules. Theor. Comput. Sci. 166, 1, 101-146. Google Scholar
- ETALLE, S., GABBRIELLI, M., AND MEO, M. C. 1998. Unfold/fold transformations of CCP programs. In CONCUR98-1998 International Conference on Concurrency Theory, D. Sangiorgi and R. de Simone, eds. LNCS 1466, Springer Verlag, 348-363. Google Scholar
- FRANCESCO,N.D.AND SANTONE, A. 1996. Unfold/fold transformation of concurrent processes. In Proceeding of the. 8th International Symposium. on Programming Languages: Implementations, Logics and Programs, H. Kuchen and S. Swierstra, eds. Vol. 1140, Springer Verlag, 167-181. Google Scholar
- GENGLER,M.AND MARTEL, M. 1997. Self-applicable partial evaluation for pi-calculus. In Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (PEPM-97). ACM SIGPLAN Not. 32, 12. ACM Press, New York, 36-46. Google Scholar
- HOGGER, C. 1981. Derivation of logic programs. J. ACM 28, 2 (April), 372-392. Google Scholar
- HOSOYA, H., KOBAYASHI,N.,AND YONEZAWA, A. 1996. Partial evaluation scheme for concurrent languages and its correctness. In Euro-Par'96, LNCS 1123, Springer Verlag, 625-632. Google Scholar
- JAFFAR,J.AND MAHER, M. J. 1994. Constraint logic programming: A survey. J. Logic Program. 19/20, 503-581.Google Scholar
- JORGENSEN, N., MARRIOTT, K., AND MICHAYLOV, S. 1991. Some global compile-time optimizations for CLP( R ). In Proceeding of the International Logic Programming Symposium, V. Saraswat and K. Ueda, eds. MIT Press, Cambridge, MA, 420-434.Google Scholar
- KAWAMURA,T.AND KANAMORI, T. 1988. Preservation of stronger equivalence in unfold/fold logic programming transformation. In Proceeding of the Internatinal Conference on Fifth Generation Computer Systems. Institute for New Generation Computer Technology, Tokyo, 413-422.Google Scholar
- KOMOROWSKI, H. 1982. Partial evaluation as a means for inferencing data structures in an applicative language: A theory and implementation in the case of Prolog. In Proceedings of the Ninth ACM Symposium on Principles of Programming Languages (Albuquerque, NM). ACM Press, New York, NY, 255-267. Google Scholar
- LLOYD, J. W. 1987. Foundations of Logic Programming. 2dn ed. Springer Verlag, Berlin. Google Scholar
- MAHER, M. 1993. A transformation system for deductive databases with perfect model semantics. Theor. Comput. Sci. 110, 2 (March), 377-403. Google Scholar
- MARINESCU,M.AND GOLDBERG, B. 1997. Partial-evaluation techniques for concurrent programs. In Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (PEPM-97). ACM SIGPLAN Not. 32, 12. ACM Press, New York, NY, 47-62. Google Scholar
- MILNER, R. 1989. Communication and Concurrency. Prentice-Hall, Englewood Cliffs, NJ. Google Scholar
- MOGENSEN,T.AND SESTOFT, P. 1997. Partial evaluation. In Encyclopedia of Computer Science and Technology, A. Kent and J. Williams, eds. Vol. 37. Marcel. Dekker, 247-279.Google Scholar
- PETTOROSSI,A.AND PROIETTI, M. 1994. Transformation of logic programs: Foundations and techniques. J. Logic Program. 19, 20, 261-320.Google Scholar
- SAHLIN, D. 1995. Partial evaluation of AKL. In Proceedings of the First International Conference on Concurrent Constraint Programming.Google Scholar
- SARASWAT,V.AND RINARD, M. 1990. Concurrent constraint programming. In Proceeding of the 17th ACM Symposium on Principles of Programming Languages. ACM Press, New York, NY, 232-245. Google Scholar
- SARASWAT, V., RINARD, M., AND PANANGADEN, P. 1991. Semantics foundations of concurrent constraint programming. In Proceeding of the 18th Annual ACM Symposium on Principles of Programming Languages. ACM Press, New York, NY. Google Scholar
- SARASWAT, V. A. 1989. Concurrent constraint programming languages. Ph.D. thesis, Carnegie- Mellon University, Pittsburgh, PA. Google Scholar
- SMOLKA, G. 1995. The Oz programming model. In Computer Science Today, J. van Leeuwen, ed. LNCS 1000, Springer Verlag; see www.ps.uni-sb.de/oz/.Google Scholar
- TAMAKI, H., AND SATO, T. 1984. Unfold/fold transformations of logic programs. In Proceedings of the Second International Conference on Logic Programming, S.-A. ke Tarnlund, ed. 127-139.Google Scholar
- UEDA, K. 1986. Guarded Horn clauses. In Logic Programming '85, E. Wada, ed. LNCS 221, Springer Verlag, Berlin, 168-179. Google Scholar
- UEDA,K.AND FURUKAWA, K. 1988. Transformation rules for GHC programs. In Proceedings of the Internatinal Conference on Fifth Generation Computer Systems. Institute for New Generation Computer Technology, Tokyo, 582-591.Google Scholar
Index Terms
- Transformations of CCP programs
Recommendations
A transformation system for CLP with dynamic scheduling and CCP
In this paper we study unfold/fold transformations for constraint logic programs (CLP) with dynamic scheduling and for concurrent constraint programming (CCP). We define suitable applicability conditions for these transformations which guarantee that ...
A transformation system for CLP with dynamic scheduling and CCP
PEPM '97: Proceedings of the 1997 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulationIn this paper we study unfold/fold transformations for constraint logic programs (CLP) with dynamic scheduling and for concurrent constraint programming (CCP). We define suitable applicability conditions for these transformations which guarantee that ...
The expressivity of universal timed CCP: undecidability of Monadic FLTL and closure operators for security
PPDP '08: Proceedings of the 10th international ACM SIGPLAN conference on Principles and practice of declarative programmingThe timed concurrent constraint programing model (tcc) is a declarative framework, closely related to First-Order Linear Temporal Logic (FLTL), for modeling reactive systems. The universal tcc formalism (utcc) is an extension of tcc with the ability to ...
Comments