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