Into CPS, never to return

CPS, or continuation-passing style, is an intermediate representation for programs, particularly functional programs. It’s used in compilers for languages such as SML and Scheme.

In CPS, there are two rules: first, that function/operator arguments must always be trivial; second, that function calls do not return. From this, a lot falls out.

In this post, we’ll introduce CPS by building a simple (Plotkin1) CPS transform from a small Scheme-like language. We’ll sketch some optimizations on the IR. Then we’ll look at a couple of the common ways to actually compile the IR for execution.

We’re going to implement a recursive function called cps incrementally, starting with the easy forms of the language and working up from there. Many people like implementing the compiler both in Scheme and for Scheme but I find that all the quasiquoting makes everything fussier than it should be and obscures the lesson, so we’re doing it in Python.

This means we have a nice clear separation of code and data. Our Python code is the compiler and we’ll lean on Python lists for S-expressions. Here’s what some sample Scheme programs might look like as Python lists:

Leave a Comment