How do generators work?

I’ve been using generators a bit lately and got curious about how they work.

I mean, pausing and resuming computation? How do you implement this sort of thing? Doesn’t control flow just go step by step, command by command? Is it just programming language magic?

I’d encountered this rabbit hole in the past and hadn’t dug further. But in trying to nurture more joy in programming, I decided to give it a go without setting a practical goal. Sometimes, an exploration is a worthy and fun goal in itself. You can experiment with baking stuff without an actual dish in mind and still be a professional chef, so why not the same with programming?

Turns out, to understand generators, we end up touching on control flow and continuations quite a bit, and even a bit on how programming language interpreters work. Also, to really grok this, go on an adventure and program some stuff along the way yourself too!

So, let’s find out how to build generators by learning about continuations! We’ll start with generators and dig deeper until we find fun, new stuff.

Simple Example: Exceptions

Exceptions are a common example of subverting normal control flow, and are simpler than generators.

def buggy_code():
for i in range(10):
if i == 7: raise Exception("Oh no, a 7!")
else: print(i, end='')
try:
buggy_code()
except Exception:
print("forget it, doing this now")
# 0123456forget it, doing this now

Above, the buggy_code method is being executed, but then the Python interpreter yields control to the error handler that wraps the buggy_code invocation, with a special raise keyword. This can happen regardless of how deep down the buggy_code invocation is.

Simple Example: Generators

Now, an example of using generators to obtain even numbers:

>>> import itertools
# infinite generator of incrementing even numbers
# note: the full range is unbounded -- it's realized one item at a time
>>> gen = (i for i in itertools.count() if i % 2 == 0)
# grab the first 10 even numbers
>>> next(gen)
0
>>> next(gen)
2
>>> list(itertools.islice(gen, 10))
[6, 8, 10, 12, 14, 16, 18, 20, 22, 24]

Above, we use an already defined basic generator itertools.count() which just keeps counting up, and then we make use of it, taking the first 10 values. The underlying range is infinite, but we’re able to do our work in a lazy way, one item at a time.

That (i for i in ...) expression is a generator expression, similar to a list comprehension (which is denoted by [...] instead). Semantically, a generator expression can be thought of as making an anonymous generator function and calling it. And a generator function is a function that calls yield in the body somehow.

Here’s the implicit anonymous generator function that gen = (i for i in itertools.count() if i % 2 == 0) would make:

def __gen(exp):
for i in exp:
if i % 2 == 0:
yield i
gen = __gen(itertools.count())

That yield behaves differently from a return, it essentially makes the invocation of the function produce a generator object, and that generator object produces new values for consumers like next(...) or list(...).

Isn’t it interesting how the control flow seemingly switches back and forth as you keep calling gen.next()?? It’s like a conversation, a boring one but still.

<- The generator does some work and yields control to the console.
-> We type some code and return it to the console with an 'enter'.
<- Then, the generator does some more of the remaining work
and yields control to the console again.

This is different from our usual experience with function invocations. Usually, invocations intuitively seem like they’re “one and done,” with some effects or returned values being the result.

What’s the generator doing?

If we were to make that implicit generator object for real (for pedagogical reasons), it might look like this pseudo code:

class MyGenerator:
def __init__(self, expression):
self.expression = expression
    def my_next_value(self):
## FAKE CODE
value, remaining_expression = $execute_until_yield(self.expression)
self.expression = remaining_expression
return value
my_gen = MyGenerator(lambda: $some_code_that_has_a_yield)

This fake generator object is providing step-by-step, resumable execution of an expression (meaning: any piece of computation, like imagine a function being passed as that argument that itself calls a whole host of other functions). It needs to know about how to execute until the next yield somehow… and it likely needs to hold onto the “remaining computation.”

When the consumer calls my_next_value repeatedly, the my_gen generator object resumes execution of the original code, returns immediately with a value, and pauses the remaining computation again.

But this is… something we don’t have a direct handle on. How would $execute_until_yield even work?

How do we get this kind of control over pausing-and-resuming computation?

And since it needs to be generalized for all possible code you could write, what does “remaining computation” really mean?

Enter: Continuations

A continuation is “remaining computation,” essentially. It makes some sense, then, that a generator would be dealing with continuations. But how do we get more specific?

