Convert to CPS (Continue Passing Style)

Question

How do I convert these procedures to a Schema form in CPS?

• (lambda (xy) ((xx) y)) 

•  (lambda (x) (lambda (f) (f (lambda (y) (((xx) f) y)))) 

•  ((lambda (x) (xx) (lambda (x) (xx)) 

* This is not homework!

Answer 1

See Programming Languages, Application, and Interpretation , Starting with Chapter 15. Chapter 18 talks about how to do this automatically, but if you are not familiar with the idea of ​​expressing a function that does “what to do next,” you will probably first want to try finger exercises.

Do not do this for you: you really want to understand the process and be able to do it manually, regardless of the Scheme or otherwise. This is especially important in asynchronous JavaScript web programming, where you really have no choice but to do the conversion.

---

In CPS conversion, all non-primitive functions should now consume a function that represents "what to do next." This includes all lambdas. Symmetrically, any application of a non-primitive function should provide the function "what to do next", and the rest should be calculated in this function.

So, if we had a program to calculate the triangle hypothesis:

 (define (hypo ab) (define (square x) (* xx)) (define (add xy) (+ xy)) (sqrt (add (square a) (square b)))) 

and if we indicate that the only primitive applications here are * , + and sqrt , then all other function definitions and function calls should be translated as follows:

 (define (hypo/kabk) (define (square/kxk) (k (* xx))) (define (add/kxyk) (k (+ xy))) (square/ka (lambda (a^2) (square/kb (lambda (b^2) (add/ka^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 have to compute “inside out” and that conversion is common: all lambdas in the original source program ultimately need an additional argument, and all non-primitive applications need to populate something-to-do-next as this argument.

Carefully read section 17.2 of the book cited: it covers this, as well as 17.5, which says why you need to touch ALL LAMBDS in the original program, so dealing with a higher order also works.

---

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

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

Then a translation of something like:

 (define (twice/kf k1) (k1 (lambda ...))) 

... because this lambda is just a value that can be passed to k1 . But, of course, the translation must go through lambda.

First, we must make an internal call to f using x (and remember that all applications that are not primitive functions must pass the corresponding "what to do next!"):

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

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

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

... and finally return this value to k2 :

 (define (twice/kf k1) (k1 (lambda (x k2) (fx (lambda (fx-val) (f fx-val k2)))))) ;; test. Essentially, ((twice square) 7) (define (square/kxk) (k (* xx))) (twice/k square/k (lambda (squaresquare) (squaresquare 7 (lambda (seven^4) (display seven^4) (newline))))) 

Answer 2

You need to choose what level you need / need for CPS conversion.

If you just want (lambda (xy) ((xx) y)) in the Continuation (lambda (kxy) (k ((xx) y))) (CP) style, then (lambda (kxy) (k ((xx) y))) will work fine.

If you want his arguments to be processed like in CP style, you need a little more.

First, suppose that only the second argument ( y ) is in the form of CP and, therefore, is really something like (lambda (k) (k y0)) , and therefore it needs to be called with some continuation in order to extract its value, then you will need:

 (lambda (kxy) (y (lambda (y0) (k ((xx) y0)) )) ) 

Finally, suppose both x and y are in CP style. Then you will need something like:

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

Here you can change the order of calls to x and y . Or maybe you only need one call to x , because you know that its value does not depend on the continuation with which it is called. For example:

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

Other expressions you requested can be converted similarly.