CPS refresher

Wiki-Quelltext dieser Seite.

<language>Scheme</language>

==CPS Refresher==

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

<code id="4b41f6608c2ec">
(define fact
  (lambda (n)
    (cond
      [(zero? n) 1]
      [else (* n (fact (sub1 n)))])))
</code>
<run id="4b41f6609018c">
(fact 5)
</run>

Here is <tt>fact-cps</tt>, which is the CPSed version of <tt>fact</tt>.

<code id="4b41f6608cab1">
(define fact-cps
  (lambda (n k)
    (cond
      [(zero? n) (k 1)]
      [else (fact-cps (sub1 n) (lambda (v)
                                 (k (* n v))))])))
</code>

We could use the identity procedure <tt>(lambda (v) v)</tt> as the initial continuation,

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

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 <tt>empty-k</tt> procedure:

<code id="4b41f6608da57">
(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"))))))
</code>

<code id="4b420bc6345ff">
(define cont (empty-k))
</code>

<run id="4b41f66091123">
(cont 120)
</run>

<run id="4b41f66091123">
(cont 120)
</run>

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

Since <tt>fact-cps</tt> consumes two arguments instead of one, we might find it convenient to also define a "driver" procedure called <tt>fact</tt>.

<code id="4b41f6608d290">
(define fact
  (lambda (n)
    (fact-cps n (empty-k))))
</code>

<run id="4b41f7e7c5d78">
(fact 5)
</run>

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

<code id="4b41f6608e223">
(define fact-cps
  (lambda (n k)
    (cond
      [(zero? n) (k 1)]
      [else (fact-cps (sub1 n) (lambda (v) (k (* n (k v)))))])))
</code>

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

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

Here is one more example, using the Fibonacci procedure. First we define <tt>fib</tt> in direct style.

<code id="4b41f6608e9f3">
(define fib
  (lambda (n)
    (cond
      [(zero? n) 1]
      [(= n 1) 1]
      [else (+ (fib (sub1 n)) (fib (sub1 (sub1 n))))])))
</code>

<run id="4b41f961b77e3">
(fib 8)
</run>

Now we transform <tt>fib</tt> into continuation-passing style.

<code id="4b41f6608f1ea">
(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))))))])))
</code>

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

<code id="4b41f6608f9b0">
(define fib
  (lambda (n)
    (fib-cps n (empty-k))))
</code>

<run id="4b41f961b7fa8">
(fib 8)
</run>
 

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