Continuation-Passing Style, Defunctionalization, Accumulations, and Associativity

Jeremy Gibbons1

The Art, Science, and Engineering of Programming, 2022, Vol. 6, Issue 2, Article 7

Submission date: 2021-05-26
Publication date: 2021-11-15
Full text: PDF



Reynolds showed us how to use continuation-passing style and defunctionalization to transform a recursive interpreter for a language into an abstract machine for programs in that language. The same techniques explain other programming tricks, including zippers and accumulating parameters.


Buried within all those applications there is usually a hidden appeal to the algebraic property of associativity.


Our purpose in this paper is to entice associativity out of the shadows and into the limelight.


We revisit some well-known applications (factorial, fast reverse, tree flattening, and a compiler for a simple expression language) to spotlight their dependence on associativity.


We replay developments of these programs through a series of program transformations and data refinements, justified by equational reasoning.


Understanding the crucial role played by associativity clarifies when continuation-passing style and defunctionalization can help and when they cannot, and may prompt other applications of these techniques.

  1., University of Oxford, UK