Coroutines and Rust


#1

Coroutines and Rust

Anyone who has ever used the Lua, Python, Javascript, Ruby, or C# language has had a good chance of coming across some sort of yield operator which 1) suspends the state of a running function and 2) yields back a value to whoever the caller is. These “generators” or “coroutines” fairly often implement some kind of iterable interface so they can be used in for-loops. Here’s a trivial generator in Python.

def range(n):
    i = 0
    while i < n:
        yield i
        i += 1

Generators have the benefit of being extraordinarily straightforward to write and refactor compared to the equivalent state machine. Similarly, async/await in C# is another example of an easy to use abstraction that compiles to a state machine which runs until it is blocked on some long running task, yielding control back to the thread pool scheduler until such time that the data is available. In fact there are a great many interesting and useful abstractions which can all be implemented with only the ability to suspend a function’s state and return a value. If one also includes the ability to asynchronously provide input, one can write streaming parsers and sinks, which siphon from streams until they have enough input to produce a value.

Many people are interested in bringing such a feature to Rust, so I think it’s worth writing this post to outline some of the things that have been said so far, pitfalls, and directions for the future, as well as compare to Ecmascript’s 6’s generator design. This post is the first of many and is intended both as a detail heavy introduction to people who are only vaguely familiar with the discussion or have not heard of coroutines before, and also as a kind of summary of the discussion in the last two RFCs so as to provide a good bounding point for the future. (If you have read the current RFCs for this feature, you can probably skip the “First Attempt” section.)

What this is not is:

  • an RFC, or even a proto-RFC
  • an authoritative document in any way
  • even the best way to do any of this, as there are tradeoffs to every design decision
  • a short read

Prior Art

The community has been very vigorous in this area and so there is a lot of acknowledgment to be had. Apologies if I have forgotten someone who deserves to be mentioned.

There was a huge issue in the Rust repo on Async IO as well as an equally large issue on C# style yielding which convinced a lot of people that we should have some kind of generator feature in Rust, be it sugar for a state machine or something more sophisticated. That led to erickt’s very impressive Stateful, a compiler plugin and library which allows you to write state machines using some macros. It gets you very far but is only meant as a temporary solution because this kind of feature deserves to be in the compiler proper. Nonetheless it laid the groundwork and was a great proof of concept.

There are currently two RFCs to this end, which I encourage you to read or skim through: Zoxc’s generator proposal and vadimcn’s stackless coroutines, which is where a lot of the following discussion occurred and pitfalls were discovered. The similarity between these two RFCs is that both allow you to write suspendable functions which yield values until they return a final value, as well as accept input on every resumption. There are many major differences but the most important in my view are that 1) zoxc’s enum representing the result of advancing a generator contains three states while vadimcn’s only has two, 2) zoxc’s rfc explicitly formalizes the notion of an executor in the RFC, and 3) vadimcn’s generators are mostly indistiguishable from FnMut, while zoxc proposes a new trait. I think zoxc’s enum actually results in a more flexible API and better ergonomics, and I make this case later. Also, vadimcn’s proposal is substantially more minimal, which makes it easier to comprehend and identifies the core elements well, opting to implement control flow abstractions with macros over yield. I draw from both of these later.

Lastly, Eduard-Mihai Burtescu from the Rust compiler team has been invested and involved in this community-wide discussion since the very beginning and has been instrumental in this getting as far as it’s gotten, as well as providing the useful perspective of someone who knows the compiler internals well. If you click on any of the links I’ve provided, you’ll see his comments, advice, and direction throughout.

Design Requirements

Any good generator design should satisfy the following requirements.

  • Allow one to yield values
  • Allow one to return a value
  • Allow values to be moved out of the generator’s environment, such as a sink moving a buffer as its return value
  • Allow one to send values into the generator
  • Be reasonably ergonomic
  • Not require any heap allocations
  • Be flexible enough to write iterators, futures, streams, sinks, and protocols like Deflate
  • Be composable, i.e. it should be painless to combine various abstractions with minimal or no reimplementation of macros
  • Allow streams to be used with for loops
  • Allow iterators to be used with for loops
  • Be usable with Futures-rs with minimal to no API redesign on the library-side.

Some optional requirements are

  • Allow one to delegate to an interior coroutine until it returns (like python’s yield from)
  • Have a robust and flexible set of “generator combinators” (for instance, imagine an ignore_all which takes a generator that yields Y and returns R and turns it into one that yields () and returns R).
  • Reduce the amount of enums users have to write (this is vague; more on this in a bit)

First Attempt

We start with a trait, because this is how we encode a uniform interface across a variety of types in Rust.

enum CoResult<Y, R> {
    Yield(pub Y), Return(pub R)
}

trait Generator {
    type Return;
    type Yield;
    fn next(&mut self) -> CoResult<Yield, Return>;
}

