Async and effect handlers

[canndrew]

Would this allow for eventually fully annotating a Rust program with explicit effects?

For backwards-compatibility’s sake, effects which already exist in code would have to be implicit and opt-out. I suppose there could be a module- or crate-wide attribute like #![no_implicit_effects] which would force you to write effect Io on things, but that would probably just be confusing.

… and still remains zero-cost.

The thing I’m proposing here is zero-cost, at least as far as I can tell. File::read for example would just get inlined as a wrapper around the ambient Io handler’s read method.

Here is a previous RFC

Interesting! Allocation and garbage collection would also be well-suited to a system like this, that’s a good point. That RFC however, assumes that there is only one handler per effect and that every effect+handler combo is cooked into the language. I’m proposing user-defined effects and handlers where you can swap-out different handlers to get things like async vs blocking code. Some effects would have to be lang-items for backwards-compatibility (eg. Io), but you could still write your own handlers for them.

[canndrew]

@zackw

I guess it’s nice being able to see where a function can block, but I don’t like that I have to do it for tokio::net::TcpStream::read and not std::net::TcpStream::read, and that they have to be two separate, incompatible types.

It would be great if it’s possible to make locking part of the Io effect as well, I don’t know feasible it is though. If it’s doable, it would mean tokio tasks / green threads / whatever could use locks the same way that native threads do. The NativeIo implementation of lock would call directly to pthread_mutex_lock or whatever Rust currently uses, but the TokioIo implementation would have to use something like eventfd on Linux, WaitForMultipleObjectsEx on Windows, something else on every other platform, tie it all together under one API, and do it without creating any non-trivial costs. That sounds hard, but the mio guys did something similar to get a working cross-platform Poll implementation, so maybe it’s not impossible.

[bbatha]

Can effect handlers be built with out allocations? As far as I know all of the implementations use heap allocations to jump between the stack and the effect handler 1 2. Though, its not clear to me if this is a problem with effect handlers or the coroutine implementation on top of them. It seems like stackless coroutines may get around this limitation with compiler support.

[canndrew]

@bbatha Yeah, stackless coroutines are what’s being worked on at the moment. I’m envisioning this effects system as a way of getting them into the language. I’m not sure if stackless coroutines are as versatile as stackful ones though. I can’t see how you’d compile a naive implementation of factorial like shown below for instance because you don’t know how much memory it’s going to need.

fn factorial(x: u32) -> u32 {
    if x == 0 {
        1
    } else {
        factorial(x - 1) * x
    }
}

If it turns out that certain kinds of code can’t be compiled as state machines then we could have a way for a coroutine to explicitly opt-in to using a heap-allocated stack. The mioco crate already has a rust implementation of heap-stacks which we could work into this somehow.

[rocallahan]

Not only are these two halves incompatible, but they’ll cause runtime problems when accidently mixed.

I thought calling non-blocking code from blocking code without an explicit wait would definitely be a compile-time error. Is that not the case? (Preventing blocking code being called by non-blocking code is conceptually difficult since in practice any code can effectively “block”.)

I’m writing lots of futures-based code and async/await would be incredibly helpful to us. Effect systems are relatively unproven. I’d hate to see async/await blocked on something experimental like this.

One big question for effect systems is how the annotation burden scales and it’s hard to determine that without experience with large, real systems. For example in your iterator example wouldn’t count_to_ten's closure need to be annotated with the Iter effect? It seems that your original complaint about the preponderance of async annotations is actually worse with your proposal because blocking code needs to be annotated with effects too.

[canndrew]

I thought calling non-blocking code from blocking code without an explicit wait would definitely be a compile-time error. Is that not the case?

Yes actually, not using await! where you need it will be a compile-time error.

(Preventing blocking code being called by non-blocking code is conceptually difficult since in practice any code can effectively “block”.)

It’s impossible to prevent all of it, but we could prevent a lot of it. Anything that’s handled by the Io effect (file/socket IO, timers, joining threads, locking (maybe)) would be safe to mix.

Effect systems are relatively unproven. I’d hate to see async/await blocked on something experimental like this.

