On this page: Language Comparison Task Features Implementation Strategy Stencil Code Submission
7.3.8 A: Generators

In this assignment you will be studying and implementing generators. Language Comparison

Consider this generator written in Python:
x = 0
def a(b):
  global x
  x = 3
def c():
  a(lambda: yield 1)
  yield x
gen = c()
Here is the seemingly equivalent program in Racket:
(require racket/generator)
(define x 0)
(define (a b)
 (set! x 3))
(define c
 (generator ()
            (a (lambda () (yield 1)))
            (yield x)))
We might expect both to yield 1 followed by 3.

Run both of them. Do they behave the same way? If not, try to explain why they differ. You are welcome to consult the Internet for help understanding their behaviors. Task

Now, we ask you to simulate the behavior of Python 2.7.16 generators.Their behavior seems to be effectively the same in Python 3, but we want to pick one reference version to avoid confusion. We would be interested in hearing about interesting differences in generators between Python 2.7.16 and Python 3. You can therefore use Python as a guide for the expected behavior, though it’s best to check in on the message board before you commit to an implementation decision (i.e., try out the program in Python, see what it does, and confirm with us that that’s what we want your implementation to do). Features

Implement the following:
  • The language construct
    (generator (arg-name) body)
    (For simplicity, we will focus on just single-argument generators.)

  • The function next, which takes a generator as an argument and returns the next value it yields.

  • The language construct
    (yield exp)
    which yields the value of exp. See below on how it should be implemented.

  • The language construct
    (loop exp)
    which implements an infinite loop whose body is given by exp (usually this will contain a yield, and perhaps use a begin if the body contains multiple operations). We don’t strictly need loop to understand generators, but it makes it much easier to write interesting programs (e.g., stream simulations). See below on how it should be implemented.

In addition, remove lambda from your language, as a way of preventing the kind of Python program we tried to write in Language Comparison. Make any uses of it an error. Implementation Strategy

You will reuse your implementation from B: ACI. Specifically, the generator macro uses the aci macro to transform its body. This provides the continuation needed by yield to store the current state of the generator before returning.

You can use let/ec (look it up) to escape from the generator and yield a value. (This is equivalent to using return in languages like Python.)

You should add yield and loop to the set of terms recognized and handled explicitly by the aci macro.

In addition to these changes to the aci macro, you may also find it helpful to nest the implementation of the macro inside the body of the generator macro.Try without and see what you run into. If you feel you need to write multiple definitions and expressions on the right-hand side of a macro rule (you don’t necessarily need to), write a begin instead, and nest the multiple definitions within it.

To match Python’s semantics, function applications no longer pass their current continuation to the callee. Instead, the function application’s returned value is given to the continuation, just as with atomic values.

An error is raised if you call next on a generator after it has gotten to the end of its body.

The generator macro returns a function that, when called, returns an instance of the a-generator structure, which is defined in the stencil.

yield evaluates to (void), similar to the behavior in Python.

It is possible to nest yields. When this happens, the expected behavior occurs: the inner yield yields first, and then the outer one.

Finally, you may need to put some thought into how you handle loop. The simple solution is to expand its body into another call of loop, but that can cause your aci macro to never terminate. Instead, it’s simpler to write a function that implements the infinite loop, taking the continuation as an argument. It will need to handle yields correctly! Stencil Code Submission