The CoResult is what we get back from calling our generator. Once we get a Return, we shouldn’t call the generator anymore (I would expect it to panic, in fact). Any function which we expect to create a generator should implement this trait, and the compiler should autogenerate the next method and do the state tracking for us. I almost put a Sized bound here for simplicity but it would be interesting to explore unsized generators that are “stackful”, i.e. have an unbounded execution space.

We need three syntactic components. The first is a way to mark a function as returning a generator. The second is a yield keyword. The third is a type signature that includes the yield type. It’s unimportant exactly what this syntax looks like as long as eventually there is some. Translating the previous python example into Rust directly might look like:

fn* range(n: usize) -> yield usize {
    let mut i = 0;
    while i < n {
        yield i;
        i += 1;
    }
}

Or more idiomatically

fn* range(n: usize) -> yield usize {
    for i in 0..n {
        yield i;
    }
}

The * after fn lets the compiler know that this is a “generator constructor”, meaning that it’s alright to use the yield keyword in this context. If we didn’t have this and inferred this from the presence of yield, it would be possible to introduce copy and paste errors that greatly change the semantics and type inference of a function. This is even less apparent if a new user uses a macro which obscures the yield. While there are some benefits, the language team has expressed preference for explicit marking.

The yield keyword here suspends the generator at that statement, returns a value to whoever called it, and stores the execution state somewhere in the environment of the generator. You can think of this as similar to how a mutable closure can change its environment. In this way both generators and closures are stored on the stack, unboxed. However, while a closure only needs to store the environment that it closes over, a generator needs to have room for both the environment it closes over and the maximum extent of its own execution stack. Notice I said maximum: the stack space required for executing such a function must be bounded. That means there can be no recursive calls because it would be impossible to determine how much stack space to store for the generator to execute in. Just like with recursive datatypes, the best way to get around this is with pointer indirection.

The type signature syntax here is Eduard’s. In general, R yield Y occurring in the return type of a generator constructor is shorthand for impl Generator<Return=R, Yield=Y> (for those unfamiliar with the impl Trait RFC, this is a compiler generated type which only guarantees that it implements some trait, and was motivated by returning unboxed closures). If you omit the return type as in yield i32, then this is shorthand for having a return type of ().

Here’s how we might use this manually.

let mut i = 0;
let mut r = range(n);      // This creates the generator. No code is run at this point as the generator is "newborn". 
while let Yield(i) = r() { // Calling the generator like a function advances it toward the next yield.
    sum += i;
}

Eventually the generator call will return Return(()) and we stop our iteration. It’s simple enough to wire this to the existing Iterator trait so we can use them in for-loops:

// This impl depends on the "trait-specialization" RFC so that it doesn't cause coherence issues.
impl<G: Generator> Iterator for G {
    type Item = G::Yield;

    fn next(&mut self) -> Option<G::Yield> {
        match self() {
            Yield(y) => Some(y),
            _ => None,
        }
    }
}

It’s notable that these are just as efficient as Rust iterators, and they are unboxed, so no heap allocations have been incurred. The stack space of the function sits there with the rest of the stack, and because it’s bounded, allows you to continue doing other work while the function remains unfinished. In fact I like to think of this as a reified stack frame - a handle to some executing function that I can resume on-demand until it finally finishes.

Because we’ve written this blanket impl for generators, we can rewrite our range function to return something that only exposes an iterator interface, hiding the low-level implementation detail that this is an execution-suspending function that returns a CoResult.

fn* range(n: usize) -> impl Iterator<Item=usize> { ... }

As a convenience, the Python language includes a yield from construct which delegates to an inner generator and yields all of its values for you. Javascript includes this as yield*. While the Javascipt notation is ambiguous in Rust with yield *expr, and from is not a reserved word, presumably this could appear in our language as yield while.

“Futures” are a datatype representing long-running computations that will eventually result in a value. You poll any type that implements Future<Item=T, Error=E> and it returns either Ok(Async::Ready(T)), Ok(Async::NotReady), or Err(E). Currently futures are written much like iterators are: you define a struct that contains the essential data and you implement poll yourself. The tokio library contains many great combinators and primitives and is extremely useful, today, for writing asynchronous code, but let’s try writing our own future anyway using a generator and a fake API.

fn* async_task(db: DatabaseHandle) -> Result<Record, E> yield () {
    let mut f = db.lookup("Linus Torvalds"); // Returns an impl Future<Item=Record, Error=DBErr>
    let r = loop {
        match f.poll() {
            Ok(Async::NotReady) => { yield; continue; },
            Ok(Async::Ready(r)) => Ok(r),
            Err(e) => Err(e),
        }
    }

    return r;
}

This is the first time we’ve seen return in a generator. Returning is what makes generators useful for much more than just implementing iterators. Note that we move the Record out of this function, which is why we can’t run a generator again once it’s already returned.

Again, writing a blanket impl by hoisting the result out:

impl<G, T, E> Future for G 
    where G: Generator<Return=Result<T, E>>
{
    type Item = T;
    type Error = E;

    fn poll(&mut self) -> Result<Async<T>, E> {
        match self() {
            Yield(_) => Ok(Async::NotReady),
            Return(Ok(t)) => Ok(Async::Ready(t)),
            Return(Err(e)) => Err(e),
        }
    }
}

