1

context: I'm currently writing a small scheme compiler and took the approach of first transforming into administrative normal form and then into cps (I find this to be the easiest to understand, since there is a clear seperation in what they do).

the question: CPS uses continuations only for non-primitives and not for primitives. I really don't understand the connection between this and being able to correctly desugar call/cc and the likes. Wouldn't it be enough to simply create a lambda for each call/cc, which represents the continuation? Why are we using continuations for all the non-primives / Have I wrongly assumed CPS being a necessity to be able to desugar call/cc?

example:

(+ 2 (call/cc (lambda (k) (k 2))))

becomes (anf)

(let ((v1 (call/cc (lambda (k) (k 2)))))
    (+ 2 v1))

becomes (continution for call/cc as well as its desugaring)

((λ (f cc) (f (λ (x _) (cc x)) cc)) (lambda (k cont) (k 2))
   (lambda (v1) ((lambda (x) (display-or-whatever x)) (+ 2 v1)))))

I'd assume this approach generally works.

Tim Eichholz
  • 119
  • 1
  • 7
  • 1
    Ok, I'm in. What would `(let ((c 11) (r (call/cc (lambda (exit) exit)))) (if (procedure? r) (r 7) (+ r c)))` look like with just lambdas and no CPS conversion? Will it still evaluate to `18`? – Sylwester Aug 09 '20 at 23:49
  • @Sylwester Thanks for your Answer! The correct transformation would be ```(let ((c1 11)) ((lambda (f cc) (f (lambda (x _) (cc x)) cc)) (lambda (exit cont) (cont exit)) (lambda (r) (let ((c2 (procedure? r))) (if c2 (halt (r 7)) (halt (+ r c1)))))))``` So in order for call/cc and the likes to work, I need to never return but instead use a chain of function calls thus needing to add the continuation to all non primitives which will be called in tail position. Correct me if I'am wrong. – Tim Eichholz Aug 10 '20 at 11:43

0 Answers0