Start of an effects system RFC (for async etc) - is there any interest in this?

[canndrew]

I’ve been kicking around some ideas for a while about what an effects system might look like. So I’ve written the start of an RFC here and I’m interested to get some feedback before I continue it. Is it readable? Does it make sense? What are the first questions that jump to mind when reading it?

[pythoneer]

I glanced over it and my first thoughts are that this is pretty huge and eventually needs to be splitted in multiple RFC’s

[leonardo]

This is a mostly off-topic comment that isn’t meant to show disrespect to your RFC

I find it curious that lot of people show interest in improving many high-level aspects of Rust, yet most people don’t show interest in improving the reliability and flexibility of the basic things I use in every Rust program: slices, arrays, integral values.

[canndrew]

@pythoneer Yeah, and most of it hasn’t been written yet. Which is why I’m wondering if it’s worth writing.

@leonardo The basic things are pretty well done to begin with. I do async programming everyday though so I’d like a better story around that, as well as a better story around global state in general.

[leonardo]

@leonardo The basic things are pretty well done to begin with.

I see, I’ll have to work to destroy that illusion

[HadrienG]

I think we could open a whole new topic about this matter. Maybe I will do that.

[aidanhs]

What are the first questions that jump to mind when reading it?

First: how do you design and implement these effects so they’re both general enough and specific enough to cover all use-cases? Traits (say Iterator) are reasonably specific so you can have some level of confidence that you have solved at least a subset of use-cases. With this, you’re trying to create an abstraction representing some arbitrary part of ‘a system’ so it’s harder to get right (perhaps some effects need a context arg for some functions), but like any trait it can be hard to modify.

Second: this seems like a subtle piece of global state that silently changes the behaviour of functions depending on the caller. I would be very surprised if there were no strange interactions here.

Third: how does this actually get implemented? Monomorphisation of every function per effect combination? Some global set of vtable pointers to indicate the current active effects (and so this affects closures based on call site rather than definition site)?

My overall impression is that the idea seems interesting (I’ve wanted something similar but with just being able to swap out one crate for a completely different one with the same interface) but very difficult to get right and I’d need to see a working implementation in another language ecosystem. Is there any background reading?

[Ixrec]

First, thank you for writing up this RFC. I have no background in “effect systems” or the kinds of languages where such things exist, but after reading that RFC draft I feel like I finally understand the general idea and motivation well enough to provide a coherent reply to it, rather than just asking “but what does any of that actually mean?” or “but how would any of this actually work?”

My type-fu is still not capable of a sophisticated reply, but I can at least manage a coherent one. So here are some of my knee-jerk and just-after-knee-jerk reactions to various parts of this proposal, without any serious attempt at reaching a conclusion:

• There’s an enormous risk of the perfect being the enemy of the good here
• Are any of today’s stable and unstable mechanisms for allocation, panicking, async I/O, and blocking I/O forward-compatible with this? What would it take to make them compatible?
• In a Rust-with-effect-systems world, when I want to write some code that prints to stdout, do I need to care about every possible implementation of Io? (including wacky only-theoretically-possible implementations like QuanumEntangledDistributedIo?) Would I have to fall back on the legacy explicitly-blocking or explicitly-threading APIs in order to allow myself to not care? Would we have to forbid such non-effect-polymorphic APIs in order to gain any of the benefits of this system? What if I’m not even writing I/O code myself but calling a bunch of libraries that happen to do I/O, and passing them handlers I don’t even know about that violate those libraries’ basic assumptions?
• The idea of automagically transforming synchronous I/O code into asynchronous I/O code terrifies me. I’ve introduced and fixed so many race conditions in Javascript code (N.B.: a single threaded event loop language) at work when manually changing blocking APIs to use promises that an Io effect abstracting over sync/async-ness sounds to me like a footgun of biblical proportions. I can understand the proposals to make await implicit, even if I dislike them, but the idea of making await implicit and conditional feels dangerously close to releasing Zalgo; maybe it’s not like that at all, but it’s not obvious that it’s not.
• Corollary to previous knee-jerk: That just happens to be the only example of an effect shift (???) that I’ve had the experience of doing manually. Are any of the other transformations similarly perilous? There must be some unsafe code out there which is abort-safe and not panic-safe, right?
• Even if this is amazing in practice, I have no idea how we’d begin to teach this sort of thing to Rustaceans. I’m the kind of person that reads Types and Programming Languages for fun, and I don’t even know how to investigate the answers to most of the other questions I’m asking in this list, much less concisely and intuitively justify those answers to a real working programmer that just wants to get their widgets frobnicated already. I only just managed to understand the motivation behind these ideas today.
• Corollary to previous knee-jerk: It seems like adding an effect system to Rust can only be a net benefit if we manage to preserve “incremental complexity”. By that I mean, I should be able to write “typical” sync I/O, async I/O, allocator, panic, etc code without understanding the underlying effect system; ideally without even seeing the syntax and terminology of effect systems come up at all. Is it possible to reimplement #[async]/await!() as sugar over effects? I assume we’d also need “default effect fallback” of some sort so that I can call my_sleeping_fn() without having to bring in effect blocks every single time? What if different libraries want different defaults for the same effects?

