đź“–Compiling without continuations

Maurer, Luke and Downen, Paul and Ariola, Zena M and Peyton Jones, Simon

1. Introduction

  • adding join point to direct-style functional intermediate language

  • based on adding join points to GHC

  • continues Appel1992, Flanagan…1993, and Kennedy2007

    • “could be extend ANF in some way, to get all the goodness of direct style and the benefits of CPS? […] yes!”

  • contributions:

    • extend ANF with join points

    • how to infer which ordinary bindings are in fact join points (contification)

    • recursive join points open up an unexpected optimization opportunity for fusion

4. Contification: inferring join points

  • “contification” = “continuation demotion”

  • contification can be performed on a known function if every call to the function is a saturated tail call

8. Why not use continuation-passing style?

  • There are many similarities between this work and Kennedy2007: join points are continuations; Kennedy separates continuations and ordinary bindings (let vs letcont), and call to continuation and call to function (f k h x vs k x).

  • Pros of direct style:

    • direct style is easier to read and reason about

    • CPS encodes order of evaluation but direct style does not (more important in a call-by-need language)

    • some transformations are harder in CPS (e.g., common sub-expression elimination)