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:
for val in gen {
// Loop Body
}
How should this be desugared?
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.
Arg
╔═══╗ │ ╔═══╗
║ 1 ║ <─┴── ║ 4 ║
╚═══╝ ╚═══╝
│ Ʌ
Return <──┤ │
V │
╔═══╗ ╔═══╗
║ 2 ║ ──┬─> ║ 3 ║ ────> Cancel
╚═══╝ V ╚═══╝
Yield
Stage 1
The generator might complete.
fn stage1(Stage1) -> Result<Stage2, Return>;
Stage 2
The generator yields a value.
fn stage2(Stage2) -> (Stage3, Yield);
Stage 3
You may choose to cancel the generator, consuming it.
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.
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:
let mut generator: Stage1 = ...;
for y in generator {
// loop body
...
if ... {
break;
} else {
continue arg;
}
}
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:
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
:
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
andReadyGenerator
? But I don't know if that is possible, because I don't fully understandPin
.-
If it isn't, I think we should carefully consider the pros and cons of providing stage 1 vs stage 3 generators.
-
I don't think stage 2 or 4 generators are useful enough to warrant inclusion in the API.
-
-
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 freelydrop
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:
- Stage1 = Stage2 ⊕ Return
- Stage2 = Stage3 ⊗ Yield
- Stage3 = Stage4 & Cancel
- Stage4 = Stage1 ⅋ Arg^⊥
-
There is also another
for
-loop issue -- the question of how to extend thefor
syntax to not throw away theReturn
value.- I like the suggestion that the
for
-loop should return the final result of the generator, because I want to be able to call generators from within other generators withfor y in gen { yield y }
.
- I like the suggestion that the
-
This is crossposted from my post on the Rust subreddit, with a few modifications.
- It is also my first post on this forum.