6.001/Recitation 11

Rob Speer

Contents 1 Review of quote 2 Review of lexical scope 3 Introducing continuations 4 call/cc 5 Generator procedures using continuations

Review of quote

• What's the difference between (list a b c) and '(a b c)?
• What's the difference between (list 'a 'b 'c) and '(a b c)?

An interesting expression to build up:

(list 2 (list (quote quote) 2))

(quote
  (lambda (x)
    (list x (list (quote quote) x))))

((lambda (x)
  (list x (list (quote quote) x)))
 2)

((lambda (x)
  (list x (list (quote quote) x)))
 (quote
   (lambda (x)
     (list x (list (quote quote) x)))))

Review of lexical scope

Every time a lambda is applied, it creates an environment where new variables are defined, and these variables will be available to all the code inside the lambda -- based on when it is defined, not when it is applied.

An explanation of how this works is called the "environment model", but I'll leave it to lecture to introduce that.

Introducing continuations

"Continuations will make your head explode. And then you'll call the continuation to get it back, and then your head will explode again."

-- huberth, after 6.891

What if we could make every function in Scheme tail-recursive? We can do this if we suppose that every function takes a continuation - a function that tells it what to do next - as its last argument.

In continuation passing style, functions never return. They just call their continuation.

Direct style: (+ (* 5 4) 3)

Continuation passing style: (* 5 4 (λ (x) (+ x 3 display)))

(You may also see a more reasonable form of continuation passing style, where built-in functions like + return as normal.)

Things to translate into CPS:

(define (product lst)
  (if (null? lst) 1
      (* (car lst) (product (cdr lst)))))

(define (silly-fib n)
  (if (< n 2) n
      (+ (silly-fib (- n 1) (- n 2)))))

call/cc

We can mix continuations into direct-style code to do interesting, head-hurting new things. call-with-current-continuation (call/cc) finds the current continuation at the point where it is being called, and passes that continuation to a function.

(+ 1 (call/cc
       (lambda (k)
         (+ 2 (k 3)))))

A useful abbreviation is let/cc, letting you skip the lambda part. The strange code above then becomes:

(+ 1 (let/cc k (+ 2 (k 3))))

Generator procedures using continuations

This is cool:

(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)

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.