📖Compiling with continuations, continued

authors

Kennedy, Andrew

year

2007

url

https://www.microsoft.com/en-us/research/wp-content/uploads/2007/10/compilingwithcontinuationscontinued.pdf

• CPS is better than ANF because it allows easier inlining (ANF requires re-normalization after inlining)

• this paper presents a contification transformation

• q

  Recently, the author has re-implemented all stages of the SML.NET compiler pipeline to use a CPS-based intermediate language. […] There are many benefits: the language is smaller and more uniform, simplification of terms is more straightforward and extremely efficient, and advanced optimizations such as contification are more easily expressed. We use CPS only because it is a good place to do optimization; we are not interested in first-class control in the source language (call/cc), or as a means of implementing other features such as concurrency. Indeed, as SML.NET targets .NET IL, a callstack-based intermediate language with support for structured exception handling, the compilation process can be summarized as “transform direct style (SML) into CPS; optimize CPS; transform CPS back to direct style (.NET IL)”

• re-normalization after inlining in ANF leads to $O(n^2)$ complexity

• Adding conditional expressions to ANF introduces more complexity.

  $\mathsf{let}\ z = (\lambda x. \mathsf{if}\ x\ \mathsf{then}\ a\ \mathsf{else}\ b)\ c\ \mathsf{in}\ M$

  Inlining either duplicates the term $M$: $\mathsf{if}\ c\ \mathsf{then}\ \mathsf{let}\ z = a\ \mathsf{in}\ M\ \mathsf{else}\ \mathsf{let}\ z = b\ \mathsf{in}\ M$

  or introduces a “join-point” function for term M: $\mathsf{let}\ k\ z = M\ \mathsf{in}\ \mathsf{if}\ c\ \mathsf{then}\ \mathsf{let}\ z = a\ \mathsf{in}\ k\ z\ \mathsf{else}\ \mathsf{let}\ z = b\ \mathsf{in}\ k\ z$ (where $k$ is basically a continuation)

• separation of functions and continuations (both in definition letval/letcont and application k x vs f k x)

  • local continuations are basic blocks

    • but this means that f k x is not a tail call if k is a local continuation

      • (or k can be lifted to closure after escape analysis)

  • k x compiles to either jump (local continuation) or tail call (if returning from function)

• §4 describes graph representation with better performance characteristics compared to usual tree

• §5 Contification

  • Continuations are always compiled to simple jumps or function returns. Functions, however, are lambda lifted (if known) or compiled to closure (if escaping). Therefore, it is always good to convert functions to continuations (a process called contification).

  • The contification is possible if a function always returns to the same place.

    • In CPS that means that (1) function is known, (2) all call sites pass the same continuation.

See also

• Appel₁₉₉₂

• Flanagan…₁₉₉₃