## Sunday, January 11, 2009

### Subsuming the Template Method pattern

It all started with this Kevin Rutherford post, where he talks about his unnatural urge to use the Template Method pattern. He mentions that whenever he sees a duplicate algorithm, he has a natural tendency is to push up the skeleton into a superclass. This way he creates too many inheritance hierarchies, which prove to be quite brittle in the face of changing algorithms.

Template method pattern mandates that the *template method* must model the invariant part of the algorithm, while the concrete classes will implement the variabilities that will be called back into the template method. While the pattern encourages implementation inheritance, which may lead to unnecessary coupling and brittle hierarchies, the pattern has been used quite effectively in various frameworks developed over times.

As the GoF book mentions, the template method pattern leads to an inverted control structure sometimes referred to as the Hollywood Principle, and find better usages in frameworks and libraries to decouple client extensions / implementations from the reusable invariance of the algorithm.

Outside the OO world, template method pattern has been put to great use by many programming languages and frameworks. In many of those applications, like many of the other design patterns, it has been subsumed within the language itself. Hence its usage has transcended into the idioms and best practices of the language itself without much of a ceremony or fanfare.

Consider this code snippet in Scala ..

def doForAll[A, B](l: List[A], f: A => B): List[B] = l match {  case x :: xs => f(x) :: doForAll(xs, f)  case Nil => Nil}

The code processes the input list and invokes the user supplied function (f) on every element. Here the invariant part of the algorithm is the traversal of the list, while the hook is provided by the user supplied function. This follows the template method pattern, and is more popularly known as "map" in functional languages ..

List(1, 2, 3, 4).map {x => x * 2}

In languages that support higher order functions, template methods are ubiquitous, and used as a common idiom to promote framework style reusability. Languages like Haskell allow you to do more advanced stuff in the base abstraction through function composition and monadic sequencing, thereby making the invariant part more robust in the face of implementation variabilities. Even with IoC frameworks like Spring, template methods promote implementing monadic combinators (to the extent you can have in OO without HOF) that result in autowiring and sequencing operations.

Higher Order Template Methods through Message Passing

Template method pattern has two distinct aspects that combine to form the wholeness of the pattern - the commonality of the algorithm described by the base class and the concrete variabilities being injected by the derived implementations. Replace class by module and we have some great examples in Erlang / OTP Framework. Here is a fun example from Joe Armstrong's Programming Erlang ..

-module(server5).-export([start/0, rpc/2]).start() -> spawn(fun() -> wait() end).wait() ->    receive        {become, F} -> F()    end.rpc(Pid, Q) ->    Pid ! {self(), Q},    receive        {Pid, Reply} -> Reply    end.

Erlang implements variability through message passing, dynamic typing and dynamic hot swapping of code. The server skeleton above really does nothing and awaits an impersonation request. On receiving the message {become, F}, the server behaves as an F. F models the variability part, while the above module is the invariant server logic. Feed it with a Factorial message and the server starts behaving as a Factorial server. Isn't this some template method on steroids ? But teh Erlang people never call it by this name. This is because, it is one of the most common idioms of Erlang programming, it needs no formal announcement in the name of a "design pattern". Of course, as I mentioned before, this does not invalidate the necessity of a design pattern - only difference with OO is that in some other languages, the pattern gets melded within the language syntax and idioms.

James Iry said...

HOFs are more like the strategy pattern than the template method pattern. Template methods are a form of static composition while HOFs are based on dynamic composition.

Thus the best translation of map into Java is with a strategy

interface Transformer[A,R] {
R transform(A arg);
}

class ListUtils {
public static[A,B] List[B] map(List[A] lst, Transformer[A,B] f) {
List[B] result = new ArrayList[B];
for (A value : lst) {
}
return result;
}
}
In fact, libraries like Google Collections and Commons Collections do pretty much exactly that - with slight differences in naming of course.

Now, something I just thought of is that in a dynamic prototype based language like Javascript the two patterns, template method and strategy, virtually merge into the same thing - is the prototype a strategy or a template? Interesting question, eh?

Debasish said...

James:

Thanks for the comments. I think in a language that supports HOFs, the difference between Strategy and Template Method goes away. In fact in Java also, I can design my Strategy as a Template Method. How about the following ..

def template(doInit: => Unit, doValidate: => Boolean, doClose: => Unit) = {
doInit
if (doValidate == true) {
// process
}
doClose
}

The initialization, validation and cleaning-up - all of them are strategies that are composed within the template method. And all of them are passed as HOFs.

Really HOFs make most of the patterns subsumed within the language.

What do u think ?

James Iry said...

> Really HOFs make most of the patterns subsumed within the language.

HOFs subsume all patterns in the sense that the Lambda Calculus is Turing complete hence anything that can be computed can be expressed in HOFs.

But once we dig our way out of the Turing tar pit what you wrote is an example of strategy, not template. It just happens to take 3 strategy objects (which we'll call closures) instead of one strategy object with 3 methods.

It's basically the same difference as this (except with some more flexibility in composing the bits).

trait Strategy {
def doInit : Unit
def doValidate : Boolean
def doClose : Unit
}

def template(strategy : Strategy) {
import strategy._
doInit
if (doValidate) {
// process
}
doClose
}

We're back to our old debate about when two patterns are the same. Template method and strategy cover some similar ground, to be sure, but to me the fact that template method is about static composition based on base classes makes it very different from the dynamic composition of HOFs and the strategy pattern.

For one thing, neither Strategy nor HOFs tend to lead you down the path towards deep brittle hierarchies that you mention in your article as being a weakness of template method. They both tend to emphasize creating small, reusable bits of code. There is some difference in granularity of course plus in a nominatively typed language there's more of a reuse barrier with Strategy than there is with HOF. But those differences are smaller than the difference between HOF or Strategy on one hand and template method on the other.

Debasish said...

My initial take on Template Method pattern is that it can lead to brittle class hierarchies and strong coupling, since it encourages implementation inheritance. Then I took up an example in Scala that did not involve any class hierarchies. I really wanted to get rid of classes and demonstrate how the difference between template method and strategy pattern meld away in the HOF context.

In the example that I stated in my last comment, I was also making the same assumption of classlessness (though I did not mention explicitly). If we bring traits / classes into picture then the example that u cited is a strategy pattern. But if we do not have classes, both template methods and strategies become subsumed into HOFs.

Are we in sync now :-) ??