[Centril]

Some background reading.

• Algebraic effects in Idris (I believe this paper is most relevant), https://eb.host.cs.st-andrews.ac.uk/drafts/effects.pdf
  • Notably, Idris is dependently typed, while Rust is not (modulo const generics), which may severely limit the usefulness of an algebraic effects system compared to monad transformers.
• 1ML effects paper, https://people.mpi-sws.org/~rossberg/1ml/1ml-effects.pdf
• Polymorphic effect systems, http://groups.csail.mit.edu/pag/OLD/parg/lucassen88effects.pdf

---

An effect system is very appealing to me, but I think it needs some significant fleshing out.

You could also consider effects such as unsafe, trusted, impure (the inversion of const, i.e: normal functions), partial, panic. For example:

effect<A: ?const>
A fn foo<F>
    (arg: u8, bar: F) -> u8
where
    F: A Fn(u8) -> u8,
{
    bar(arg)
}

This quantifies an effect variable A which is possibly const but not necessarily. Then, if you call foo(0, alpha) with alpha : const Fn(u8) -> u8 , then foo(0, alpha) is const, however, if you pass alpha : Fn(u8) -> u8 then foo(0, alpha) is not const.

See https://github.com/rust-lang/rfcs/pull/2237#issuecomment-354569345 for a discussion of those kinds of effects.

[aturon]

I don’t have time to get deeply involved in this thread at the moment, but in general things like effect systems tend to come with a specific downside: they create a need for additional polymorphism across the entire type system. That is, where you parameterize over a closure today, you’ll want to parameterize over an effect and a closure tomorrow, and then say how that effect is propagated.

Rust already makes some fine distinctions around things like ownership which show up in polymorphic situations (e.g., the three kinds of closure traits). My view has always been that adding additional dimensions would almost certainly break our complexity budget. I think the payoff would have to be extremely high in order to consider such an addition.

[Centril]

but in general things like effect systems tend to come with a specific downside

I’d argue that we already have an effect system for a limited number of effects: const (or more accurately, impure), trusted, unsafe. So the need for polymorphism, is also already present. Particularly as const fn and async fn becomes stable.

I think the payoff would have to be extremely high in order to consider such an addition.

I think it would; The cost due to an ecosystem split along the lines of const / async / not would be extremely high and result in massive code duplication. Being able to avoid this duplication and splits is to me an extremely high payoff.

[rpjohnst]

I’m not sure that reuse between const/async/non would be quite that high a payoff. It’s possible the cure could be worse than the disease- it might require either a loss of stability guarantees or an explosion of impenetrable types; it might lead to even more binary bloat as more and more functions are monomorphized for various effects.

I’m not saying I don’t want to solve the problems an effect system would aim to solve, just that it could very easily not be worth it. It’s also possible there are better solutions in the context of Rust, or that the problems won’t turn out to be that bad.

[jmst]

The solution to the async/sync split is simply that all new crates should be async and existing ones should be converted ASAP.

“Pluggable” async vs sync was tried when Rust had a runtime and green threads and was abandoned.

This sort of TLS interface hacks also have been tried in Rust as “conditions”, also abandoned.

[scottmcm]

it might lead to even more binary bloat as more and more functions are monomorphized for various effects

This is a good observation. I wonder, though, whether there might be a possible world where the effects aren’t monomorphized, the same way that lifetimes aren’t monomorphized today. It doesn’t seem completely implausible, as whether a function is unsafe doesn’t change the code outputted for it…

[ExpHP]

Being able to avoid this duplication and splits is to me an extremely high payoff.

According to the link from @Ixrec above, it is exactly this deduplication (of async vs sync) which results in the release of Zalgo. Which kind of saddens me because I’ve always figured in the back of my mind that there should be a solution to this problem.

[leonardo]

Some background reading.

Also: https://www.rise4fun.com/Koka/tutorial/guide

[rpjohnst]

The solution to the async/sync split is simply that all new crates should be async and existing ones should be converted ASAP.

“Pluggable” async vs sync was tried when Rust had a runtime and green threads and was abandoned.

This sort of TLS interface hacks also have been tried in Rust as “conditions”, also abandoned.

Those are precisely the inverse situation from async vs sync. They caused problems because they were runtime mechanisms that interfered with FFI and embedding.

Async is a compile time mechanism- it transforms control flow into a suspendable state machine. It’s not “pluggable,” so forcing everything to become async has only one possible outcome: astronomical overhead in debug builds, and lots of compiler busywork on release builds.

[rpjohnst]

I wonder, though, whether there might be a possible world where the effects aren’t monomorphized, the same way that lifetimes aren’t monomorphized today.