More and more, I turn to Scheme when building intuition.

Racket’s docs describe their evaluation model so well, I’ll quote them:

Racket evaluation can be viewed as the simplification of expressions
to obtain values. For example, just as an elementary-school
student simplifies
1 + 1 = 2
Racket evaluation simplifies
(+ 1 1) -> 2

Computation can be understood as simply repeated reduction of expressions down to a level where we’re left with just values, a value being anything that can’t be reduced further.

Paraphrasing some other resources here — but basically, operational semantics tries to answer “how is a program executed?”. There have been many presentations of operational semantics, and one of them is reduction semantics (introduced by Hieb and Felleison in ‘92).

The operational semantics for a programming language describe how a valid program is interpreted as sequences of computational steps. With the reduction semantics presentation, the description is a series of reductions.

Back to understanding basic evaluation:

Some simplifications require more than one step. For example:
(- 4 (+ 1 1)) → (- 4 2) → 2
------ -------
An expression that is not a value can always be partitioned into two
parts: a redex, which is the part that changed in a single-step
simplification (highlighted), and the continuation, which is the evaluation
context surrounding an expression.
In (- 4 (+ 1 1)), the redex is (+ 1 1), and the continuation is (- 4 []),
where [] takes the place of the redex. That is, the continuation says
how to “continue” after the redex is reduced to a value.

Continuations are described as the evaluation context surrounding some expression. But that’s just prose!

What does (- 4 []) look like? It’s some kind of closed form that has a hole in it. It looks like a lambda (anonymous function)!

So, continuations can be thought of as just functions!

Let’s apply this idea to understand the even number generators a bit more.

Before looking at Racket code, here’s how to read it if you’re unfamiliar with LISP-like languages:

  • The literal values look like 1, 0.5, 'c, #t, my-func, #hash((a . 1) (b . 2)).
  • Function applications look like (foo bar biz). This is equivalent to, say, foo(bar, bar). foo here is in the function application position (the head of the form), and the parens indicate that this is an s-expression.
  • #lang racket is one of Racket’s superpowers… it makes it easy to make languages and use them like modules, even within the same project. Racket is quite great for making purposeful languages — read more about why that’s useful here.
#lang racket
(require racket/generator)
(define evens
(generator
()
(let loop ([x 1])
(if (zero? (modulo x 2))
(begin
(yield x)
(loop (+ 1 x)))
(loop (+ 1 x))))))
;; and in the console:
> (evens)
2
> (evens)
4

Alright, we see the familiar yield here, inside an infinite iteration counting up from 1.

Let’s say we invoke the generator once: (evens).

What happens is that the generator evaluates some code, produces some effects, and then yields control. In the background, there is a continuation, a function, representing the rest of the computation. Each time this generator is called, it’s then calling this implicit continuation and yielding control.

But how do you implement a generator?

Introducing shift and reset

Racket provides a lot of firepower for us. I enlisted the help of my friend Max (PhD student at Northeastern) to put all this power to good use. I had started the exploration by just reading about call/cc on wikipedia, and after enough experimentation to figure that out and sharing that with Max, Max suggested something even better: shift and reset.

What are shift and reset?

They are control operators that work together to allow you to do things like “non local return”. “The reset operator sets the limit for the continuation while the shift operator captures or reifies the current continuation up to the innermost enclosing reset” (from wikipedia, haha). But let’s unpack that.

When you have an expression you’re trying to compute, you essentially go from the leaves to the root of the tree. For example, (+ (+ 2 3) 4) is a tree with + at the root, and with (+ 2 3) and 4 as the leaves. So, the “remaining computation” roughly corresponds to the earlier parts of the tree. Like in the explanation about redex and continuation, the redex here would be (+ 2 3) (4 is already reduced to a value and can’t be reduced, and the only other leaf not already a value is (+ 2 3)). And the continuation would be (lambda (x) (+ x 4)).

So, reset marks the node of the tree until which the continuation is delimited, and then shiftcaptures the continuation up to that point.

Let’s try to use shift and reset to figure them out:

