Implementing continuation passing style

I have recently been struggling to implement transformation of Common Lisp source code to continuation passing style (CPS) in my owlisp compiler. I’m not yet done with that, but after hours of racking my brains, it’s finally on a good way as it seems 😉 .

The transformation is being done entirely inside the source language (Common Lisp), so it is one of the first steps that the compiler does, before even thinking about the target language.

Why? Well, CPS brings some benefits with it:

  • It removes the need for a stack, since no function call will ever return to its caller. I aim to translate to C code that gets rid of its implicit call stack (e.g. using setjmp/longjmp, trampolining or any other technique).
    This also means that tail call optimization is implicit and I don’t have to implement that seperately.
  • Once continuations are available, I can implement other control structures by means of them, so I won’t have to hard-wire them into the compiler but can use continuations as building blocks.
    I will however have to figure out if this maybe means a performance penalty. However, I am still far from a stage to put effort into performance optimizations 😉 .
  • I want to provide continuations as a language feature anyway, so having the compiler work in continuation passing style probably won’t hurt – just the opposite.
  • It makes a lot of things explicit that are otherwise implicit, e.g. order of evaluation, returning values etc.