6.001 Spring '00 27 April 2000
Notes on Continuation Passing Style
Date: Thu, 27 Apr 2000 13:17:02 -0400 (EDT)
From: Leslie Pack Kaelbling
To: 6001-staff@ai.mit.edu
Subject: continuation-passing notes
Hi folks,
I took material from previous email on the subject, plus some very
basic examples and text of my own and typed it in....
Hope this is useful,
Leslie
=======================
Basic Example
-------------
In typical style, we might write:
(define add (lambda (a b) (+ a b)))
(define square (lambda (x) (* x x)))
Then
(square (add 1 2)) => 9
In continuation-passing style, we would write
(define c-add (lambda (a b continue)
(continue (+ a b))))
(define c-square (lambda (x continue)
(continue (* x x))))
Then, the composition would be something like
(c-add 1 2 (lambda (sum) (c-square sum id)))
The way to think about c-add, for instance, is that its job is to take
two numbers, add them together, then hand the result to the continue
procedure, which will do some further processing (but we don't care
what). The type is (num, num, (num -> A)) -> A. I'm not sure whether
the types are all that illuminating here, though.
Some rules of thumb
-------------------
- Continue is a procedure of one argument
- Only primitive operations can occur in the expression that is an
argument to continue
- Procedures must contain only conditionals (if, cond, and, or),
and other direct calls to procedures (including continue), with no
pending operations
- The tests in the conditionals should only involve primitive operations
Factorial
---------
Standard style:
(define (fact n)
(if (= n 1)
1
(* n (fact (- n 1)))))
CP-style:
(define (c-fact n continue)
(if (= n 1)
(continue 1)
(c-fact (- n 1)
(lambda (fact-n-1)
(continue (* n fact-n-1))))))
In converting basic recursive procedures to CP style
- test remains the same
- call continue directly on base-case result
- recursive case has to be tail-recursive, so include a recursive call
directly, on a simpler sub-problem
- when making the new continuation for the recursive case,
* you know it has to be a procedure, so start with a lambda
* it must have one argument, which is the result of the recursive
call; give the parameter a nmae that makes this clear
* if only primitive operations are left (as in fact above), then
embed that expression in a call to continue; otherwise, see later
examples
Sum-list
--------
Another example of simple recursion
Standard style:
(define (sum-list lst)
(if (null? lst)
0
(+ (car lst) (sum-list (cdr lst)))))
CP-style:
(define (c-sum-list lst continue)
(if (null? lst)
(continue 0)
(c-sum-list (cdr lst)
(lambda (sum-of-cdrs)
(continue (+ (car lst) sum-of-cdrs))))))
Same rules as above apply.
Odd
---
Odd is naturally tail-recursive, even in the usual style:
(define (odd? x)
(cond ((= n 0) #f)
((= n 1) #t)
(else (odd? (- n 2)))))
Following the rules above, we get
(define (c-odd? x continue)
(cond ((= n 0) (continue #f))
((= n 1) (continue #t))
(else (c-odd? (- n 2)
(lambda (odd-n-2?) (continue odd-n-2?))))))
Notice, though, that
(lambda (odd-n-2?) (continue odd-n-2?))
is equivalent to
continue
so we can just write
(define c-odd? (lambda (x continue)
(cond ((= n 0) (continue #f))
((= n 1) (continue #t))
(else (c-odd? (- n 2) continue)))))
This is typical in procedures that are already tail-recursive.
Remove
------
Here we have multiple cases with continuations. No problem.
(define (remove item lst)
(cond ((null? lst)
nil)
((eq? item (car lst))
(remove item (cdr lst)))
(else
(cons (car lst) (remove item (cdr lst))))))
In CP style, it's
(define (c-remove item lst continue)
(cond ((null? lst)
(continue nil))
((eq? item (car lst))
(c-remove item (cdr lst) continue))
(else
(c-remove item (cdr lst)
(lambda (purged-cdr)
(continue (cons (car lst) purged-cdr)))))))
Note that the middle case was already tail-recursive, so we can just
pass continue on directly.
Filter
------
Remove was pretty straightforward because the test in the condition was
primitive. Now, let's do filter, in which the predicate can be arbitrarily
complicated.
In usual style, it looks a lot like remove above.
In continuation-passing style, let us also assume that our predicate is
written in continuation-passing style. A good example would be c-odd?
above.
So, we'll have
(define (c-filter c-pred lst continue)
(if (null? lst)
(continue nil)
(c-pred (car lst)
(lambda (keep-car?)
(if keep-car?
(c-filter c-pred (cdr lst)
(lambda (filtered-cdr)
(continue (cons (car lst) filtered-cdr))))
(c-filter c-pred (cdr lst) continue))))))
A sample call would be
(c-filter c-odd? '(1 2 3 4 5) id) => (1 3 5)
Fibonacci
---------
Another interesting case is Fibonacci, in which there are two recursive
calls and no obvious way to make it tail-recursive using extra parameters
to accumulate the answers.
Typically, it's
(define (fib n)
(if (or (= n 0) (= n 1))
1
(+ (fib (- n 1)) (fib (- n 2)))))
In CP style, it's
(define (c-fib n continue)
(if (or (= n 0) (= n 1))
(continue 1)
(c-fib (- n 1)
(lambda (fib-n-1)
(c-fib (- n 2)
(lambda (fib-n-2)
(continue (+ fib-n-1 fib-n-2))))))))
How do you figure this out? Well, the test and the base-case are
pretty straightforward. When you hit the (doubly) recursive case,
just take a deep breath and pick part of it to start with. We decided
to start by computing fib of n-1. Having done that, we have to say
how to continue. So, what do you do if you already have fib-n-1 in
your hand? You compute fib of n-2. Now, how do you continue after
that? Well, you add fib-n-1 and fib-n-2 together and hand that result
off to continue.
Map
---
Another example, sort of like filter, in which we map a procedure down
a list. We assume it's a continuation-passing style procedure, like
c-square (from the first section). (Example due to Kyle and Albert).
It turns out that there are two ways to do this, corresponding to
whether the elements are mapped in left-to-right or right-to-left
order. In CP-style, we have very explicit control over the order in
which operations are done.
The left-to-right case goes like this:
(define (c-map-lr c-op lst continue)
(if (null? lst)
(continue nil)
;; We decide to op the first element first
(c-op (car list)
(lambda (opped-car)
;; Now, op the cdr
(c-map-lr c-op (cdr lst)
(lambda (opped-cdr)
;; And continue with the combined result
(continue (cons opped-car opped-cdr))))))))
The right-to-left case is:
(define (c-map-rl c-op lst continue)
(if (null? lst)
(continue nil)
;; We decide to op the cdr first
(c-map-rl c-op (cdr lst)
(lambda (opped-cdr)
;; Now, op the car
(c-op (car lst)
(lambda (opped-car)
;; And continue with the combined result
(continue (cons opped-car opped-cdr))))))))