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.

I am Professor of Computing in the Department of Computer Science at the University of Oxford. I also lead the Algebra of Programming research group. I have served as Deputy Head of Department, and as Director of the Software Engineering Programme, which offers part-time professional Masters’ degrees in Software Engineering and in Software and Systems Security. I am Editor-in-Chief of the Journal of Functional Programming, Chair of the ICFP Steering Committee, Past Vice Chair of ACM SIGPLAN, Past Chair of IFIP WG2.1. Before taking up this post in 1999, I held lectureships at Oxford Brookes University and the University of Auckland, New Zealand.