Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-12-01T09:10:13.319Z Has data issue: false hasContentIssue false
  • English
  • Français

Transactional events1

Part of: JFP Research Articles

Published online by Cambridge University Press:  30 October 2008

KEVIN DONNELLY  and
MATTHEW FLUET
KEVIN DONNELLY
Affiliation:
Boston University, Boston, MA 02215, US (e-mail: [email protected])
MATTHEW FLUET
Affiliation:
Toyota Technological Institute at Chicago, Chicago, IL 60637, US (e-mail: [email protected])
Rights & Permissions [Opens in a new window]

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.

Concurrent programs require high-level abstractions in order to manage complexity and enable compositional reasoning. In this paper, we introduce a novel concurrency abstraction, dubbed transactional events, which combines first-class synchronous message passing events with all-or-nothing transactions. This combination enables simple solutions to interesting problems in concurrent programming. For example, guarded synchronous receive can be implemented as an abstract transactional event, whereas in other languages it requires a non-abstract, non-modular protocol. As another example, three-way rendezvous can be implemented as an abstract transactional event, which is impossible using first-class events alone. Both solutions are easy to code and easy to reason about.

The expressive power of transactional events arises from a sequencing combinator whose semantics enforces an all-or-nothing transactional property – either both of the constituent events synchronize in sequence or neither of them synchronizes. This sequencing combinator, along with a non-deterministic choice combinator, gives transactional events the compositional structure of a monad-with-plus. We provide a formal semantics for transactional events and give a detailed account of an implementation.

Type
Articles
Information
Journal of Functional Programming , Volume 18 , Special Double Issue 5-6 , September 2008 , pp. 649 - 706
Copyright
Copyright © Cambridge University Press 2008

Footnotes

2Portions of this work were completed while the author was affiliated with Cornell University, Ithaca, NY 14853, US.
1

