Introduction
In this tutorial we will work through how to add generators to a language by using language level continuations. This continues (har har) the second half of Lecture 16. The generators are based on those discussed in Chapter 14 of PLAI. The approach here (as in Lecture 16) relies on parameters (dynamic scope), rather than on macros (as the version in PLAI).
Step -1: Exceptional Demo
We saw how exceptions could be implemented using (syntactic) continuations Lecture 16. We skipped over
#lang plait
(define exception (make-parameter identity))
(define (throw msg)
((parameter-ref exception) msg))
(define (try thunk recovery)
(let/cc esc
(parameterize ([exception
(λ (x) (esc (recovery x)))])
(thunk))))
(try
(lambda ()
(begin
(throw "abort!")
(/ 1 0)
(display "done")))
(lambda (x)
(display (list "caught" x))))
In the lectures we wrap this up in some syntax rules to make it nicer for a user.
Step 0: What's a generator?
Some of you may be familiar with generators e.g. from Python. The racket standard library includes a generator module. The following is an example from the manual, translated to use more familiar (to us) idioms.
#lang racket
(require racket/generator)
(define g
(generator ()
(define (loop lst)
(if (empty? lst) 0
(begin
(yield (first lst))
(loop (rest lst)))))
(loop '(a b c))))
(module+ test
(require rackunit)
(check-equal? (g) 'a)
(check-equal? (g) 'b)
(check-equal? (g) 'c)
(check-equal? (g) 0)
(check-equal? (g) 0)
)
Fill in the definition to make a counter generator that counts up from the initial value.
(define counter
(generator (initial)
;; definition goes here
))
(module+ test
(check-equal? (counter 10) 10)
(check-equal? (counter 10) 11)
(check-equal? (counter 10) 12)
(check-equal? (counter 10) 13)
)
Roughly speaking, generators require two control flow features: early return, and resuming execution. We'll work through how to implement each of these features using continuations.
Early return
Recall that racket (and in particular #lang plait provides let/cc.
Early return is a simplified version of the exception example from
Lecture 16. Complete the definition of the
following by rebinding return-k appropriately.
#lang plait
(define return-k (make-parameter (lambda (v) (error 'return "outside with-return"))))
(define (return v) ((parameter-ref return-k) v))
(define (with-return thunk)
(let/cc calling-context
(parameterize
(.... )
(thunk))))
(with-return
(lambda ()
(begin
(return 42)
(/ 1 0))))
We can tidy up the syntax by defining a syntax rule. The missing part
here is the same as above. Note that ... is very different from
.... in racket.
#lang plait
(define return-k (make-parameter (lambda (v) (error 'return "outside with-return"))))
(define (return v) ((parameter-ref return-k) v))
(define-syntax-rule (with-return exprs ...)
(let/cc calling-context
(parameterize
(....)
(begin exprs ...))))
(with-return
(return 42)
(/ 1 0))
Resuming execution
Early return is familiar to us from imperative programming languages like Java, C and JavaScript. Resuming execution is a bit more exotic. Suppose we are given the following code:
(define printer
(with-checkpoint
(lambda ()
(begin
(display "first\n")
(checkpoint!)
(display "second\n")))))
We want to define a form with-checkpoint and a function
checkpoint! so that
(printer)
(printer)
(printer)
prints
first
second
second
second
i.e. that execution restarts at the last (checkpoint!) reached.
As a warm-up, let's figure out how to have functions with state. We
could combine boxes with closures for this, but since we don't need
the pass-by-reference features of boxes, we will use the
usually-forbidden set! instead. The goal is to define a function
last-call that remembers the last value of it's parameter, and
returns that. The "tricky" bit is the use of let to define a
variable to preserve the state in. This variable is visible only
inside the define (note also the use of the plait Option type).
#lang plait
(define last-call
(let ([state (none)])
(lambda (n)
(....))))
(test (last-call 1) (none))
(test (last-call 2) (some 1))
(test (last-call 3) (some 2))
(test (last-call 3) (some 3))
Now that we know how to store store things for future invocations of a
function, we can use a combination of let and set! to store a
continuation.
In the following we need to use let/cc inside checkpoint to capture the continuation where it is called
(we might loosely call this the call site)
#lang plait
(define checkpoint-param (make-parameter (lambda () (error 'checkpoint! "outside with-checkpoint"))))
(define (checkpoint!) ((parameter-ref checkpoint-param)))
(define with-checkpoint
(let* ([last-checkpoint (none)])
(lambda (thunk)
(lambda ()
(parameterize ([checkpoint-param ....])
(type-case (Optionof (Void -> 'a)) last-checkpoint
[(none) (thunk)]
[(some k) (k (void))]))))))
Generators
To make a generator we need to combine the two ideas from above. We
have two continuations: dyn-k is the call site for the generator,
and gen-k is the "checkpoint" where we will resume the the execution
of the generator the next time we call it (i.e. call site of yield).
#lang plait
(define yield-param (make-parameter (lambda (v) (error 'yield! "outside generator"))))
(define (yield v) ((parameter-ref yield-param) v))
(define generator
(lambda (fun)
(let* ([last-checkpoint (none)])
(lambda (v)
(let/cc dyn-k
(parameterize ([yield-param
(lambda (v)
(let/cc gen-k
....))])
(type-case (Optionof ('a -> 'b)) last-checkpoint
[(none) (fun v)]
[(some k) (k v)])))))))
Here some (more ) sample generators taken from PLAI.
(define g1
(generator
(lambda (v)
(letrec ([loop (lambda (n)
(begin
(yield n)
(loop (+ n 1))))])
(loop v)))))
(g1 10)
(g1 10)
(g1 10)
(define g2
(generator
(lambda (v)
(letrec ([loop (lambda (n)
(loop (+ (yield n) n)))])
(loop v)))))
(g2 10)
(g2 10)
(g2 10)
The identifier names are different, but my generator solution is based
on the following macro based solution from Chapter 14 of
PLAI.
If you're interested in macros, notice the tricky way the macro
parameter yield is being used here.
#lang plait
(define-syntax (generator e)
(syntax-case e ()
[(generator (yield) (v) b)
#'(let ([where-to-go (lambda (v) (error 'where-to-go "nothing"))])
(letrec ([resumer (lambda (v)
(begin b
(error 'generator "fell through")))]
[yield (lambda (v)
(let/cc gen-k
(begin
(set! resumer gen-k)
(where-to-go v))))])
(lambda (v)
(let/cc dyn-k
(begin
(set! where-to-go dyn-k)
(resumer v))))))]))
(define g1
(generator (yield) (v)
(letrec ([loop (lambda (n)
(begin
(yield n)
(loop (+ n 1))))])
(loop v))))
(define g2
(generator (yield) (v)
(letrec ([loop (lambda (n)
(loop (+ (yield n) n)))])
(loop v))))
Finally, we can define a syntax rule to make it slightly nicer to define generators in our solution. In my humble opinion this is a more programmer friendly syntax than the text's.
#lang plait
(define yield-param (make-parameter (lambda (v) (error 'yield! "outside generator"))))
(define (yield v) ((parameter-ref yield-param) v))
(define-syntax-rule (generator (v) exprs ...)
(let ([last-checkpoint (none)]
[fun (lambda (v) exprs ...)])
(lambda (v)
(let/cc dyn-k
(parameterize ([yield-param
(lambda (v)
(let/cc gen-k ....))])
(type-case (Optionof ('a -> 'b)) last-checkpoint
[(none) (fun v)]
[(some k) (k v)]))))))
(define g1
(generator (v)
(letrec ([loop (lambda (n)
(begin
(yield n)
(loop (+ n 1))))])
(loop v))))
(g1 10)
(g1 10)
(g1 10)
(define g2
(generator (v)
(letrec ([loop (lambda (n)
(loop (+ (yield n) n)))])
(loop v))))
(g2 10)
(g2 10)
(g2 10)