📖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)