12 Generators
12.1 Introduction
In this assignment, you will implement generators.
12.2 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!
You do not need to read this article for anything in this assignment. However, it’s important if you want to further study programming languages. You may also find it interesting for thinking as a programmer.
12.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!):
| #lang racket |
| (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, and answer the following question:
Do these programs behave the same way? If not, try to explain why they differ. You are welcome to consult the Internet for help understanding their behaviors.
12.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:
| #lang racket |
| (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, your generator should not allow the use of yield or loop inside of lambda - think about the provided python example for a clue about why we might want to disallow such uses of yield and loop. Any programs that attempt to do either thing 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 raises an error. If next is called on a previously exhausted generator (one that has already caused next to error) its behavior is undefined. If the generator never reaches the end of its body and never reaches a yield, next may loop infinitely.
12.5 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>) |
12.6 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:
| #lang racket |
| (define-syntax outer-macro |
| (syntax-rules () |
| [(_ some-pattern) |
| (begin |
| (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).
12.7 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
type-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.
12.8 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.