Search code examples
schemelispcontinuation-passing

What are the continuation passing style conversion rules?

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.

Solution

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