CPS refresher

Aus ProgrammingWiki

Archivierte Version vom 2010-01-04T14:08:33+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))))])))

<eval id="4b41f66090954"> (fact-cps 5 display) </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))))

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

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

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>

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

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

CPS refresher

CPS Refresher

Suche