I’d hate to see Rust rush into a crummy solution if there’s potentially much better options on the table.

One big question for effect systems is how the annotation burden scales and it’s hard to determine that without experience with large, real systems. For example in your iterator example wouldn’t count_to_ten’s closure need to be annotated with the Iter effect?

I’m assuming that if Iter is in scope then the effect could be inferred there.

It seems that your original complaint about the preponderance of async annotations is actually worse with your proposal because blocking code needs to be annotated with effects too.

No, because the Io effect would be implicit. It has to be for backwards-compatibility, though I wrote it explicitly in some of the example code I gave.

[RalfJung]

For a lot of people, this is one of the advantages of async/await. In tutorials on the concept, you will see things like “it is a lot easier to reason about the locking requirements and other potential concurrency issues when every point where a complex function might ‘block’ is explicitly visible in the code.” And I can personally attest that this is true — in Python, where all errors are runtime errors.

That’s not the case though. Calling blocking code from non-blocking code can just happen, any time. I.e., if you directly call println inside your async task, there is no warning but this code may now block on IO – and that’s bad, of course, as it blocks the entire worker that this async task is currently running on. Rust doesn’t have the effect system required to detect this. The system proposed in this thread could probably do that. It is calls to non-blocking functions that need extra annotations. (Or at last, that’s what I gather from reading some examples and skimming the RFC.)

[glaebhoerl]

Yeah, stackless coroutines are what’s being worked on at the moment. I’m envisioning this effects system as a way of getting them into the language. I’m not sure if stackless coroutines are as versatile as stackful ones though.

Hmm, is your own proposal stackful or stackless (the second sentence suggests stackless but it’s not completely clear)? My recollection of the general consensus from the other threads is that while stackful coroutines are more expressive and/or pleasant to use, they are not performant and “zero-cost” enough for “a systems language like Rust”, and in particular that they would not be appropriate to use for writing implementations of Iterator, which is one of the main use cases alongside async I/O.

Also, just by looking at your proposal without you telling me, from what could I determine for myself whether it’s stackful or stackless? As far as I’ve managed to understand these things so far, “stackless” means that only the top-level function/coroutine may yield (= invoke effects, IINM), while if it’s stackful, that function may call another, which may yield for both of them. (In the stackless proposals so far, they are clearly stackless because if one function which may yield wants to delegate to another function which may yield, the only way to do it is to invoke it in a loop with the outer function yielding every time the inner one does.) In your proposal, I believe (1) any function with a given effect may transparently call any other functions with that effect, which (2) implies that it’s stackful? Or am I mistaken about either of those?

It’s been a while since I read any effect systems papers and I’m making all this up as I go along.

Do you remember them well enough to say how closely your proposal corresponds to algebraic effects systems “from the literature” (I’m familiar with Frank and am reading about Koka in particular, fwiw), or, if there are some important differences, what those are?

(Just a few days ago I was trying to google for whether “algebraic effects” correspond to “stackful” or “stackless” coroutines, with literally zero useful results (does nobody else on the internet care about how these things relate to each other, or what?), but based on the same logic as above concluded that they are almost surely stackful…)

[canndrew]

Stackless is definitely what I’m going for here, although with the possible ability to explicitly opt-in to having a stack where it’s needed. In this proposal, functions can yield (= invoke effects ) from as many layers deep as they want. This requires all the functions between the yielding function and the effect handler to be compiled into a great big state machine. This is the same as what happens when you compose a bunch of futures together into a great big future, and some deeply-nested future yields. I believe @alexcrichton’s coroutines work will allow rust to generate these state machines automatically from plain old, synchronous-looking rust code. I don’t know precisely what limitations this imposes on the code.

Do you remember them well enough to say how closely your proposal corresponds to algebraic effects systems “from the literature” (I’m familiar with Frank and am reading about Koka in particular, fwiw), or, if there are some important differences, what those are?

Uhh, I don’t know. I’ll need to go back to doing research. Frank is one of the inspirations for this though, and I’m pretty sure this is the same as what’s in Frank except that here you explicitly wrap the effectful code up into a Generator which is used basically like an Iterator.