The type signature of our last function becomes a simple fn* async_task(db: DatabaseHandle) -> impl Future<Item=Record, Error=DBErr>, which is an improvement over the raw generator signature. The looping is unfortunate, but trivially remedied with a small macro (whose definition is an exercise for the reader) that expands into the same pattern.

fn* async_task(db: DatabaseHandle) -> impl Future<Item=Record, Error=DBErr> {
    await!(db.lookup("Linus Torvalds"))
}

Thus a user who only knows about the Future trait and the await! macro is able to write his own asynchronous code without having to know anything about generators and yielding.

In general, this is the predicted usage pattern for generators: library writers will write generators and then write traits and macros which abstract over their usage. Library users will either use the preconfigured components or have the ability to make their own components by writing a generator that yields and returns the correct types.

This is where the smooth sailing ends in the design.


#2

Unforeseen Pitfall 1 - It doesn’t compose

Future has a sequence counterpart called Stream, which could be thought of as “many futures”. You poll it repeatedly and on occasion it gives you back a value wrapped in an option. When you’ve hit None, you’ve reached the end of the stream. A Stream<Item=I, Error=E> should be obtainable from any Generator<Yield = Result<Async<I>, E>, Return = ()>. Annoyingly, even though we were able to get rid of the Async type in our future, we need it in the stream because we need a way to signal that we’re still waiting on a value to become available. We don’t need the option because we expect to return unit at the end of our generator. I don’t need to explicitly write out the blanket impl; you can imagine how onerous the datatype origami is here.

Let’s write a simple stream.

fn* stream() -> impl Stream<Item=&'static str, Error=()> {
    let strings = vec!["Three", "Blind", "Mice"];
    for s in &strings {
        yield Ok(Async::Ready(s));
    }
}

Besides the nesting of types, this works just fine. But this isn’t especially asynchronous. Let’s throw in a query that is bottlenecked by IO.

fn* matches<'a>(search_string: &'a str) -> impl Stream<Item=Static, Error=()> {
    let matches = await!(find_matches(search_string)); // web request to some server, possibly
    for string in matches {
        yield Ok(Async::Ready(string));
    }
}

Here we’ve attempted to use a future in a stream, but this won’t compile at all. Because we’ve defined futures to have a yield type of (), the await macro attempts to suspend the stream with Yield(()), which is not what the stream wants to yield. Ok, we can change the generator that maps to futures to be Generator<Yield=Result<Async<R>>, Return=Result<Async<R>>>. Now, we change the await macro to yield Ok(Async::NotReady). The type signatures here feel very wrong, and are sure to scare beginning users - but this does work. Let’s continue.

Suppose we want to inject the value of a future right into a stream.

fn* statuses() -> impl Stream<Item=Status, ()> {
    for num in 0..NUM_MACHINES {
        yield await!(check_status(num)).unwrap();
    }
}

Now, this isn’t the best code. It unnecessarily serializes what should have been a parallel dispatch (I also punted on error handling). But by all appearances this code should be correct, and yet it isn’t. The problem is that our await macro lifts the value out of the Async wrapper because we didn’t need it anymore, but the stream yields polls, so it expects us to wrap in a Ready.

This problem is not isolated. Our abstraction is too simple and thus does not compose well at all. Unfortunately, it seems that every combination of abstractions of generator-like traits results in having to write more macros, and we end up deeply nested in these enumerations. This is why I think Zoxc’s addition of a third variant to represent suspension or waiting is a better design choice. We start with this alternative definition of CoResult:

enum CoResult<Y, R> { 
    Yield(pub Y), Return(pub R), Wait
}

Wait is the value returned by a yield with no values. (Zoxc’s RFC actually parameterizes his suspension variant to contain a “reason” for waiting, but I think that complicates the API too much and we lose the dead-simple composability I’m about to show. Besides, futures-rs already uses TLS and some other machinery to communicate wait-reasons when it installs wakeup callbacks, so I think we’re alright here without it.) Now we redefine our impl of Futures:

impl<G, T, E> Future for G 
    where G: Generator<Return=Result<T, E>, Yield=!>
{
    type Item = T;
    type Error = E;

    fn poll(&mut self) -> Result<Async<T>, E> {
        match self() {
            Wait => Ok(Async::NotReady),
            Return(Ok(t)) => Ok(Async::Ready(t)),
            Return(Err(e)) => Err(e),
            _ => unreachable!(),
        }
    }
}

Not much change here. We use !, the diverging type, to indicate that this branch can never happen because futures don’t yield. We’ve also regained our sensible type signatures. What does the await macro look like now?

// await $expr expands into...
{
    let mut e = $expr;
    loop {
        match e.poll() {
            Ok(Async::NotReady) => { yield; continue; },
            Ok(Async::Ready(r)) => Ok(r),
            Err(e) => Err(e),
        }
    }
}

