Looks good on my end. Thanks!

hello, I was wondering if someone here can explain to me what C is in the notation [E]C where it means the continuation passing style conversion of expression E in the continuation C for example [c]C ==> (C c) ;; application what is C in this case? heres some slides by Marc Feeley, the creator of gambit scheme http://churchturing.org/y/90-min-scc.pdf (scroll down to cps conversion rules) Another example is [(if E1 E2 E3)] C ==> [E1] (lambda (r1) (if r1 [E2] [E3])) C C but I just dont know what C is. any help will be appreciated

The notation [E]C is defined on slide 24 to mean “the Scheme expression that is the CPS-conversion of the Scheme expression E where the Scheme expression C represents E’s continuation”.

Suppose we have an expression (+ 1 2) and focus on the expression E=1. Then the continuation of E is “what happens next”. In this case, after E evaluates to 1, the computation continues adding 2. Thus C=(lambda (v) (+ v 2).

can you do this examples please: (if (= 1 1) 3 4)

so i can get a better idea

thanks

The continuation of (= 1 1) is what happens next. That is, (lambda (v) (if v 3 4).

@soegaard2 will a cps converter turn (if (= 1 1) 3 4) into (lambda (v) (if v 3 4))?

@soegaard2 how should I go about writing a cps converter of scheme expressions?

No, I was just giving an example what the C in [E]C meant.

Let’s figure out what the CPS conversion of the program (if (= 1 2) 3 4) is together. While rule in the slide is the first rule?

so while C is (lambda (r) (%halt r))?

I wrote The conversion rule for if statements above

Yes. The converter gets the program: (if (= 1 2) 3 4) and rewrites it to

[(if (= 1 2) 3 4)] (λ (r) (%halt r) The [ ] is meant to be a box.

Everything in box still needs to be converted. The next rule is:

What is the result?

so the first rule is used first in every type of expression?

Yes.

I dont know what the result is

What’s E1, E2 and E3?

e1 = #t, e2 = 3, and e3 = 4

so (lambda (a) 3)

and (lambda (b) 4)

?

CPS only rewrites the rule, so E1 is `(= 1 2) in my example but E2=3 and E3=4.

So (if (= 1 2) 3 4)] (λ (r) (%halt r) becomes [(= 1 2)] (λ (r1) (if r1 [3] [4]) C C where C is short for (λ (r) (%halt r)

so it becomes (lambda (r1) (if 1 (lambda (r) (%halt 3) (lambda (r) (%halt 4)

?

Almost. The C part becomes: (λ (r1) (if r1 (C 3) (C 4))) or (λ (r1) (if r1 ((λ (r) (%halt r) 3) ((λ (r) (%halt r) 4)))

The result so far is: [(= 1 2)] (λ (r1) (if r1 ((λ (r) (%halt r) 3) ((λ (r) (%halt r) 4)))

If we look at = as a primitive, we can use the + rule as a template:

to rewrite r1 right?

To rewrite (= 1 2). Only things in boxes need to be rewritten.

Let’s put C=(λ (r1) (if r1 ((λ (r) (%halt r) 3) ((λ (r) (%halt r) 4))) and look at: [(= 1 2)] C

If we use the rule with = instead of +, we get:

[1] (λ (r1) [2] (λ (r2) (C (+ r1 r2))))

you mean (= r1 r2) right?

Yes., I meant r2 not r3.

So the box [1] contains a value v. We can use the rule:

((λ (r1) [2] (λ (r2) (C (+ r1 r2)))) 1)

We can use the same rule on the box [2]. ((λ (r1) ((λ (r2) (C (+ r1 r2)))) 2) 1)

And the only thing left to do, is to insert our old C = (λ (r1) (if r1 ((λ (r) (%halt r) 3) ((λ (r) (%halt r) 4))).

((λ (r1) ((λ (r2) ((λ (r1) (if r1 ((λ (r) (%halt r) 3) ((λ (r) (%halt r) 4))) (+ r1 r2)))) 2) 1)

Im going to write this down

@sorawee Do you know of some examples/exercises Job can read/do ?

thanks a lot

Examples are great to look at when learning this.

@soegaard2 yes more examples would be great. you should write a blog about cps conversion. there isnt a lot of info about this

Shriram wrote about CPS conversion in http://cs.brown.edu/courses/cs173/2012/book/Control_Operations.html and https://papl.cs.brown.edu/2020/control-operations.html, in case that’s helpful.