How Functional Programming will (Finally) do Away With the GoF Patterns


A recent article about various ways to implement structural pattern matching in Java has triggered my interest:
http://blog.higher-order.com/blog/2009/08/21/structural-pattern-matching-in-java

The article mentions a Scala example where a tree data structure can be traversed very easily and neatly using Scala’s match keyword, along with using algebraic data types (more specifically, a sum type):

def depth(t: Tree): Int = t match {
  case Empty => 0
  case Leaf(n) => 1
  case Node(l, r) => 1 + max(depth(l), depth(r))
}

Even if you’re not used to the syntax, it is relatively easy to understand what it does:

  • There’s a function depth that calculates the (maximum) depth of a tree structure
  • It does so by checking if the input argument is empty, a leaf node, or any other node
  • If it is any other node, then it adds 1 to the maximum of the remaining tree, recursively

The elegant thing here is that the Scala type system helps the author of the above code get this right from a formal point of view, by offering formal type checking. The closest we can do in Java as illustrated by the article is this

public static int depth(Tree t) {
  if (t instanceof Empty)
    return 0;
  if (t instanceof Leaf)
    return 1;
  if (t instanceof Node)
    return 1 + max(depth(((Node) t).left), depth(((Node) t).right));
  throw new RuntimeException("Inexhaustive pattern match on Tree.");
}

But these instanceof checks do smell kind of fishy…

For more details, read the full article here, highly recommended:
http://blog.higher-order.com/blog/2009/08/21/structural-pattern-matching-in-java

How does this compare to the GoF design patterns?

In our object-orientation-brainwashed Java ecosystem (which inherited the OO brainwash from C++), the above instanceof logic would most likely be refactored into an implementation using the visitor pattern from the GoF design patterns book. This refactoring would be done by The Team Architect™ himself, as they are supervising the object oriented quality of your software. The 7 lines of code using instanceof would quickly bloat up to roughly 200 lines of weird interfaces, abstract classes, and cryptic accept() and visit() methods. When in fact, the functional programming approach was so much leaner, even in its imperfect Java instanceof form!

A lot of the GoF design patterns stem from a time when EVERYTHING needed to be an object. Object orientation was the new holy grail, and people even wanted to push objects down into databases. Object databases were invented (luckily, they’re all dead) and the SQL standard was enhanced with ORDBMS features (only really implemented in Oracle, PostgreSQL, and Informix, and maybe some other minor DBs), most of which – also luckily – were never widely adopted.

Since Java 8, finally, we’re starting to recover from the damage that was made in early days of object orientation in the 90s, and we can move back to a more data-centric, functional, immutable programming model where data processing languages like SQL are appreciated rather than avoided, and Java will see more and more of these patterns, hopefully.

If you’re not convinced by the above visitor pattern vs pattern matching example, do read this very interesting series of articles by Mario Fusco:

You will see that with functional programming, many patterns lose their meaning as you’re just starting to pass around functions, making code very simple and easy to understand.

As a wrap up, as Mario presented the content at Voxxed Days Ticino:

Happy functional programming!

18 thoughts on “How Functional Programming will (Finally) do Away With the GoF Patterns

  1. Interesting article. I certainly agree that the GoF patterns can be expressed better in FP.

    I think that the characterization of the world that “Design Patterns” landed in is a bit wide of the mark. Sure, DP was about OO, but OO then meant large objects and inheritance and the book challenged that by promoting small objects and composition. It was revolutionary at the time and changed the way many of us coded, just as FP is changing that again today.

    Rather than seeing the GoF patterns in negative terms, I see them as an important stepping stone to where we are today as functions are a brilliant way of encapsulating and composing small bits of functionality, which the GoF were trying to do with the technology of the time.

    • Thanks for your comment. You’re right, the criticism isn’t entirely fair. The criticism should be directed towards the 90s object orientation hype only. Perhaps, after this OO madness that happened at the time, it would have been too radical to accept that alternative ideas had existed since the 50s (e.g. Lisp) and were concurrently being developed, even in XML with XSLT. So, design patterns were perhaps a much more pragmatic small step back towards reason than going directly functional.

      I still kind of regret this “intermediate” step, though.

      • I think the criticism was fair. In particular they deserve blame for failing to describe the costs of their patterns and sketch out guidelines for where the pros of a pattern outweighed the cons and where they didn’t. I well remember the proliferation of abuses of these patterns back in the GoF heyday, as these patterns were presented and regarded as an absolute Good rather than something to be used judiciously and with restraint.

        Never mind all the jargon they introduced which was used by many programmers to wow managers into letting them build over-engineered monstrosities. They sure sounded more sophisticated than the old-timer saying that “I don’t know what all these visitors and adapters and factories are but I’m pretty sure this could be a lot simpler and more straight-forward.”

        • Perhaps the authors did sketch out those guidelines but you know… People never listen. I have another example of people never listening to the author:

          Never mind all the jargon they introduced which was used by many programmers to wow managers into letting them build over-engineered monstrosities.

          Are you still talking about design patterns, or about J2EE and EJB 2.0? 🙂

          • Perhaps the authors did sketch out those guidelines

            I’m pretty sure they didn’t. I recall checking once some years ago after reading this criticism.

            Are you still talking about design patterns, or about J2EE and EJB 2.0? 🙂

            Heh! Well it’s a common anti-pattern, and not just in our field!

        • No, OO mirrors the common human delusion that the real world is full of objects. Objects are not part of the real world they are constructions of human perception and mental modeling of the world, and as such they are often provisional and prone to no longer working when you look at the “real world” (i.e. problem domain) from a new angle, with new information, or with changes to your needs.

  2. Haha I spent 5 minutes trying to figure out a better pattern for the Java implementation. Eventually I got to admit: the “instance of” pattern is often a code smell, but not always 🙂

  3. You might be interested in Derive4J (on github). One of the problems with Java is it does not have ADTs aka Variants and thus Pattern Matching is just not that elegant. ADTs are one of the things I truly love about type safe Functional Programming that seems to not get as much press or love as the other FP things (monads, higher order functions, higher order kinds, arrows, etc, etc).

    However there are still people like Alan Kay that think there is still hope for a better local (or non local) OOP dispatch (see https://news.ycombinator.com/item?id=11940028). I am not sure what it is but I suppose multimethods might be what he was thinking about and if it is I still prefer ADTs.

  4. Wouldn’t the “proper” object oriented solution just be to override .depth() in Node and Leaf? The implementations would just be their line from the case clause in the match.

    • depth() alone is perhaps just not that good of an example. But let’s also do… Breadth? Average depth? Std deviation on depth? Sum? Count? toString? And suddenly, you will have tons of “rather specialized API”, which could be covered by a single pattern matching API (or visitor accepting API), with a couple of simple traversing functions only.

      As a general rule of thumb:

      • If you have many behaviours (“visitors”) and few types in your hierarchy, follow the visitor pattern, or better, pattern matching
      • If you have many types in your hierarchy and few behaviours, follow your approach
  5. Interesting, when Scala pattern matching is being discussed, it’s typically discussed in the context of the double dispatch, but the multiple dispatch (receiver + N arguments, N>1) is never addressed. I’m curious how Scala handles this case – is it still an elegant code?

    Sure, in Java there is no built-in support, but there are libraries that provide necessary functionality in a pretty elegant way:
    http://www.lshift.net/blog/2006/06/23/multimethods-for-java
    https://github.com/vsilaev/java-multi-methods (forgive me this shameless plug:) )

    Btw, Closure has full built-in support for multimethods – http://clojure.org/reference/multimethods. Worth to mention, I guess.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s