A lowering strategy for control effects in Rust(abubalay.com)
abubalay.com
A lowering strategy for control effects in Rust
https://www.abubalay.com/blog/2024/01/14/rust-effect-lowering
2 comments
> many complex abstractions like generators, async/await, error propagation, injected context, etc can all be built on a simple extensible language primitive.
I have conflicting feelings about this. On the one hand, it feels like call/cc all over again (a "simple" language primitive that can express devilishly complex control flow) that a lot of people would call a design mistake. The fact you can implement complex abstractions with a small primitive doesn't make the complex abstractions not complex for consumers of the API.
On the other hand, it's not call/cc and lets you do complex things with a decent amount of modularity.
But I also don't buy into the argument that implementing such foundational primitives like control flow in library code is good (I use async Rust every day, and it sucks how much has been pawned off to the ecosystem, please don't reply to this comment telling me how wrong I am). Even if you can implement these things in the ecosystem doesn't mean you should - it leads to bifurcations in the wild where libraries become incompatible because they aren't working with the same tools. The very thing that makes programming a force multiplier is modularity and reuse, making those harder by making a language too expressive makes that language worse, imo.
And all that said, the biggest knock that I have against algebraic effects is I haven't seen a compelling argument why they can't be replaced with coroutines which are well understood and don't require much magic to implement.
I have conflicting feelings about this. On the one hand, it feels like call/cc all over again (a "simple" language primitive that can express devilishly complex control flow) that a lot of people would call a design mistake. The fact you can implement complex abstractions with a small primitive doesn't make the complex abstractions not complex for consumers of the API.
On the other hand, it's not call/cc and lets you do complex things with a decent amount of modularity.
But I also don't buy into the argument that implementing such foundational primitives like control flow in library code is good (I use async Rust every day, and it sucks how much has been pawned off to the ecosystem, please don't reply to this comment telling me how wrong I am). Even if you can implement these things in the ecosystem doesn't mean you should - it leads to bifurcations in the wild where libraries become incompatible because they aren't working with the same tools. The very thing that makes programming a force multiplier is modularity and reuse, making those harder by making a language too expressive makes that language worse, imo.
And all that said, the biggest knock that I have against algebraic effects is I haven't seen a compelling argument why they can't be replaced with coroutines which are well understood and don't require much magic to implement.
The article is not suggesting that Rust should support arbitrary library-defined effects. It's suggesting that Rust's existing language-defined effects should be combined algebraically.
> the biggest knock that I have against algebraic effects is I haven't seen a compelling argument why they can't be replaced with coroutines which are well understood and don't require much magic to implement.
Rust's effects are already implemented as coroutines! Algebraic effects are a specific pattern for how those coroutines communicate, to make them more composable.
> the biggest knock that I have against algebraic effects is I haven't seen a compelling argument why they can't be replaced with coroutines which are well understood and don't require much magic to implement.
Rust's effects are already implemented as coroutines! Algebraic effects are a specific pattern for how those coroutines communicate, to make them more composable.
I'm replying to the comment on algebraic effects more than the article.
> But I also don't buy into the argument that implementing such foundational primitives like control flow in library code is good (I use async Rust every day, and it sucks how much has been pawned off to the ecosystem, please don't reply to this comment telling me how wrong I am). Even if you can implement these things in the ecosystem doesn't mean you should - it leads to bifurcations in the wild where libraries become incompatible because they aren't working with the same tools. The very thing that makes programming a force multiplier is modularity and reuse, making those harder by making a language too expressive makes that language worse, imo.
That seems pretty backwards to me. Being able to implement flow control as regular functions increases modularity and reuse a lot, not least because it makes it easy to abstract across async or not. IMO the biggest reason async Rust is so painful is precisely because control flow is a bunch of special case magic builtins that you can't share or reuse (e.g. you can't use regular if/while/for with async, and you can't write your own equivalents (like Haskell's ifM/whileM) because the language doesn't provide the tools you'd need to do that).
That seems pretty backwards to me. Being able to implement flow control as regular functions increases modularity and reuse a lot, not least because it makes it easy to abstract across async or not. IMO the biggest reason async Rust is so painful is precisely because control flow is a bunch of special case magic builtins that you can't share or reuse (e.g. you can't use regular if/while/for with async, and you can't write your own equivalents (like Haskell's ifM/whileM) because the language doesn't provide the tools you'd need to do that).
> you can't use regular if/while/for with async
What do you mean by this? You can certainly mix if/while/for freely with .await, that's the whole reason it exists.
What do you mean by this? You can certainly mix if/while/for freely with .await, that's the whole reason it exists.
Sorry, yes, what I meant was you can use builtin if/while/for, but they're magic special cases that you can't reuse. E.g. if you have a repeated snippet of code that uses if/while/for, you might have exactly the same code in one async and one regular function, but you can't factor it out into a shared helper function (you can write the async and the non-async version of that helper function, but you can't write one that does both).
I believe the distinction is that in rust, `if a_cond.await` can only be written in an async function, whereas Haskell’s `ifM` takes a `Monad Bool` (and async is a kind of monad) as its condition and therefore can be written anywhere, not just within an existing monad.
That's a distinction without a difference. `ifM` takes a monadic bool but it also returns a monadic value, in exactly the same way that `.await` can only be done within an async computation.
I thought coroutines don’t solve the function coloring problem considering we do have coroutines but combinatorial explosion due to function coloring is an issue. In other words, I need a try_async_map function if I want to support a map operation that has failability and async (as I need a duplicate try_map vs map to support just failability).
Whether this should be solved by a formal generic algebraic effects system or generic keywords is an open question but unless I’m mistaken this is a real problem that can’t be solved with coroutines.
The article also highlights an advantage for generic algebraic effects by reducing the cost of async code by not constructing the Waker until there’s a suspension point. I don’t understand the proposals well enough to know if generic keywords would solve this too, but it’s certainly worth considering.
I’m less bearish on new language mechanics if they solve a class of problems very consistently and improve efficiency. Complexity of usage is a concern vs something like generic keywords, but honestly self consistent mechanics like this might be less complex to master than generic keywords in the long run. There’s precedent here for example with macros which is a pretty complex subsystem but it’s carved out by experts providing libraries for the most part and I would expect similar behavior here where library code might be more complex in implementation but there’s no code duplication and the user code gets a simpler .map function usable in any context. There will also be plenty of copy-passable examples to learn from the std library APIs.
Whether this should be solved by a formal generic algebraic effects system or generic keywords is an open question but unless I’m mistaken this is a real problem that can’t be solved with coroutines.
The article also highlights an advantage for generic algebraic effects by reducing the cost of async code by not constructing the Waker until there’s a suspension point. I don’t understand the proposals well enough to know if generic keywords would solve this too, but it’s certainly worth considering.
I’m less bearish on new language mechanics if they solve a class of problems very consistently and improve efficiency. Complexity of usage is a concern vs something like generic keywords, but honestly self consistent mechanics like this might be less complex to master than generic keywords in the long run. There’s precedent here for example with macros which is a pretty complex subsystem but it’s carved out by experts providing libraries for the most part and I would expect similar behavior here where library code might be more complex in implementation but there’s no code duplication and the user code gets a simpler .map function usable in any context. There will also be plenty of copy-passable examples to learn from the std library APIs.
If you could spawn a coroutine and pass it around as a value, you could implement your effects just by calling coroutine.resume(...), coroutine.yield(...). The reason this is more powerful abstraction than async/await is that it's colorless - structs that could be sync or async just need a field that's Option<Coroutine> and when they want to be "effectful" they just do something like
I'm less compelled about code duplication for trivial stuff like try_async_map, whereas being able to duct tape together major libraries with a few lines of code internally is much more compelling. And solves real problems, the previous example is actually a problem faced in codebases today.
I can think of a few arguments against this, but I don't see it as structurally that different from algebraic effects.
if let Some(async) = self.async.as_mut() {
let next_arg = async.yield(next_result);
}
I'm less compelled about code duplication for trivial stuff like try_async_map, whereas being able to duct tape together major libraries with a few lines of code internally is much more compelling. And solves real problems, the previous example is actually a problem faced in codebases today.
I can think of a few arguments against this, but I don't see it as structurally that different from algebraic effects.
I agree that try_async_map is whatever, but currently if you want to call several fallible functions from different libraries and propagate the errors you get into a bit of a mess.
> The article also highlights an advantage for generic algebraic effects by reducing the cost of async code by not constructing the Waker until there’s a suspension point.
No, it doesn't. It highlights that as an advantage of one specific implementation style, while suggesting a different implementation for Rust.
No, it doesn't. It highlights that as an advantage of one specific implementation style, while suggesting a different implementation for Rust.
Lots of coroutine implementations solve this problem, see maybe Lua or greenlet or Byuu's libco. Shipping async as-is and delaying async-in-trait until 1 month ago was a deliberate choice to make all libraries less composable.
> But I also don't buy into the argument that implementing such foundational primitives like control flow in library code is good
Library code doesn't mean bespoke. Core and std are library code, and stuff can be migrated in there from the ecosystem whenever a truly best-in-class solution that won't be replaced anytime soon becomes apparent.
Library code doesn't mean bespoke. Core and std are library code, and stuff can be migrated in there from the ecosystem whenever a truly best-in-class solution that won't be replaced anytime soon becomes apparent.
Library code means every project has to choose which library they use. Smolstring or SmartString? Tokio or one of the others?
And then suddenly we have “colored” libraries. Does my http library work with the async runtime I’m using? How many arena allocator implementations does my package depend on and compile in?
The advantage of something being in core or std is that, because all libraries implicitly depend on it, there’s no choice to be made. String is available everywhere. Libraries pass Strings to each other all the time. Nobody is confused when String is in the public API.
> stuff can be migrated in there from the ecosystem whenever a truly best-in-class solution that won't be replaced anytime soon becomes apparent.
Rust has been remarkably conservative when it comes to adding stuff to std in the last few years. I think it would make sense at the very least to add an async executor and async syscalls to std. You shouldn’t need 3rd party libraries to async read from a file or network stream. Obviously it would be a hugely divisive choice but making no choice at all hurts users.
And then suddenly we have “colored” libraries. Does my http library work with the async runtime I’m using? How many arena allocator implementations does my package depend on and compile in?
The advantage of something being in core or std is that, because all libraries implicitly depend on it, there’s no choice to be made. String is available everywhere. Libraries pass Strings to each other all the time. Nobody is confused when String is in the public API.
> stuff can be migrated in there from the ecosystem whenever a truly best-in-class solution that won't be replaced anytime soon becomes apparent.
Rust has been remarkably conservative when it comes to adding stuff to std in the last few years. I think it would make sense at the very least to add an async executor and async syscalls to std. You shouldn’t need 3rd party libraries to async read from a file or network stream. Obviously it would be a hugely divisive choice but making no choice at all hurts users.
You are right. This situation played out (and still kinda is playing out) in Scala.
Yeah, the learning curve is there, but it has its benefits for software development.
Personally I really am enjoying the one implemented by Unison: https://www.unison-lang.org/docs/fundamentals/abilities/usin...
But Koka's was fun to play around with as well!
Personally I really am enjoying the one implemented by Unison: https://www.unison-lang.org/docs/fundamentals/abilities/usin...
But Koka's was fun to play around with as well!
You see something similar with CL and Clojure (but the latter to a lesser extent): these abstractions are so powerful that those that grok them are able to construct things that others have little chance of understanding without a significant investment in time (if at all). Go does more or less the opposite: it tries to avoid any kind of cleverness.
There’s no fundamental objection to requiring people to master difficult concepts in programming: see the ubiquity of the LeetCode Hard interview. Why then is this such a barrier to the adoption of functional programming and sophisticated type systems?
Because the benefit of the "smart" approach vs the "simple" approach is usually smaller than its cost.
The cost being: Having to hire especially talented developers and developers spending more time reading and understanding code. And there is the hard-to-measure but insidious aversion of software developers to work on code that will require effort to understand.
The cost being: Having to hire especially talented developers and developers spending more time reading and understanding code. And there is the hard-to-measure but insidious aversion of software developers to work on code that will require effort to understand.
Thing is, the "smart" approach can often be the simplest in the long term. What gets sold as "simple" to newcomers only adds technical debt which ultimately becomes even harder to survey and understand.
Because there are many alternatives that at first sight seem both easier to master and more productive. This results in perceived lower initial cost of development.
Nothing I've seen in any other language comes close to CLs condition system. It makes exceptions look like stone age technology.
Technically I'm sure you could do everything conditions do even in C with like setjmp/longjmp, but... good luck with that.
Technically I'm sure you could do everything conditions do even in C with like setjmp/longjmp, but... good luck with that.
You can implement resumable conditions using coroutine support. They're very comparable features.
True. It's so nice to just have them in the language though. Because then the whole library ecosystem is using the same abstraction, making it far more useful.
Fun fact: long ago, Rust had conditions!
Interesting. Why were they removed?
See https://github.com/rust-lang/rust/issues/9795 and the linked PR that removed them.
> let tps = if_ok!(self.tps(as_.tps, bs.tps));
Ha, that's how the question mark operator (and the previous encarnation, the `try!` macro) was born then :)
Ha, that's how the question mark operator (and the previous encarnation, the `try!` macro) was born then :)
> In practice I do wonder though if that much power won't make code very confusing to read and write, and if the general programmer should be trusted with that much flexibility.
This is not for ordinary code, it's for writing support libraries and DSL's. You need this stuff so that the "general programmer" can write code that's as straightforward as possible in its proper context.
This is not for ordinary code, it's for writing support libraries and DSL's. You need this stuff so that the "general programmer" can write code that's as straightforward as possible in its proper context.
On the very far end of the spectrum you will have something that may look a bit like mathematical notation. Something describing a relationship extremely concisely, but the hard thing will be figuring out what exactly follows from that concise expression.
I can understand how people could see the appeal in this, but I think this doesn't necessarily make it easier to write good software.
I can understand how people could see the appeal in this, but I think this doesn't necessarily make it easier to write good software.
I read this as "we have a set of effects we can layer" instead of "we build give the user the ability of make effects"
What about a more imperative shape? What if you could have a closure that "goto"s into the parent function scope?
Or imagine coroutines built with `swapcontext` (man 3).
Or imagine coroutines built with `swapcontext` (man 3).
Stackful fibers are an anti-pattern. See Gor Nishanov's review for the C++ ISO committee http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2018/p136... linked from https://devblogs.microsoft.com/oldnewthing/20191011-00/?p=10... . Notice how it sums things up:
> DO NOT USE FIBERS!
> DO NOT USE FIBERS!
Let's say that not everybody agrees. Also all the issues identified by Gor are due to retrofitting continuations into an existing language as a pure library without compiler help.
Can Gor Nishanov post one of his hand-made state machines that handles several nested protocols? Or does he believe that operating systems are good at scheduling work across 100,000 threads?
Huh? That might be exactly how "effect handlers" are implemented.
> Rust should learn from this work and skip the layering.
As someone who uses Haskell professionally, 100% agree. Monad transformers are an (unfortunate) solution to the problem of stacking effects, not only due to the required lifting (to pick the appropriate handler), but due to the lack of compositionality and rough UX for the developer. Algebraic effect libraries are a lot easier to use (but I cannot speak for how easy/hard are to implement).
As someone who uses Haskell professionally, 100% agree. Monad transformers are an (unfortunate) solution to the problem of stacking effects, not only due to the required lifting (to pick the appropriate handler), but due to the lack of compositionality and rough UX for the developer. Algebraic effect libraries are a lot easier to use (but I cannot speak for how easy/hard are to implement).
I'm fascinated with effect systems.
In theory they have the potential to make code both simpler and more powerful, because many complex abstractions like generators, async/await, error propagation, injected context, etc can all be built on a simple extensible language primitive.
The by far nicest implementation I've seen is Koka lang [1]. Unfortunately it's bound to be a small research language.
In practice I do wonder though if that much power won't make code very confusing to read and write, and if the general programmer should be trusted with that much flexibility.
For Rust specifically, I do wonder how generic effects could slot into a language that was not designed for them upfront, without compromising the design and DX.
[1] https://koka-lang.github.io/koka/doc/index.html