Algebraic Effect Handlers as a General Control flow mechanism

[TimWhiting]

Summary of issue:

This is a language feature request. What are the opinions of the leads about having a general control flow mechanism that is extensible by users? Delimited continuations is one approach - which were implemented for a time in #368. A more recent general control flow mechanism which provides a more structured and type safe approach to delimited continuations is Algebraic Effects. Are the leads familiar with work on Algebraic Effects, and what are the opinions about using algebraic effects to implement general control flow mechanisms?

Algebraic Effect Handlers are a general control flow mechanism, which unifies many different control flow operators, and makes control flow more user extensible. They allow users to define async / await, coroutines / schedulers, exceptions, generators, etc in a typed and composable way that can be efficiently compiled. While they were born out of functional language research, there are libraries showing their use in languages such as Scala, C++, and even C library.

Details:

Pros:

• It allows coroutine schedulers to be customizable by users rather than being built into the language
• It requires only implementing one control flow abstraction (i.e. a lot less compiler work & more theoretically sound - this keeps the language implementation more clean and fewer edge cases)
• Other control flow constructs can be parts of the standard library or user libraries (users don't have to wait for each different control construct to be implemented separately in the compiler and not as flexibly as they might want it, or suffer from unintended bad interactions with other control flow constructs).
• Issue Open design idea: implicit scoped function parameters #1974, and potentially others could be subsumed by this
• Machine learning algorithms including backprop and automatic differentiation can be defined using algebraic effects
• Algebraic effects can be used for other scientific computing such as probabilistic computing and simulation
• They can be used for sharing data in a parallel computation, fusion of iterator loops, reasoning about capabilities and effects of functions, event stream / asynchronous reactive programming. I can add paper links to these, but here is a general bibliography of research on this topic https://github.com/yallop/effects-bibliography. A general google scholar search should also turn up a lot of results.
• Optimizations for specific patterns can be applied across the board instead of implemented for each control flow mechanism independently

Cons:

• Type systems for tracking algebraic effects have not completely been agreed upon in PL research (but tracking effects is necessary for reasons of safety and not having undefined behavior)
• There is some minimal overhead (but no more than implicit parameters Open design idea: implicit scoped function parameters #1974), and not to functions that choose not to use it. - The overhead is likely no more than implementing the aforementioned control flow constructs without it, and research is heavily focused on making more progress in this area.
• This gives a lot of power to the user to create confusing non-local control flow. However, with a type system, there is at least some visual indication of potential side effects (more than you get for side effects / control flow regularly in C++)
• There is a difference between what are called deep versus shallow handlers, it is general consensus that it is possible to implement deep handlers more efficiently than shallow handlers, but it is not clear which is better for a language to have, some languages include both, some just deep, and some shallow. Most uses mentioned above can be implemented on either.
• It introduces a sort of dynamic scope, that is lexically apparent (with effect types), it can be argued that dynamic scope would already be present with Open design idea: implicit scoped function parameters #1974, and exceptions are sort of a dynamic scope mechanism. This would just be a generalization of both of those features, but it should be used wisely and not overdone. A disciplined approach to working with effect handlers has not been identified, but there is research into more lexically apparent approaches.
• Most research on asynchronous / coroutines assumes a scheduling loop, associating effects with true interrupts is only addressed in a few papers.

Any other information that you want to share?

Further Information:
A good overview in one research language can be found here. There are different approaches to type systems, but I think possibly the C++ library linked at the top of the issue could be one place to draw inspiration for including this feature in a language that isn't 'purely functional'.

Implementation:
They can be built on top of delimited continuations which were added to the Carbon interpreter here (#368.), but there are more efficient ways of implementing them as well: google scholar link to papers - Specifically I'd recommend looking at Generalized evidence passing for effect handlers: efficient compilation of effect handlers to C.

[geoffromer]

Can you be more specific about what question you want the leads to resolve, or what decision you want them to make?

[TimWhiting]

I updated the first paragraph to be an explicit question.

[clavin]

(Aside: Happy to see another Utahn popping their head up in this project! And I was looking into Koka just months ago too! Greetings from SLC 🙂)

I'm not a lead here, but in the project milestones document the features involving effects are explicitly deferred until later in Carbon's development:

Features explicitly deferred until at least 0.2

• ...
• Coroutines, async, generators, etc.
• Comprehensive story for handling effects, and how functions can be generic across effects

(Emphasis mine.)

Granted, there is no explicit mention of user-defined effects or a full effects system. Still, these milestones were drafted by the leads, so I take it that they're aware of the problem space. This excerpt also indicates that effects are, at most, low priority at the moment (deferred to the 0.2 milestone), thus it may be a while before this problem space gets adequate attention in Carbon.

To bring up an example of effects in other languages for discussion, OCaml 5.0 recently released with runtime support for effects. At present, there is no syntax associated with effects in OCaml. It may be sufficient for Carbon to follow this route, providing the machinery but not necessarily any syntax, even if just for a phase of the design of effects. This approach is similar to the C++ library referenced in the OP.

I'd also like to point out that many of the references in the OP involve Daan Leijen (github profile), a researcher currently at Microsoft Research.

For anyone unfamiliar, Daan Leijen has contributed numerous research papers on the topic of algebraic effects (among others) and has a strong background in Programming Language Design, Type Systems, and Effect Typing. Prominently, Daan has contributed the research language Koka, which features effect types and handlers (among other impressive language features). I wouldn't be surprised if the leads already know of Daan and/or their work! 😁

---

To add my own commentary:

Playing with Koka, I found the effects system to be very intuitive and simple to use. I would love to see user-defined effects make their way into Carbon's design, but I will admit I have no idea what that design or proposal would look like in practice.

I feel like algebraic effects are still in their "research language" phase, which makes it tough for me to currently see how they'd fit into a language like Carbon that, similar to C++, wants to be very practical. Working with effects is a little bit of a paradigm shift, and it's not one that I've personally wrapped my head fully around yet. It doesn't help that effects don't have mainstream patterns and well-known usages yet. I can only hope this gets better with time, especially as Carbon develops past 0.1 and is able to address this problem space with more resources and knowledge. 🤞

(Fun fact: Daan Leijen is one of the authors of the popular Haskell parser combinator library, Parsec.)