What are the continuation passing style conversion rules?

Question

I am trying to understand continuation passing style conversion.

I am trying to build a Scheme to C compiler and I want to use continuation passing style. Whether or not continuation passing style is the right way to do this can you guys explain me the conversion rules?

For example, here is a presentation by Marc Feeley, the creator of Gambit Scheme.

I will summarize the continuation passing style rules he gives, but note: I don't understand them. In particular I don't understand what C is.

Here is the notation:

[E]
 C

which denotes the continuation passing style conversion of the expression E in the continuation C.

So, for example, one conversion rule is this one:

[c] 
 C
==>
(C c) ;; application of C to c

which denotes the CPS conversion of the constant c in the continuation C.

What is C? I am having trouble understanding what C is. It is like magic.

Another rule is:

[(if E1 E2 E3)]
     C

==>

    [E1]
(lambda (r1)
  (if r1 [E2] [E3]))
          C    C

where E1 gets passed to r1.

But what is C?

Can you guys please explain?

Thanks.

Answer 1

If you scroll higher up in the article, to page 7, you will find definitions of what a continuation is, which is necessary to understand the rules for converting to continuation-passing style. An example given is

 > (sqrt (+ (read) 1))

and it notes that the continuation for (read) is

a computation that takes a value, adds 1 to it, computes its square-root, prints the result and goes to the next REPL interaction.

So the continuation C for an expression E is "whatever happens to the value of this expression". This is reiterated on page 20, with the example

(let ((square (lambda (x) (* x x))))
  (write (+ (square 10) 1)))

where the continuation of (square 10) is

(lambda (r) (write (+ r 1)))

So as you are recursively translating the program to CPS style, the continuation C will grow as you get deeper into the expression. Note that each of the translation rules [E]|C results in a smaller un-translated E, perhaps empty if E was simple enough, and a larger translated C.

Answer 2

When you convert a code in CPS you practically introduce a strict discipline in evaluation.

When you write (+ x y z), it is unclear the order in which you evaluate each of +, x, y, z. If the language you write in explicitly defines an order, you know what happens. But if the language does not insert an order, you can define the order you wish by writing in/converting the code into CPS, in the example I proposed you would write:

(eval + (lambda (+)
  (eval x (lambda(x)
   (eval y (lambda (y)
    (eval z (lambda (z)
             (+ x y z))))

if you want a left-right evaluation.

If you write your code in CPS, this is like writing code in assembler, as each piece of code can be associated with an instruction that has a corresponding in very low programming. If you convert some code in CPS, you need to uniquely rename variables to avoid collisions. At the time the C language was created, I think it was not clearly defined the CPS transform; this is why the inline specifier rejects recursive calls. It is possible to convert a recursive function into a goto-loop by rewriting the C code and using the CPS transform, but standard C does not want to.

The ways to convert the code into CPS are many. In Mit-scheme for example, the input code is not explicitly rewritten in CPS form, but the evaluation process uses a combination of goto statements and trampoline calls to simulate it (this is a way you won's learn in school about, but it is used in practice).

The recursive CPS code can be converted directly into iterative loops (this is why scheme->C translators do the conversion first) to solve the tail recursion. The first edition of EPL of Dan Friedman details it. There is also an article of Friedman on this. If you cannot find it, I will try to find it for you.