RFC 2033: experimental-coroutines

lang (syntax | expressions | control-flow | generators)

Summary

This is an experimental RFC for adding a new feature to the language, coroutines (also commonly referred to as generators). This RFC is intended to be relatively lightweight and bikeshed free as it will be followed by a separate RFC in the future for stabilization of this language feature. The intention here is to make sure everyone's on board with the general idea of coroutines/generators being added to the Rust compiler and available for use on the nightly channel.

Motivation

One of Rust's 2017 roadmap goals is "Rust should be well-equipped for writing robust, high-scale servers". A recent survey has shown that the biggest blocker to robust, high-scale servers is ergonomic usage of async I/O (futures/Tokio/etc). Namely, the lack of async/await syntax. Syntax like async/await is essentially the defacto standard nowadays when working with async I/O, especially in languages like C#, JS, and Python. Adding such a feature to rust would be a huge boon to productivity on the server and make significant progress on the 2017 roadmap goal as one of the largest pain points, creating and returning futures, should be as natural as writing blocking code.

With our eyes set on async/await the next question is how would we actually implement this? There's sort of two main sub-questions that we have to answer to make progress here though, which are:

The focus of this experimental RFC is predominately on the second, but before we dive into more motivation there it may be worth to review the expected syntax for async/await.

Async/await syntax

Currently it's intended that no new keywords are added to Rust yet to support async/await. This is done for a number of reasons, but one of the most important is flexibility. It allows us to stabilize features more quickly and experiment more quickly as well.

Without keywords the intention is that async/await will be implemented with macros, both procedural and macro_rules! style. We should be able to leverage procedural macros to give a near-native experience. Note that procedural macros are only available on the nightly channel today, so this means that "stable async/await" will have to wait for procedural macros (or at least a small slice) to stabilize.

With that in mind, the expected syntax for async/await is:

#[async]
fn print_lines() -> io::Result<()> {
    let addr = "127.0.0.1:8080".parse().unwrap();
    let tcp = await!(TcpStream::connect(&addr))?;
    let io = BufReader::new(tcp);

    #[async]
    for line in io.lines() {
        println!("{}", line);
    }

    Ok(())
}

The notable pieces here are:

The intention with this syntax is to be as familiar as possible to existing Rust programmers and disturb control flow as little as possible. To that end all that's needed is to tag functions that may block (e.g. return a future) with #[async] and then use await! internally whenever blocking is needed.

Another critical detail here is that the API exposed by async/await is quite minimal! You'll note that this RFC is an experimental RFC for coroutines and we haven't mentioned coroutines at all with the syntax! This is an intentional design decision to keep the implementation of #[async] and await! as flexible as possible.

Suspending in async/await

With a rough syntax in mind the next question was how do we actually suspend these futures? The function above will desugar to:

fn print_lines() -> impl Future<Item = (), Error = io::Error> {
    // ...
}

and this means that we need to create a Future somehow. If written with combinators today we might desugar this to:

fn print_lines() -> impl Future<Item = (), Error = io::Error> {
    lazy(|| {
        let addr = "127.0.0.1:8080".parse().unwrap();
        TcpStream::connect(&addr).and_then(|tcp| {
            let io = BufReader::new(tcp);

            io.lines().for_each(|line| {
                println!("{}", line);
                Ok(())
            })
        })
    })
}

Unfortunately this is actually quite a difficult transformation to do (translating to combinators) and it's actually not quite as optimal as we might like! We can see here though some important points about the semantics that we expect:

A major benefit of the desugaring above is that there are no hidden allocations. Combinators like lazy, and_then, and for_each don't add that sort of overhead. A problem, however, is that there's a bunch of nested state machines here (each combinator is its own state machine). This means that our in-memory representation can be a bit larger than it needs to be and take some time to traverse. Finally, this is also very difficult for an #[async] implementation to generate! It's unclear how, with unusual control flow, you'd implement all the paradigms.

