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!

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