If this is what you wrote before, congratulations. We have not yet lost intuitive behavior. The real test now is to use a future in a stream and to inject one into a stream. First we define the impl over streams…

impl<G, E> Stream for G
    where G: Generator,
          G::Return = Option<E>,
{
    type Item = G::Yield;
    type Error = E;

    fn poll(&mut self) -> Result<Async<Option<T>>, E> {
        match self() {
            Yield(y) => Ok(Async::Ready(Some(y))),
            Wait => Ok(Async::NotReady),
            Return(None) => Ok(None),
            Return(Some(err)) => Err(err),
        }
    }
} 

The type of generator we use has actually dramatically simplified since we now only have to worry about yielding values instead of signalling in the type that we’re not ready to yield one. Now let’s see using a future in a stream.

fn* matches<'a>(search_string: &'a str) -> impl Stream<Item=Static, Error=()> {
    let matches = await!(find_matches(search_string)).unwrap(); // web request to some server, possibly
    for string in matches {
        yield string;
    }
}

It’s actually simpler than what we tried writing before. This is because our suspensions (due to waiting on the future) are handled by the Wait variant. The await macro is robust enough to be used in this situation. In fact this is what a novice would try writing and - surprise - it works just fine. This is a big usability improvement and a win for ergonomics. In fact I would make the argument that a future version of tokio or futures should scrap their datatypes and just use the CoResult directly, since it matches so cleanly with their semantics. This would avoid the unnecessary translation.

Let’s try injecting a future into a stream.

fn* statuses() -> impl Stream<Item=Status, ()> {
    for num in 0..NUM_MACHINES {
        yield await!(check_status(num)).unwrap();
    }
}

Identical to what we wrote before, even though this expands into a double nested yield. The inner yield in the await’s loop tells the generator to notify that it’s waiting. The visible yield finally yields back the result of the value. We seamlessly combined two features here, and we’re writing asynchronous streams as simply as we were writing iterators earlier.

I talked about yield while in the last section. Let’s revisit this to find something surprising (at least , I didn’t expect it). If this were written as a macro, what would we expect it to expand to? Probably something like this:

let generator = $expr;
loop {
    match generator() {
        Wait => yield;                      // If our sub-generator waits, so do we
        Yield(y) => { yield y; continue; }  // Whatever our sub-generator yields, we yield
        Return(r) => r                      // The last result of a generator is often useful, so we return this as the value of the expression.
                                            // (This is what ES6 does)
    }
}

We place the restriction of course that one can only yield while a generator that has the same yield type as the calling generator. Looking at this hypothetical expansion is interesting because it almost exactly resembles our await macro. The only two differences are that ours passes back a yield value while the future generator never yields a value (remember that the yield type was !), and that ours operates directly on a generator. In fact, if generators were the exposed interface for the futures library, we could simply expand await!(expr) as yield while expr! There is probably something more fundamental going on here (like, on a categorical level) that yield-while feels like a sister operation to yield. The point I’m trying to make here is that the CoResult type with a Wait variant is not convenient for our API by accident: it more directly allows us to express the relationships between “asynchronous” processes that we wanted. await! over a future is only useful for the one abstraction that exposes poll; with yield-while and raw generators we can “await” any datatype/process that we want that we know will eventually provide Return, such as a stream which finishes with a StreamCloseReason, for instance.

Some people might want to prevent an interior generator from providing values to the exterior one to yield. For instance, if we were awaiting another generator to finish which also functioned as a stream of values, we wouldn’t necessarily want it to inject its own values into our streams. I mentioned combinators earlier. I provide a list of useful and interesting combinators I’ve come up with later but here’s one called ignore_all which converts any Generator<Yield=Y> into a Generator<Yield=!>:

fn* ignore_all<G: Generator>(g: G) -> G::Return yield ! {
    loop {
        match g() {
            Wait | Yield(_) => { yield; },
            Return(r)       => { return r; }
        }
    }
}

This kind of selective mapping from one type parameter to another (in this case G::Yield to !) should come naturally to anyone who has ever used Result, Iterator::map, Option, etc.

