Document Open Access Logo

Theory and Practice of Coroutines with Snapshots

Authors Aleksandar Prokopec , Fengyun Liu

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2018.3.pdf
  • Filesize: 0.73 MB
  • 32 pages

Document Identifiers

Author Details

Aleksandar Prokopec
  • Oracle Labs, Zürich, Switzerland
Fengyun Liu
  • École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland

Cite AsGet BibTex

Aleksandar Prokopec and Fengyun Liu. Theory and Practice of Coroutines with Snapshots. In 32nd European Conference on Object-Oriented Programming (ECOOP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 109, pp. 3:1-3:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ECOOP.2018.3

Abstract

While event-driven programming is a widespread model for asynchronous computing, its inherent control flow fragmentation makes event-driven programs notoriously difficult to understand and maintain. Coroutines are a general control flow construct that can eliminate control flow fragmentation. However, coroutines are still missing in many popular languages. This gap is partly caused by the difficulties of supporting suspendable computations in the language runtime. We introduce first-class, type-safe, stackful coroutines with snapshots, which unify many variants of suspendable computing. Our design relies solely on the static metaprogramming support of the host language, without modifying the language implementation or the runtime. We also develop a formal model for type-safe, stackful and delimited coroutines, and we prove the respective safety properties. We show that the model is sufficiently general to express iterators, single-assignment variables, async-await, actors, event streams, backtracking, symmetric coroutines and continuations. Performance evaluations reveal that the proposed metaprogramming-based approach has a decent performance, with workload-dependent overheads of 1.03-2.11 x compared to equivalent manually written code, and improvements of up to 6 x compared to other approaches.

Subject Classification

ACM Subject Classification
  • Software and its engineering → Coroutines
  • Software and its engineering → Control structures
Keywords
  • coroutines
  • continuations
  • coroutine snapshots
  • asynchronous programming
  • inversion of control
  • event-driven programming

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Akka. Akka documentation, 2011. http://akka.io/docs/. Google Scholar
  2. Konrad Anton and Peter Thiemann. Towards Deriving Type Systems and Implementations for Coroutines, pages 63-79. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010. URL: http://dx.doi.org/10.1007/978-3-642-17164-2_6.
  3. Kenichi Asai and Chihiro Uehara. Selective cps transformation for shift and reset. In Proceedings of the ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, PEPM '18, pages 40-52, New York, NY, USA, 2018. ACM. URL: http://dx.doi.org/10.1145/3162069.
  4. V. Beltran, D. Carrera, J. Torres, and E. Ayguade. Evaluating the scalability of java event-driven web servers. In International Conference on Parallel Processing, 2004. ICPP 2004., pages 134-142 vol.1, Aug 2004. URL: http://dx.doi.org/10.1109/ICPP.2004.1327913.
  5. Gérard Berry and Georges Gonthier. The ESTEREL Synchronous Programming Language: Design, Semantics, Implementation. Sci. Comput. Program., 19(2):87-152, 1992. URL: http://dx.doi.org/10.1016/0167-6423(92)90005-V.
  6. G.M. Birtwhistle, O.J. Dahl, B. Myhrhaug, and K. Nygaard. Simula Begin. Chartwell-Bratt Ltd, 1979. Google Scholar
  7. Andrey Breslav. Coroutines for kotlin (revision 3.2), 2017. https://github.com/Kotlin/kotlin-coroutines/blob/master/kotlin-coroutines-informal.md. Google Scholar
  8. Carl Bruggeman, Oscar Waddell, and R. Kent Dybvig. Representing control in the presence of one-shot continuations. In Proceedings of the ACM SIGPLAN 1996 Conference on Programming Language Design and Implementation, PLDI '96, pages 99-107, New York, NY, USA, 1996. ACM. URL: http://dx.doi.org/10.1145/231379.231395.
  9. Eugene Burmako. Scala Macros: Let Our Powers Combine!: On How Rich Syntax and Static Types Work with Metaprogramming. In Proceedings of the 4th Workshop on Scala, SCALA '13, pages 3:1-3:10, New York, NY, USA, 2013. ACM. URL: http://dx.doi.org/10.1145/2489837.2489840.
  10. Mike Cantelon, Marc Harter, TJ Holowaychuk, and Nathan Rajlich. Node.Js in Action. Manning Publications Co., Greenwich, CT, USA, 1st edition, 2013. Google Scholar
  11. Melvin E. Conway. Design of a Separable Transition-Diagram Compiler. Commun. ACM, 6(7):396-408, 1963. URL: http://dx.doi.org/10.1145/366663.366704.
  12. Olivier Danvy and Andrzej Filinski. Abstracting Control. In Proceedings of the 1990 ACM Conference on LISP and Functional Programming, LFP '90, pages 151-160, New York, NY, USA, 1990. ACM. URL: http://dx.doi.org/10.1145/91556.91622.
  13. A. Lúcia de Moura, N. Rodriguez, and R. Ierusalimschy. Coroutines in Lua. Journal of Universal Computer Science, 10(7):910-925, July 2004. Google Scholar
  14. Iulian Dragos, Antonio Cunei, and Jan Vitek. Continuations in the Java Virtual Machine. In Second ECOOP Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems (ICOOOLPS'2007), Berlin, 2007. Technische Universität Berlin. Google Scholar
  15. Gregory Ewing. PEP 380 - Syntax for Delegating to a Subgenerator, 2009. https://www.python.org/dev/peps/pep-0380/. Google Scholar
  16. Mattias Felleisen. The theory and practice of first-class prompts. In Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '88, pages 180-190, New York, NY, USA, 1988. ACM. URL: http://dx.doi.org/10.1145/73560.73576.
  17. Jeffrey Fischer, Rupak Majumdar, and Todd Millstein. Tasks: Language support for event-driven programming. In Proceedings of the 2007 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-based Program Manipulation, PEPM '07, pages 134-143, New York, NY, USA, 2007. ACM. URL: http://dx.doi.org/10.1145/1244381.1244403.
  18. Richard P. Gabriel. The Design of Parallel Programming Languages. In Vladimir Lifschitz, editor, Artificial Intelligence and Mathematical Theory of Computation, pages 91-108. Academic Press Professional, Inc., San Diego, CA, USA, 1991. URL: http://dl.acm.org/citation.cfm?id=132218.132225.
  19. Andy Georges, Dries Buytaert, and Lieven Eeckhout. Statistically rigorous java performance evaluation. In Proceedings of the 22Nd Annual ACM SIGPLAN Conference on Object-oriented Programming Systems and Applications, OOPSLA '07, pages 57-76, New York, NY, USA, 2007. ACM. URL: http://dx.doi.org/10.1145/1297027.1297033.
  20. Philipp Haller and Heather Miller. RAY: Integrating Rx and Async for Direct-Style Reactive Streams. In Workshop on Reactivity, Events and Modularity, 2013. Google Scholar
  21. Philipp Haller and Martin Odersky. Scala actors: Unifying thread-based and event-based programming. Theor. Comput. Sci., 410(2-3):202-220, feb 2009. URL: http://dx.doi.org/10.1016/j.tcs.2008.09.019.
  22. Philipp Haller, Aleksandar Prokopec, Heather Miller, Viktor Klang, Roland Kuhn, and Vojin Jovanovic. Scala improvement proposal: Futures and promises. In SIP-14, 2012. URL: https://docs.scala-lang.org/sips/futures-promises.html.
  23. Philipp Haller and Jason Zaugg. Scala Async Repository, 2013. https://github.com/scala/async. Google Scholar
  24. Shams M. Imam and Vivek Sarkar. Savina - An Actor Benchmark Suite: Enabling Empirical Evaluation of Actor Libraries. In Proceedings of the 4th International Workshop on Programming Based on Actors Agents &Decentralized Control, AGERE! '14, pages 67-80, New York, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2687357.2687368.
  25. Jamboree. Co2: A c++ await/yield emulation library for stackless coroutine, 2017. URL: https://github.com/jamboree/co2.
  26. Ralph E. Johnson and Brian Foote. Designing reusable classes. Journal of Object-Oriented Programming, 1(2):22-35, June/July 1988. URL: http://www.laputan.org/drc.html.
  27. Oliver Kowalke. Coroutine2, 2017. URL: http://www.boost.org/doc/libs/1_66_0/libs/coroutine2.
  28. Charles E. Leiserson. Programming irregular parallel applications in Cilk, pages 61-71. Springer Berlin Heidelberg, Berlin, Heidelberg, 1997. URL: http://dx.doi.org/10.1007/3-540-63138-0_6.
  29. Barbara Liskov, Alan Snyder, Russell Atkinson, and Craig Schaffert. Abstraction Mechanisms in CLU. Commun. ACM, 20(8):564-576, aug 1977. URL: http://dx.doi.org/10.1145/359763.359789.
  30. Ingo Maier and Martin Odersky. Deprecating the Observer Pattern with Scala.react. Technical report, EPFL, 2012. Google Scholar
  31. A. Marzinotto, M. Colledanchise, C. Smith, and P. Ögren. Towards a Unified Behavior Trees Framework for Robot Control. In 2014 IEEE International Conference on Robotics and Automation (ICRA), pages 5420-5427, May 2014. URL: http://dx.doi.org/10.1109/ICRA.2014.6907656.
  32. Erik Meijer. Your Mouse is a Database. Commun. ACM, 55(5):66-73, may 2012. URL: http://dx.doi.org/10.1145/2160718.2160735.
  33. Ken Moody and Martin Richards. A coroutine mechanism for bcpl. Softw., Pract. Exper., 10(10):765-771, 1980. URL: http://dx.doi.org/10.1002/spe.4380101002.
  34. Ana Lúcia De Moura and Roberto Ierusalimschy. Revisiting Coroutines. ACM Trans. Program. Lang. Syst., 31(2):6:1-6:31, 2009. URL: http://dx.doi.org/10.1145/1462166.1462167.
  35. Lasse R. Nielsen and BRICS. A selective cps transformation. Electronic Notes in Theoretical Computer Science, 45:311-331, 2001. MFPS 2001,Seventeenth Conference on the Mathematical Foundations of Programming Semantics. URL: http://dx.doi.org/10.1016/S1571-0661(04)80969-1.
  36. Rickard Nilsson. ScalaCheck Website, 2010. https://www.scalacheck.org/. Google Scholar
  37. Martin Odersky, Philippe Altherr, Vincent Cremet, Burak Emir, Sebastian Maneth, Stéphane Micheloud, Nikolay Mihaylov, Michel Schinz, Erik Stenman, and Matthias Zenger. An Overview of the Scala Programming Language. Technical report, EPFL, 2004. Google Scholar
  38. Greg Pettyjohn, John Clements, Joe Marshall, Shriram Krishnamurthi, and Matthias Felleisen. Continuations from Generalized Stack Inspection. SIGPLAN Not., 40(9):216-227, sep 2005. URL: http://dx.doi.org/10.1145/1090189.1086393.
  39. Benjamin C. Pierce. Types and Programming Languages. MIT Press, Cambridge, MA, USA, 2002. Google Scholar
  40. A. Prokopec, D. Petrashko, and M. Odersky. Efficient lock-free work-stealing iterators for data-parallel collections. In 2015 23rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, pages 248-252, March 2015. URL: http://dx.doi.org/10.1109/PDP.2015.65.
  41. Aleksandar Prokopec. Data Structures and Algorithms for Data-Parallel Computing in a Managed Runtime. PhD thesis, IC, Lausanne, 2014. URL: http://dx.doi.org/10.5075/epfl-thesis-6264.
  42. Aleksandar Prokopec. Scalameter website, 2014. URL: http://scalameter.github.io.
  43. Aleksandar Prokopec. Pluggable scheduling for the reactor programming model. In Proceedings of the 6th International Workshop on Programming Based on Actors, Agents, and Decentralized Control, AGERE 2016, pages 41-50, New York, NY, USA, 2016. ACM. URL: http://dx.doi.org/10.1145/3001886.3001891.
  44. Aleksandar Prokopec. Scala Coroutines Website, 2016. https://storm-enroute/coroutines. Google Scholar
  45. Aleksandar Prokopec. Accelerating by idling: How speculative delays improve performance of message-oriented systems. In Francisco F. Rivera, Tomás F. Pena, and José C. Cabaleiro, editors, Euro-Par 2017: Parallel Processing, pages 177-191, Cham, 2017. Springer International Publishing. Google Scholar
  46. Aleksandar Prokopec. Encoding the building blocks of communication. In Proceedings of the 2017 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software, Onward! 2017, pages 104-118, New York, NY, USA, 2017. ACM. URL: http://dx.doi.org/10.1145/3133850.3133865.
  47. Aleksandar Prokopec. Reactors.io website, 2018. URL: http://reactors.io.
  48. Aleksandar Prokopec, Phil Bagwell, Tiark Rompf, and Martin Odersky. A generic parallel collection framework. In Proceedings of the 17th international conference on Parallel processing - Volume Part II, Euro-Par'11, pages 136-147, Berlin, Heidelberg, 2011. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=2033408.2033425.
  49. Aleksandar Prokopec, Philipp Haller, and Martin Odersky. Containers and aggregates, mutators and isolates for reactive programming. In Proceedings of the Fifth Annual Scala Workshop, SCALA '14, pages 51-61, New York, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2637647.2637656.
  50. Aleksandar Prokopec, David Leopoldseder, Gilles Duboscq, and Thomas Würthinger. Making collection operations optimal with aggressive JIT compilation. In Proceedings of the 8th ACM SIGPLAN International Symposium on Scala, SCALA 2017, pages 29-40, New York, NY, USA, 2017. ACM. URL: http://dx.doi.org/10.1145/3136000.3136002.
  51. Aleksandar Prokopec and Fengyun Liu. On the soundness of coroutines with snapshots. CoRR, abs/1806.01405, 2018. URL: http://arxiv.org/abs/1806.01405.
  52. Aleksandar Prokopec, Heather Miller, Philipp Haller, Tobias Schlatter, and Martin Odersky. FlowPools: A Lock-Free Deterministic Concurrent Dataflow Abstraction, Proofs. Technical report, EPFL, 2012. Google Scholar
  53. Aleksandar Prokopec, Heather Miller, Tobias Schlatter, Philipp Haller, and Martin Odersky. Flowpools: A lock-free deterministic concurrent dataflow abstraction. In LCPC, pages 158-173, 2012. URL: http://dx.doi.org/10.1007/978-3-642-37658-0_11.
  54. Aleksandar Prokopec and Martin Odersky. Isolates, Channels, and Event Streams for Composable Distributed Programming. In 2015 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (Onward!), Onward! 2015, pages 171-182, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2814228.2814245.
  55. Aleksandar Prokopec, Dmitry Petrashko, and Martin Odersky. On lock-free work-stealing iterators for parallel data structures. Technical report, EPFL, 2014. Google Scholar
  56. Tiark Rompf, Ingo Maier, and Martin Odersky. Implementing First-Class Polymorphic Delimited Continuations by a Type-Directed Selective CPS-Transform. SIGPLAN Not., 44(9):317-328, 2009. URL: http://dx.doi.org/10.1145/1631687.1596596.
  57. P. James Roshan and Amr Sabry. Yield: Mainstream delimited continuations, 2011. Google Scholar
  58. Neil Schemenauer, Tim Peters, and Magnus Hetland. PEP 255 - Simple Generators, 2001. https://www.python.org/dev/peps/pep-0255/. Google Scholar
  59. Tobias Schlatter, Aleksandar Prokopec, Heather Miller, Philipp Haller, and Martin Odersky. Multi-lane flowpools: A detailed look. Tech Report, 2012. Google Scholar
  60. Tatsurou Sekiguchi, Takahiro Sakamoto, and Akinori Yonezawa. Portable implementation of continuation operators in imperative languages by exception handling. In Advances in Exception Handling Techniques (the Book Grow out of a ECOOP 2000 Workshop), pages 217-233, London, UK, UK, 2001. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=647332.722736.
  61. Denys Shabalin, Eugene Burmako, and Martin Odersky. Quasiquotes for Scala. Technical report, EPFL, 2013. Google Scholar
  62. Lukas Stadler, Christian Wimmer, Thomas Würthinger, Hanspeter Mössenböck, and John Rose. Lazy continuations for java virtual machines. In Proceedings of the 7th International Conference on Principles and Practice of Programming in Java, PPPJ '09, pages 143-152, New York, NY, USA, 2009. ACM. URL: http://dx.doi.org/10.1145/1596655.1596679.
  63. Arvind K. Sujeeth, Tiark Rompf, Kevin J. Brown, HyoukJoong Lee, Hassan Chafi, Victoria Popic, Michael Wu, Aleksandar Prokopec, Vojin Jovanovic, Martin Odersky, and Kunle Olukotun. Composition and reuse with compiled domain-specific languages. In Proceedings of the 27th European Conference on Object-Oriented Programming, ECOOP'13, pages 52-78, Berlin, Heidelberg, 2013. Springer-Verlag. URL: http://dx.doi.org/10.1007/978-3-642-39038-8_3.
  64. Gerald Jay Sussman and Guy L. Steele, Jr. Scheme: A interpreter for extended lambda calculus. Higher Order Symbol. Comput., 11(4):405-439, 1998. URL: http://dx.doi.org/10.1023/A:1010035624696.
  65. Peter Van Roy and Seif Haridi. Concepts, Techniques, and Models of Computer Programming. The MIT Press, 1st edition, 2004. Google Scholar
  66. Robert Virding, Claes Wikström, and Mike Williams. Concurrent Programming in ERLANG (2nd Ed.). Prentice Hall International (UK) Ltd., Hertfordshire, UK, UK, 1996. Google Scholar
  67. Philip Wadler. Monads for Functional Programming. In Advanced Functional Programming, First International Spring School on Advanced Functional Programming Techniques-Tutorial Text, pages 24-52, London, UK, UK, 1995. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=647698.734146.
  68. N. Wirth. Programming in Modula-2. Texts and Monographs in Computer Science. Springer-Verlag, 1985. URL: https://books.google.ch/books?id=ZVaRXPrD1AoC.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact