How are generators implemented?

Question

Several languages, such as JavaScript, C#, and Python, have "generator" methods that lazily yield a series of values rather than returning a single one:

function* upToThree() {
  for (let i = 1; i < 3; ++i) {
    console.log(`In generator, i = ${i}`);
    yield i;
  }
}

let g = upToThree();
console.log('Before the loop');
for (const el of g)
  console.log(`In loop, got ${el}`);

/* Console:
Before the loop
In generator, i = 1
In loop, got 1
In generator, i = 2
In loop, got 2
*/

While this feature is convenient to have, it's not obvious how to implement them, especially in a compiled language: local variables can't necessarily be stored on the stack, as the generator could be partially iterated and then passed somewhere else.

What are some strategies for implementing generators?

Answer 1

One possible method, which is what babel does in javascript, is to have a struct containing the current position in the generator then a switch case like construct to be able to start the function in the middle. For example, this:

generator fib() {
    a, b = 1, 2
    while (a<100) {
        b, a = a, a+b
        yield a
    }
    yield a-1
}

can be converted into:

struct fibState {
    a,
    b,
    position
}

int fib(fibState state) {
    switch (fibState.postion) {
        case 0:
            fibState.a, fibState.b = 1,2
            while (a<100) {
                fibState.b, fibState.a = fibState.a, fibState.a+fibState.b
                // switching the context
                fibState.position = 1;
                return fibState.a;
        case 1:
            }

            fibState.position = 2;
            return fibState.a-1
        case 2:
            fibState.position = -1;
    }
}

Yes, C allows you to interleave switch case and loops like that.

Basically, we use a switch case in this case to act as a goto, and allow us to immediately jump to the part of the function we left off. We have a struct which contains all our local variables, and also a variable that tells us where to jump to next time the generator is resumed.

In real assembly the entire switch case and looping construct would be compiled down to gotos.