CPS refresher

Aus ProgrammingWiki

Archivierte Version vom 2010-01-04T14:17:46+00:00. Aktuelle Version

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

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

<eval id="4b41f66090954"> (fact-cps 5 (lambda (v) v)) </eval>

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

<eval id="4b41f66091123"> (empty-k) </eval>

<eval id="4b41f66090954"> (fact-cps 5 (empty-k)) </eval>

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

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:

<eval id="4b41f660918f7"> (fact-cps 5 (empty-k)) </eval>

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

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