Lambda the Ultimate

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 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 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:

http://www.soe.ucsc.edu/~cormac/papers/best-pldi.pdf

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.

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 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!)