How can we convert between a program using `call/cc` and a program using functions written in CPS?

0
votes

The Scheme Programming Language says

It turns out that any program that uses call/cc can be rewritten in CPS without call/cc, but a total rewrite of the program (sometimes including even system-defined primitives) might be necessary.

What are the general techniques to

  • convert a program using call/cc to a program using functions written in CPS

  • convert in the reverse direction?

1
schemecontinuationscontinuation-passingcallcc
I first learned about the CPS transform from these slides churchturing.org/y/90-min-scc.pdf - it transforms source code in lambda calculus + call/cc to plain lambda calculus. It does this by adding a continuation parameter to every procedure and making each procedure invocation pass in a continuation. - rain1
the intent is, you convert any program into CPS. then, call/cc becomes trivial, in the converted program. -- (call/cc (lambda (k) ...)) ==> (call/cc& (lambda (k) ...) k) == ((lambda (k) ...) k). i.e. (define (call/cc& lam k) (lam k)) is the definition. that's the simple story; I think there were some recent posts about the call/cc implementation in CPS, in scheme, try searching for them. - Will Ness
actually, it should've been (call/cc (lambda (k) ...)) ==> (call/cc& (lambda (k c) ...) c) == ((lambda (k c) ...) c c). i.e. (define (call/cc& lam c) (lam c c)) (under the scheme where the continuation is always passed as the last argument (which is of course an arbitrary choice)). - Will Ness

1 Answers

0
votes

You can learn how to implement the continuation passing transform here http://matt.might.net/articles/cps-conversion/ or from the book Compiling With Continuations by Appel.

The reverse transform is more difficult and has less practical applications but there is a paper about it: Back to Direct Style (1994) by Olivier Danvy