📖Compiling without continuations

authors

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

year

2017

url

https://dl.acm.org/doi/pdf/10.1145/3062341.3062380

1. Introduction

• adding join point to direct-style functional intermediate language
• based on adding join points to GHC
• continues Appel₁₉₉₂, Flanagan…₁₉₉₃, and Kennedy₂₀₀₇
  • “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 Kennedy₂₀₀₇: 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)