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!
Like this:
Like Loading...
Published by lukaseder
I made jOOQ
View all posts by lukaseder
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:
https://twitter.com/javaooq/status/504184043765002240
Are you still talking about design patterns, or about J2EE and EJB 2.0? :)
I’m pretty sure they didn’t. I recall checking once some years ago after reading this criticism.
Heh! Well it’s a common anti-pattern, and not just in our field!
This reminds me of: “the purpose of bureaucracy is to fulfil the requirements produced by bureaucracy”
OO is mirroring the real world (which is full of objects).
I have started my career in procedural programming, switching to OO in 1990s and I never regretted the switch.
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.
You probably also believe that you are living in a Matrix :)
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 :)
Indeed. The “code smell” criticism is overrated in this case :) I kind of like the solution using lambdas on the linked blog post, though:
http://blog.higher-order.com/blog/2009/08/21/structural-pattern-matching-in-java
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.
Indeed, ADTs would be excellent. Java is so close with the enum type ;)
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:
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.
Hmm, I’m sorry, I’m not quite sure how this is related…?
Both examples, Scala and Java, are very similar. Whatever the differences, they have nothing to do with “functional programming”.