Dagstuhl Seminar 18172
Algebraic Effect Handlers go Mainstream
( Apr 22 – Apr 27, 2018 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/18172
Organizers
- Daan Leijen (Microsoft Research - Redmond, US)
- Matija Pretnar (University of Ljubljana, SI)
- Tom Schrijvers (KU Leuven, BE)
- KC Sivaramakrishnan (University of Cambridge, GB)
Contact
- Michael Gerke (for scientific matters)
- Susanne Bach-Bernhard (for administrative matters)
Impacts
- Faster Coroutine Pipelines : A Reconstruction : article in International Symposium on Practical Aspects of Declarative Languages, PADL 2019 : LNCS 11372 - Pieters, Ruben P.; Schrijvers, Tom - Berlin : Springer, 2019. - pp 133-149.
- Syntax and Semantics for Operations with Scopes : article in LICS '18 : Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science - Pirog, Maciej; Schrijvers, Tom; Wu, Nicolas; Jaskelioff, Mauro - New York : ACM, 2018. - Pages 809-818.
Languages like C#, C++, or JavaScript support complex control flow statements like exception handling, iterators (yield), and even asynchrony (asyncawait) through special extensions. For exceptions, the runtime needs to be extended with exception handling stack frames. For iterators and asynchrony, the situation is more involved, as the compiler needs to turn regular code into stack restoring state machines. Furthermore, these features need to interact as expected, e.g. finally blocks must not be forgotten in the state machines for iterators. And all of this work needs to be done again for the next control flow abstraction that comes along.
Or we can use algebraic effect handlers! This single mechanism generalizes all the control flow abstractions listed above and more, composes freely, has simple operational semantics, and can be efficiently compiled, since there is just one mechanism that needs to be supported well. Handlers allow programmers to keep the code in direct-style, which is easy to reason about, and empower library writers to implement various high-level abstractions without special extensions.
The idea of algebraic effects handlers has already been experimented with in the form of small research languages and libraries in several mainstream languages, including OCaml, Haskell, Clojure, and Scala. The next step, and the aim of this seminar, is to seriously consider adoption by mainstream languages including both functional languages such as OCaml or Haskell, as well as languages like JavaScript and the JVM and .NET ecosystems.
Topics of the seminar will include:
- Presenting ways algebraic effect handlers solve current issues and express legacy abstractions in mainstream programming languages.
- Discussing ways of introducing handlers into existing mainstream languages and ecosystems that have grown around them, and exploring ways of presenting handlers to the programmer.
- Analysing issues that have surfaced in initial prototypes such as interaction with other language features, runtime performance, or concurrent execution, and surveying recent theoretical developments.
- Showcasing programs such as a high performance web server or a user interface library, which illustrate the benefit of handler-oriented architecture.
Creative Commons BY 3.0 DE
Daan Leijen, Matija Pretnar, Tom Schrijvers, and KC Sivaramakrishnan
Algebraic effects and their handlers have been steadily gaining attention as a programming language feature for composably expressing user-defined computational effects. Algebraic effect handlers generalise many control-flow abstractions such as exception handling, iterators, async/await, or backtracking, and in turn allow them to be expressed as libraries rather than implementing them as primitives as many language implementations do. While several prototype languages that incorporate effect handlers exist, they have not yet been adopted into mainstream languages. This Dagstuhl Seminar 18172 "Algebraic Effect Handlers Go Mainstrea" touched upon various topics that hinder adoption into mainstream languages. To this end, the participants in this seminar included a healthy mix of academics who study algebraic effects and handlers, and developers of mainstream languages such as Haskell, OCaml, Scala, WebAssembly, and Hack.
This seminar follows the earlier, wildly successful Dagstuhl Seminar 16112 "From Theory to Practice of Algebraic Effects and Handlers" which was dedicated to addressing fundamental issues in the theory and practice of algebraic effect handlers. We adopted a similar structure for this seminar. We had talks each day in the morning, scheduled a few days ahead. The folks from the industry were invited to present their perspectives on some of the challenges that could potentially be address with the help of effect handlers. The afternoons were left free for working in self-organised groups and show-and-tell sessions with results from the previous days. We also had impromptu lectures on the origins of algebraic effects and handlers, which were quite well received and one of the highlights of the seminar.
Between the lectures and working-in-groups, the afternoons were rather full. Hence, a few participants offered after-dinner "cheesy talks" just after the cheese was served in the evening. The participants were treated to entertaining talks over delightful cheese and fine wine. We encourage the organisers to leave part of the day unplanned and go with what the participants feel like doing on that day. The serendipitous success are what makes Dagstuhl Seminars special.
We are delighted with the outcome of the seminar. There were interesting discussions around the problem of encapsulation and leaking of effects in certain higher order use cases, with several promising solutions discussed. It was identified that the problem of encapsulation and leaking effect names is analogous to the name binding in lambda calculus. Another group made significant progress in extending WebAssembly with support for effect handlers. The proposal builds on top of support for exceptions in WebAssembly. During the seminar week, the syntax extensions and operational semantics were worked out, with work begun on the reference implementation. During the seminar, Andrej Bauer pointed out that several prototype implementations that incorporate effect handlers exist, each with their own syntax and semantics. This makes it difficult to translate ideas across different research groups. Hence, Andrej proposed and initiated effects and handlers rosetta stone - a repository of examples demonstrating programming with effects and handlers in various programming languages. This repository is hosted on GitHub and has had several contributions during and after the seminar.
In conclusion, the seminar inspired discussions and brought to light the challenges in incorporating effect handlers in mainstream languages. During the previous seminar (16112), the discussions were centered around whether it was even possible to incorporate effect handlers into mainstream languages. During this seminar, the discussions were mainly on the ergonomics of effect handlers in mainstream languages. This is a testament to the success of the Dagstuhl Seminars in fostering cutting edge research.
Sivaramakrishnan Krishnamoorthy Chandrasekaran, Daan Leijen, Matija Pretnar, and Tom Schrijvers
- Amal Ahmed (Northeastern University - Boston, US) [dblp]
- Robert Atkey (University of Strathclyde - Glasgow, GB) [dblp]
- Lennart Augustsson (X Inc - Mountain View, US) [dblp]
- Andrej Bauer (University of Ljubljana, SI) [dblp]
- Oliver Bracevac (TU Darmstadt, DE) [dblp]
- Jonathan Immanuel Brachthäuser (Universität Tübingen, DE) [dblp]
- Edwin Brady (University of St Andrews, GB) [dblp]
- Stephen Dolan (University of Cambridge, GB) [dblp]
- Jeremy Gibbons (University of Oxford, GB) [dblp]
- Daniel Hillerström (University of Edinburgh, GB) [dblp]
- Mauro Jaskelioff (National University of Rosario, AR) [dblp]
- Ohad Kammar (University of Oxford, GB) [dblp]
- Andrew Kennedy (Facebook - London, GB) [dblp]
- Oleg Kiselyov (Tohoku University - Sendai, JP) [dblp]
- Daan Leijen (Microsoft Research - Redmond, US) [dblp]
- Sam Lindley (University of Edinburgh, GB) [dblp]
- Andres Löh (Well-Typed LLP, DE) [dblp]
- Ziga Luksic (University of Ljubljana, SI) [dblp]
- Anil Madhavapeddy (Docker Inc. - Cambridge, GB) [dblp]
- Conor McBride (University of Strathclyde - Glasgow, GB) [dblp]
- Adriaan Moors (Lightbend Inc. - San Francisco, CH) [dblp]
- Matija Pretnar (University of Ljubljana, SI) [dblp]
- Andreas Rossberg (Dfinity Foundation, CH) [dblp]
- Tom Schrijvers (KU Leuven, BE) [dblp]
- KC Sivaramakrishnan (University of Cambridge, GB) [dblp]
- Perdita Stevens (University of Edinburgh, GB) [dblp]
- Wouter Swierstra (Utrecht University, NL) [dblp]
- Leo White (Jane Street - London, GB) [dblp]
- Nicolas Wu (University of Bristol, GB) [dblp]
- Jeremy Yallop (University of Cambridge, GB) [dblp]
Related Seminars
Classification
- programming languages / compiler
- semantics / formal methods
Keywords
- algebraic effect handlers
- implementation techniques
- programming languages
- programming abstractions
