Continuation-Passing Style, Defunctionalization, Accumulations, and Associativity
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 MarDisplayed time zone: Osaka, Sapporo, Tokyo change
14:00 - 15:30
|Continuation-Passing Style, Defunctionalization, Accumulations, and AssociativityVol. 6
Jeremy Gibbons Department of Computer Science, University of OxfordLink to publication
|Consistency types for replicated data in a higher-order distributed programming languageVol. 5
Research PapersLink to publication
|A Theory of Composing ProtocolsVol. 7
Laura Bocchi University of Kent, Dominic Orchard University of Kent, UK, A. Laura Voinea University of Kent, UKLink to publication