There is so much more I have to say about the things that fall out of this design, like what this means for Streams and IntoIterator/Iterator, but I want to save that for future posts… but there’s one final point I want to make on this subtopic. I just made a fairly long argument for exposing the generator trait directly to people who want to use and create futures by claiming that it simplifies the API (I called this “type-origami” earlier because of all of the nesting, which can be considered user-hostile) and gives us more composable tools. This is true. But I also claimed earlier that functions shouldn’t expose the “low-level” generator interface and expose an easier to read trait that obscures unnecessary type information (for instance, most people who use streams really do not want a return value, and most people who use futures don’t want a yield value). This is also true! As it stands, these are not especially reconcilable. The current version of conservative impl trait is a “tightly-sealing abstraction mechanism” for any trait which is not an OIBIT (like Copy, Send, etc.), so there’s no way to use any impl Trait Future<Item=I> as a generator that returns I and never yields. There are two solutions for this, as far as I can tell. The first is to allow Generator to be a leaking abstraction type like Copy and Send are. This is what I would prefer as it makes things simpler. The second is to have a second blanket impl that actually implements Generator<Yield=!, Return=I> for any Future. I don’t know if this will actually work due to coherency (and I think impl specialization has to form a DAG) and it isn’t especially nice because it feels like an ouroboros of abstraction that should be simplified to begin with. At every step of the way we should be thinking about the end user - even if we can justify byzantine layers of abstraction to ourselves, will a newcomer to Rust be as forgiving? There is a third option similar to the second one to introduce IntoGenerator, have the await macro expand into a call that turns anything that implements this into a generator, and then does what it does here. I could envision tokio adopting this as the most flexible option because it allows them to maintain their API, and it also results in very simple error messages (await!(2) errors with “Error: i32 does not implement IntoGenerator”). …And a fourth option of course is to just break the existing library entirely, write it from the ground up, and introduce trait synonyms to the language. I don’t think anyone wants this. :slight_smile:

Unforeseen Pitfall 2 - Sending values isn’t as easy

I haven’t mentioned input at all yet. I imagine that many people might ask “why would I want to send input to a generator?”, especially if you have only ever heard of generators in the context of futures, streams, and iterators. I conjecture that there are actually vastly more use-cases for asynchronously receiving values than there are for yielding or returning them. ES6 refers to this as the “observer pattern”, so I transliterate many of their disseminated examples here, but I describe their generator implementation at length in the next post.

vadimcn’s RFC tackles this by treating generators almost indistinguishably from FnMut. In fact, any generator is essentially an FnMut(Input) -> CoResult<Y, R>. This is elegant, both conceptually and implementation-wise. The functions we’ve been writing as fn* all desugar into returning a closure, and the traits we’ve been implementing are implemented over mutable closures returning CoResults. On to sending values: the idea is that the initial argument to the closure is the first input, and future inputs are returned by yield, i.e. yield becomes both an expression and control-flow. To see what I mean, consider this code:

let mut concat = |s: Option<&str>| {
    match s {
        None => { return String::new(); }
        Some(s) => {
            let string = String::from(s);
            while let Some(s) = yield {
                string += s;
            }

            return string;
        }
    }
}

This generator concatenates slices onto an internal string until we send it None, signaling that we’ve ended our function. In fact, we can actually write any iterator consumer as an FnMut(Option<Item>) -> CoResult<!, R>. Here’s a hypothetical method on the Iterator trait:

pub fn feed_into<F, R>(self, f: F) -> R where F: Fn(Option<Self::Item>) -> CoResult<!, R> {
    let mut r;
    for i in self {
        r = f(i);
    }

    match r {
        Return(ret) => ret,
        _ => panic!("Did not receive enough input."),
    }
}

I want to stress that this input type is actually distinct from the type of our constructor arguments. Our constructor constructs a generator but does not begin running it on anything. Doing so would be hazardous. For instance, as I’ve mentioned, futures use thread local storage liberally, such as to install callbacks and unpark, but this isn’t possible if the thread isn’t running an executor (like your main thread won’t be while you’re building up future-computations). It would be impossible to use futures at all if they immediately started running while you’re building new futures with combinators.

Thus far we have always assumed we have input to begin with. But it’s often the case that we don’t have any input when we start our generator and wait for more. Here’s a “logger” in javascript.

// Prints anything it receives.
function* dataConsumer() {
    var i = 1;
    while (true) {
        console.log(`${i}. ${yield}`);
        i++;
    }
}

Our constructor definitely doesn’t start off with any string to print and we probably don’t want to initialize it with one anyway. If I were using this in a real application, I’d prefer to have this declared somewhere in main, pass it down my app as necessary, and send a string when I’m very deep in the logic already and need to log something. A poor solution to this problem is to force the api to take in Option<String>. But this doesn’t really match the semantics that we want because we always know that there won’t be input to start with, and we’re forced to unwrap all later input. It also becomes more onerous to call from user code. You might object that we’ve already done something like this previously, with our string concatenator. But we should be motivated to remove as many unnecessary enumeration types as possible and reduce the complexity of our interfaces. Furthermore, even our string concatenator benefits from these improved semantics:

// Sorry in advance for this type signature.
fn* concat() -> for<'a> impl Generator<&'a str, Yield=!, Return=String> {
    let string = String::new();
    while let Some(s) = yield {
        string += s;
    }
    return string;
}

An entire layer of nesting has been removed from our generator and we didn’t need to unroll the first case. There is also an argument here for generality. Let’s call a generator scheme that requires input “input requiring generators” and let’s call a generator scheme that doesn’t “input-optional generators”. Every input-requiring generator can be written in the input-optional scheme by immediately yielding on the first line of the generator, but in order to write an input-optional generator in an input-requiring scheme, you need to introduce an Option and unwrap on every usage.

