An Introduction to Functional Programming Through Lambda Calculus

Looking at the book from a markedly older and greyer perspective, I feel happy with it, by and large. In particular, I remain firmly wedded to the pedagogy of learning by abstraction from concrete examples, of understanding calculus through actually ‘doing’ it in an explicitly operational manner, and of gaining oversight of the layers between a simple, foundational system and a rich language of variegated constructs and structures.

The book’s major eccentricity remains my reformulation of classic calculus syntax. In Church’s notation, applications in function bodies are unbracketed, but functions are bracketed except where there is no ambiguity. I chose instead to bracket applications in function bodies but to not bracket functions except where there is ambiguity, as I felt these were more in keeping with programming language conventions. In retrospect, I suspect that this may prove unduly confusing to novices trying to use this book to complement other sources.

I also now think that the account of lazy evaluation could be simplified and tidied up. There is also merit in one reviewer’s suggestion that a pure lazy polymorphic language might have been described given that both Lisp and SML are strict and impure. However, when the book was written, Miranda was a commercial product and Haskell had not been standardised.

When I started to write this book in 1986, functional programming seemed on an upward trajectory, out of academia into ‘real-world’ computing. Spurred by the Japanese 5th Generation programme, many other nations initiated research and development schemes around ‘stateless’ declarative programming languages. The Japanese projects laid great stress on hardware and software to support logic programming. In contrast, the UK Alvey programme gave equal emphasis to functional languages. Thus, major multi-University and industry projects sought to develop viable functional computing platforms at all levels, from VLSI and multi-processor hardware for graph reduction and combinators, like Coweb, Alice and GRIP, through novel programming languages, like Hope, Standard ML and Haskell, to fully integrated systems like the Flagship.