On page 138 of the second edition of his 1971 book, “Categories for the Working Mathematician”, American mathematician Saunders Mac Lane inadvertently coined one of the most famous memes ever made around programming. It is there, precisely there, and not anywhere else, where the phrase “a monad in X is just a monoid in the category of endofunctors” was published for the first time. As is often the case, the true origin of the meme got lost in collective memory, and it ended up being falsely attributed to Philip Wadler, although, in hindsight and all things considered, it was an understandable oversight.
The source of the confusion is none other than an excerpt of a masterpiece often quoted in the pages of this magazine: James Iry’s 2009 brilliant “A Brief, Incomplete, and Mostly Wrong History of Programming Languages”:
1990 - A committee formed by Simon Peyton-Jones, Paul Hudak, Philip Wadler, Ashton Kutcher, and People for the Ethical Treatment of Animals creates Haskell, a pure, non-strict, functional language. Haskell gets some resistance due to the complexity of using monads to control side effects. Wadler tries to appease critics by explaining that “a monad is a monoid in the category of endofunctors, what’s the problem?”
The jury is still out debating the role that Ashton Kutcher had in the creation of Haskell, but as usual, I digress.
What is important to consider is that, yes, Philip Wadler might as well have coined the “endofunctors” meme; after all, he has singlehandedly done more to popularize and to extend the usage of functional programming languages than anyone else in the history of computing. And he has even coined the term “list comprehension”, which might ring a bell among Python developers, among others.
On the other hand, monads are a relatively recent addition to the arsenal of functional programmers; Italian computer science professor Eugenio Moggi was the first to describe the use of monads in programming in two papers published between 1989 and 1991. Philip Wadler took the idea, bolted it down into Haskell, James Iry wrote his blog post, and the Internet did the rest.
I am kidding; Wadler did more than just take the idea: he helped everyone comprehend how monads could be used to marry the “impure” necessities of actual programming with the “pure” realm of functional programming:
Purity has its regrets, and all programmers in pure functional languages will recall some moment when an impure feature has tempted them. For instance, if a counter is required to generate unique names, then an assignable variable seems just the ticket. In such cases it is always possible to mimic the required impure feature by straightforward though tedious means. For instance, a counter can be simulated by modifying the relevant functions to accept an additional parameter (the counter’s current value) and return an additional result (the counter’s updated value).
A quick search shows that Mr. Wadler had a strong interest in such a marriage early on; case in point, his 1985 paper “How to replace failure by a list of successes: a method for exception handling, backtracking, and pattern matching in lazy functional languages” where he argues that
The method itself is straightforward. Each term that may raise an exception or backtrack is replaced by a term that returns a list of values.
Mr. Wadler went above and beyond, explaining that monads were “the essence of functional programming” (1992) and then using them to perform input/output in a pure functional way in the widely acclaimed 1993 paper “Imperative functional programming” (winner of the 2003 ACM SIGPLAN Most Influential POPL Paper Award):
We need a way to reconcile being with doing: an expression in a functional language denotes a value, while an I/O command should perform an action. We integrate these worlds by providing a type
IO adenoting actions that, when performed, may do some I/O and then return a value of typea.
Speaking about “monads” and “functions” and whatnot, the astute reader will remark that mostly everything that has to do with functional programming is related, eventually, to some obscure mathematical theory most self-taught software developers (like the one writing these words) have never heard about, created by a long list of mathematicians including Peano, Cantor, Russell, and Gödel.
And let us not forget the list of functional programming languages whose names derive from mathematicians: Haskell, Curry, Church, Gödel, Russell, Frege, Rocq (originally named “Coq” after French mathematician Thierry Coquand), Kleenex (named after American mathematician Stephen Cole Kleene), and Erlang. Honorific mentions of the non-functional languages Euler, Pascal, Napier88, occam, Z notation (whose name derives from Ernst Zermelo), and Ada are definitely worth mentioning.
Wait, what is Russell’s name doing in the previous lists? Well, according to a 2003 paper by Kevin Klement, from the University of Massachusetts, unpublished papers from Russell suggest that he did much more than just suggest the notation that Alonzo Church used for lambda calculus. But we leave this bit to the reader to explore.
A certain D. A. Turner, from the University of Kent & Middlesex University, wrote in “Some History of Functional Programming Languages” (2013) that the lineage of functional programming starts in the 1930s with Church & Rosser’s Lambda Calculus (a very mathematical theory of computation), then flows through McCarthy’s LISP, Algol 60 (believe it or not), and Gordon & Milner’s ML, culminating in the creation of Haskell from 1987 onwards:
In what follows I have, firstly, focussed on the developments leading to lazy, higher order, polymorphically typed, purely functional programming languages of which Haskell is the best known current example.
Would we be too picky to argue that Mr. Turner forgot to include John Backus, of FORTRAN and ALGOL fame, who in his 1977 Turing Award lecture proposed functional programming as a viable alternative to the Von Neumann programming model?
In this section we give an informal description of a class of simple applicative programming systems called functional programming (FP) systems, in which “programs” are simply functions without variables. The description is followed by some examples and by a discussion of various properties of FP systems.
Philip Wadler is a member of the original committee behind Haskell, probably the most successful exception in the world of committee-created things. Not only that, he also co-created this thing called XQuery (which you might have used 20 years ago to parse some XML, a format not so much en vogue these days) and was also heavily involved in bolting generics on top of Java 5 (a language and a feature that, yes, you might have had a much higher probability of using).
Haskell enjoys quite a level of popularity in our century, similar to that of Lisp in previous decades. Even Edsger Dijkstra defended it in 2001, when a group at the University of Austin, Texas, decided to replace Haskell with Java in the introductory programming course:
A very practical reason for preferring functional programming in a freshman course is that most students already have a certain familiarity with imperative programming. Facing them with the novelty of functional programming immediately drives home the message that there is more to programming than they thought.
But again, Haskell is a subject in itself, and I cannot help but digress once again.
As explained in the “Frequently Asked Questions for comp.lang.functional” page, Philip Wadler collaborated in 1997 with a certain Martin Odersky to create “Pizza”, a functional superset of Java… any similarities with Scala are, I suppose, just a coincidence.
Oh, and Mr. Wadler is a prolific writer of research papers and books, among which stand out the chapters he contributed to “The Implementation of Functional Programming Languages” (1987) by his aforementioned partner in crime, Simon Peyton-Jones (and available for free on the Microsoft Research website at the time of this writing). Also notable is “Introduction to Functional Programming” (1988), co-authored with Richard Bird and renamed “Introduction to Functional Programming using Haskell” for its second edition published in 1998.
Among his most famous papers, let us mention “Theorems for Free!” (1989), “Call-by-Value is Dual to Call-by-Name” (2003), “The essence of functional programming” (1992), and “A History of Haskell: Being Lazy With Class” (2007), the latter being a very appropriate entry for the upcoming HOPL V conference in 2035. Furthermore, a full-text search for his family name on the Journal of Functional Programming (of which Wadler was editor from 1990 to 2004) returns a staggering 421 entries at the time of this writing.
All this record of writing and conference talks is quite opinionated. Philip Wadler has made his life’s mission to show that functional programming languages could be used in the real world as a counterstrike against the overwhelming marketing campaigns around those languages that are not. In his “An Angry Half-Dozen” paper (1998), he describes 6 major technological wonders brought to life thanks to functional programming, and one of them is Erlang:
Erlang bears a striking resemblance to another modern phenomenon, Java. Like Java, Erlang (along with all other functional languages) uses heap allocation and garbage collection, and ensures safe execution that never corrupts memory. Like Java, Erlang comes with a library that provides functionality independent of a particular operating system. Like Java, Erlang compiles to a virtual machine, ensuring portability across a wide range of architectures. And like Java, Erlang achieved its first success based on interpreters for the virtual machine, with faster compilers coming along later.
That same year, he tried to explain why no one was using functional languages:
If a manager chooses to use a functional language for a project and the project fails, then he or she will certainly be fired. If a manager chooses C++ and the project fails, then he or she has the defense that the same thing has happened to everyone else.
Ouch. The following year he repeated himself, merging the previous two papers into another one called “How enterprises use functional languages, and why they don’t”. Was anybody listening at all?
Philip Wadler has kept a record of every important use of functional programming on his own website since at least 1999, as the Internet Archive can testify, and this effort continues at the time of publication of this article.
However, and rather surprisingly, Pandoc is not mentioned in this list, and yet, it is literally made with Haskell! We are delighted to use Pandoc every month to produce the beautiful (DRM-free, by the way) PDF and EPUB files that you can download from this website.
I hope the core idea of this article is clear. Philip Wadler is a towering figure in the field of functional programming, and the pervasiveness of functional features in most mainstream programming languages nowadays owes a lot to the efforts of this single person.
Haskell is a subject in and of itself, and there have been an incredible number of excellent books written about it in the past two decades. At the risk of leaving aside some obviously outstanding entries, we should mention at least “Real World Haskell” by Bryan O’Sullivan, Don Stewart, and John Goerzen; “Learn You a Haskell for Great Good!” by Miran Lipovača (this one taking more than a few cues from _why’s “Poignant Guide to Ruby”); and the more recent “Haskell Programming from First Principles” by Christopher Allen and Julie Moronuki.
However, if you are just interested in a rather short and high-level overview of the Haskell language, “Seven Languages in Seven Weeks” by Bruce Tate (2010) will give you an excellent starting point for your exploration. Precisely, Chapter 8, dedicated to Haskell, starts like this:
Haskell represents purity and freedom for many functional programming purists. It’s rich and powerful, but the power comes at a price. You can’t eat just a couple of bites. Haskell will force you to eat the whole functional programming burrito.
You have been warned.
To close this article, we feel that the general functional programming literature is so vast, we can only scratch the surface by enumerating some hallmark titles; please do not be offended if your favorite title does not appear on this list:
- “The Implementation of Functional Programming Languages”, by Simon Peyton Jones and Philip Wadler.
- “Introduction to Functional Programming”, by Richard Bird and Philip Wadler.
- “Structure and Interpretation of Computer Programs”, in either edition, in Scheme or in JavaScript, by Harold Abelson and Gerald Jay Sussman.
- “The Genius of Lisp”, a recently released gem by Cees de Groot.
- “Practical Common Lisp”, a classic book by Peter Seibel.
- “Paradigms of Artificial Intelligence Programming”, another historically relevant book by Peter Norvig.
- “Introduction to Lambda Calculus”, a freely available book by Henk Barendregt and Erik Barendsen.
- “From Mathematics to Generic Programming”, by Alexander Stepanov & Daniel Rose.
- “F# for Fun and Profit” and “Domain Modeling Made Functional”, both by Scott Wlaschin.
- “Functional Swift”, by Chris Eidhof, Florian Kugler, and Wouter Swierstra.
- “Scala for the Impatient”, by Cay Horstmann.
- And finally, “Learn Functional Programming the Fast Way!”, by Alvin Alexander, also using Scala to teach concepts.
Cover photo by the author.