CPS refresher

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

We could use the identity procedure <tt>(lambda (v) v)</tt> 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:

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

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
cps-refresher.txt · Last modified: 2009/10/08 09:10 by lkuper
CPS refresher

Suche
