Design patterns as higher-order datatype-generic programs

Well, I got side-tracked from working directly on the book. One of the sidetracks was working on my paper Design Patterns as Higher-Order Datatype-Generic Programs from the Workshop on Generic Programming in 2006, revising and extending it for a journal; I’ve put the revised version online. In my defence, I offer that although this isn’t directly content for the book, it is indirectly so.

The central argument of the paper is that current mainstream programming languages such as Java and C# are not expressive enough to allow one to capture the code parts of design patterns such as the Visitor pattern. However, functional languages such as Haskell are sufficiently expressive—which I demonstrate in the paper by providing Haskell representations of four of the GOF patterns.

As the title of the paper suggests, the specific concepts that Haskell provides but current mainstream languages do not are higher-order (parametrization by a function, sometimes called a “lambda” or a “closure”) and datatype-generic (parametrization by a type functor) features. I’ve taken to calling programs exploiting these features “HODGPs”, and languages providing them as “HODGP languages”. A HODGP language lets you capture the code of design patterns as highly flexible reusable software components. Interestingly, Scala also provides HODGP features, together with everything you’d expect from an OO language; I’m hopeful that Java and C# will follow Scala’s lead (or that Scala will supercede them!). Bruno Oliveira‘s DPhil thesis Genericity, Extensibility and Type-Safety in the Visitor Pattern explored using Scala for HODGPs.

Of course, I admit that “capturing the code parts of a pattern” is not the same as capturing the pattern itself. There is more to the pattern than just the code; the “prose, pictures, and prototypes” form an important part of the story, and are not captured in a HODGP representation of the pattern. So the HODGP isn’t a replacement for the pattern.

The four GOF patterns I discuss in the paper are Composite, Iterator, Visitor and Builder. My claim is that Composite (hierarchical structures) amounts to recursive datatypes, Iterator (linear traversals over the elements of a collection) to maps, Visitor (structured traversals also exploiting the shape of a collection) to folds, and Builder (separating the construction of an object from its representation) to unfolds and builds. This is a simplification, both of the patterns and the paper; take a read if you want the full story!

The story so far

I’ve already written a fair amount on these topics, and I don’t propose to blog that as I go. If you’d like some background, you might want to look at the following notes of mine:

• Calculating Functional Programs
• Origami Programming
• Design Patterns as Higher-Order Datatype-Generic Programs

Of course, many others have also written on these topics too. Some articles that have particularly inspired me are:

• Richard Bird’s Marktoberdorf notes An Introduction to the Theory of Lists and Lectures on Constructive Functional Programming (which I’m in the process of making electronically available)
• Roland Backhouse’s Exploration of the Bird-Meertens Formalism
• Grant Malcolm’s PhD thesis Algebraic Datatypes and Program Transformation (sadly not online, as far as I know; but his SCP paper is a good approximation)
• Maarten Fokkinga’s and Erik Meijer’s Program Calculation Properties of Continuous Algebras, and (with Ross Paterson) the bananas paper Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire
• Phil Wadler’s papers Theorems for Free! and Monads for Functional Programming
• Richard Bird and Oege de Moor’s book Algebra of Programming
• The AFP notes on Generic Programming, by Roland Backhouse, Patrik Jansson, Johan Jeuring, and Lambert Meertens
• Roland Backhouse and Paul Hoogendijk’s notes on Generic Properties of Datatypes
• Ralf Hinze and Johan Jeuring’s notes on the Practice and Theory and the Applications of Generic Haskell

(I’m sure there are many others too, which I’ve forgotten to mention.)

Recursion patterns

The central idea in this book is the importance of recursion patterns in functional programming. One of the simplest examples is the map operator on lists, defined in Haskell as follows:

(Intuitively, applies a function to every element of a list, returning a new list. When is applied to the empty list , it returns the empty list; applied to a non-empty list with head and tail , it returns the list whose head is applied to , and whose tail is applied recursively to . Because the function accepts another function as an argument, it is called a higher-order function.)

Another example familiar to Haskell programmers is the fold operator on lists:

(Intuitively, this “folds” a list up into a value; the empty list is folded into the initial value , and a non-empty list is folded by recursively folding the tail then combining the result of this with the head using the binary function .)

One can think of the operators and as abstracted patterns of computation: many useful functions can be expressed in terms of them, and identifying them as useful and reusable concepts saves a lot of repetition in code. Put another way, functional programming (especially lazy functional programming) languages provide the programmer with good tools for building their own control structures; if you don’t have the right kind of loop built-in, just define it as a higher-order function.

But there’s another benefit to be derived from certain recursion patterns (in particular, for the map and fold above, but not for any old custom control structure that you might just have defined). Take the definition of , but abstract from the part:

and read this as an equation in the unknown , for fixed and . It turns out that this equation has a unique solution (modulo some subtleties, as we’ll cover later) — which is, as you might have guessed, . This is called the universal property of , and it is very convenient for reasoning about programs with. For example, to show that some complicated expression equals a given fold, it suffices to show that the expression satisfies the universal property for that fold. Such universal properties will come up again and again throughout the book.

Functional programming

So, what is the “functional programming” in the title about, then? Here’s a very brief characterization, for those who haven’t heard of it before. I’m mostly thinking of the Haskell programming language, and there’s a good explanation and many resources at www.haskell.org.

In a nutshell, functional programming restricts itself to programming with values, rather than with actions. Most programming languages are “imperative”, focussing on the actions: the program describes a series of actions to perform, and only makes incidental use of values in passing; there is a sublanguage of statements (such as assignments to variables, loops, conditional choices) and a sublanguage of expressions (such as for the computation yielding the value to be assigned to a variable in an assignment statement, and for the condition on which a conditional depends).

In contrast, pure functional programming languages dispense with the statements, and make use only of expressions. This might seem very limiting, restricting programs to variations on a mere pocket calculator. But of course, a useful functional language extends the grammar of expressions, so that they cover much more than arithmetic; indeed, expressions typically encompass complex data structures and recursive function definitions, and so are every bit as expressive as statements. Moreover, it turns out that programs expressed in terms of expressions rather than statements are usually shorter (many of the details of the equivalent imperative program are redundant) and simpler (because there are no assignment statements, variables don’t vary, and so the familiar equational reasoning principles of high-school algebra are applicable throughout).

The characterization of programming languages as “functional” versus “imperative” is by no means exhaustive; there are many other styles too. But many of them are also discovering the joys of functional programming; for example, good practice in object-oriented programming states that value objects should be immutable.