In February, Mary Sheeran gave a talk at LambdaDays called “In praise of Higher Order Functions and of some friends and heroes”. I was not able to attend LambdaDays, but I watched the video of the talk and I really enjoyed it.
Sheeran is urging us to read these historic papers, but I was disappointed to be unable to find many of them on the internet. It wasn’t until her 41st slide that she referred to something that we can see unimpeded! I guess it’s not really possible for an amateur to read all of these papers. One really must belong to a university or some other institution that subscribes to these journals and has (or can borrow) these books. What a shame.
Sheeran ended her talk with an admonishment from Christopher Strachey to bring together theory and practice.
It has long been my personal view that the separation of practical and theoretical work is artificial and injurious. Much of the practical work done in computing, both in software and in hardware design, is unsound and clumsy because the people who do it have not any clear understanding of the fundamental design principles of their work. Most of the abstract mathematical and theoretical work is sterile because it has no point of contact with real computing.
Strachey said that over fifty years ago in another paper I can’t find on the internet (“Towards a formal semantics”, 1966), but it doesn’t seem like we’ve listened. I’m a working programmer and I can’t easily read this research.
Anyway, I did track down some of the papers, so I thought I’d post the links I found. Some of the links are PDFs.
- Strachey began experimenting with higher-order functions in 1961
- Strachey developed R1 (foldr) and R2 (foldl)
- David W. Barron reproduced the 1963 workshop from audio recordings
- Barron and Strachey, “Programming”, 1966 (chapter three of Advances in Programming and Non-Numerical Computation, which you can buy from Elsevier)
- Oliver Danvy and Michael Spivey, “On Barron and Strachey’s Cartesian Product Function”, 2007 (buy from the ACM).
- Bitwise Operations, 1961 (buy from the ACM).
- Can Programming Be Liberated form the von Neumann Style? A Functional Style and Its Algebra of Programs, 1978 (1977 Turing award)
- A tutorial on the universality and expressiveness of fold, 1999
- I like that the link is to a file just called “fold.pdf”
- Sheeran mentions that Hutton originally wanted to call the paper “Fold”
R. S. Bird
Guy E. Blelloch
Duane Merrill and Andrew Grimshaw
Horacio Gonzalez-Velez and Mario Leyton
- A survey of algorithmic skeleton frameworks: high-level structured parallel programming enablers, 2010 (behind a paywall)