So we’ve established that input is desirable and we don’t necessarily want input at the beginning of the generator’s execution. Now we have to complicate our trait a little.

trait Generator<Input> {
    type Yield;
    type Return;

    fn start(&mut self, Input) -> CoResult<Yield, Return>;
    fn next(&mut self) -> CoResult<Yield, Return>;
}

Again, though, we’ve run into a little bit of trouble. What happens if we start a generator that’s already executing? I’d recommend panicking, since that’s what we do when we try to advance a generator that’s already returned. What happens when we try to advance a newborn generator that hasn’t been started? Again, I’d recommend panicking here, but this is far more precarious because when you’ve been given a generator from somewhere, you don’t know if someone has already started it for you. This is actually a problem in Javascript: you start a generator with next() to “prime it” and then advance it with next(args). This is annoying for observer adapters, so there is a helper function that primes your generator for you, but I’m unconvinced that’s the right approach. I’m inclined to say that “Observers” (state machines which read values and might return but never yield) and “Generators” (state machines which yield and return but never read) are distinct enough to warrant having different traits. One argument for that is that having a design which covers every case but complicates usage is strictly worse than having multiple abstractions that are simple to use and do their job well. You see this in the design of Rust’s error handling, where Result types are encoded at the type level for exceptional but expected situations, and hard-panics are for unrecoverable errors, vs. the typical approach of having everything implemented with “exceptions”.

