CPS refresher

Aus ProgrammingWiki

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

(fact 5)

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

We could use the identity procedure (lambda (v) v) as the initial continuation,

(fact-cps 5 (lambda (v) v))

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

(define cont (empty-k))

(cont 120)

(cont 120)

(fact-cps 5 (empty-k))

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

(fact 5)

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:

(fact-cps 5 (empty-k))

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

(fib 8)

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

(fib 8)

Found on http://www.cs.indiana.edu/cgi-pub/lkuper/c311/cps-refresher, slightly modified by CW.
cps-refresher.txt · Last modified: 2009/10/08 09:10 by lkuper

CPS refresher

CPS Refresher

Suche