Godot: All the Benefits of Implicit and Explicit Futures

Authors Kiko Fernandez-Reyes , Dave Clarke , Ludovic Henrio , Einar Broch Johnsen , Tobias Wrigstad



PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2019.2.pdf
  • Filesize: 0.91 MB
  • 28 pages

Document Identifiers

Author Details

Kiko Fernandez-Reyes
  • Uppsala University, Sweden
Dave Clarke
  • Storytel, Stockholm, Sweden
Ludovic Henrio
  • Univ Lyon, EnsL, UCBL, CNRS, Inria, LIP, France
Einar Broch Johnsen
  • University of Oslo, Norway
Tobias Wrigstad
  • Uppsala University, Sweden

Cite AsGet BibTex

Kiko Fernandez-Reyes, Dave Clarke, Ludovic Henrio, Einar Broch Johnsen, and Tobias Wrigstad. Godot: All the Benefits of Implicit and Explicit Futures. In 33rd European Conference on Object-Oriented Programming (ECOOP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 134, pp. 2:1-2:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ECOOP.2019.2

Abstract

Concurrent programs often make use of futures, handles to the results of asynchronous operations. Futures provide means to communicate not yet computed results, and simplify the implementation of operations that synchronise on the result of such asynchronous operations. Futures can be characterised as implicit or explicit, depending on the typing discipline used to type them. Current future implementations suffer from "future proliferation", either at the type-level or at run-time. The former adds future type wrappers, which hinders subtype polymorphism and exposes the client to the internal asynchronous communication architecture. The latter increases latency, by traversing nested future structures at run-time. Many languages suffer both kinds. Previous work offer partial solutions to the future proliferation problems; in this paper we show how these solutions can be integrated in an elegant and coherent way, which is more expressive than either system in isolation. We describe our proposal formally, and state and prove its key properties, in two related calculi, based on the two possible families of future constructs (data-flow futures and control-flow futures). The former relies on static type information to avoid unwanted future creation, and the latter uses an algebraic data type with dynamic checks. We also discuss how to implement our new system efficiently.

Subject Classification

ACM Subject Classification
  • Software and its engineering → Concurrency control
  • Software and its engineering → Concurrent programming languages
  • Software and its engineering → Concurrent programming structures
Keywords
  • Futures
  • Concurrency
  • Type Systems
  • Formal Semantics

Metrics

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

References

  1. Akka Futures. https://doc.akka.io/docs/akka/current/futures.html, 2019.
  2. Rx Extensions. http://reactivex.io/, 2019.
  3. Laurent Baduel, Françoise Baude, Denis Caromel, Arnaud Contes, Fabrice Huet, Matthieu Morel, and Romain Quilici. Programming, Composing, Deploying for the Grid, pages 205-229. Springer London, London, 2006. Google Scholar
  4. Henry G. Baker and Carl E. Hewitt. The Incremental Garbage Collection of Processes. In Proc. Symposium on Artificial Intelligence Programming Languages, number 12 in SIGPLAN Notices, page 11, August 1977. Google Scholar
  5. Samuel Beckett. Waiting for Godot. Samuel Beckett: The Complete Dramatic Works, pages 7-89, 1954. Google Scholar
  6. Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, and Yuli Zhou. Cilk: An Efficient Multithreaded Runtime System. J. Parallel Distrib. Comput., 37(1):55-69, 1996. URL: http://dx.doi.org/10.1006/jpdc.1996.0107.
  7. Stephan Brandauer, Elias Castegren, Dave Clarke, Kiko Fernandez-Reyes, Einar Broch Johnsen, Ka I Pun, Silvia Lizeth Tapia Tarifa, Tobias Wrigstad, and Albert Mingkun Yang. Parallel Objects for Multicores: A Glimpse at the Parallel Language Encore. In Advanced Lectures on Formal Methods for Multicore Programming - 15th Intl. School on Formal Methods for the Design of Computer, Communication, and Software Systems (SFM 2015), volume 9104 of Lecture Notes in Computer Science, pages 1-56. Springer, 2015. Google Scholar
  8. Denis Caromel, Ludovic Henrio, and Bernard Serpette. Asynchronous and deterministic objects. In Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 123-134. ACM Press, 2004. Google Scholar
  9. Elias Castegren, Dave Clarke, Kiko Fernandez-Reyes, Tobias Wrigstad, and Albert Mingkun Yang. Attached and Detached Closures in Actors. In Proc. 8th ACM SIGPLAN Intl. Workshop on Programming Based on Actors, Agents, and Decentralized Control, AGERE 2018, pages 54-61. ACM, 2018. URL: http://dx.doi.org/10.1145/3281366.3281371.
  10. Dave Clarke, Tobias Wrigstad, Johan Östlund, and Einar Broch Johnsen. Minimal Ownership for Active Objects. In G. Ramalingam, editor, Proc. 6th Asian Symposium on Programming Languages and Systems (APLAS 2008), volume 5356 of Lecture Notes in Computer Science, pages 139-154. Springer, 2008. Google Scholar
  11. Frank S. de Boer, Dave Clarke, and Einar Broch Johnsen. A complete guide to the future. In Proc. 16th European Symposium on Programming (ESOP'07), volume 4421 of Lecture Notes in Computer Science, pages 316-330. Springer, 2007. Google Scholar
  12. Frank S. de Boer, Vlad Serbanescu, Reiner Hähnle, Ludovic Henrio, Justine Rochas, Crystal Chang Din, Einar Broch Johnsen, Marjan Sirjani, Ehsan Khamespanah, Kiko Fernandez-Reyes, and Albert Mingkun Yang. A Survey of Active Object Languages. ACM Comput. Surv., 50(5):76:1-76:39, 2017. URL: http://dx.doi.org/10.1145/3122848.
  13. Kiko Fernandez-Reyes, Dave Clarke, Elias Castegren, and Huu-Phuc Vo. Forward to a Promising Future. In Giovanna Di Marzo Serugendo and Michele Loreti, editors, Proc. 20th IFIP WG 6.1 Intl. Conf. on Coordination Models and Languages (COORDINATION 2018), volume 10852 of Lecture Notes in Computer Science, pages 162-180. Springer, 2018. Google Scholar
  14. Kiko Fernandez-Reyes, Dave Clarke, and Daniel S. McCain. ParT: An asynchronous parallel abstraction for speculative pipeline computations. In Alberto Lluch-Lafuente and José Proença, editors, Proc. 18th IFIP WG 6.1 Intl. Conf. on Coordination Models and Languages (COORDINATION 2016), volume 9686 of Lecture Notes in Computer Science, pages 101-120. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-319-39519-7_7.
  15. Cormac Flanagan and Matthias Felleisen. The Semantics of future and an application. Journal of Functional Programming, 9(1):1-31, 1999. Google Scholar
  16. Elena Giachino, Ludovic Henrio, Cosimo Laneve, and Vincenzo Mastandrea. Actors may synchronize, safely! In PPDP 2016 18th International Symposium on Principles and Practice of Declarative Programming , Edinburgh, United Kingdom, September 2016. URL: https://hal.inria.fr/hal-01345315.
  17. Google. Listenable Future Explained. https://github.com/google/guava/wiki/ListenableFutureExplained, January 2018.
  18. Philipp Haller, Heather Miller, Aleksandar Prokopec, Viktor Klang, Roland Kuhn, and Vojin Jovanovic. Futures and Promises. http://docs.scala-lang.org/overviews/core/futures.html, 2016. Google Scholar
  19. Phillip Haller and Martin Odersky. Scala actors: Unifying thread-based and event-based programming. Theoretical Computer Science, 410(2-3):202-220, 2009. Google Scholar
  20. Ludovic Henrio. Data-flow Explicit Futures. Research report, I3S, Université Côte d'Azur, April 2018. URL: https://hal.archives-ouvertes.fr/hal-01758734.
  21. Ludovic Henrio and Justine Rochas. Multiactive objects and their applications. Logical Methods in Computer Science, Volume 13, Issue 4, November 2017. URL: http://dx.doi.org/10.23638/LMCS-13(4:12)2017.
  22. Einar Broch Johnsen, Reiner Hähnle, Jan Schäfer, Rudolf Schlatte, and Martin Steffen. ABS: A core language for abstract behavioral specification. In Bernhard Aichernig, Frank S. de Boer, and Marcello M. Bonsangue, editors, Proc. 9th Intl. Symp. on Formal Methods for Components and Objects (FMCO), volume 6957 of Lecture Notes in Computer Science, pages 142-164. Springer Verlag, 2011. Google Scholar
  23. Einar Broch Johnsen, Olaf Owe, and Ingrid Chieh Yu. Creol: A type-safe object-oriented model for distributed concurrent systems. Theor. Comput. Sci., 365(1-2):23-66, 2006. URL: http://dx.doi.org/10.1016/j.tcs.2006.07.031.
  24. Simon Peyton Jones. Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press, 2003. Google Scholar
  25. Robert H. Halstead Jr. MultiLisp: A language for concurrent symbolic computation. ACM Trans. Program. Lang. Syst., 7(4):501-538, 1985. URL: http://dx.doi.org/10.1145/4472.4478.
  26. R. Greg Lavender and Douglas C. Schmidt. Active Object: an Object Behavioral Pattern for Concurrent Programming. Proc. Pattern Languages of Programs, 1995. Google Scholar
  27. Barbara Liskov and Liuba Shrira. Promises: Linguistic Support for Efficient Asynchronous Procedure Calls in Distributed Systems. In Richard L. Wexelblat, editor, Proceedings of the ACM SIGPLAN'88 Conference on Programming Language Design and Implementation (PLDI), Atlanta, Georgia, USA, June 22-24, 1988, pages 260-267. ACM, 1988. URL: http://dx.doi.org/10.1145/53990.54016.
  28. Magnus Madsen, Ondrej Lhoták, and Frank Tip. A model for reasoning about JavaScript promises. PACMPL, 1(OOPSLA):86:1-86:24, 2017. URL: http://dx.doi.org/10.1145/3133910.
  29. Joachim Niehren, Jan Schwinghammer, and Gert Smolka. A Concurrent Lambda Calculus with Futures. Theoretical Computer Science, 364(3):338-356, November 2006. Google Scholar
  30. Oscar Nierstrasz. Active Objects in Hybrid. In Norman K. Meyrowitz, editor, Proc. Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'87), pages 243-253. ACM, 1987. Google Scholar
  31. Martin Odersky, Lex Spoon, and Bill Venners. Programming in Scala. Artima Inc, 2008. Google Scholar
  32. Oracle. JDK 10 for java.util.concurrent.Future. https://docs.oracle.com/javase/10/docs/api/index.html?java/util/concurrent/Future.html, 2018.
  33. Benjamin C. Pierce. Types and Programming Languages. The MIT Press, 1st edition, 2002. Google Scholar
  34. John H. Reppy. Concurrent Programming in ML. Cambridge University Press, 1999. Google Scholar
  35. Andreas Rossberg, Didier Le Botlan, Guido Tack, Thorsten Brunklaus, and Gert Smolka. Alice Through the Looking Glass, volume 5 of Trends in Functional Programming, pages 79-96. Intellect Books, Bristol, UK, ISBN 1-84150144-1, Munich, Germany, February 2006. Google Scholar
  36. Jan Schafer and Arnd Poetzsch-Heffter. JCoBox: Generalizing active objects to concurrent components. ECOOP 2010-Object-Oriented Programming, pages 275-299, 2010. Google Scholar
  37. Kenjiro Taura, Satoshi Matsuoka, and Akinori Yonezawa. ABCL/f: A future-based polymorphic typed concurrent object-oriented language - its design and implementation. In Proceedings of the DIMACS workshop on Specification of Parallel Algorithms, pages 275-292. American Mathematical Society, 1994. Google Scholar
  38. Peter Van Roy and Seif Haridi. Concepts, Techniques, and Models of Computer Programming. MIT Press, March 2004. Google Scholar
  39. Adam Welc, Suresh Jagannathan, and Antony Hosking. Safe futures for Java. In Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications (OOPSLA'05), pages 439-453, New York, NY, USA, 2005. ACM Press. Google Scholar
  40. Andrew K. Wright and Matthias Felleisen. A Syntactic Approach to Type Soundness. Inf. Comput., 115(1):38-94, 1994. URL: http://dx.doi.org/10.1006/inco.1994.1093.
  41. Derek Wyatt. Akka Concurrency. Artima, 2013. Google Scholar
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