Dagstuhl Seminar 21292
Scalable Handling of Effects
( Jul 18 – Jul 23, 2021 )
- Danel Ahman (University of Ljubljana, SI)
- Amal Ahmed (Northeastern University - Boston, US)
- Sam Lindley (University of Edinburgh, GB)
- Andreas Rossberg (Dfinity - Zürich, CH)
- Michael Gerke (for scientific matters)
- Annette Beyer (for administrative matters)
Dagstuhl Seminar Wiki
- Dagstuhl Seminar Wiki (Use personal credentials as created in DOOR to log in)
Built on solid mathematical foundations, effect handlers offer a uniform and elegant approach to programming with user-defined computational effects. They subsume many widely used programming concepts and abstractions, such as actors, async/await, backtracking, coroutines, generators/iterators, and probabilistic programming. As such, they allow language implementers to target a single implementation of effect handlers, freeing language implementers from having to maintain separate ad hoc implementations of each of the features listed above.
Due to their wide applicability, effect handlers are enjoying growing interest in academia and industry. For instance, several effect handler oriented research languages are under active development (such as Eff, Frank, and Koka), as are effect handler libraries for mainstream languages (such as C and Java), effect handlers are seeing increasing use in probabilistic programming tools (such as Uber’s Pyro), and proposals are in the pipeline to include them natively in low-level languages (such as WebAssembly). Effect handlers are also a key part of Multicore OCaml, which incorporates an efficient implementation of them for uniformly expressing user-definable concurrency models in the language.
However, enabling effect handlers to scale requires tackling some hard problems, both in theory and in practice. Inspired by experience of developing, programming with, and reasoning about effect handlers in practice, we identify five key problem areas to be addressed at this Dagstuhl Seminar in order to enable effect handlers to scale: Safety, Modularity, Interoperability, Legibility, and Efficiency. In particular, we seek answers to the following questions:
- How can we enforce safe interaction between effect handler programs and external resources?
- How can we enable modular use of effect handlers for programming in the large?
- How can we support interoperable effect handler programs written in different languages?
- How can we write legible effect handler programs in a style accessible to mainstream programmers?
- How can we generate efficient code from effect handler programs?
Algebraic effects and effect handlers are currently enjoying significant interest in both academia and industry as a modular programming abstraction for expressing and incorporating user-defined computational effects in programming languages. For example, there are a number of effect handler oriented languages in development (such as Eff, Frank, and Koka); there exist effect handler libraries for mainstream languages (such as C and Java); effect handlers are a key part of languages such as Multicore OCaml (and indeed they are due to appear in the production release of OCaml next year); effect handlers are being increasingly used in statistical probabilistic programming (such as Uber's Pyro tool); and proposals are in the works to include effect handlers in new low-level languages (such as WebAssembly). While effect handlers have solid mathematical foundations and have been extensively experimented in prototype languages and on smaller examples, enabling effect handlers to scale still requires tackling some hard problems. To this end, this Dagstuhl Seminar 21292 "Scalable Handling of Effects" focused on addressing the following key problem areas for scalability: Safety, Modularity, Interoperability, Legibility, and Efficiency.
This seminar followed the earlier successful Dagstuhl Seminars 16112 "From Theory to Practice of Algebraic Effects and Handlers" and 18172 "Algebraic Effect Handlers go Mainstream", which were respectively dedicated to the foundations of algebraic effects and to the introduction of them into mainstream languages. In contrast to these previous two seminars which took place in person at Schloss Dagstuhl, the current seminar was organised fully online due to the SARS-CoV-2 pandemic. As the seminar was attended by participants from a wide range of time zones (ranging from the West coast of the US all the way to Japan), coming up with a schedule that was suitable for everybody was a challenge. In the end, we decided to have three scheduled two-hour sessions each day, with impromptu informal discussions also happening between-times. These sessions were: (i) 15:00-17:00 CEST, which were deemed the Core Hours, where all participants were most likely to be able to present; (ii) 10:00-12:00 CEST, which was most suitable for participants from Asia and Europe; and (iii) 17:30-19:30 CEST, which was most suitable for participants from America and Europe. The Core Hours included talks, breakouts, and discussions of interest to the widest audience, with more specialised talks and breakouts taking place in the other two daily scheduled blocks. Talks were recorded so that participants could catch up due to being in an incompatible time zone, then deleted at the end of the week.
In order to run a successful virtual Dagstuhl seminar we exploited several different technologies. For talks we used Zoom. For breakouts we used a combination of Zoom and Gather.town, and for asynchronous communication and further discussions we used Zulip. For scheduling purposes, we used the wiki page provided by Dagstuhl. We collected initial lists of proposed talks and breakout topics before the seminar began using an online form. We extended these throughout the week. We scheduled talks and breakout groups daily depending on audience interest and the participant availability. While the first part of the week was dominated by talks, the second part of the week saw more emphasis on breakouts and discussions. During Friday's Core Hours, the leaders of each breakout group presented a short overview of the discussions and results (11 reports in total). Initially, we were a little unsure about how well breakout sessions would work in a virtual seminar, but as the week went on they became more and more popular and they seemed to go remarkably well. Initially, we mostly used Gather.town and its virtual whiteboards for the breakout sessions. Subsequently, we transitioned to mostly using Zoom breakout rooms (partly because some people had difficulty using Gather.town on their systems).
The seminar was a great success, particularly given the constraints of the virtual format.
There were vibrant discussions around multishot continuations. These are vital for exciting new applications such as probabilistic programming and automatic differentiation, but more research is needed on how to implement them safely and efficiently in different contexts. Flipping perspective, it was mooted that for certain applications, particularly those involving direct interaction with the external world, it might be worthwhile restricting attention to runners, which are even more constrained than effect handlers with singleshot continuations.
There were several discussions relating to usability of effect handlers. These resulted in proposals to design a lecture course on effect handlers and to write a book on how to design effectful programs.
A major area of interest instigated at a prior Dagstuhl Seminar (18172 "Algebraic Effect Handlers go Mainstream") is the addition of effect handlers to WebAssembly. A design is being actively worked on as part of the official WebAssembly development process. At the current seminar we worked out extensions to the existing proposal to accommodate named effect handlers and symmetric stack-switching, both of which promise more efficient execution.
An issue with many existing benchmarks for effect handlers is that they often require installing a range of experimental software and configuring it with just the right settings. In order to make it easier to compare systems and share experimental setups we created the effect handlers benchmarks suite -- a repository of benchmarks and systems covering effects and handlers in various programming languages, based on Docker scripts that make it easy for anyone to run the benchmarks and adapt them for their own research. The repository is hosted on GitHub. Since the seminar, 5 systems have been added to the repository and it has been actively updated and maintained by different members of the community.
At the end of the week, there was strong interest among the participants to continue this successful seminar series and submit a proposal for another incarnation, hopefully possible to take place on site in about two years.
- Danel Ahman (University of Ljubljana, SI) [dblp]
- Amal Ahmed (Northeastern University - Boston, US) [dblp]
- Robert Atkey (University of Strathclyde - Glasgow, GB) [dblp]
- Andrej Bauer (University of Ljubljana, SI) [dblp]
- Oliver Bracevac (Purdue University - West Lafayette, US) [dblp]
- Jonathan Immanuel Brachthäuser (EPFL - Lausanne, CH) [dblp]
- Youyou Cong (Tokyo Institute of Technology, JP) [dblp]
- Paulo Emílio de Vilhena (INRIA - Paris, FR)
- Stephen Dolan (Jane Street - London, GB) [dblp]
- Ronald Garcia (University of British Columbia - Vancouver, CA) [dblp]
- April Gonçalves (Heliax - Glasgow, GB)
- Maria Gorinova (University of Edinburgh, GB) [dblp]
- Daniel Hillerström (University of Edinburgh, GB) [dblp]
- Mauro Jaskelioff (National University of Rosario, AR) [dblp]
- Ohad Kammar (University of Edinburgh, GB) [dblp]
- Oleg Kiselyov (Tohoku University - Sendai, JP) [dblp]
- Filip Koprivec (University of Ljubljana, SI)
- Daan Leijen (Microsoft Research - Redmond, US) [dblp]
- Sam Lindley (University of Edinburgh, GB) [dblp]
- Conor McBride (University of Strathclyde - Glasgow, GB) [dblp]
- Daniel Patterson (Northeastern University - Boston, US) [dblp]
- Maciej Piróg (University of Wroclaw, PL) [dblp]
- Gordon Plotkin (Google - Mountain View, US) [dblp]
- Matija Pretnar (University of Ljubljana, SI) [dblp]
- Aseem Rastogi (Microsoft Research India - Bangalore, IN) [dblp]
- Andreas Rossberg (Dfinity - Zürich, CH) [dblp]
- Philipp Schuster (Universität Tübingen, DE) [dblp]
- Taro Sekiyama (National Institute of Informatics - Tokyo, JP) [dblp]
- KC Sivaramakrishnan (Indian Institute of Techology, IN) [dblp]
- Antal Spector-Zabusky (Jane Street - London, GB)
- Nikhil Swamy (Microsoft Research - Redmond, US) [dblp]
- Wouter Swierstra (Utrecht University, NL) [dblp]
- Luke Wagner (Fastly - San Francisco, US) [dblp]
- Leo White (Jane Street - London, GB) [dblp]
- Nicolas Wu (Imperial College London, GB) [dblp]
- programming languages / compiler
- semantics / formal methods
- algebraic effects
- delimited control
- effect handlers
- type systems