;; some basics examples
> (require racket/control)
> (reset 3)
3
> (reset (shift k 1))
1
> (reset (shift k (k 1)))
1
;; now, the same buggy_code from above, but with shift/reset!
> (define (buggy-code)
(for-each
(lambda (x) (and (= x 7) (shift k "oh no it's a 7")))
(range 0 10)))
> (reset (print (string-append "Runetime Error: " (buggy-code))))
"oh no it's a 7

This is interesting! We’re able to mimic the behavior of rasing exceptions with shift and reset.

Instead of prose about shift and reset, here are the reduction rules for reset:

1. (reset val) => val
2. (reset E[(shift k expr)]) => (reset ((lambda (k) expr)
(lambda (v) (reset E[v]))))
; where E has no reset

Rule 1 is easy. If the argument that reset is being applied to doesn’t have shift in it, we just reduce the reset form down to that value.

Rule 2 tells us a lot about how this works.

Notice that the reduction removes the shift form in E, and that there’s a sort of switching of things happening. The expr inside the shift form is now the function body of a lambda abstraction, with k as the parameter. Also, what is being provided as the argument to this lambda with the k parameter? It seems like it’s E but with the shift form punched out by the parameter v, inside another lambda abstraction with v as the parameter.

(lambda (v) (reset E[v])) is basically the current continuation. What reset does is to set the outer boundary up to which the continuation is delimited, and what shift does is to “capture” that delimited continuation.

For example, in (reset (print (string-append "Runetime Error: " (shift k "oh no it's a 7")))), the continuation is (lambda (v) (reset (print (string-append "Runetime Error: " v)))).

Continuing that example, the reset would reduce to:

((lambda (k) "oh no it's a 7")
(lambda (v) (reset (print (string-append "Runetime Error: " v)))))

So, when shift captures the delimited current continuation and passes it k as the parameter, it’s doing a control flow switch to that continuation.

Implementing Generators

Turns out, we can implement generators with shift and reset.

Here is an approach by making our own yield to do a non-local return of a value:

> (define (yield x)
(shift k (cons x (k (void)))))
> (reset
(for-each
(lambda (x) (and (zero? (modulo x 2)) (yield x)))
(range 1 10)))
(2 4 6 8 . #<void>)

Above, for-each goes through a list and applies the supplied function to each item. What’s happening is that the supplied function captures the (for-each ...) continuation, since it’s beneath the reset.

As the interpreter starts to reduce this reset form, it follows its reduction rules down to for-each, which essentially becomes a series of function applications that each get applied one by one. For example, here’s the application of the function to 0.

((lambda (x)
(and
(zero? (module x 2))
(yield x)))
0)

Which reduces a bit further to…

((lambda (x)
(shift k (cons x (k (void)))))
0)
; and then...
(shift k (cons 0 (k (void))))

And that shift reduces according to reset’s reduction rules above to:

(lambda (k) (cons 0 (k (void))))

…called with the current continuation, which includes the rest of the for-each, which reduces to just more applications of yield (which only gets called when it’s an even number) just with different values!

And that’s how we end up with:

(2 4 6 8 . #<void>)

It comes down to straightforward reduction of expressions!

Also, here is yet another implementation of a simple “generate one at a time” generator. Max noodled about this and provided this quick example.

(define (generate-one-at-a-time lst)
(define k #f)
(define (go)
(if k
(k)
(reset (let ()
(for-each
(lambda (x)
(shift cur-k
(let ()
(set! k cur-k)
x)))
lst)
‘done))))
go)
;; some usage:
> (define my-gen (generate-one-at-a-time '(1 2 3 4)))
> (my-gen)
1
> (my-gen)
2
> (my-gen)
3

The interesting thing about this one is that it’s all enclosed and feels much more like the generator from the very top of this post. It similarly has the for-each inside the reset, so the continuation contains the full remaining list, but it interestingly maintains and updates some simple state so that it knows where it is and can “resume” properly.

A nice way to sort of fill in the pseudo/fake code we had from before!

End Notes

For more, check out Danvy and Filinski’s Abstracting Control, from 1990. Really good one.

Also, check out pypy’s source code instead of CPython’s if you are itching to dig into the Python implementation. It uses continuations and seemed easier to read to me.

Finally, a big thank you to Max New for his super thorough review.