[glaebhoerl]

This requires all the functions between the yielding function and the effect handler to be compiled into a great big state machine. This is the same as what happens when you compose a bunch of futures together into a great big future, and some deeply-nested future yields.

Ah okay, I see. This does seem less restrictive while being still-hopefully-implementable than restricting it to a single function.

I don’t know precisely what limitations this imposes on the code.

Presumably “no virtual calls (to effecting functions)”, for starters? Or no cross-crate calls, even… (or does monomorphization of generics save us)?

[canndrew]

Cross-crate calls should be fine, since we can call generic functions cross-crate. You’re right about virtual calls though… that’s problematic

[genieme]

I think we will need some nice keywords for coroutine and generator as indicators just like fn is used for function.

I propose : ‘co’ for coroutine; ‘gn’ for generator; we have ‘fn’ for function. that implies consistency in using the first syllable of each word. ‘fn’ -> fun; ‘co’ -> co; ‘gn’ -> gen;

e.g : fn plusfive(x: u32)->u32; gn yieldfive()->u32; co awaitfive()->u32;

Just Brain Rumbling for Discussion

THANKS.

[canndrew]

I think we could get around the virtual methods issue, firstly by attaching effects to types instead of methods. So File might look like (if Io wasn’t implicit):

struct File: effect Io {
    fd: RawFd,
}

impl File {
    fn read(&mut self, &mut [u8]) -> io::Result<usize>
    // no effect annotation
    {
        // can use Io because it's attached to the type
        Io::read(...)
    }
}

So, essentially, the effect becomes an extra generic parameter on the type instead of the method. Standalone functions could still be given effects though. It would also have to be illegal to call virtual methods while in an effect context that needs to yield and resume, because it would be impossible to build the required state machine without knowing what method impl you’re going to be calling (and thus what state you need and how much memory you need for it). There’d also have to be the same restriction on recursive functions generally. Having a way to explicitly allow a generator to allocate memory could allow the user to lift these restrictions though.

[steven099]

fn eff_iter<T, F>(f: F) -> EffIterator<impl Generator<Yield = T, Resume = (), Return = ()>>
where F: FnOnce() effect Iter<T> { ... }

I’m trying to understand the interaction with closures here. Am I correct that the effect Iter<T> is part of the bound on F? (I initially thought the effect Iter<T> was still an annotation on eff_iter, which I later realized didn’t make sense.) This seems to imply that F is a higher-kinded type parameter, which would seem to require your later suggestion that effects would have to be able to be applied to types.

It also seems like this would mean that using asynchronous io would have a somewhat broader footprint. With async/await, only the new async functions are treated as asynchronous when called in asynchronous contexts. If effect Io is a default effect, then existing functions will be treated as asynchronous as well. For functions that don’t do any io, I supposed these could be inferred not to have effect Io, though if they do virtual dispatch, that would have to be treated as potentially effectful. Is there any potential that interpreting a presently correct synchronous function as asynchronous could break it?

[canndrew]

I’m trying to understand the interaction with closures here. Am I correct that the effect Iter<T> is part of the bound on F? This seems to imply that F is a higher-kinded type parameter, which would seem to require your later suggestion that effects would have to be able to be applied to types.

Yeah… as it’s written it would require higher-kinded types. Since we know that function uses the For handler though, it could be re-written as something like this maybe:

fn eff_iter<T, F>(f: F) -> EffIterator<impl Generator<Yield = T, Resume = (), Return = ()>>
where F: FnOnce(),
      F effect Iter<T>=For

With async/await, only the new async functions are treated as asynchronous when called in asynchronous contexts. If effect Io is a default effect, then existing functions will be treated as asynchronous as well. For functions that don’t do any io, I supposed these could be inferred not to have effect Io, though if they do virtual dispatch, that would have to be treated as potentially effectful.

I’m not quite sure what you’re saying here. All functions that could potentially do Io would need to be (potentially) compiled twice. Or rather, they’re secretly a generic function which can be compiled with different Io type parameters. If we know they don’t actually do any Io then they could be compiled just once and monomorphisation would turn my_func<Io=Native> and my_func<Io=Async> into the same function. If they call any function that may need to do Io though then they’ll need to be compiled into a state machine when built with Io=Async.

