Convert to CPS (Continuation Passing Style)

Question

How do I convert these procedures in Scheme to CPS form?

1. (lambda (x y)
     ((x x) y))
   

2. (lambda (x)
     (lambda (f)
       (f (lambda (y)
            (((x x) f) y))))
   

3. ((lambda (x) (x x)
    (lambda (x) (x x))
   

*This is not any homework!

Continent

Answer 1

See Programming Languages, Application and Interpretation, starting around Chapter 15. Chapter 18 talks about how to do it automatically, but if you're not familiar with thinking about expressing a function that does "what to do next", you'll probably want to try the finger exercises first.

Don't have someone do it for you: you'll really want to understand the process and be able to do it by hand, independent of Scheme or otherwise. It comes up especially in Asynchronous JavaScript web programming, where you really have no choice but to do the transform.

---

In the CPS transform, all non-primitive functions need to now consume a function that represents "what-to-do-next". That includes all lambdas. Symmetrically, any application of a non-primitive function needs to provide a "what-to-do-next" function, and stuff the rest of the computation in that function.

So if we had a program to compute a triangle's hypothenuse:

(define (hypo a b)
  (define (square x) (* x x))
  (define (add x y) (+ x y))

  (sqrt (add (square a)
             (square b))))

and if we state that the only primitive applications here are *, +, and sqrt, then all the other function definitions and function calls need to be translated, like this:

(define (hypo/k a b k)
  (define (square/k x k)
    (k (* x x)))

  (define (add/k x y k)
    (k (+ x y)))

  (square/k a 
            (lambda (a^2)
              (square/k b
                       (lambda (b^2)
                         (add/k a^2 b^2
                                (lambda (a^2+b^2)
                                  (k (sqrt a^2+b^2)))))))))

;; a small test of the function.
(hypo/k 2 3 (lambda (result) (display result) (newline)))

The last expression shows that you end up having to compute "inside-out", and that the transformation is pervasive: all lambdas in the original source program end up needing to take an additional argument, and all non-primitive applications need to stuff "what-to-do-next" as that argument.

Take a close look at section 17.2 of the cited book: it covers this, as well as 17.5, which talks about why you need to touch ALL the lambdas in the source program, so that the higher-order case works too.

---

As another example of the transform, applied for a higher-order case, let's say that we have:

(define (twice f)
  (lambda (x) 
    (f (f x))))

Then the translation of something like this is:

(define (twice/k f k1)
  (k1 (lambda ...)))

... because that lambda's just a value that can be passed to k1. But of course, the translation needs to run through the lambda as well.

We must first do the inner call to f with x (and remember that all non-primitive function applications need to pass an appropriate "what-to-do-next!"):

(define (twice/k f k1)
  (k1 (lambda (x k2)
        (f x (lambda (fx-val)
               ...)))))

... take that value and apply it again to f...

(define (twice/k f k1)
  (k1 (lambda (x k2)
        (f x (lambda (fx-val)
               (f fx-val ...))))))

... and finally return that value to k2:

(define (twice/k f k1)
  (k1 (lambda (x k2)
        (f x (lambda (fx-val)
               (f fx-val k2))))))

;; test.  Essentially, ((twice square) 7)
(define (square/k x k) (k (* x x)))
(twice/k square/k 
         (lambda (squaresquare)
           (squaresquare 7
                         (lambda (seven^4) 
                           (display seven^4)
                           (newline)))))

Elga

I'm sorry, this is not helping me. Thank you anyway for trying. – Continent

What part are you having trouble with? Do you know how to transform a simple function, such as (lambda (x) (+ x 1)) to CPS style? It's very hard to help, with no mental model of where you're getting stuck. Have you gone through those chapters in the cited book, or do you not have time? – Elga

Yes I have, and I know how to transform "simple" procedures like (lambda (x) (+ x 1)), but what if the 'x' is a procedure itself? like (lambda (x) (x 1))? I do need to transform every user defined procedure don't I? – Continent

and what you do when an inner lambda is involved? – Continent

Edited the answer to include example, as well as stronger recommendation to read the book. It talks specifically how to do the higher-order case in 17.5. – Elga

Answer 2

You need to choose to what level you need/want to CPS-transform.

If you just want (lambda (x y) ((x x) y)) in continuation-passing(CP) style, then (lambda (k x y) (k ((x x) y))) will do fine.

If you want its arguments to be treated as being in CP style too, then you need a little more.

Suppose first that only the second argument (y) is in CP form and is thus really something like (lambda (k) (k y0)) and so needs to be called with some continuation to extract its value, then you would need:

(lambda (k x y)
  (y (lambda (y0) (k ((x x) y0)) )) )

Finally assume that both x and y are in CP style. Then you would need something like:

(lambda (k x y)
  (x (lambda (x0)
       (x (lambda (x1)
            (y (lambda (y0)
                 (k ((x0 x1) y0)) ))))

Here you have the freedom to reorder the calls to x and y. Or maybe you only need one call to x, because you know its value does not depend on the continuation it is called with. For example:

(lambda (k x y)
  (y (lambda (y0)
       (x (lambda (x0)
            (k ((x0 x0) y0)) ))))

The other expressions you asked about can be transformed similarly.

Marlyn