Before we go on to our final solution below it's worth pointing out that a popular solution to this problem of generating a future is to side step this completely with the concept of green threads. With a green thread you can suspend a thread by simply context switching away and there's no need to generate state and such as an allocated stack implicitly holds all this state. While this does indeed solve our problem of "how do we translate #[async] functions" it unfortunately violates Rust's general theme of "zero cost abstractions" because the allocated stack on the side can be quite costly.

At this point we've got some decent syntax and rough (albeit hard) way we want to translate our #[async] functions into futures. We've also ruled out traditional solutions like green threads due to their costs, so we just need a way to easily create the optimal state machine for a future that combinators would otherwise emulate.

State machines as "stackless coroutines"

Up to this point we haven't actually mentioned coroutines all that much which after all is the purpose of this RFC! The intention of the above motivation, however, is to provide a strong case for why coroutines? At this point, though, this RFC will mostly do a lot of hand-waving. It should suffice to say, though, that the feature of "stackless coroutines" in the compiler is precisely targeted at generating the state machine we wanted to write by hand above, solving our problem!

Coroutines are, however, a little lower level than futures themselves. The stackless coroutine feature can be used not only for futures but also other language primitives like iterators. As a result let's take a look at what a hypothetical translation of our original #[async] function might look like. Keep in mind that this is not a specification of syntax, it's just a strawman possibility for how we'd write the above.

fn print_lines() -> impl Future<Item = (), Error = io::Error> {
    CoroutineToFuture(|| {
        let addr = "127.0.0.1:8080".parse().unwrap();
        let tcp = {
            let mut future = TcpStream::connect(&addr);
            loop {
                match future.poll() {
                    Ok(Async::Ready(e)) => break Ok(e),
                    Ok(Async::NotReady) => yield,
                    Err(e) => break Err(e),
                }
            }
        }?;

        let io = BufReader::new(tcp);

        let mut stream = io.lines();
        loop {
            let line = {
                match stream.poll()? {
                    Async::Ready(Some(e)) => e,
                    Async::Ready(None) => break,
                    Async::NotReady => {
                        yield;
                        continue
                    }
                }
            };
            println!("{}", line);
        }

        Ok(())
    })
}

The most prominent addition here is the usage of yield keywords. These are inserted here to inform the compiler that the coroutine should be suspended for later resumption. Here this happens precisely where futures are themselves NotReady. Note, though, that we're not working directly with futures (we're working with coroutines!). That leads us to this funky CoroutineToFuture which might look like so:

struct CoroutineToFuture<T>(T);

impl<T: Coroutine> Future for CoroutineToFuture {
    type Item = T::Item;
    type Error = T::Error;

    fn poll(&mut self) -> Poll<T::Item, T::Error> {
        match Coroutine::resume(&mut self.0) {
            CoroutineStatus::Return(Ok(result)) => Ok(Async::Ready(result)),
            CoroutineStatus::Return(Err(e)) => Err(e),
            CoroutineStatus::Yield => Ok(Async::NotReady),
        }
    }
}

Note that some details here are elided, but the basic idea is that we can pretty easily translate all coroutines into futures through a small adapter struct.

As you may be able to tell by this point, we've now solved our problem of code generation! This last transformation of #[async] to coroutines is much more straightforward than the translations above, and has in fact already been implemented.

To reiterate where we are at this point, here's some of the highlights:

Put another way: if the compiler implements stackless coroutines as a feature, we have now achieved async/await syntax!

Features of stackless coroutines

At this point we'll start to tone down the emphasis of servers and async I/O when talking about stackless coroutines. It's important to keep them in mind though as motivation for coroutines as they guide the design constraints of coroutines in the compiler.

At a high-level, though, stackless coroutines in the compiler would be implemented as:

Beyond this, though, there aren't many other constraints at this time. Note that a critical feature of async/await is that the syntax of stackless coroutines isn't all that important. In other words, the implementation detail of coroutines isn't actually exposed through the #[async] and await! definitions above. They purely operate with Future and simply work internally with coroutines. This means that if we can all broadly agree on async/await there's no need to bikeshed and delay coroutines. Any implementation of coroutines should be easily adaptable to async/await syntax.

