Generators¶
In Control, we implemented a rudimentary way to define and work with generators in our small stack-based language. In this section, we’ll see how Racket provides us with full continuations that can be used for this purpose.
call/cc
and let/cc
¶
When working with our now-familiar “distance” function, (sqrt (+ (* dx dx) (* dy dy)))
,
we saw how we can get “the rest of the computation that’s supposed to happen after (* dx dx)
”
by β-abstracting over (* dx dx)
to get (λ (dx2) (sqrt (+ dx2 (* dy dy))))
. Racket/Scheme
provide access to this function for us. We just have to ask!
Terminology
The function that represents “the rest of the computation” at any given evaluation point (i.e. sub-expression) is called the current continuation at that point. This function will differ depending on which sub-expression is under consideration, since what remains to be done will differ.
In the “distance” expression, to get access to the current continuation at the
time we’re evaluating the (* dx dx)
(note that the language talks about
the dynamic state of the program, not its lexical structure) can be obtained
using call/cc
(read as “call with current continuation”) like this –
(sqrt (+ (call/cc (λ (k) (k (* dx dx)))) (* dy dy)))
The entire (call/cc (λ (k) (k (* dx dx))))
is simply equivalent to (* dx dx)
.
One way to understand this is to think of the k
continuation as labeling
the dynamic return point of the call/cc
invocation that is providing it.
So call k
with some value will result in the entire call/cc
expression that provided that k
completing its computation with the
value as its result. In the above code, we’re supplying (* dx dx)
to
k
, and so the whole call/cc
expression is equivalent to (*
dx dx)
. So you could think of it as (call/cc (λ (return) (return (* dx
dx))))
and that would be correct.
It can get quite cumbersome to write lambdas every time we use call/cc
, so
Racket/Scheme provides some syntactic sugar for it – let/cc
that is convenient.
(let/cc k ...some-expression-using-k...)
; desugars into
(call/cc (λ (k) ..some-expression-using-k...))
i.e., let/cc
introduces the local variable k
into the expression
much like let
.
You could ask “so what?”. Having access to the current continuation as a value gives us many super powers – we can implement many different types of control flow within our program with this as a primitive. For example, since the continuation is available as a value, we can store it away to be called later on. This is what we need to implement generators.
Python generators¶
In python, you can return from a function in two ways –
Using the
return <value>
statement.Using the
yield <value>
statement.
While return
finishes the calculations that the function was doing, yield
merely suspends it at that state. It means you can resume from that dynamic point
and continue on to the next yield
. While all code that follows return
is dead code, you can have multiple yield
statements in the code and the function
will suspend every time it encounters such a yield
.
A function that uses yield
is called a “generator” in python. Similar
constructs in other languages may be called “co-routines” or “asynchronous
functions” when combined with event loops. Though some subtle differences exist
between these various presentations exist, they’re all basically the same idea
underneath – the idea of “reified continuations”. The word “reified” in CS is
used to mean “made real” – i.e. made into a value that can be used like a
value.
Consider the following code sequence.
def silly_gen():
print("Generating 'one'");
yield "one"
print("Generating 'two'");
yield "two"
print("Generating 3");
yield 3;
print("Generating 4");
yield 4;
g = silly_gen(); # Prints nothing
next(g)
#> Generating 'one'
#> 'one'
next(g)
#> Generating 'two'
#> 'two'
next(g)
#> Generating 3
#> 3
next(g)
#> Generating 4
#> 4
next(g)
#> Traceback (most recent call last):
#> File "<stdin>", line 1, in <module>
#> StopIteration
#
# (This last bit could differ depending on where you run this code)
What’s happening there?
With the first call to
silly_gen()
, we create a “generator object” that can suspend and resume computations. No computation has actually started just yet though, as noted by “Generating ‘one’” not being printed at that point.Every time we cann
next(g)
, we resume the generator and cause it to run until the nextyield
. The return value of thenext(g)
call is what was given as the value inyield <value>
.Once we run out of yields, python arranges to terminate the code by raising an exception named
StopIteration
.
We’ll now see how to implement that in Racket. The idea is that in any language
that gives us the equivalent of call/cc
(like our stack language to which
we gave that power in Control), we can follow the same thinking. What we
won’t do here is to develop generator syntax in Racket. We’ll merely show how
to mechanically produce generator-like behaviour. Once you learn how to define
your own syntax in Racket, it then becomes a simple matter to mechanically translate
generator code to produce the necessary constructs.
Generators in Racket¶
We want to be able to write something like this –
(generator (a b c)
(yield "one")
(yield "two")
(yield 3)
(yield 4))
… as a parallel to the python code.
Let’s start with treating the generator as an ordinary lambda –
(define (gen)
(let/cc return
;...
))
The return
captures the dynamic continuation point at the point of call
of (gen)
. We will need to return something to that point to help
control the progress of the generator. What could the “yield” point look like?
(define (gen)
(let/cc return
;...
(let/cc resume (yield (list "one" resume)))
))
The “list of two values” is a placeholder mechanism to pass on the resume point to the
point at which next
call is happening. We’re yet to determine the yield
though.
What should yield
be? If we treat it as a function that doesn’t return to the point
(unless resumed), we can see that it is essentially a continuation. What continuation is it
though?
Note
Think about it for a bit and see if you can answer it.
The yield continuation is expected to come from the caller’s dynamic call point. So we need a mechanism for the caller to pass their continuation into the generator so it can yield contro back to that call point when it wants to pause.
We therefore see that there are two bits of shared state information we need to have for each generator instance – one channel passes a resume continuation from the generator to the caller and another channel passes a yield continuation from the caller into the generator. Let’s use a box for each of these.
(define (gen)
(let/cc return
(define yield-box (box #f))
(define resume-box (box #f))
(define (yield val) ((unbox yield-box) val))
;...
))
… but we want “yield” to also enable resumption. For that we can roll the
let/cc resume
into the yield and put that continuation into the
resume-box
.
(define (gen)
(let/cc return
(define yield-box (box return))
(define resume-box (box #f))
(define (yield val)
; Mark the point where we want the code that calls "next"
; to resume from.
(let/cc resume
; Store this resume point in the resume-box accessible to
; the generator user.
(set-box! resume-box resume)
; Return to the caller at the marked yield point provided by
; the caller. In the very first instance, this will return to
; the point where the generator is being created by calling
; (gen). In that case alone, we pass the caller both the
; yield-box and resume-box.
((unbox yield-box) val)))
(yield (list yield-box resume-box)) ; Pass the channels to the caller at
; the generator creation point.
; Ordinary generator code using yield like a function.
; ...
(yield "one")
; ...
))
(define g (gen))
; g is now a list of yield-box and resume-box
(define (next g val)
(let/cc yield
(let ([yield-box (first g)]
[resume-box (second g)])
(set-box! yield-box yield)
((unbox resume-box) val))))
(next g #f) ; The value is currently unused, but could be used if needed.
; As much as the generator is capable of passing a value back
; to the caller, the caller can also pass values back into the
; generator which will become the result of the (yield ..)
; expression.
Notice how the beginning part of the generator is completely independent of what the generator actually does – i.e. it is “boiler plate code” that can be auto generated.
Exercise
Try out the above version of the generator on your own. Explore what’s
possible with this. In particular explore the idea of the yield function
itself being a first class value in our scheme of things. This is more
powerful than Python generators where yield
is a keyword and not
a value that can be passed out. In our case, for example, you can pass this
yield funciton down as arguments to other functions as well.
Let’s see if we can absorb the boiler plate code into a reusable function.
Given we’re representing the generator state as a pair of boxes that contain
continuations, we can start there and model our generator as a lambda that
takes an extra parameter as its first argument, called yield
.
i.e. we want to write our generator as –
(lambda (yield arg1 arg2 ...)
;...
(yield val)
;...
(yield val)
;...
)
(define (generator genfn . args)
(let/cc return
(define yield-box (box return))
(define resume-box (box #f))
(define (yield val)
(let/cc resume
(set-box! resume-box resume)
((unbox yield-box) val)))
; Pass the generator state to the caller for use by "next".
(yield (list yield-box resume-box))
; Call the generator function with our newly minted "yield" function
; as the first argument.
(apply genfn (cons yield args))))
Now, we can easily write the above python code like this –
(define g (generator (λ (yield) (map yield '("one" "two" 3 4)))))
; Note that we can't map the yield function like this in Python
; because in Python yield is not a function or a value that works
; as one.
(next g #f)
(next g #f)
(next g #f)
(next g #f)
You can also make generator
a bit more convenient to use by
uncurrying the args
.
(define (generator genfn)
(lambda args
(let/cc return
(define yield-box (box return))
(define resume-box (box #f))
(define (yield val)
(let/cc resume
(set-box! resume-box resume)
((unbox yield-box) val)))
; Pass the generator state to the caller for use by "next".
(yield (list yield-box resume-box))
; Call the generator function with our newly minted "yield" function
; as the first argument.
(apply genfn (cons yield args)))))
(define gen (generator (λ (yield . args) (for-each yield '("one" "two" 3 4)))))
; With this form, the function `generator` works like a word that
; declares the given lambda function to be a generator. You can then call
; the produced functions to make make independently evolving generator instances.
(define g (gen))
(next g #f)
;...
Enjoy … and the journey always continues on!
Exercise
Notice that if you call next
one too many a time, you get an error.
How can you arrange for the generator to finish its calculations
gracefully?
Hint: Attend to where the result expression of the genfn is returning its value to. Where should it return to? .. and what can it possibly return to signal the end?
Search as a language feature¶
Many popular languages today have a language feature usually going by the name “set comprehension”, “list comprehension”, “array comprehension” or “dictionary comprehension”. The essence of these constructs is nested for-loop iteration where values are produced based on the for loop iterations which meet some criteria expressed as a boolean constraint on the values being enumerated.
Generators are closely linked with comprehensions and languages like Julia even make generators use the same syntax as comprehensions. So it is not unreasonable to expect that the ideas we developed above can serve to explore a space of variable values that need to meet some constraints. For example, let’s consider a toy problem of finding pythagorean triplets.
def pytriplets(m, n):
for x in range(m, n):
for y in range(m, n):
for z in range(m, n):
if x*x+y*y == z*z:
yield (x,y,z)
How can we model this kind of searching using our scheme of things. First off,
we need to realize that the inner-most for loop gets to run fully for each of
the outer for loops – i.e. the search is depth first. This kind of a
search can be modeled using a stack, where the top state of the stack captures
the state of the inner loop. Similar to what we did above, we will need
yield
to be modeled as “try to find one more case”. One other point to
note here is that there is a role played by the “else” part of the if – it
tries the next possible set of values for x,y,z. We’ll model that instead of
yield directly, because with search, we’re interested in finding one solution
(at least for starters).
And what we’ll use here is a stack of continuations!
(define stack (box empty))
(define (push val)
(set-box! stack (cons val (unbox stack))))
(define (pop)
(let ([top (first (unbox stack))])
(set-box! stack (rest (unbox stack)))
top))
(define (try-again)
((pop)))
(define (ensure bool)
(when (not bool)
(try-again)))
; range produces one value at a time. If you don't
; like it, you can call (try-again) to get another.
(define (range m n)
(let/cc return
(let/cc trynext
(push trynext)
(return m))
(if (< m n)
(range (+ m 1) n)
(try-again))))
(define (pytriplets m n)
(let ([x (range m n)]
[y (range m n)]
[z (range m n)])
(ensure (equal? (* z z) (+ (* x x) (* y y))))
(list x y z)))
Now, if you call, say, (pytriplets 10 50)
, it will return a list
of three numbers that form a triplet. If you’re not happy and want another,
you can invoke (try-again)
to get the next one.
> (pytriplets 10 50)
'(10 24 26)
> (try-again)
'(12 16 20)
> (try-again)
'(12 35 37)
> (try-again)
'(14 48 50)
> (try-again)
'(15 20 25)
> (try-again)
'(15 36 39)
>
That was fun, wasn’t it?
Question
Notice that the next result isn’t being returned from the (try-again)
.
Why is that? Do you want to change that behaviour? If so, how would you?
Also, why is the result being printed out even though we aren’t writing it
out explicitly and are simply returning a list from pytriplets
?
Terminology
This kind of behaviour is referred to as “non-determinism” in a language.
We know that the program is quite deterministic alright, but the reason the
term is used is that at the point where the (range m n)
function
call returns, the result could be any value in the range that meets
criteria that’s going to be specified later in the program. So at that
point, we don’t truly know what value it is going to produce.
Exercise
Write an options
function similar to range
that behaves like
this – It takes any number of arguments and, just as range runs over integers
from the first arg to the second arg, steps through the arguments one by one.
In other words, options
can return any one of its arguments, and the
value it returns can be decided by any constraints on the value that may appear
in the code after the options
call.
(define (pytriplets)
(let ([x (options 2 3 4 5 6 7 8 9)]
[y (options 2 3 4 5 6 7 8 9)]
[z (options 2 3 4 5 6 7 8 9)])
(ensure (equal? (* z z) (+ (* x x) (* y y))))
(list x y z)))
The above code should behave the same way as though (range 2 9)
was
used instead of (options 2 3 4 5 6 7 8 9)
. Except that in the case
of options
, the values can be of any type.