Professor at Chalmers University of Technology, Göteborg, Sweden. Mary has pioneered the use of functional domain specific languages in hardware design and verification, and in resource aware parallel programming. Founder member of IFIP Working Group 2.8 on Functional Programming.
In this talk, I will argue that the ways in which we compose functions should be developed, studied, and even enjoyed for their sheer elegance. From the earliest days of Functional Programming, Higher Order Functions (functions that take functions as arguments and return functions as results) have been a central idea. For example, John Backus, in his classic Turing Award paper from 1978: "Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs", studied a set of higher order functions that still feel pretty familiar. Backus made choices about what higher order functions to include based on the algebraic laws that they obeyed. Richard Bird then delighted us with his beautiful "Introduction to the Theory of Lists", and many colleagues have since built on this fine tradition. I will look back at the history of higher order functions and the study of their algebra, show some of my favourites from the scientific literature, and a few from my own work on capturing patterns in hardware description and GPU programming. This is not just about history, however. I will contend that the idea of capturing patterns of computation as higher order functions has a role to play as we try to figure out how to program heterogeneous systems containing accelerators like FPGAs and GPUs.