Detailed design

Alright hopefully now we're all pumped to get coroutines into the compiler so we can start playing around with async/await on the nightly channel. This RFC, however, is explicitly an experimental RFC and is not intended to be a reference for stability. It is not intended that stackless coroutines will ever become a stable feature of Rust without a further RFC. As coroutines are such a large feature, however, testing the feature and gathering usage data needs to happen on the nightly channel, meaning we need to land something in the compiler!

This RFC is different from the previous RFC 1823 and RFC 1832 in that this detailed design section will be mostly devoid of implementation details for generators. This is intentionally done so to avoid bikeshedding about various bits of syntax related to coroutines. While critical to stabilization of coroutines these features are, as explained earlier, irrelevant to the "apparent stability" of async/await and can be determined at a later date once we have more experience with coroutines.

In other words, the intention of this RFC is to emphasize that point that we will focus on adding async/await through procedural macros and coroutines. The driving factor for stabilization is the real-world and high-impact use case of async/await, and zero-cost futures will be an overall theme of the continued work here.

It's worth briefly mentioning, however, some high-level design goals of the concept of stackless coroutines:

As a reference point @Zoxc has implemented generators in a fork of rustc, and has been a critical stepping stone in experimenting with the #[async] macro in the motivation section. This implementation may end up being the original implementation of coroutines in the compiler, but if so it may still change over time.

One important note is that we haven't had many experimental RFCs yet, so this process is still relatively new to us! We hope that this RFC is lighter weight and can go through the RFC process much more quickly as the ramifications of it landing are much more minimal than a new stable language feature being added.

Despite this, however, there is also a desire to think early on about corner cases that language features run into and plan for a sort of reference test suite to exist ahead of time. Along those lines this RFC proposes a list of tests accompanying any initial implementation of coroutines in the compiler, covering. Finally this RFC also proposes a list of unanswered questions related to coroutines which likely wish to be considered before stabilization

Open Questions - coroutines
Open Questions - async/await
Tests - Basic usage
Tests - Basic compile failures
Test - Interesting control flow
Tests - Panic safety
Tests - Debuginfo

Suggestions for more test are always welcome!

How We Teach This

Coroutines are not, and will not become a stable language feature as a result of this RFC. They are primarily designed to be used through async/await notation and are otherwise transparent. As a result there are no specific plans at this time for teaching coroutines in Rust. Such plans must be formulated, however, prior to stabilization.

Nightly-only documentation will be available as part of the unstable book about basic usage of coroutines and their abilities, but it likely won't be exhaustive or the best learning for resource for coroutines yet.

Drawbacks

Coroutines are themselves a significant feature for the compiler. This in turns brings with it maintenance burden if the feature doesn't pan out and can otherwise be difficult to design around. It is thought, though, that coroutines are highly likely to pan out successfully with futures and async/await notation and are likely to be coalesced around as a stable compiler feature.

Alternatives

The alternatives to list here, as this is an experimental RFC, are more targeted as alternatives to the motivation rather than the feature itself here. Along those lines, you could imagine quite a few alternatives to the goal of tackling the 2017 roadmap goal targeted in this RFC. There's quite a bit of discussion on the original rfc thread, but some highlight alternatives are:

Overall while there are a number of alternatives, the most plausible ones have a large amount of experimental and anecdotal evidence already (green threads/stackful coroutines). The next-most-viable alternative (stackless coroutines) we do not have much experience with. As a result it's believed that it's time to explore and experiment with an alternative to M:N threading with stackless coroutines, and continue to push on the 2017 roadmap goal.

Some more background about this motivation for exploring async/await vs alternatives can also be found in a comment on the RFC thread.

Unresolved questions

The precise semantics, timing, and procedure of an experimental RFC are still somewhat up in the air. It may be unclear what questions need to be decided on as part of an experimental RFC vs a "real RFC". We're hoping, though, that we can smooth out this process as we go along!