How do generators work?

(modulo x 2)) (begin (yield x) (loop (+ 1 x))) (loop (+ 1 x))))));; and in the console:> (evens)2> (evens)4Alright, 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 resetRacket 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 7This 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) => val2.

(reset E[(shift k expr)]) => (reset ((lambda (k) expr) (lambda (v) (reset E[v])))) ; where E has no resetRule 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 GeneratorsTurns 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)3The 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 NotesFor 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.

.. More details

Leave a Reply