Pre-RFC: CPS transform for generators

language design
18

Can I clarify anything in particular? Here is a quick sketch of the actual changes I'm proposing:

  • Generators are constructed with and save a caller: *mut dyn Generator.
  • In the generated resume methods, replace return GeneratorState::Return(x) with (conceptually) become self.caller.resume(x).
  • Replace this (approximation of await!) in the generator source:
    let f = f(args..);
loop {
    match f.resume() {
        GeneratorState::Yielded(x) => yield x,
        GeneratorState::Complete(x) => break x,
    }
}
    with this code in the generated resume method:
    self.f = F::new(self, args..);
self.state = next; // also save live values, etc.
become self.f.resume();
next:
  • Use only a single Future to wrap an entire stack of generators. The leaf generator yields a reference to itself as a *mut dyn Generator, and poll saves that and resumes it on its next invocation. Generators awaiting Futures (as opposed to directly awaiting other generators) keep using the loop technique (and thus keep (de)serializing that stack frame every time).

Based on the changes above, I don't believe it is forward compatible as-is, but it could be made compatible with some tweaks and selective stabilization. I believe there are two things to address:

  • The interface and calling convention between awaiters and awaitees needs to remain an implementation detail of the compiler. If we switch to the "single Future per stack of generators" model that seems doable- forbid directly invoking a generator without awaiting it, and instead provide a standard library API to drive a whole stack of them.
  • The generator-driving Future needs to be !Unpin, as it would eventually hold a reference into the generator. Generators that await other generators also need to be !Unpin, as they would also eventually hold references to their caller generators.

The idea that generators directly await other generators without going through a Future doesn't have to make awaiting Futures much more cumbersome. Give Future an async method that contains the polling loop and await that, instead of baking the loop into the definition of await.

Interestingly, this is how Kotlin works- their generators are also not possible to invoke directly without awaiting, they also provide standard library APIs to drive whole stacks of them at once because they don't pass through their Future interface at every level, and they also provide helper async methods on Futures for when you do want to await one from within a coroutine. Then, because you can't ever invoke a generator without also awaiting it, they drop the await keyword altogether.

Thus, instead of this:

async fn foo() -> Result<T, E> {
    // ...
    await some_other_generator()
    // ...
    await some_future
    // ...
}

fn main() {
    let the_future = foo();
    tokio::run(the_future);
}

you write this:

async fn foo() -> Result<T, E> {
    // ...
    await some_other_generator()
    // ...
    await some_future.poll_wait()
    // ...
}

fn main() {
    let the_future = future_from_generator(foo);
    tokio::run(the_future);
}

(Or leave off the awaits if you like, because some_other_generator() on its own is meaningless).

This also neatly sidesteps the question of "but if foo() really returns a Future why isn't Future in its type signature!?" by making foo() not return a Future.

4 Likes