Continuation-Passing Style, Defunctionalization, Accumulations, and Associativity

Jeremy Gibbons¹

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

Submission date: 2021-05-26
Publication date: 2021-11-15
DOI: https://doi.org/10.22152/programming-journal.org/2022/6/7
Full text: PDF

Abstract

Context

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.

Inquiry

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

Approach

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

Knowledge

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.

Grounding

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

Importance

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.