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 fact in direct style.

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

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,

<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 <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>
<eval id="4b41f66091123">
(empty-k)
</eval>

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

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>

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

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:

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

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

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>
 

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