 indiana.edu Go back Open original

# CPS Refresher

To refresh our memory, let's CPS the factorial procedure. Here is the definition of `fact` in direct style.

`(define fact (lambda (n) (cond [(zero? n) 1] [else (* n (fact (sub1 n)))])))`

Here is `fact-cps`, which is the CPSed version of `fact`.

`(define fact-cps (lambda (n k) (cond [(zero? n) (k 1)] [else (fact-cps (sub1 n) (lambda (v) (k (* n v))))])))`

Since `fact-cps` consumes two arguments instead of one, we might find it convenient to also define a “driver” procedure called `fact`.

`(define fact (lambda (n) (fact-cps n (empty-k))))`

We could use the identity procedure `(lambda (v) v)` as the initial continuation, but we want to signal an error if the initial continuation is invoked more than once. Therefore, we will use the continuation returned from calling the following `empty-k` procedure:

`(define empty-k (lambda () (let ([okay #t]) (lambda (v) (if okay (begin (set! okay #f) v) (error 'empty-k "k invoked in non-tail position"))))))`

Just for fun, and to demonstrate how `empty-k` behaves, let's write an incorrect definition of `fact-cps` that invokes the continuation `k` multiple times.

`(define fact-cps (lambda (n k) (cond [(zero? n) (k 1)] [else (fact-cps (sub1 n) (lambda (v) (k (* n (k v)))))])))`

When we test our new version, we get an error:

```Error in empty-k: k invoked in non-tail position.
Type (debug) to enter the debugger.
```

Here is one more example, using the Fibonacci procedure. First we define `fib` in direct style.

`(define fib (lambda (n) (cond [(zero? n) 1] [(= n 1) 1] [else (+ (fib (sub1 n)) (fib (sub1 (sub1 n))))])))`

Now we transform `fib` into continuation-passing style.

`(define fib-cps (lambda (n k) (cond [(zero? n) (k 1)] [(= n 1) (k 1)] [else (fib-cps (sub1 n) (lambda (v) (fib-cps (sub1 (sub1 n)) (lambda (w) (k (+ v w))))))])))`

Once again, we can define a driver procedure if we like.

`(define fib (lambda (n) (fib-cps n (empty-k))))`