Abstract: It is 50 years since Tony Hoare observed “certain close analogies between the methods used for structuring data and the methods for structuring a program which processes that data”. But programs have both static structure (following the data) and dynamic structure (execution), and these need not coincide. For example, breadth-first tree traversal should be executed across the grain of the tree structure. I will present a technique for resolving the tension between these conflicting forces: the static structure specifies a multi-phase computation, whose dynamic execution structure might be entirely different. The appropriate abstraction turns out to be an applicative functor - similar to but different from the free applicative.

This is joint work with Oisin Kidney, Tom Schrijvers, and Nicolas Wu.

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 am currently Director of the Software Engineering Programme, which offers part-time professional Masters’ degrees in Software Engineering and in Software and Systems Security. I am current Editor-in-Chief of the Programming Journal, Past Editor-in-Chief of the Journal of Functional Programming, Past Chair of the ICFP Steering Committee, Past Vice Chair of ACM SIGPLAN, Past Chair of IFIP WG2.1. Before taking up my current post in 1999, I held lectureships at Oxford Brookes University and the University of Auckland, New Zealand.