📖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(n2)O(n^2) complexity
  • Adding conditional expressions to ANF introduces more complexity.

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

    Inlining either duplicates the term MM: if c then let z=a in M else let z=b in 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: let k z=M in if c then let z=a in k z else let z=b in k z\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 kk 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

Backlinks

Want to receive my 🖋 posts as I publish them?