6.001/Recitation 12

Rob Speer

More continuation head-explody

What does this evaluate to? Or, since it's pretty clear what the answer would have to be, why does it evaluate to that?

(((call/cc (lambda (k) k)) (lambda (x) x)) "HEY!")

Generator procedures using continuations

Remember this from last recitation:

(define (int-generator cont)
  (let loop ((i 0))
    (let/cc resume
      (set! int-generator resume)
      (cont i))
    (loop (+ i 1))))

(call/cc int-generator)
(call/cc int-generator)

If we want to write another generator function, we'll have to duplicate that whole let/cc thing every time we want to yield a value. Why not abstract over it? While we're at it, why not make it possible to have more than one int-generator at a time? I'd like int-generator to look like this:

(define (int-generator)
  (make-generator (lambda (yield)
   (let loop ((i 0))
     (yield i)
     (loop (+ i 1))))))

No way am I going to remember this, so here's the code, for my benefit. I'll walk through it on the board.

(define (make-generator f)
  (letrec [(entry-point
    (box (lambda (cont)
      (let [(yield (lambda (val)
                (let/cc resume
                  (set-box! entry-point resume)
                  (cont val))))]
        (f yield)))))]
    entry-point))

(define (generate gen)
  (call/cc (unbox gen)))

(define gen (int-generator))
(define gen2 (int-generator))

We can use the generator idea to compare two trees to see if they have the same list of leaves (the same "fringe"), such as (1 (2 3)) and ((1 2) 3). Of course, one way to do this is to flatten both trees and compare that, but that would be inefficient if the trees were huge.

Macros

It would have been nice if I could have done that with a macro. Then we might not need the boilerplate like "lambda (yield)".

Macros are a way to define new special forms; in other words, they're a way to transform one expression into another wherever it occurs, and you can use this to abstract things that would break if you made them lexically-scoped procedures.

Here's how you define a macro in R5RS (MIT Scheme is different):

(define-syntax macro-name
  (syntax-rules (literals)   ; I don't really know how to use literals, but it's almost always empty.
    ((macro-name args)
     expression to replace it with)
    ((macro-name different args)
     expression to replace it with))))

Remember that the expressions you put in here are not going to be evaluated as they are: they're going to be substituted into other Scheme code.

Example: let's define when, which evaluates a sequence of expressions if its first argument is true, and returns false otherwise. (Yes, and used together with begin does the same thing.)

(define-syntax when
  (syntax-rules ()
    ((when condition . body) (if condition (begin . body) #f))))