On this page:
9.1 Introduction
9.2 Reading
9.3 Part 1:   Language Comparison
9.4 Part 2:   Implementation
9.4.1 Grammar
9.4.2 Yielding a Value
9.4.2.1 Example Usage
9.4.3 Implementation Hints
9.4.4 Starter Code
9.5 What To Hand In
9 Generators

    9.1 Introduction

    9.2 Reading

    9.3 Part 1: Language Comparison

    9.4 Part 2: Implementation

      9.4.1 Grammar

      9.4.2 Yielding a Value

        9.4.2.1 Example Usage

      9.4.3 Implementation Hints

      9.4.4 Starter Code

    9.5 What To Hand In

9.1 Introduction

In this assignment, you will implement generators.

9.2 Reading

Chapter 14.3 of PAPL 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

Consider the following program written in Python 3 (run it online!):

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 yieldaci 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 raises an error. 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
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 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.

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.

Finally, submit your answer to Part 1: Language Comparison to the “Question” drop on Gradescope.
You can update your submissions as many times as you want before the deadline.