‹Programming› 2023
Mon 13 - Fri 17 March 2023 Tokyo, Japan

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.

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.

Wed 15 Mar

Displayed time zone: Osaka, Sapporo, Tokyo change

14:00 - 15:30
Research Papers 2Research Papers at Faculty of Engineering Building 2, Room 212
Chair(s): Sebastian Kloibhofer Johannes Kepler University Linz
Continuation-Passing Style, Defunctionalization, Accumulations, and AssociativityVol. 6
Research Papers
Jeremy Gibbons Department of Computer Science, University of Oxford
Link to publication
Consistency types for replicated data in a higher-order distributed programming languageVol. 5
Research Papers
Xin Zhao KTH Royal Institute of Technology, Philipp Haller KTH Royal Institute of Technology
Link to publication
A Theory of Composing ProtocolsVol. 7
Research Papers
Laura Bocchi University of Kent, Dominic Orchard University of Kent, UK, A. Laura Voinea University of Kent, UK
Link to publication