# Some thoughts on Generators and For-Loops

**URL:** https://internals.rust-lang.org/t/some-thoughts-on-generators-and-for-loops/12014
**Category:** language design
**Created:** [March 23, 2020, 4:37pm UTC](https://internals.rust-lang.org/t/some-thoughts-on-generators-and-for-loops/12014 "2020-03-23T16:37:34Z")
**Posts on this page:** 14
**Page:** 1

<div class="post-metadata">

### Author: ![finegeometer](https://avatars.discourse-cdn.com/v4/letter/f/9fc348/32.png) [@finegeometer](https://internals.rust-lang.org/u/finegeometer)
#### Post date: [March 23, 2020, 4:37pm UTC](https://internals.rust-lang.org/t/some-thoughts-on-generators-and-for-loops/12014/1 "2020-03-23T16:37:35Z")

</div>

_Edit: I am no longer as convinced as I used to be of the utility of `for`-loops over generators with `resume` arguments. But I still think this idea I introduce of stage 1 vs. stage 3 generators is important._

_Original post follows..._

There are issues with getting Rust's generators to work well with `for`-loops. In this post, I would like to explain my view of what generators really are, and show how that sheds light on the problem. I hope this helps!

# The problem

We want `for`-loops to work with generators:

```rust
for val in gen {
    // Loop Body
}

```

How should this be desugared?

```rust
let mut arg = ???;
loop {
    match gen.resume(arg) {
        GeneratorState::Yielded(val) => {
            arg = {
                // Loop Body
            };
        }
        GeneratorState::Complete(_) => break;
    }
}

```

The first time through the loop, we don't have an argument to pass to `resume`!

# What is a generator, really?

In my view, a generator is a cycle of four stages.

```rust
               Arg
        ╔═══╗ │ ╔═══╗
        ║ 1 ║ <─┴── ║ 4 ║
        ╚═══╝ ╚═══╝
          │ Ʌ
Return <──┤ │
          V │
        ╔═══╗ ╔═══╗
        ║ 2 ║ ──┬─> ║ 3 ║ ────> Cancel
        ╚═══╝ V ╚═══╝
              Yield

```

## Stage 1

The generator might complete.

```rust
fn stage1(Stage1) -> Result<Stage2, Return>;

```

## Stage 2

The generator yields a value.

```rust
fn stage2(Stage2) -> (Stage3, Yield);

```

## Stage 3

You may choose to cancel the generator, consuming it.

```rust
fn stage3(Stage3) -> Stage4;
fn cancel(Stage3) -> Cancel;

```

Usually, `Cancel` will be `()`, and `cancel` will be equivalent to `drop`. But I could imagine `Cancel` containing some of the internal state of the generator.

## Stage 4

You must provide a value to the generator.

```rust
fn stage4(Stage4, Arg) -> Stage1;

```

There is a nice duality here:

- In stage 2, the generator gives you a value. In stage 4, you give it a value.
- In stage 1, the generator might decide to stop. In stage 3, you might decide to stop the generator.

In fact, this duality is how I discovered stage 3.

# The problem

I claim that the problem is this:

- For loops want to work on stage 1 generators.
- The current `Generator` trait describes stage 3 generators.

## Loop

Desugaring of a `for`-loop over a stage 1 generator:

```rust
let mut generator: Stage1 = ...;
for y in generator {
    // loop body
    ...
    if ... {
        break;
    } else {
        continue arg;
    }
}

```

```rust
let mut generator: Stage1 = ...;
loop {
    match stage1(generator) {
        Ok(s2) => { 
            let (s3, y) = stage2(s2);

            // loop body
            ...
            if ... {
                let _: Cancel = cancel(s3);
                break;
            } else {
                generator = stage4(stage3(s3), arg);
                continue;
            }
        }
        Err(_) => {
            break;
        }
    }
}

```

## Current Generator trait

Here is part of the [current definition of Generator](https://github.com/rust-lang/rust/blob/master/src/libcore/ops/generator.rs):

```rust
trait Generator {
    ...
    /// If `Complete` is returned then the generator has completely finished
    /// with the value provided. It is invalid for the generator to be resumed
    /// again.
    ...
    fn resume(self: Pin<&mut Self>, arg: R) -> GeneratorState<Self::Yield, Self::Return>;
}

```

Compare that to this function on `Stage3`:

```rust
fn resume(s: Stage3, arg: Arg) -> Result<(Stage3, Yield), Return> {
    let s: Stage4 = stage3(s);
    let s: Stage1 = stage4(s, arg);
    let s: Stage2 = stage1(s)?;
    Ok(stage2(s))
}

```

In both cases, the function acts on a generator, and returns either a `Yield` or a `Return`. If you get a `Yield`, you get the generator back. If you get a `Return`,

- In the `Stage3` implementation, you don't get the generator back.
- In the current `Generator`, you get it back but it is now invalid.

# Conclusion

A generator is a cycle of four stages. `for`-loops make sense over stage 1 generators. The `Generator` trait describes stage 3 generators. This mismatch is the cause of the trouble.

# P.S.

(A collection of random notes)

- Personally, I would like to see a generator API that provides types for both stage 1 and stage 3 generators. Maybe `WaitingGenerator` and `ReadyGenerator`? But I don't know if that is possible, because I don't fully understand `Pin`.

- Current generator syntax defines stage 3 generators, but this could probably be changed.

- I would be fine with leaving `Cancel` out of the design. The fact that we can freely `drop` things removes much of its utility. And I don't see a nice way to integrate it into the generator syntax.

- A `for`-loop over a stage 2 generator also makes sense, and the body of the loop is guaranteed to run at least once.

- If you know linear logic / linear type theory, you might like this description of the generator cycle:

- There is also another `for`-loop issue -- the question of how to extend the `for` syntax to not throw away the `Return` value.

- This is crossposted from [my post](https://www.reddit.com/r/rust/comments/fn2345/some_thoughts_on_generators_and_for_loops/) on the Rust subreddit, with a few modifications.

---

<div class="post-metadata">

### Author: ![lachlansneff](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/lachlansneff/32/5924_2.png) [@lachlansneff](https://internals.rust-lang.org/u/lachlansneff)
#### Post date: [March 23, 2020, 4:47pm UTC](https://internals.rust-lang.org/t/some-thoughts-on-generators-and-for-loops/12014/2 "2020-03-23T16:47:07Z")

</div>

Why not just assume the args is `()`? I can't imagine that wanting resume args in an iterator generator will be very common, and if the user does want that, they can write some sort of adapter that does that for them.

---

<div class="post-metadata">

### Author: ![finegeometer](https://avatars.discourse-cdn.com/v4/letter/f/9fc348/32.png) [@finegeometer](https://internals.rust-lang.org/u/finegeometer)
#### Post date: [March 23, 2020, 5:35pm UTC](https://internals.rust-lang.org/t/some-thoughts-on-generators-and-for-loops/12014/3 "2020-03-23T17:35:08Z")

</div>

> [@lachlansneff](#):
>
> Why not just assume the args is `()` ? I can't imagine that wanting resume args in an iterator generator will be very common, and if the user does want that, they can write some sort of adapter that does that for them.

Nearly any use of generators, including those with arguments, will end in iterating over them. I don't want that to require this boilerplate:

```rust
let mut tmp = ...;
loop {
    match (yield gen.resume(tmp)) {
        Yielded(y) => tmp = { /* Loop Body */ },
        Complete(r) => break r;
    }
}

```

As an important special case, suppose you are dealing with a complicated generator:

```rust
|arg: Arg| {
    // Lots of code
    while ... {
        // Lots of code
    }
    // Lots of code
}

```

You might want to refactor so that that `while`-loop is in its own generator. Currently, that requires the above boilerplate. Even if there were a `map` function for generators, you couldn't use it here, because the loop body might call `yield`!

If generators were compatible with `for`-loops, you could just say this:

```rust
|arg: Arg| {
    // Lots of code
    for y in other_generator {yield y}; // other_generator contains the `while`-loop
    // Lots of code
}

```

---

<div class="post-metadata">

### Author: ![PoignardAzur](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/poignardazur/32/6464_2.png) [@PoignardAzur](https://internals.rust-lang.org/u/PoignardAzur)
#### Post date: [March 23, 2020, 5:42pm UTC](https://internals.rust-lang.org/t/some-thoughts-on-generators-and-for-loops/12014/4 "2020-03-23T17:42:57Z")

</div>

Personally, I really wouldn't expect the "return" value of a for loop to be the value passed to the generator's resume argument (especially in case where it's not obvious that the object being iterated is a generator).

Honestly, I don't really see any use case where the syntax you suggest would be idiomatic or natural.

---

<div class="post-metadata">

### Author: ![finegeometer](https://avatars.discourse-cdn.com/v4/letter/f/9fc348/32.png) [@finegeometer](https://internals.rust-lang.org/u/finegeometer)
#### Post date: [March 23, 2020, 5:48pm UTC](https://internals.rust-lang.org/t/some-thoughts-on-generators-and-for-loops/12014/5 "2020-03-23T17:48:20Z")

</div>

> [@lachlansneff](#):
>
> I can't imagine that wanting resume args in an iterator generator will be very common

I would expect people to invent unexpected uses for generators, especially if they are eventually stabilized. For instance, I am currently experimenting with modeling a game loop with `Generator<Event, Yield = (), Return = !>`.

---

<div class="post-metadata">

### Author: ![finegeometer](https://avatars.discourse-cdn.com/v4/letter/f/9fc348/32.png) [@finegeometer](https://internals.rust-lang.org/u/finegeometer)
#### Post date: [March 23, 2020, 6:16pm UTC](https://internals.rust-lang.org/t/some-thoughts-on-generators-and-for-loops/12014/6 "2020-03-23T18:16:01Z")

</div>

> [@PoignardAzur](#):
>
> Personally, I really wouldn't expect the "return" value of a for loop to be the value passed to the generator's resume argument (especially in case where it's not obvious that the object being iterated is a generator).
> 
> Honestly, I don't really see any use case where the syntax you suggest would be idiomatic or natural.

I got the idea from [https://internals.rust-lang.org/t/pre-rfc-generator-integration-with-for-loops/6625/11](https://internals.rust-lang.org/t/pre-rfc-generator-integration-with-for-loops/6625/11).

But that is a fair criticism. I'll have to think of some examples before I decide whether I agree. I do think there should be _some_ nice way to iterate over generators with return arguments, though. And a `for_each` combinator isn't enough, because we may want to `yield` in the body of the loop.

But I honestly think that the stuff about `for`-loops is the less-interesting part of my post. The more interesting part is the idea that there are different kinds of generators (stage 1 and stage 3), and that they are useful in different circumstances.

---

<div class="post-metadata">

### Author: ![endsofthreads](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/endsofthreads/32/1769_2.png) [@endsofthreads](https://internals.rust-lang.org/u/endsofthreads)
#### Post date: [March 23, 2020, 6:43pm UTC](https://internals.rust-lang.org/t/some-thoughts-on-generators-and-for-loops/12014/7 "2020-03-23T18:43:08Z")

</div>

I might be misunderstanding something critical here, so I apologize in advance.

Assuming the following trait implementation:

```rust
impl<T> Iterator for Generator<R = (), Yield=T, Return=()> {
    type Item = T;
    
    fn next(&mut self) -> Option<T> {
        match self.resume() {
            GeneratorState::Yielded(value) => Some(value),
            GeneratorState::Complete(_) => None
        }
    }
}

```

...and a hypothetical shorthand for defining generators as standalone functions along the lines of:

```rust
gen fn evens() -> i32 {
    for i in 0..20.filter(|i| i % 2 == 0) {
        yield i;
    }
}

gen fn odds() -> i32 {
    for i in 1..20.filter(|i| i % 2 == 1) {
        yield i;
    }
}

```

Why wouldn't the following code work?

```rust
for i in evens() {
    for j in odds() {
        dbg!(i, j);
    }
}

```

* * *

> I would expect people to invent unexpected uses for generators, especially if they are eventually stabilized. For instance, I am currently experimenting with modeling a game loop with `Generator<Event, Yield = (), Return = !>` .

> But that is a fair criticism. I'll have to think of some examples before I decide whether I agree. I do think there should be _some_ nice way to iterate over generators with return arguments, though. And a `for_each` combinator isn't enough, because we may want to `yield` in the body of the loop.

I am _really_ wary of trying to find an ideal, highly general solution for this use-case when we can solve concrete issues today, allowing people to easily create streams and iterators without needing manual implementations or interacting with `Pin`. I'd really hate for perfect to become the enemy of good, especially when more exotic variations on generators could be explored in libraries with macros.

---

<div class="post-metadata">

### Author: ![finegeometer](https://avatars.discourse-cdn.com/v4/letter/f/9fc348/32.png) [@finegeometer](https://internals.rust-lang.org/u/finegeometer)
#### Post date: [March 23, 2020, 7:20pm UTC](https://internals.rust-lang.org/t/some-thoughts-on-generators-and-for-loops/12014/8 "2020-03-23T19:20:45Z")

</div>

> [@endsofthreads](#):
>
> I am _really_ wary of trying to find an ideal, highly general solution for this use-case when we can solve concrete issues today...

This makes sense.

One specific issue I worry about is refactoring complex generators into smaller pieces. As an example, let's take my experiment where I model a game loop as a `Generator<Event, Yield = (), Return = !>`. Here is some sample code:

```rust
let game_loop = |mut event| {
    loop { // Game Loop
        match event {
            Key("e") => {
                loop { // Inventory Loop
                    match (yield) {
                        Key("e") => break,
                        ...
                    }
                }
            }
            ...
        }
        event = yield;
    }
};

```

I would like to factor the inventory loop into its own generator:

```rust
let inventory_loop = |mut event| {
    loop { // Inventory Loop
        match event {
            Key("e") => break,
            ...
        }
    }
    event = yield;
}

let game_loop = |mut event| {
    loop { // Game Loop
        match event {
            Key("e") => {
            	while let GeneratorState::Yielded(()) = inventory_loop.resume(yield) {}
            }
            ...
        }
        event = yield;
    }
};

```

... ... ...

Ok, that's nowhere near as much boilerplate as I was expecting. Never mind.

---

<div class="post-metadata">

### Author: ![PoignardAzur](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/poignardazur/32/6464_2.png) [@PoignardAzur](https://internals.rust-lang.org/u/PoignardAzur)
#### Post date: [March 23, 2020, 8:15pm UTC](https://internals.rust-lang.org/t/some-thoughts-on-generators-and-for-loops/12014/9 "2020-03-23T20:15:27Z")

</div>

Also, "removing boilerplate" is the kind of design problem that should really be solved last, when a working implementation has been shipped and developers have used it in various real-life context so we can get a good model of what the boilerplate actually is.

---

<div class="post-metadata">

### Author: ![endsofthreads](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/endsofthreads/32/1769_2.png) [@endsofthreads](https://internals.rust-lang.org/u/endsofthreads)
#### Post date: [March 23, 2020, 9:05pm UTC](https://internals.rust-lang.org/t/some-thoughts-on-generators-and-for-loops/12014/10 "2020-03-23T21:05:14Z")

</div>

> [@finegeometer](#):
>
> Ok, that's nowhere near as much boilerplate as I was expecting. Never mind.

Glad to hear! It's always fun to realize you can get away with the "ugly" solution, and besides, the "ugly" solution is rather nice!

> [@PoignardAzur](#):
>
> Also, "removing boilerplate" is the kind of design problem that should really be solved last, when a working implementation has been shipped and developers have used it in various real-life context so we can get a good model of what the boilerplate actually is.

+1 to that. I think about the canonical example of syntax simplification/reduction in Rust, is the `?` operator. For those unfamiliar, Rust went from `match`ing on a result, to the `try!` macro, to the `?` operator. Trying to come up with a nice syntax for resuming a generator feels a bit like trying to come up with the `?` operator before `match`ing on a result was even supported.

* * *

I'm sure others can weight in on this, but the main thing blocking the stabilization of some subset of functionality with generators as outlined in [withoutboats's "async interview"](http://smallcultfollowing.com/babysteps/blog/2020/03/10/async-interview-7-withoutboats/#full-generality-considered-too-dang-difficult) is a champion to push through the RFC + getting this feature implemented in the compiler?

---

<div class="post-metadata">

### Author: ![RustyYato](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/rustyyato/32/13627_2.png) [@RustyYato](https://internals.rust-lang.org/u/RustyYato)
#### Post date: [March 23, 2020, 11:09pm UTC](https://internals.rust-lang.org/t/some-thoughts-on-generators-and-for-loops/12014/11 "2020-03-23T23:09:12Z")

</div>

Also note that you could use the `while let` syntax for generators if you don't care about the return value

```rust
while let GeneratorState::Yielded(item) = generator.resume(argument) {
}

```

---

<div class="post-metadata">

### Author: ![finegeometer](https://avatars.discourse-cdn.com/v4/letter/f/9fc348/32.png) [@finegeometer](https://internals.rust-lang.org/u/finegeometer)
#### Post date: [March 23, 2020, 11:36pm UTC](https://internals.rust-lang.org/t/some-thoughts-on-generators-and-for-loops/12014/12 "2020-03-23T23:36:10Z")

</div>

I should mention that while I no longer care about the `for`-loop issue, I still like the idea I outlined about the different stages of the generator cycle. I'm thinking it may have been a mistake to present it as I did, because all of the focus ended up on the `for`-loop syntax, rather than the interesting part.

---

<div class="post-metadata">

### Author: ![PoignardAzur](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/poignardazur/32/6464_2.png) [@PoignardAzur](https://internals.rust-lang.org/u/PoignardAzur)
#### Post date: [March 24, 2020, 8:42am UTC](https://internals.rust-lang.org/t/some-thoughts-on-generators-and-for-loops/12014/13 "2020-03-24T08:42:34Z")

</div>

I mean, I don't really get how that's a better abstraction than "stage 1 is when it's yielding something, stage 2 is when it returns something".

As you point out yourself, the "cancel" value is usually empty (unless we want to implement cancel tokens, but I don't think resume arguments are relevant then); and if the "return" value is empty (or bottom), then you essentially have a regular iterator.

I don't get what your abstraction brings in concrete terms that iterators don't have.

---

<div class="post-metadata">

### Author: ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)
#### Post date: [June 22, 2020, 8:52am UTC](https://internals.rust-lang.org/t/some-thoughts-on-generators-and-for-loops/12014/14 "2020-06-22T08:52:28Z")

</div>

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