Co-routines
On this page
Note: Generators are built: a function declared yields, with yield and yield each, among a module's functions or as a method of a struct, generic or not. A generator may not be inline, have a where clause, or be a method of a trait, an enum, an actor or a type that declares lifetimes. A pub generator of a library is walked by the packages that import it. each walks one, as it walks any value with a next. Two-way yield (the last section) is an idea that is not built.
A generator is a function that hands its caller values one at a time. It runs until it reaches a yield, gives the caller the value written there, and waits. When the caller asks for the next value it goes on from that yield, with its local variables as they were. It is a function whose result is a sequence, written as the loop that makes the sequence:
fn count(n i64) yields i64 {
mut i = 0i64;
while i < n {
yield i;
i = i + 1i64;
}
}
After yields comes the type of each value handed out. Calling count(4i64) runs nothing. It gives a value that holds the parameters, and every call of its next runs the body up to the next yield. next gives Some(value) for each value handed out and None once the body ends, by its last statement or by a return, which takes no value:
mut g = count(4i64);
while true {
match g.next() {
case imm v Some { printInt(v); } // 0 1 2 3
case is None { break; }
}
}
each x in count(4i64) { printInt(x); } // the same, 0 1 2 3
A loop that leaves early, by break or return, leaves the generator suspended, and it dies there (see Dying).
The value a generator gives is a struct made for it, of a type no source names. A message that has to spell it writes count.Gen. Since no source can write that type, a function cannot declare a generator as its result or a struct as a field. It is a move type: it is moved, not copied, so two walks of one generator never run. Having next(self &mut) Option[i64], it complies with core's Iterator[i64] as any cursor does, so it is passed to generic code bounded by that trait, or lent as a virtual reference:
fn sum[S Iterator[i64]](s &mut S) i64 { ... }
fn sumVirtual(s &<mut Iterator[i64]) i64 { ... }
...
mut g = count(4i64);
sum(&mut g);
A yield is a statement of its own. It stands in a block, or in the arms of an if or match written as statements, and in a loop, but not inside an expression: f(a(), if c { yield 1; 2; } else { 3; }) would have to keep the value of a() across the wait, and is refused. Compute it into a variable first.
Yielding another generator's values#
yield each hands on every value of another generator, or of anything with a next, in turn, and goes on when they are all handed on. It joins sequences, and it makes a recursive walk as short as the recursion:
fn joined(a i64, b i64) yields i64 {
yield each count(a);
yield 99;
yield each count(b);
}
// In order, a tree kept in an array
fn inorder(nodes &Array[Node], at usize) yields &Node {
imm n = &nodes[at];
if n.left >= 0 { yield each inorder(nodes, usize.from(n.left)); }
yield n;
if n.right >= 0 { yield each inorder(nodes, usize.from(n.right)); }
}
The generator being handed on is kept in the one that hands it on, in its own storage, when its size is known. A generator that hands on one of its own kind, as inorder does, would have to hold itself, so that one is kept on the heap, one for each yield each that needs it, made when the walk begins and freed when the generator dies. A value handed on is the sub-generator's own Some(value): it is moved up, not copied. Each value costs a step through every generator that hands it on.
Generator methods#
A method may be a generator, called as any method is. In its body self is the receiver, exactly as in any method. The generator holds the receiver as it holds a parameter, so what the receiver was lent as keeps it lent for as long as the generator lives:
struct Tree {
nodes Array[Node, 7];
fn walk(self &) yields &Node { // in order
yield each self.from(0);
}
fn from(self &, at usize) yields &Node {
imm n = &self.nodes[at];
if n.left >= 0 { yield each self.from(usize.from(n.left)); }
yield n;
if n.right >= 0 { yield each self.from(usize.from(n.right)); }
}
}
each n in tree.walk() { printInt(n.val); }
- A receiver borrowed with self & may be read, not changed, while the generator may still be resumed; one borrowed with self &mut may be neither read nor changed. The generator may change what it was lent, and may hand out borrows of it, yields &mut i64 among them. The borrow lasts until the generator dies, not until it is last called: a block around the generator ends it.
- A receiver taken by value, fn run(self) yields i64, moves into the generator and dies with it, after its locals. As with any parameter, the body may borrow or copy it (and change it, if declared mut self), not move it out.
- Self in the body is the type the method belongs to.
- A bare name that is a field of the receiver's type means self.name, as it does in any method, unless a local or a parameter of the generator is named so, which shadows it. A bare name of a method of the type is refused: write self.name().
- A function of a type with no receiver, fn range(from i64, to i64) yields i64, is a generator too, called as Span.range(3, 7).
The method that makes the generator is the one written; the struct that is the generator is made beside the type and has no name in source (a message spells it Tree.walk.Gen). A method of a trait or of an enum cannot be a generator, since a trait's methods are copied into each type that implements it and an enum's into each of its variants; nor can an actor's, or a method of a type that declares lifetimes. Write a function that takes what the method would.
Generic generators#
A generator may be generic, a function over a type or a method of a generic type or both. The struct that is the generator takes the type parameters, with their bounds as written, so each use is a generator of its own kind, made for the types it was called with, and checked as any generic is, where it is used:
fn items[T](l &List[T]) yields &T { ... }
struct Bag[T] {
all List[T];
fn backward(self &) yields &T { ... }
}
each x in items(&ints) { ... } // a generator over i64
each p in items(&points) { ... } // another, over Point
each p in bag.backward() { ... }
A generic generator may hand on another, itself included, with yield each, and a recursive one keeps its sub-generator on the heap in each instance as a plain one does. A type parameter of a generator does not name lifetimes ([T + 'a]) yet.
Generators across packages#
A pub generator of a package, a function, a method or a method of a generic type, can be walked from another package as it is from its own. The struct that is the generator, and the frame that holds its locals across a yield, are made from its body, so the package's include file carries the generator's declaration whole, as it carries an inline or a generic function, and the importer makes the struct again from it. What the body names in the package, a private type, a private function or another private generator, is declared beside it and exported. A generator that is not pub stays inside the package, unless a body the include file carries names it; neither it nor the private names only it uses are in the file, and no other package can name them.
Borrows across a yield#
A yield leaves the body, and the generator, a value, may be moved by its caller before it is resumed. What the body keeps across a yield is held in the generator's value, so:
- A borrow of what the generator was lent, a parameter that is a reference, lasts across it. So does a copy of any value.
- A borrow of one of the body's own local variables, or of a parameter the generator holds by value, does not last: it ends at the yield, and it is an error to use it after. The error names the yield.
- What a yield hands the caller may borrow only what the generator was lent. It is a borrow of that, not of the generator, so a caller may keep a value handed out for as long as the generator lives, several of them at once.
- So the body holds each borrow it has handed out, from the yield to the end of the body, as if a variable of its own held it. It may go on reading what it lent, or change another part of it, but it may not change the thing the borrow points into, or call anything that could change the shape of the collection it points into (a push or a clear on a list). The error is at the change. Copy the value to hand it out, or hand out the borrow once the body has done changing what it borrows.
fn words(text &str) yields &str { // each word borrows the text
...
yield &text[start ..< i];
...
}
fn grows(xs &mut List[i64]) yields &i64 {
yield xs[0usize];
xs.push(1i64); // ERROR: the caller may still hold the borrow just yielded,
// and the push could move the list's elements
}
fn bad(k i64) yields i64 {
mut x = 5i64;
imm r = &x;
yield k; // ERROR: r borrows a local, which cannot last across this yield
yield *r;
}
The parameters are held in the generator, and the body names them as a method names its fields. It may borrow or copy one, or change one declared mut, but it may not move one out. A parameter lives as long as the generator does, not as long as the body, and dies after the locals.
Dying#
The locals of the body die as they would in a function, in the order they were declared, last first, where the body ends. A generator that dies while it waits at a yield finalizes the locals it holds there, in the same order, and then its parameters. One never run holds only its parameters. A local moved on some paths only is finalized only if it still holds its value, as anywhere.
Two-way yield#
This is an interesting idea which may or may not end up in the language in something like this form. None of it is built.
Co-routines are functions able to suspend their execution back to their caller using the yield statement. The caller may later resume the co-routine where it left off. Information may be exchanged between the caller and co-routine at each yield and resumption.
// A type defining what might yield, and what is expected back
yieldenum Number {
even(i32) i32;
odd(i32) i32;
}
// A co-routine that yields according to the protocol
fn gen(n i32) yields Number {
while n {
if n & 1 {
n += yield odd(n);
} else {
n -= yield even(n);
}
}
}
// Make use of the co-routine
fn main() {
genner = executer.spawn(gen);
while {
match genner(10) {
even(n): TBD;
odd(n): TBD;
_: break;
}
}
}