An algorithm is basically a formula, or a set of steps to solve a problem. There are usually several different ways to solve a problem. Take the act of baking a loaf of bread for example. Your grandma bakes bread a little bit differently than my grandma does, but the process that they use is probably very similar:
Generalized Bread Recipe
1. Put some ingredients into a bowl to make the dough.
2. Turn and knead the dough on a floured surface.
3. Shape and place the dough into baking pans.
4. Stick the pans into the oven to bake.
These are four basic steps that can be followed to bake bread. Following these steps will result in different kinds of bread, depending on how the baker decides to perform each step. Some bakers may even choose to add additional steps to their own recipe, which is totally fine.
Who’s Down With OOP?
One awesome result of Object Oriented Programming (OOP) is that it allows developers to more accurately model real-world situations and concepts. In OOP, the types of problems that programs solve can be broken down into steps and carried out differently in a variety of situations. One effective way to accomplish this is via the template method design pattern.
The Template Method
The template method pattern is used encapsulate algorithms. It defines a skeleton of an algorithm, leaving the details of each step to its subclasses while preserving the actual structure of the algorithm. Consider how putting an algorithm inside of a template could be beneficial. I have listed a few potential benefits below:
- Avoid writing the same code in multiple places.
- Isolate the details of an algorithm inside of a single class.
- Encourages a reusable algorithm design.
- Improved readability.
- Improved maintainability.
What’s a design pattern? A design pattern is a reusable solution to a problem in a given context.
Here is a brief overview of the template method design pattern.
Create an abstract base class, which will represent the skeleton of the algorithm.
Within the abstract base class, declare abstract methods to be overridden for each step of the algorithm. These will essentially act as placeholders.
Within the abstract base class, create a method to serve as the template for the algorithm. This method should be marked as
finalso that it cannot be changed by any subclasses. It will simply call each step in the algorithm.
Other optional methods may be added to the abstract base class.
To implement the abstract base class, simply create a new subclass and provide an implementation of each abstract method. Subclasses of the a skeleton provide a concrete implementation of each step. They represent all the different types of bread-bread baking grandmas — bless their hearts.
These design steps will begin to make more sense as you examine the code below.
Python Example Code
Note that Python does not have a
final keyword like in Java, which is used to mark methods as “un-overridable” by subclasses. After doing some research, I discovered that there are several different ways around this. The simplest way is to just not worry about it and document the usage of your class in the docstring. Due to the nature of the Python programming language, that’s perfectly fine, however there is a way to effectively get the same behavior as the
Making Things Final
If you don’t care to learn about this Python-specific detail, just skip right over this part.
To understand how methods can be marked as
final, first understand what a meta class is. A meta class is basically the class of a class, and to create a custom meta class, you need to subclass
type. That’s what’s going on below with the “Final” class.
__new__ is the first step in instance construction — even before
__init__. There is a lot more to
__new__ in the documentation\), but for this example, just know that it’s used to check if a base class contains a certain method. If it does, then it will throw a syntax error. Using this method, we can essentially mark class methods as final by checking if they exist from the bases argument in the
The Abstract Base Class
Here’s an example of what an abstract base class (the class that represents the skeleton of the algorithm) might look like:
class Final(type): def __new__(self, name, bases, d): if bases and "templateMethod" in d: raise SyntaxError, "Overriding 'templateMethod' is not allowed." return type.__new__(self, name, bases, d) class AbstractClass: __metaclass__ = Final def stepOne(self): msg = "Must provide an implementation of 'stepOne' method." raise NotImplementedError(msg) def stepTwo(self): msg = "Must provide an implementation of 'stepTwo' method." raise NotImplementedError(msg) def stepThree(self): msg = "Must provide an implementation of 'stepThree' method." raise NotImplementedError(msg) def stepFour(self): msg = "Must provide an implementation of 'stepFour' method." raise NotImplementedError(msg) def stepFourHook(self): # Provides a *hook* so that a subclass # may choose to override this method. return False def templateMethod(self): # This method has essentially been marked # as *final* from the class defined up top. # No subclasses can change this. self.stepOne() self.stepTwo() self.stepThree() if self.stepFourHook(): self.stepFour()
If this code was for the bread example, this class might be named something along the lines of, “BasicBreadRecipe” Trying to use this class on its own should result in an error. That’s because this class is only meant to be inherited from. Let’s look at what some subclasses might look like.
I’ve created two separate classes that implement the same algorithm, but have slightly different details for each step. Back to bread…these classes could be likened to, “GrandmaMaeRecipe,” and, “GrandmaEllenRecipe.” Notice that
Solver gracefully adds a fourth step to the process while
OtherSolver simply does not do that part. That’s known as a hook.
These two classes can be used to provide different details for the algorithm. At the same time, they are restricted to only stay within the bounds that have been established by their base class. That’s the template method design pattern.
class Solver(AbstractClass): def stepOne(self): print("Step 1..."), def stepTwo(self): print("Step 2..."), def stepThree(self): print("Step 3..."), def stepFour(self): print("Step 4 too!") def stepFourHook(self): return True class OtherSolver(AbstractClass): def stepOne(self): print("????? 1..."), def stepTwo(self): print("????? 2..."), def stepThree(self): print("????? 3..."),
If I were to try and modify the
templateMethod that we have marked as final, and which represents the core steps of the algorithm, I would be met with an error.