Virtual dispatch also requires dynamic memory allocation. In the RFC I’ve half-written, using virtual dispatch is a compilation error unless you explicitly opt-in to giving your generator a heap-allocated stack.

Is there any potential that interpreting a presently correct synchronous function as asynchronous could break it?

Well we can’t possibly make the Io effect capture all potential kinds of blocking, so there’ll be some libraries that will lock up your event loop if used in an async context. That’s no worse than the status-quo though. Or did you mean something else?

[steven099]

Virtual dispatch also requires dynamic memory allocation. In the RFC I’ve half-written, using virtual dispatch is a compilation error unless you explicitly opt-in to giving your generator a heap-allocated stack.

How does this work if you can already call virtual methods which could potentially do Io? It seems like trait objects would have to default to effect Io=NativeIo.

[canndrew]

I’m getting confused as well, so let’s try and put this in more concrete terms: An effect is like a trait, handlers are types which implement these traits. Something is effectful if it has a type parameter bound by that effect/trait. A function which invokes an effect needs a run-time reference to the effect handler. For now let’s assume there are no implicit effects.

We have:

effect Io {
    fn blah(&self);
}
==>
trait Io {
    fn blah(&self);
}


handler Async for Io yields A -> B {
    fn blah(&self) { .. }
}
==>
impl Effect for Async {
    type Yield = A;
    type Resume = B;
}
impl Io for Async {
    fn blah(&self) { .. }
}


struct MyType effect Io { .. }
==>
struct MyType<H: Io> { .. }


trait MyTrait effect Io {
    fn wub();
    fn zoom() effect Alloc;
}
==>
trait MyTrait<H: Io> {
    fn wub(io: &H);
    fn zoom<A: Alloc>(io: &H, alloc: &A);
}


fn my_func() effect Io {
    Io::blah();
}
==>
fn my_func<H: Io>(io: &H) {
    io.blah()
}


impl MyTrait for MyType {
    fn wub() { .. }
    fn zoom() effect Alloc { .. }
}
==>
impl<H: Io> MyTrait<H> for MyType<H> {
    fn wub(io: &Io) { .. }
    fn zoom<A: Alloc>(io: &H, alloc: &A) { .. }
}


trait MyEffectlessTrait {
    fn smash();
}
impl MyEffectlessTrait for MyType {
    fn smash() { .. }
}
==>
impl<H: Io> MyEffectlessTrait for MyType<H> {
    fn smash() { .. }
}


impl MyTrait for MyEffectlessType { .. }
==>
impl<H: Io> MyTrait<H> for MyEffectlessType {
    fn wub(io: &H) { .. }
    fn zoom<A: Alloc>(io: &H, alloc: &A) { .. }
}


impl MyType {
    fn bar() effect Alloc { .. }
}
==>
impl<H: Io> MyType<H> {
    fn bar<A: Alloc>(io: &H, alloc: &A) { .. }
}

So, in order to have a trait method impl use an effect, the effect needs to be on the trait, not (necessarily) the type. Otherwise we don’t have the required argument for the handler. This means we could have a trait object of type Read<Io=Async> and, so long as we’re in an Async context (have io: &Async in scope) we can call methods on it. Does this model make sense?

[steven099]

Okay, so my understanding of this is that Read<Io=Async> would require explicit allocation to call its methods while Read<Io=NativeIo> (or any effect yielding !) could have its methods called in any effect Io=NativeIo context. Is this right? That seems like it could work, though it would mean that the default effect for code using objects would need to be effect Io=NativeIo rather than being generic over Io. This seems reasonable enough. It would mean that less code would work in async contexts by default, though.

[canndrew]

@steven099 Any effect yielding ! or resuming !, but otherwise yes. I don’t think we need to have any notion of default effect handlers though, just that any code which requires a stack has to be called with a handler which allows it to have a stack, or with an explicitly heap-allocated stack.

[system]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.