9 Generators
9.1 Introduction
In this assignment, you will implement generators.
9.2 Reading
Chapter 14.3 of PLAI 2/e.
Optional Reading:
This article provides a very nice introduction to generators in the Icon programming language, which is no longer used but inspired most modern work on generators. Generators in Icon were central to the language, not an added-on feature, and this shows how they are integrated into the language. (Notice, in paricular, how the truthy-falsy nature of the language appears to be a win early on, but becomes problematic later on.) You can see other examples on
Wikipedia. It’s worth noting that Icon was created in the late 1970s!
9.3 Part 1: Language Comparison
x = 0 |
|
def a(b): |
global x |
b() |
x = 3 |
|
def c(): |
a(lambda: (yield 1)) |
yield x |
|
gen = c() |
print(next(gen)) |
print(next(gen)) |
We’ve translated the above program into this seemingly equivalent Racket program (
run it online!):
(require racket/generator) |
|
(define x 0) |
|
(define (a b) |
(b) |
(set! x 3)) |
|
(define c |
(generator () |
(a (lambda () (yield 1))) |
(yield x))) |
|
(c) |
(c) |
First, confirm that these programs look equivalent; that is, we might expect the generators in both to yield 1, then yield 3.
Then, run both programs. Answer the following question(s):
Do they behave the same way? If not, why do they differ?
You are welcome to consult the Web (within the rules set down in the syllabus) for help understanding their behaviors.
9.4 Part 2: Implementation
You will now emulate Python 3 generators in Racket by adapting your aci implementation from the ACI assignment to implement the generator construct:
(generator (arg-name) body) |
which defines an unary function. This function returns a generator with routine body, and any references to arg-name within body are bound to the function’s argument.
Be very careful when you’re reading this spec—the generator construct defines a function, not a generator. Applying the function defined by generator (the syntactic construct) produces a generator (in the semantic sense).
In addition to the base constructs from the aci language (that is, everything except web-read), the language for a generator’s body should support the following new forms:
(yield exp)
which yields the value of exp from the generator. We need our aci implementation because of yield—aci provides the continuation needed to store the generator’s current state before yielding.
(yield ...) itself should evaluate to (void). Also, programs may nest yields, and inner yields should yield before outer yields.
(loop exp)
which infinitely runs exp. (We don’t need loop to understand generators, but it makes it easier to write interesting programs [e.g., streams].)
Additionally, because we are trying to mimic Python, your generator should not allow the use of yield or loop inside of lambda, just as in the example above. Any programs that attempt to do either should result in an error (a syntax error is acceptable here).
The body of a generator should be able to support references to definitions defined outside of the body (for example, functions and variables previously declared in a define statement), though those outer definitions do not need to support the constructs in the generator language (such as yield and loop). To do this, you should update your aci macro such that function applications do not pass their current continuation to the callee. Instead, the function application’s result should be given to the continuation just as with atomic values.
This modification to how continuations interact with function applications matches Python’s semantics.
Finally, you should implement the next function, which takes a generator as an argument, resumes computation of the generator from the point at which it last yielded, and returns the next value that the generator yields. If the generator has reached the end of its body, next should call raise-stop-iteration-error (defined in the support code) to signal that the generator has been exhausted. If the generator never reaches the end of its body and never reaches a yield, next may loop infinitely.
9.4.1 Grammar
Your final generator macro implementation should handle the following grammar:
<generator> ::= (generator (<id>) <gen-expr>) |
|
<gen-expr> ::= <basic-expr> |
| (yield <gen-expr>) |
| (loop <gen-expr>) |
|
<basic-expr> ::= <num> |
| <string> |
| true |
| false |
| (<gen-expr> <gen-expr>) # function application |
| (lambda (<id>) <basic-expr>) |
| (set! <id> <gen-expr>) |
| (begin <gen-expr> <gen-expr>) |
| (+ <gen-expr> <gen-expr>) |
| (string-append <gen-expr> <gen-expr>) |
9.4.2 Yielding a Value
When you need to
yield a value, you should use
let/ec to escape from the
generator and return a value. This creates an
escape continuation. Escape continuations are analogous to
return statements in languages like Python—
when applied to an argument, the continuation unwinds the current stack out of
let/ec and returns the argument.
Your program must call the escape continuation within the dynamic extent of let/ec. In other words, you must call the continuation before the continuation’s let/ec (and the point where the escape continuation would unwind to) pops off the stack. Otherwise, Racket will raise an error.
Pay attention to the distinction between the continuation created by let/ec (echo-charlie) and the continuations we’ve seen in lecture, created by let/cc (charlie-charlie). let/cc’s continuations allow you to jump back to the copy of the stack where the continuation was made, regardless of where the continuation was called. In contrast, let/ec’s continuations are only allowed to escape the current stack——they don’t preserve a copy of the stack to permit the program to resume the computation.
9.4.2.1 Example Usage
The following use of let/ec works because the escape continuation k is invoked before the let/ec call that defined k has popped off the stack:
(+ 1 (let/ec k (k 5))) ; the let/ec expression evaluates to 5 |
When the escape continuation k is called, the application of the continuation unwinds the stack back to the invocation of let/ec. Then, the let/ec expression evaluates to the value passed to k. Thus, the above program evaluates to 6.
We can even bind the escape continuation k to a new variable, and call the escape continuation via that variable (hint!):
(define hold "dummy variable") |
|
(+ 1 (let/ec k (begin (set! hold k) |
(hold 5)))) |
However, the following example results in an error (since k is invoked after the let/ec call that defined k has popped off the stack):
(define hold "dummy variable") |
|
(+ 1 (let/ec k (begin (set! hold k) |
3))) |
(hold 5) ; error! "continuation application: attempt to jump into an escape continuation" |
Make sure you understand why the semantics of let/cc would allow the third program to work if we were to replace let/ec with let/cc.
Because of these semantics, you’ll need to carefully consider how you use let/ec to return values. Specifically, every time we call next on a generator, we’d like to return the yielded value to this specific invocation of next. However, defining a continuation only saves the current stack at the time the continuation was defined. As such, you’ll need to figure out a way to update the escape continuation used by yield every time you call next or you’ll end up using an old escape continuation.
9.4.3 Implementation Hints
We recommend that you create a struct that stands for generators; exactly what this struct looks like is up to you.
You may find it helpful to nest your aci macro inside your generator macro; try implementing generator without doing this and see what you run into. You can nest a define-syntax construct within another define-syntax construct by moving the “inner” macro inside of a particular pattern branch of your “outer” macro:
(define-syntax outer-macro |
(syntax-rules () |
[(_ some-pattern) |
(let () |
(define-syntax inner-macro |
(syntax-rules () |
[(_ another-pattern) (+ 1 2)])) ; (+ 1 2) can be whatever you want |
(inner-macro "bar"))])) |
|
(outer-macro "foo") |
You might find it tricky to know how to catch uses of loop and yield inside of lambda. Think about how you wrote your lambda case in ACI. In ACI, it was legal for a web-read to appear in the body of a lambda, so it was necessary to use aci on the body of a lambda in order to handle possible web-reads. In this assignment, a world where yield and loop aren’t allowed to appear inside of lambdas, do you need to handle your lambda case in the same way?
Finally, you might find implementing loop tricky. You might start by expanding loop’s body into another call to loop, but that can cause your aci macro to never terminate. Instead, try implementing it via a helper function that consumes the continuation representing loop’s body and runs this continuation repeatedly (it’s up to you to figure out how to do this, though).
9.4.4 Starter Code
We’ve provided starter code for your implementation at
generators.rkt. This includes a template for your
generator macro as well as the
next function.
We’ve also provided a stencil for your test cases at
generators-tests.rkt and testing support code at
test-support.rkt. You should check that you can run your
generators-tests.rkt file successfully in DrRacket before submitting—if you can’t, it means that a definition is missing or you’re trying to test a function that you shouldn’t be testing.
9.5 What To Hand In
You will submit two files for this assignment:
generators.rkt, which should be uploaded to the “Code” drop on Gradescope.
generators-tests.rkt, which should be uploaded to the “Tests” drop on Gradescope.
You can update your submissions as many times as you want before the deadline.