This is a revised and extended version of the paper that appeared in the Eleventh ACM SIGPLAN International Conference on Functional Programming (ICFP'06) (Donnelly & Fluet, 2006).

References

Adl-Tabatabai, Ali-Reza, Lewis, Brian T., Menon, Vijay, Murphy, Brian R., Saha, Bratin & Shpeisman, Tatiana. (2006) Compiler and runtime support for efficient software transactional memory. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'06). New York: ACM Press, pp. 26–37.Google Scholar
Armstrong, Joe, Virding, Robert, Wikström, Claes & Williams, Mike. (1996) Concurrent Programming in Erlang, 2nd ed. Hertfordshire, UK: Prentice Hall International (UK) Ltd.Google Scholar
Donnelly, Kevin & Fluet, Matthew. (2006) Transactional events. In Proceedings of the Eleventh ACM SIGPLAN International Conference on Functional Programming (ICFP'06). New York: ACM Press, pp. 124–135.Google Scholar
Flatt, Matthew & Findler, Robert Bruce. (2004) Kill-safe synchronization abstractions. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'04). New York: ACM Press, pp. 47–58.Google Scholar
Gasner, Emden R. & Reppy, John H. (1993) A multi-threaded high-order user interface toolkit. In User Interface Software, Bass, Len & Dewan, Prasun (eds). Software Trends, Vol. 1. New York: John Wiley & Sons, Chap. 4, pp. 61–80.Google Scholar
Glasgow Haskell Compiler (version 6.6). (2006) http://www.haskell.org/ghc.Google Scholar
Grossman, Dan. (April 2006) Software Transactions are to Concurrency as Garbage Collection is to Memory Management. Tech. Rept. 2006-04-01. University of Washington, Department of Computer Science & Engineering.Google Scholar
Harris, Tim & Fraser, Keir. (2003) Language support for lightweight transactions. In Proceedings of the 18th Annual ACM SIGPLAN Conference on Object-Oriented Programing, Systems, Languages, and Applications (OOPSLA'03). New York: ACM Press, pp. 388–402.Google Scholar
Harris, Tim, Marlow, Simon & Peyton Jones, Simon. (2005a) Haskell on a shared-memory multiprocessor. In Proceedings of the ACM SIGPLAN Workshop on Haskell. New York: ACM Press, pp. 49–61.Google Scholar
Harris, Tim, Marlow, Simon, Peyton Jones, Simon & Herlihy, Maurice. (2005b) Composable memory transactions. In Proceedings of the Tenth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP'05). New York: ACM Press, pp. 48–60.Google Scholar
Harris, Tim, Plesko, Mark, Shinnar, Avraham & Tarditi, David. (2006) Optimizing memory transactions. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'06). New York: ACM Press, pp. 14–25.Google Scholar
Herlihy, Maurice & Moss, J. Eliot B. (1993) Transactional memory: Architectural support for lock-free data structures. In Proceedings of the 20th Annual International Symposium on Computer Architecture (ISCA'93). New York: ACM Press, pp. 289–300.Google Scholar
Hindman, Benjamin & Grossman, Dan. (2006) Atomicity via source-to-source translation. In Proceedings of the Workshop on Memory System Performance and Correctness (MSPC'06). New York: ACM Press, pp. 82–91.Google Scholar
Hinze, Ralf. (2000) Deriving backtracking monad transformers (functional pearl). In Proceedings of the Fifth ACM SIGPLAN International Conference on Functional Programming (ICFP'00). New York: ACM Press, pp. 186–197.CrossRefGoogle Scholar
Hoare, C. A. R. (1978) Communicating sequential processes. Commun. ACM 21 (8), 666–677.CrossRefGoogle Scholar
Jeffrey, Alan. (1995a) A fully abstract semantics for a concurrent functional language with monadic types. In Proceedings of the Tenth Annual IEEE Symposium on Logic in Computer Science (LICS'95). Los Alamitos, CA: IEEE Computer Society Press, pp. 255–265.Google Scholar
Jeffrey, Alan. (1995b) A fully abstract semantics for a nondeterministic functional language with monadic types. In Proceedings of the Eleventh Conference on the Mathematical Foundations of Programming Semantics (MFPS XI). Electronic Notes in Theoretical Computer Science, Vol. 1. New York: Elsevier.Google Scholar
Karlsen, Einar. (1997) The UniForM Concurrency ToolKit and its extensions to Concurrent Haskell. In The Glasgow Functional Programming Workshop (GFPW).Google Scholar
Kiselyov, Oleg, Shan, Chung-chieh, Friedman, Daniel & Sabry, Amr. (2005) Backtracking, interleaving, and terminating monad transformers (functional pearl). In Proceedings of the Tenth ACM SIGPLAN International Conference on Functional Programming (ICFP'05). New York: ACM Press, pp. 192–203.CrossRefGoogle Scholar
Manson, Jeremy, Baker, Jason, Cunei, Antonio, Jagannathan, Suresh, Prochazka, Marek, Xin, Bin & Vitek, Jan. (2005) Preemptible atomic regions for real-time Java. In Proceedings of the 26th IEEE International Real-Time Systems Symposium (RTSS'05). Los Alamitos, CA: IEEE Computer Society, pp. 62–71.CrossRefGoogle Scholar
Marlow, Simon, Peyton Jones, Simon, Moran, Andrew & Reppy, John. (2001) Asynchronous exceptions in Haskell. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'01). New York: ACM Press, pp. 274–285.Google Scholar
Moggi, Eugino. (1989) Computational lambda calculus and monads. In Proceedings of the Fifth Annual IEEE Symposium on Logic in Computer Science (LICS'89). Los Alamitos, CA: IEEE Computer Society Press, pp. 14–23.Google Scholar
Moggi, Eugino. (1991) Notions of computation and monads. Info. Comput. 93 (1), 55–92.Google Scholar
MonadPlus. (2005) http://www.haskell.org/hawiki/MonadPlus.Google Scholar
Moran, Andrew, Lassen, Soren B. & Peyton Jones, Simon. (1999) Imprecise exceptions, co-inductively. In Proceedings of the Third International Workshop on Higher Order Operational Techniques in Semantics (HOOTS'99). Electronic Notes in Theoretical Computer Science, Vol. 26. New York: Elsevier, pp. 122–141.Google Scholar
Moss, J. Eliot B. (1985) Nested Transactions: An Approach to Reliable Distributed Computing. Cambridge, MA: MIT Press.Google Scholar
Panangaden, Prakash & Reppy, John. (1997) The essence of Concurrent ML. In ML with Concurrency: Design, Analysis, Implementation, and Application, Nielson, Flemming (ed). Monographs in Computer Science. New York: Springer-Verlag, Chap. 2, pp. 5–30.Google Scholar
Peyton Jones, Simon. (2001) Tackling the awkward squad: Monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell. In Engineering Theories of Software Construction, Hoare, Tony, Broy, Manfred & Steinbrüggen, Ralf (eds). NATO Science Series: Computer & Systems Sciences, Vol. 180. Amsterdam, The Netherlands: IOS Press, pp. 47–96.Google Scholar
Peyton Jones, Simon, Gordon, Andrew & Finne, Sigbjorn. (1996) Concurrent Haskell. In Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'96). New York: ACM Press, pp. 295–308.Google Scholar
Peyton Jones, Simon, Reid, Alastair, Henderson, Fergus, Hoare, Tony & Marlow, Simon. (1999) A semantics for imprecise exceptions. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'99). New York: ACM Press, pp. 25–36.CrossRefGoogle Scholar
Peyton Jones, Simon, & Wadler, Philip. (1993) Imperative functional programming. In Proceedings of the 20th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'93). New York: ACM Press, pp. 71–84.Google Scholar
Pike, Rob. (1989) A concurrent window system. Comput. Syst. 2 (2), 133–153.Google Scholar
Reppy, John. (1999) Concurrent Programming in ML. Cambridge, UK: Cambridge University Press.Google Scholar
Ringenburg, Michael F. & Grossman, Dan. (2005) AtomCaml: First-class atomicity via rollback. In Proceedings of the Tenth ACM SIGPLAN International Conference on Functional Programming (ICFP'05). New York: ACM Press, pp. 92–104.Google Scholar
Russell, George. (2001) Events in Haskell, and how to implement them. In Proceedings of the Sixth ACM SIGPLAN International Conference on Functional Programming (ICFP'01). New York: ACM Press, pp. 157–168.Google Scholar
Sangiorgi, David & Walker, David. (2001) The π-Calculus: A Theory of Mobile Processes. Cambridge, UK: Cambridge University Press.Google Scholar
Shavit, Nir & Touitou, Dan. (1997) Software transactional memory. Distribut. Comput. 10 (2), 99–116.CrossRefGoogle Scholar
Turbak, Franklyn. (1996) First-class synchronization barriers. In Proceedings of the First ACM SIGPLAN International Conference on Functional Programming (ICFP'96). New York: ACM Press, pp. 157–168.CrossRefGoogle Scholar
Wadler, Philip. (1995) Monads for functional programming. In Advanced Functional Programming, Jeuring, Johan & Meijer, Erik (eds). Lecture Notes in Computer Science, Vol. 925. New York: Springer-Verlag.Google Scholar
Welc, Adam, Jagannathan, Suresh & Hosking, Antony L. (2004) Transactional monitors for concurrent objects. In Proceedings of the Eighteenth European Conference on Object-Oriented Programming (ECOOP'04). Lecture Notes in Computer Science, Vol. 3086. New York: Springer-Verlag, pp. 519–542.Google Scholar
Ziarek, Lukasz, Schatz, Philip & Jagannathan, Suresh. (2006) Stabilizers: A modular checkpointing abstraction for concurrent functional programs. In Proceedings of the Eleventh ACM SIGPLAN International Conference on Functional Programming (ICFP'06). New York: ACM Press, pp. 136–147.Google Scholar
Supplementary material: File

Donnelly supplementary material

Donnelly supplementary material

Download Donnelly supplementary material(File)
File 121.6 KB
Supplementary material: PDF

Donnelly Supplementary Material

Appendix.pdf

Download Donnelly Supplementary Material(PDF)
PDF 189.3 KB
Submit a response

Discussions

No Discussions have been published for this article.