đź“–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)


Want to receive my đź–‹ posts as I publish them?