Compiling without continuations
Presenter: Mehmet
Preview
Mehmet will present a fairly recent paper on a new intermediate representation (IR): “Compiling without continuations” by Maurer et al. which proposes an IR for higher-order functional languages that adds join points (the points in the program when control flow “joins”) to direct functional style instead of continuation passing style (CPS). The authors demonstrate that the IR is expressive enough to admit some optimizations like an improved version of stream fusion. They implement their IR (which they call System FJ) on top of GHC’s Core IR to demonstrate that it can be used in production-ready compilers.
Summary
The paper adds two constructs to an IR in ANF and shows that it makes some transformations straightforward such as case-of-case transformation which flattens consecutive pattern-matches. The join points help de-duplicating (or not duplicating at all) of big expressions in the AST while doing these transformations and they compile to just jumps to certain labels.
They modify GHC to perform a simple analysis to discover which let bindings can be transformed to join points. These are the let bindings that are not captured in a closure or thunk and are applied fully (called with right number of arguments) so they don’t require any heap allocation so tail calls to these let bindings are simple jumps after adjusting the stack. These ideas already existed since first Scheme compilers however this paper introduces ways to statically preserve and exploit join points by integrating them into a type system. Then the paper introduces a way to infer join points by contification and gives some equational transformations (commuting conversions) involving join points for optimizations that can be applied by the compiler. The paper also shows that stream fusion optimization is obtained for free by these commuting conversions.
They compare GHC with this IR against vanilla GHC and measure number of allocations on some micro-benchmarks. In some benchmarks they observe that join points eliminated most of the allocations whereas in other benchmarks the join points increase number of allocations marginally. Finally, the paper argues that join points’ main advantage over CPS is its simplicity which makes many optimizations more straightforward to express.
Discussion
Their join points are similar to notJS merge points used in JSAI, dictating where control flow merges syntactically. However, the similarity is somewhat superficial and their uses differ as JSAI uses them for keeping a smaller representation of the fixpoint and their compiler use it to extract some control flow information to be used in optimizations.