In (Exploring ES6)[http://exploringjs.com/es6/ch_generators.html], Dr. Axel Rauschmayer gives a few examples of generators which are both observers but also yield values. In my view, none of these examples are really relevant or expressible in Rust. For instance, there is a kind of fake y-combinator pattern where a generator expects a reference to itself as an input so that it can call next on itself later, thereby driving its own execution. In Rust this would be illegal (and memory unsafe) self-borrowing. Also, there is an example of an implementation of javascript’s communicating sequential processes which uses yield to provide a reason-for-suspending to the green thread executor, but our futures library already does this just fine without any notion of (further) complicating the return type of poll. But it still feels like the wrong decision to not have the ability to both receive and send input asynchronously, so I think this deserves some more consideration.

The last thing before I end this sub-section is yield while. I’ve been referring to it as if it were an operator but we can certainly implement it as a macro. For ergonomic reasons, and because we expect it to run a generator to completion, we expect the generator to be newborn. We also want it to send input sent to the exterior generator down into to inner one. Thus this code:

let value = yield_from!(generator());

should translate to

let value = {
    let mut value;
    let g = generator();
    let mut next = g.start();
    loop {
        let input = match next {
            Wait => yield,
            Yield(y) => (yield y),
            Return(r) => { value = r; break; },
        }
        next = g(input);
    }

    value
}

Unforeseen Pitfall 3 - Suspending while an interior borrow is held

The two RFCs I mentioned in the prior art section have one specific, important restriction: no borrows to anything in the execution space of a generator must persist across suspension points. To see why this is a problem, consider this trivial code.

fn* gen() -> yield {
    let x = 2;
    let r = &x;
    yield;
    let y = *r;
    return;
}

let g = gen();
g.start();
return g;

After I call the start method, there’s a borrow in g pointing somewhere to the stack. Then I move the generator. This pointer now points to garbage. So the RFCs explicitly disallow this. But this is unfortunate and undesirable for at least three reasons.

The first is that it makes writing generator functions really hard compared to writing a normal function. You have to move your operations around and assign temporaries so that no borrows exist. This is a substantial break from what people are used to and makes for a poor experience.

The second is that there is a lot of code I want to write that should be correct but isn’t. For instance, here’s a perfectly reasonable future that fills a buffer:

fn* task() -> impl Future<Item=Vec<u8>> {
    let mut v = Vec::new();
    
    await!(task1(&mut v));
    await!(task2(&mut v));
    await!(task3(&mut v));

    return v;
}

Or, a common problem in using futures is that with the current combinators, you can’t share state in what is essentially a sequential chain of futures without using an Arc. With generators, this is just a normal matter of scope, not sharing.

The third is that in practice, a lot of generators aren’t really going to be partially run and then moved, anyway. Take a future. Typically futures that are run on a queue are boxed once, and then live on the heap for the entirety of their execution, so they are never moved anyway. Or, if you run a future with the blocking wait executor, it consumes the future and runs it in place until it finally returns. Or take a for loop. The for loop always consumes the iterator, so you never have an opportunity to run it anyway. Writing generators that borrow their own interiors isn’t a problem as long as they’re used in the way that we typically use them right now, it’s just that Rust isn’t smart enough to understand immovable values. This recent RFC by Zoxc attempts to solve this problem with a new Move marker trait that some types don’t implement. The compiler will know that once you mutate this type, you shouldn’t move it. This also should allow Rust to have better support for and safer interfaces for “intrusive datastructures”, which just means that the interior components are aware of and have pointers to the surrounding datatype.

impl Trait currently doesn’t support multiple bounds, but if it eventually does, then you can write something like this:

fn* count(n: usize) -> impl Iterator<Item=usize> + Move {
    for i in 0..n { yield i; }
}

and the compiler will yell at you if you have an interior borrow somewhere. Rust’s safety and marker traits really shine here. This is simultaneously the most important roadblock and also the shortest section because it is so easy to solve.

Conclusion

If you weren’t familiar with the full range of use-cases for generators, you probably are now. We’ve made a straightforward but naive first attempt and seen the drawbacks. Hopefully this post is useful as a good starting point for anyone who wants to contribute to what is a community wide discussion. These issues were discovered by trying to build usable abstractions with the proposals. The next post (which is already written) goes further with this philosophy. We’ll try to implement an Actors library and a Communicating Sequential Processes library and learn some lessons. The third post will get into much more detail into futures-rs, as well as the standard library and IO (such as providing non-blocking methods to currently blocking datastructures like Mutex). And if I don’t get repetitive strain injury, I’ll write a fourth post about some more exotic extensions to generators like generators which have multiple methods and unsized/stackful generators (for tree iterators).


#3

Interesting read. I think the internals forum would be a more appropriate audience.


#4

I considered that and decided against it, but in retrospect, maybe you’re right.


#5

FWIW, I think the informal “plan” here is to wait for stateful (which is close to completion), let it simmer outside the compiler and get baked, iterate on that, and build something similar in the compiler itself. I don’t think it’s fair to call it a temporary solution.

I believe that stateful satisfies most of the requirements in your list. You can’t send values to generators (like JS’s yield-as-expression), but that might not be too hard to add. It should be easy to write wappers that make it composable with futures.


#6

Has anyone reviewed fringe it does a rather good job of snappy user level co-routines in the little I’ve used it.


#7

I must admit that I find the idea of having a dynamic check (panicking) instead of a compile time check to signal completion seems a step back from the power Rust’s ownership model grants us.

Instead, I would rather see a Generator like so:

trait Generator {
    type Yield;
    type Return;

    fn next(&mut self) -> Option<Yield>;
    fn recycle(self) -> Return;
}

Then the semantics would be that after next yields None it shouldn’t start returning values again (though no big deal if it does).

Also, at any time, you can call recycle to get your state back. In general you’d do it once you’ve finished iterating, but in the case of “infinite” generators (such as a generator yielding prime numbers), running it to completion may take long than you wish to wait for.

This design solves that, though there’s a trade-off: Generator is no longer object safe (I wonder if disallowing particular associated functions rather than whole types wouldn’t be better).

What is the chance that object-safety and Return are necessary? I imagine it may happen.


Maybe start can be attacked in the same way:

trait Generator<Input> {
    type Yield;
    type Return;

    fn start(input: Input) -> Self;
    fn next(&mut self) -> Option<Yield>;
    fn recycle(self) -> Return;
}

Or not variant on the Input:

trait Generator {
    type Input;
    type Yield;
    type Return;

    fn start<I: Into<Self::Input>>(input: I) -> Self;
    fn next(&mut self) -> Option<Yield>;
    fn recycle(self) -> Return;
}

Or maybe a GeneratorBuilder is a better option:

trait Generator {
    type Yield;
    type Return;

    fn next(&mut self) -> Option<Yield>;
    fn recycle(self) -> Return;
}

trait GeneratorBuilder {
    type G: Generator;

    fn build(self) -> Self::G;
}

It’s a very interesting topic, thanks for the very helpful summaries.


#8

For the record, erickt was one of the first people to comment on vadimcn’s proposal (whose pull request has since been removed by the author, I think :frowning: ) and was actually the one to say that stateful is a temporary solution, so I’m using his words. My understanding (although I’m not trying to speak for him) is that eventually you have to do this at the MIR level and that there are fundamental limitations to the plugin approach.

Also, as I outlined in my post, adding input complicates the design a lot (like having to prime generators) and so I don’t think it’s as easy as an afterthought.


#9

I think the implementation is temporary, but the API (traits, etc – which is what this post is discussing) is supposed to be more permanent ; in the sense that it is the base to be iterated on before settling on a final API for inclusion in rustc. I could be wrong though.


#10

100% agree with leveraging statically guaranteed safety and builder patterns being preferable to “call these methods in the right order”, but losing object safety is impossible to reconcile with futures because they are boxed once into trait objects before they are queued. Something nice I considered along those lines is interacting with generators only by handles which poison on drop (think mutex style):

trait Generator {
    type Yield;
    type Return;

    /// Returns a handle. Does not advance at all.
    fn handle(&mut self) -> Handle<Self>;
    
    /// Advances the generator. Unsafe to call outside of a handle 
    /// because it might be newborn.
    unsafe fn next(&mut self) -> Option<Self::Yield>;

    /// Poisons the generator so it can't be called again, and returns a value.
    unsafe fn finish(&mut self) -> Self::Return;

    /// Poisons the generator so it can't be called again.
    fn poison(&mut self);
}

struct Handle<'g, G: Generator + 'g>(&'g mut G);

impl<'g, G: Generator + 'g> Handle<'g, G> {

    /// The safe way to advance a generator
    pub fn next(&mut self) -> Option<G::Yield> { self() }

    /// Runs the generator to completion. 
    pub fn finish(self) -> G::Return {
        while let Some(_) = (self.0)() { ; }
        unsafe { (self.0).finish() }
    }
}

/// Dropping a handle poisons the generator.
impl<'g, G: Generator + 'g> Drop for Handle<'g, G> {
    fn drop(&mut self) {
        (self.0).poison();
    }
}

