Concurrency Semantics in Continuation-Passing Style

• Autorzy: Todoran E. N. , Papaspyrou N.

Identyfikatory

DOI

10.3233/FI-2017-1534

• Języki publikacji: EN

Abstrakty

EN

We present a denotational semantics designed in continuation-passing style (CPS) for an abstract language providing operators for nondeterministic choice, sequential and parallel composition, and a general mechanism of interaction between multisets of distributed actions. We show that the basic laws of concurrent systems are satisfied in this semantics. Next, by customizing the behavior of continuations we obtain denotational semantics for a couple of concurrent languages and a nature-inspired formalism. The languages discussed include Hoare's communicating sequential processes (CSP), and two formalisms based on multiparty interactions: a version of CSP extended with communication and synchronization on multiple channels, and a language similar to a process algebra for DNA computing introduced by Cardelli. We accomplish the semantic investigation in the mathematical framework of complete metric spaces.

Słowa kluczowe

EN

concurrency semantics; continuation-passing style; denotational semantics; metric spaces

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 153, nr 1/2
• Strony: 125--146
• Opis fizyczny: Bibliogr. 31 poz.

Twórcy

autor

Todoran E. N.

• Department of Computer Science, Technical University of Cluj-Napoca, Cluj-Napoca, Romania

autor

Papaspyrou N.

• School of Electrical and Computer Engineering, Software Engineering Laboratory, National Technical University of Athens, Athens, Greece

Bibliografia

• [1] Strachey C, Wadsworth CP. Continuations: A Mathematical Semantics for Handling Full Jumps. Higher-Order and Symbolic Computation, 2000;13(1):135–152. doi:10.1023/A:1010026413531.
• [2] Reynolds JC. The Discoveries of Continuations. LISP and Symbolic Computation, 1993;6(3-4):233–248. doi:10.1007/BF01019459.
• [3] Queinnec C. Inverting Back the Inversion of Control or, Continuations Versus Page-centric Programming. ACM SIGPLAN Notices, 2003;38(2):57–64. doi:10.1145/772970.772977.
• [4] Cooper E, Lindley S, Wadler P, Yallop J. Links: Web Programming without Tiers. Lecture Notes in Computer Science, 2007;4709:266–296. doi:10.1007/978-3-540-74792-5_12.
• [5] Leger P, Fukuda H. Using Continuations and Aspects to Tame Asynchronous Programming on the Web. In: Modularity Companion 2016: Companion Proceedings of the 15th International Conference on Modularity. 2016 pp. 79–82. doi:10.1145/2892664.2892675.
• [6] Haynes CT, Friedman DP, Wand M. Obtaining Coroutines with Continuations. Computer Languages, 1986;11(3-4):143–153. doi:10.1016/0096-0551(86)90007-X.
• [7] Wand M. Continuation-based Multiprocessing. Higher-Order and Symbolic Computation, 1999;12(3): 285–299. doi:10.1023/A:1010093700911.
• [8] Dybvig RK, Hieb R. Engines from Continuations. Computer Languages, 1989;14(2):109–123. doi:10.1016/0096-0551(89)90018-0.
• [9] Sitaram D, Felleisen M. Control Delimiters and their Hierarchies. LISP and Symbolic Computation, 1990;3(1):67–99. doi:10.1007/BF01806126.
• [10] Hieb R, Dybvig RK, Anderson CW. Subcontinuations. LISP and Symbolic Computation, 1994;7(1):83–109. doi:10.1007/BF01019946.
• [11] Mosses PD. Programming Language Description Languages: From Christopher Strachey to Semantics Online. In: Boca P, et al. (eds.), Formal Methods: State of the Art and New Directions, pp. 249–273. Springer, 2010. doi:10.1007/978-1-84882-736-3 8.
• [12] Todoran EN. Metric Semantics for Synchronous and Asynchronous Communication: A Continuation based Approach. Electronic Notes in Theoretical Computer Science, 2000;28:101–127. doi:10.1016/S1571-0661(05)80632-2.
• [13] Ciobanu G, Todoran EN. Continuation Semantics for Asynchronous Concurrency. Fundamenta Informaticae, 2014;131(3-4):373–388. doi:10.3233/FI-2014-1020.
• [14] Claessen K. A Poor Man’s Concurrency Monad. Journal of Functional Programming, 1999;9(3):313–323.
• [15] DeBakker JW, DeVink EP. Control Flow Semantics. MIT Press, 1996. ISBN 978-0262041546.
• [16] Todoran EN, Papaspyrou N. Concurrency Semantics in Continuation-Passing Style. Technical Report CSD-SE-TR-16-01, Software Engineering Laboratory, Computer Science Department, Technical University of Cluj-Napoca, 2016. Available at http://ftp.utcluj.ro/pub/users/gc/eneia/fi17/CSD-SE-TR-16-01.pdf.
• [17] Alexandru A, Ciobanu G. Mathematics of Multisets in the Fraenkel-Mostowski Framework. Bulletin Mathématique de la Société des Sciences Mathématiques de Roumanie, 2015;58(1):3–18.
• [18] America P, Rutten JJMM. Solving Reflexive Domain Equations in a Category of Complete Metric Spaces. Journal of Computer and System Sciences, 1989;39(3):343–375. doi:10.1016/0022-0000(89)90027-5.
• [19] Milner R. Communication and Concurrency. Prentice Hall, 1989. ISBN 978-0131150072.
• [20] Baeten JCM, Weijland WP. Process Algebra. Cambridge University Press, 1990. ISBN 978-0521400435.
• [21] Bergstra JA, Klop JW. Process Algebra for Synchronous Communication. Information and Control, 1984;60(1-3):109–137. doi:10.1016/S0019-9958(84)80025-X.
• [22] Hoare CAR. Communicating Sequential Processes. Prentice Hall, 1985. ISBN 978-0131532717.
• [23] Fournet C, Gonthier G. The Join Calculus: A Language for Distributed Mobile Programming. Lecture Notes in Computer Science, 2002;2395:268–332.
• [24] Todoran EN. Comparative Semantics for Modern Communication Abstractions. In: Proceedings of the IEEE 4th International Conference on Intelligent Computer Communication and Processing (ICCP 2008). 2008 pp. 153–160. doi:10.1109/ICCP.2008.4648367.
• [25] Ciobanu G, Todoran EN. Continuation Semantics for Concurrency with Multiple Channels Communication. Lecture Notes in Computer Science, 2015;9407:400–416. doi:10.1007/978-3-319-25423-4 26.
• [26] INMOS Ltd. Occam Programming Manual. Prentice Hall, 1984. ISBN 978-0136292968.
• [27] Cardelli L. Strand Algebras for DNA Computing. Natural Computing, 2011;10(1):407–428. doi:10.1007/s11047-010-9236-7.
• [28] Todoran EN, Papaspyrou N. Experiments with Continuation Semantics for DNA Computing. In: Proceedings of the IEEE 9th International Conference on Intelligent Computer Communication and Processing (ICCP 2013). 2013 pp. 251–258. doi:10.1109/ICCP.2013.6646117.
• [29] Peyton Jones S, Hughes J. Report on the Programming Language Haskell 98: a Non-Strict Purely Functional Language, 1999. Available at http://www.haskell.org.
• [30] Plotkin GD. A Powerdomain Construction. SIAM Journal of Computing, 1976;5(3):452–487. doi:10.1137/0205035.
• [31] Milner R. Fully Abstract Models of Typed λ-Calculi. Theoretical Computer Science, 1977;4(1):1–22. doi:10.1016/0304-3975(77)90053-6.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).