In Praise of Higher Order Functions

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.

screen shot of video playing

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.

John McCarthy

  • LISP Programmer’s Manual
    • Modification number 7 – March 3, 1959
    • Modification number 12 – March 20, 1959
    • I found one version (not sure which one) behind a paywall
  • LISP 1.5 Programmer’s Manual, second edition, fifteenth printing, 1985

Christopher Strachey

  • 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).

Kenneth Iverson

Graham Hutton

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)
In Praise of Higher Order Functions