This preserves object safety. You can also do a similar wrapper for anything that implements DerefMut, which is what the futures library would use instead of this. The disadvantage is that you can’t implement IntoIterator for this and have to do it for handles instead. Then you’d use it like

for val in some_generator().handle() { ... }

Of course, if you have any kind of input, suddenly you have to change the handle method to return (Handle<Self>, Option<Self::Yield>). Which is far less ergonomic if you use the api directly but perhaps people don’t really notice it under wrappers. :slight_smile:

This also indirectly solves the problem of having interior self borrows, and any future solution is backwards compatible with this (we just deprecate the `method and the Handle datatype, and remove unsafe from the method). Because you can only interact with a generator through a Handle, and dropping it dynamically poisons it, you don’t have a chance to move it and keep using it. But this is all a little convoluted since there’s already an RFC for immovable types.


#11

There is no API. The crux of Stateful can be seen on this line. The library is hardcoded to understand generators and asynchronous code. It is not extensible by user code. This is where Stateful currently implements its await expansion, and if it looks familiar, that’s because erickt actually contributed the proper await! expansion to the stackless coroutines rfc. But because this isn’t extensible, you can’t implement, say, streams. Getting some kind of API at all is still unexplored territory.


#12

Ah, I see.


#13

I have a couple of comments.

In design requirements, the last 3 are dubious.

  • Having streams work with for-loops (or some await for variant which I propose im my RFC) would be nice, but shouldn’t be a requirement. Using both iterators and streams with regular for looks could be problematic since it need to suspend, but only in the stream case. Since there would be references which can’t cross a suspend point, requiring a suspend point for looping over iterator would be quite restrictive.
  • Iterators can already be used with for-loops. You probably meant that generators can be iterators here?
  • I don’t think we should restrict ourself to designs with interact well with futures-rs. It was not designed with generators in mind, but rather convenient asynchronous programming given the current feature set of Rust. We will probably end up with a design which works well with it, but having it be a requirement seems wrong.

futures-rs combines return types and errors. This results in additional complexity when considering its traits when discussing generators. It is a good idea to deal with futures and streams which cannot results in errors. We can instead use Result to indicate that a future or stream can result in an error. This is what I did in my RFC.

I don’t think the R yield Y sugar is a good idea, since you’d typically want to return iterators, futures or streams instead of plain generator types.

There are 2 reasons to have a Wait or Blocked variant on the result enum. You’d want yield x to work in streams without having to write yield State::Yield(x) there. This can be worked around with a yield! macro, with some loss of ergonomics. The other is to allow await for or for-loops to iterate over streams. The loops needs to yield Wait only when the streams it’s waiting on does, so we need that concept in the language. This can again be worked around with a await_for! macros with greater loss of ergonomics.

Note that an await feature would not require the Wait variant as part of the language. In a poll model, await does the same thing as yield from. These are also the same in Python (ignoring some dynamic type checks).

You do mention generators which do not start out paused. These are useful where the generators are consuming input. They also work for futures-rs since it allows computations to start out immediately and well as starting out paused. I think this kind of generators will have to be separate kind of generators in the language, in addition to generators which start out paused. They do not work for iterators, and they aren’t as nice for asynchronous programming since you have to pass around references to the event loop (like how you pass around Handle in tokio).

impl Iterator<Item=usize> + Move doesn’t actually work since built in traits leak through. We’ll probably need some syntax to indicate that a generator is immovable (or movable).


#14

Well, what I had intended to write here but didn’t have space was that streams and futures should probably migrate into the standard library, and that in a generator-context, for-loops should be able to operate not just on IntoIterator but Stream. I think that’s preferable to an await_for macro, which you do mention is not ergonomic.

// for value in stream { body }
loop {
    let value = match stream.poll() {
        Ok(Async::Ready(None)) => { break; },
        Ok(Async::Ready(Some(val))) => Ok(val),
        Ok(Async::NotReady) => { yield; continue; },
        Err(e) => Err(e)
    };
        
    // body
}

Correct, I apologize for my imprecision.

I disagree. I think people are ultimately interested in this so that we have ergonomic ways to write futures and streams. If tokio and futures-rs are going to be as ubiquitous as I think they are, writing implementations of those traits is going to be the first stress test of any design.

As we’ve both shown, a wait variant would make await more general and composable with other features.

I’m starting to agree. Generator and Observer sound like a very sensible pair of traits.