Compiling with Continuations, Continued

Compiling with Continuations, Continued, Andrew Kennedy. ICFP 2007.

We present a series of CPS-based intermediate languages suitable for functional language compilation, arguing that they have practical benefits over direct-style languages based on A-normal form (ANF) or monads. Inlining of functions demonstrates the benefits most clearly: in ANF-based languages, inlining involves a renormalization step that rearranges let expressions and possibly introduces a new ‘join point’ function, and in monadic languages, commuting conversions must be applied; in contrast, inlining in our CPS language is a simple substitution of variables for variables.

We present a contification transformation implemented by simple rewrites on the intermediate language. Exceptions are modelled using so-called ‘double-barrelled’ CPS. Subtyping on exception constructors then gives a very straightforward effect analysis for exceptions. We also show how a graph-based representation of CPS terms can be implemented extremely efficiently, with linear-time term simplification.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Very interesting and well

Very interesting and well written paper!

The introduction provides a good overview of the field, and is recommended even for those only looking for a general understanding of the available implementation approaches.

I think these kind of

I think these kind of experience reports are extremely valuable, especially when it comes to something like designing an intermediate language for a compiler which is still very much an art. It's also exciting that the conclusion goes against the common wisdom in the field.

What really would like is to hear some comments on this article from a couple of other compiler gurus like Simon Peyton Jones and Andrew Appel. Especially Appel since he wrote a whole compiler using CPS and then threw that out in favor of ANF.

The decline of CPS

Appel didn't implement CPS very efficiently. His compiler did not stack allocate any closures, possibly because of his beliefs regarding heap allocation at the time, whereas both Rabbit and Orbit would do so whenever possible.

The way they implemented

The way they implemented support for control operators had nothing to do with having CPS as an intermediate language or the switch to ANF afaiu. There was a number of very influential papers in the beginning of the 90's (see the above paper for references) which showed that CPS was in some cases inferior as an intermediate language and argued that people should use ANF. I think the switch was motivated by these papers.

I wasn't referring to

I wasn't referring to control operators. I was referring to something as simple as ordinary function calls and returns. A CPS compiler can turn them into the same stack operations as a direct style compiler, but SML / NJ didn't. This is a considerable hit on architectures like x86 that are optimized for the use of a stack, and it also increases the allocation rate needlessly.

The retrospective in the Best of PLDI by the authors of "The Essence of Compiling With Continuations" is a good read on this subject:

ANF does give you some of the benefits of CPS for free, but not all of them. One problematic example is optimization of nested loops. I don't think there is a way of handling them properly in direct style other than special-casing loops on integer ranges like OCaml and recognizing it in the codegen, or doing a local CPS conversion. CPS also has the benefit of having very orthogonal features, which means a reduction in compiler complexity. The paper we are commenting on is a good example.

Of course, CPS has some disadvantages as well. It does fix an explicit evaluation order early in the compiler, which may not be desirable or may complicate some low-level optimizations in the code generator. As far as control and data flow analysis is concerned, there are results in either direction, although in pure quantity the results seem to favour CPS. The negative results for CPS seem to be mostly due to the merging of calls to continuations in 0CFA style analyses. This problem may be fixed with Gamma-CFA type analyses that merge fewer contexts unnecessarily. There may also be variations on analyses that improve precision for ANF, but most new analyses seem to be developed for CPS anyways.

two different lambdas

Olin Shivers was pointing out to me the other day that when you perform a CPS transformation, you can distinguish "CPS-lambdas", which take a single intermediate result, from "user-lambdas", which take some number of arguments in addition to a continuation and return a computation. Imagine distinguishing them syntactically (say, λ for user-lambda and λ* for control-lambda). Now you have a representation of control that looks like a closure, but it doesn't have to be implemented exactly like a closure.

Of course, you can reuse some or all of the runtime system's implementation of closures for representing continuations, but you can also use a different data structure (say, an algebraic datatype representing evaluation contexts); furthermore you can use the stack if the language's operations on evaluation contexts make it possible and reasonable to do so. Frankly, you can use any of the implementation strategies of continuations you like; CPS just happens to be a syntactic representation that highlights the similarity between continuations and closures.

[note: this probably should've been a reply to the previous comment]

Also note...

Also note that exactly this two-level partitioning is used explicitly in this work, currently being discussed in another thread. (I love cross-thread synchronicity, particularly when it's about CPS triumphalism!)