That’s certainly possible for some effects (safety and const-ness), but wouldn’t work out for others. Yielding, async, and Result/Try/? (to name a few potential candidates) are all transformations on the generated code. The only reason to make them effects is to control that transformation.

One possible alternative might be Kotlin-style inline functions. Kotlin’s inline isn’t an optimization hint at all- instead it request something like source-level inlining, where control flow can bleed across function boundaries. This means inline “closures” passed to and “called” from inline functions can return from their environment, across their “caller.”

In Rust, this could be an opt-in for small combinator functions like unwrap_or_else that lets things like ?, yield, or await work across them. Of course that also leads to fairly spooky implicit behavior in some situations, and it doesn’t really solve the binary bloat problem, but it is a smaller gun.

[Centril]

I’m not sure that reuse between const/async/non would be quite that high a payoff.

At least for const if you want to be able to reuse any of the standard library traits, you’ll need some form of const polymorphism a la:

const? fn foo<I>(iter: I) -> usize
where I: const? Iterator<Item = usize> {
    iter.sum()
}

This is a syntactically lightweight way of saying that foo(iter) is const if all the methods of <I as Iterator> are const, otherwise foo(iter) is not const. I think it is quite important to be syntactically lightweight here.

it might require either a loss of stability guarantees

I’m not sure why that would be the case… elaborate?

it might lead to even more binary bloat as more and more functions are monomorphized for various effects.

This assumes that one application is reusing both async and sync versions or const and non-const versions. If you only monomorphize to async, then you get zero extra overhead. The great benefit of polymorphism is that you can write libraries which can be customized to the needs of the application, and so you don’t need two libraries, or even more when you get more effects.

wonder, though, whether there might be a possible world where the effects aren’t monomorphized, the same way that lifetimes aren’t monomorphized today. It doesn’t seem completely implausible, as whether a function is unsafe doesn’t change the code outputted for it…

This seems plausible for effects (or restrictions) such as const, total, nopanic, unsafe (these would all be built-in), but implausible for async as the latter must generate different code. So it could be beneficial to denote per effect it if should participate in monomorphization or not with a default that it should. Given that the former set of effects are built-in, the non-monomorphization property for those effects could also just be built-in. Note: I’m speculating wildly here.

According to the link from @Ixrec above, it is exactly this deduplication (of async vs sync) which results in the release of Zalgo.

Truth be told, my main concern is const

That said, that post does not seem very relevant to a strongly and statically typed language which is principled about effects. If you are using the “io” effect and then explicitly decide what handler to instantiate, then are you “releasing Zalgo”?

[Ixrec]

According to the link from @Ixrec above, it is exactly this deduplication (of async vs sync) which results in the release of Zalgo.

Truth be told, my main concern is const

That said, that post does not seem very relevant to a strongly and statically typed language which is principled about effects. If you are using the “io” effect and then explicitly decide what handler to instantiate, then are you “releasing Zalgo”?

Your rhetorical question is technically correct because that’s not quite the scenario I was worried about. Since this is the only sub-issue in this thread I have any confidence in, I’ll try to get more specific.

Pretend I have a library that subscribes to Twitter updates, and logs to stdout. It might contain a method like:

fn process_updates(&self, updates: &[Update]) {
    let seq_num = self.last_sequence_num;
    for update in updates {
        Io::print_stdout(seq_num, update); // more strawman APIs
        seq_num++;
    }
    self.last_sequence_num = seq_num;
}

The user of my library is supposed to write something like:

fn main() {
    let tweets = TwitterFeed::new();
    let gen = generator<Io = Blocking> {
        tweets.subscribe(["big_ben_clock"]);
    }
    // do whatever you wanted to do with the tweets
}

Then one day the user learns that async I/O is amazing and decides to change <Io = Blocking> to <Io = Tokio>. That Io::print_stdout() call automagically becomes async. The program automagically compiles with totally different semantics that make the UI much more responsive or whatever. But that also automagically makes it possible for a tweet to happen, call process_updates, get suspended, and have another tweet happen during that suspension so that process_updates gets called again, and hopefully it’s obvious how two interleaved calls to that function lead to seq_num being out of sync with self.last_sequence_num and blatantly erroneous logs. Hopefully it’s also obvious what the fix would be if I were manually porting this library to Tokio, and that a more complex scenario may have no simple fix at all even if I do know why it broke.

To be super clear, this is not an example of “releasing Zalgo”. It is an example of a mechanical translation of sync code into async code introducing bugs that previously did not exist. I could construct other more convoluted examples in which the bug happened to also be an instance of Zalgo release, but the problem I’m worried about is much more general: I don’t think it’s possible for synchronous code to be mechanically transformed into asynchronous code without introducing severe logic bugs, and if that’s true, I would think that’s a knockout argument against any language feature that tries to polymorphize (?) over sync and async I/O, whether we call it effect systems or dependency injection or runtime customization or whatever.