Straight to the Point
Software developers are busy people. They have no time to read long, glossy texts. This post is for the experienced Pythonista, so let’s get straight to the point.
The Composite Design Pattern is one of my favorites. It’s an extremely powerful structure — useful any time one needs to treat a collection and its basic elements uniformly. Whenever we have a tree-like data structure, be it a file system, cloud stack resources, code or anything composed from smaller parts, the Composite Pattern is the first design pattern to consider.
In its traditional OO formulation, however, this approach has some serious drawbacks. Look carefully at the typical Composite Design Pattern class diagram:
Fig 1: Composite Design Pattern (from Wikipedia)
Do you see the problem here? If not, that’s understandable. There are actually two, closely-related problems.
First, the traditional Abstract Base Class approach makes overloading ALL abstract interface methods mandatory. Second, as a consequence, the Composite class has to overload all abstract interface methods, even while their implementation would most likely be something as trivial as going over all child components and invoking the corresponding method one by one. It could be Depth First or Breadth First traversing; in most cases, nobody would care which one. All in all, the outcome of the Composite operation is some form of aggregation of the child components’ operations.
If the abstract interface had only one or two methods, that might be a minor problem, although one could argue that it subtly violates the Don’t Repeat Yourself (DRY) principle.
But, what if you have half-dozen or more methods? Overloading all of them would be tedious. Oh, yes, I hear you telling me: “apply the Interface Segregation Principle, and avoid fat interface bloatware.” Maybe, unless I will need a Composite for each segregated interface (then the total number of overloads will be the same if not larger).
But, what if I tell you that enforcing the Interface Segregation Principle is not always practical? Here is an example of an “Abstract” Base Class I recently worked on during the course of a Service Template Compiler project:
Fig 1: CompositeResourceTemplateBuilder
Here, I had a number of challenges to address. I needed to provide a common interface for building cloud resource-specific parts of an AWS CloudFormation Stack Template. Some resources will come from the outside, and thus need to be defined as Stack Template parameters. Others will be created inside the stack and need to be exposed via AWS CloudFormation Stack Template outputs. Some resources might need special conditions to be defined, many will not.
Some will define special descriptors for every function (e.g., API Gateway route and integration), some will not. Some will contribute additional properties to every cloud function resource descriptor (e.g. xRay ActiveTracing); others will not need it. Many will need special environment variables to be defined (e.g., DynamoDB Table reference), but still, some minority (e.g., API Gateway) will not.
And finally, almost every resource, with rare exceptions, will need to provide some access permissions for the functions (‘principle of the least privilege’, you know).
With such a high degree of variability, defining abstract methods turns out to be impractical — many resources will need to implement only a small subset of the overall 8 methods. In this case, a variation of the Null Object Design Pattern worked better — the Abstract Base Class defined a default implementation of each method just returning an empty Tuple (or doing nothing in the case of building permissions).
Applying the Interface Segregation Principle to separate 4 methods invoked on behalf of the whole service from 4 methods invoked for each cloud function also turned out to be more of theoretical than practical value — almost every resource will need to implement some subset of each group.
Now, I’m going to have multiple resources in my service and I need to run the template resource building for each of them and for each function. I might even need to organize my resources in some form of deeper hierarchy (explaining why it’s so would be a long story — maybe in another article).
Applying the Composite Design Pattern seemed to be a very natural choice, but overloading all 8 functions just to define a dump loop running over the composite parts did not sound well. Many years ago, after finishing 2 packs of “Belomor Kanal” (sort of Soviet papirosen I used to smoke as a young software engineer) during a long debugging white night, I learned a very simple principle: when a problem could be defined and solved in a formal way, do it. Every seemingly shorter cut would cost more pain and humiliation.
In the case of my problem, it sounded exactly this: rather than try to find a special solution for the CompositeResourceBuilder, formulate it as a general case problem and solve it. How could such a formal problem statement be defined? Here you go:
For any base (not necessarily abstract) class, automatically define a derived class that will perform a reduce operation for each base class non-void method and foreach operation for each void method
By non-void method, I meant any method which returns some value, and by void method, correspondingly, any method which returns nothing.
Such a problem statement assumes that the return value type of every non-void method belongs to the monoid class. While it sounds intimidating, in practice, it’s fairly simple: it has an identity (e.g., neutral) value (for example, 0 or 1) and associative binary operation (for example, add or multiply). Since all but one of my methods return Tuples, I decided to use reduce over addition. For my case, it was enough.
Ok, how could one automatically define a derived class in Python and the required methods associated with it? For that purpose, Python decorators exist.
We need to write a function, which gets a class as a parameter and returns a new class with the required properties. Here is how it could look like:
Fig 2: CompositeResourceTemplateBuilder class definition
Apparently, it’s fairly simple. We derive a composite class from the base class and prepend it with the @composite decorator. No function overloading, nothing. Looks nice, doesn’t it?
Now, what happens inside? The composite is just a function, which obtains the original class, creates and returns a new one:
Fig 3: Composite Decorator
We first run over each method of the original class (using the Python inspect library), skipping all magic methods (normally surrounded with__) and create a composite version of them.
We then define the __init__() method and a new class using the standard Python type() function structure. After that we stick an __iter__() method into the newly formed class and return it. Nothing too complicated so far.
The __init__() method is also very simple — it just stores the input collection of parts:
Fig 4: Composite Constructor
To really understand what’s going on here we need to look at the _make_method() function:
Fig 5: Composite _make_method
It defines two inner functions: _make_reduce() and _make_foreach() that check the original method return annotation and return the result of one of them accordingly. It’s amazing how powerful E.W. Dijkstra’s stepwise program composition tool is (if applied correctly, of course).
We need to sneak into the _make_reduce() and _make_foreach() functions. First thing first:
Fig 6: Composite _make_reduce
Now, things get a bit more involved. Why in the world would we define yet another inner function? What does it mean that we iterate over self? What’s really going on here?
First, we need yet another inner function because of the Python closure gotcha — without it, we will get a reduce() wrapper over only the last method. If this gotcha drives you mad, you are not alone.
Second, remember the __iter__() method defined above? We utilize it here to go over the composite parts in the Depth First fashion. How exactly it works will be discussed below. To complete the picture, we need to look at the _make_initializer() function:
Fig 7: Composite _make_initializer
Only one line of Python code and such “pleasure”! What happens here? Well, remember the monoid identity value mentioned above? This is it. We need to create an initial value for a return type without knowing what it is. If it were one of the Python built-ins, for example, tuple, we could just call it rt() and that’s it.
The problem is that the return type might be wrapped with one of the Python generic types, for example, Tuple, and then we need to try our luck with the __origin__ attribute.
The _make_foreach() function is even simpler:
Fig 8: Composite _make_foreach
The same need to deal with the Python closure gotcha, the same mysterious looping over self, but at least no need to deal with the return type identity value.
Now, we turn our attention to the Composite iterator:
Fig 9: Composite _make_iterator
We, once again, need to define yet another inner function. This time, not because of gotcha, but because we really need to keep the Composite class in closure. The inner function is a straightforward, non-recursive implementation of the Depth First algorithm over a tree. Why DepthFirst, and why do we need an Iterator at all? First, the Iterator Design Pattern very often comes together with the Composite Design Pattern. The Visitor Design Pattern is another popular option, but in this case, I found it less suitable.
This Iterator allows us to go through the whole Composite Tree and to do something useful; for example, invoke some original method and aggregate the results. But it would also allow us to collect information about which concrete types are present in the Composite Tree (I needed this information in order to decide whether to apply some defaults to the template builder).
I did not have any specific requirement to do it exactly Depth First, but the common implementation works this way and I did not see any particular reason why not.
The basic algorithm works as a Python generator, yielding the Composite parts one by one. It has, however, three special branches triggered by the part type:
- If the part is of the same Composite type, we expand the queue from left — this ensures the Depth First traverse
- The same happens if the part is just an Iterable — a very handy feature that allows for building Composite directly from a collection
- If the part is of a type derived from the original one, we need to yield it as is — the iteration algorithm will take care of iterating over
The later rule is important since the derived class might have some special logic of traversing its parts.
Initially, I tried to implement a recursive version (I did not want to deal with deque), but it did not handle a generic Iterable well, so I gave up. All in all, the approach works, and works well.
Once it started working, I was surprised by how powerful this generic Composite is. When programming the intricate template building rules, I was able to just throw individual pieces of logic into a Composite without worrying too much about how deep the nesting is (it takes seconds, anyhow).
This liberation of mind was a real epiphany saving me a lot of time and effort. As late Steve Jobs used to say: “it just works.”
What was even more powerful and surprising — it’s a combination of the Composite Design Pattern and the Decorator Design Pattern:
Fig 10: Composite and Decorator ResourceTemplateBuilders
The Decorator Design Pattern should not be confused with the Python decorators. The class decorator wraps every method of the original base class and does something useful before and/or after the original method. Some people might argue that what I applied was actually the Proxy Design Pattern.
I also had some doubts about choosing a proper name, but finally settled on Decorator. What works extremely well is that Composite and Decorator are mutually complementing pass/block filters.
Indeed, unless stated otherwise explicitly, the Composite will just delegate every method invocation to its parts. The Decorator, on the other hand, will do exactly the opposite: unless stated otherwise explicitly, it will block every method invocation with the default implementation, which as we remember, does nothing.
Such a combination allows for building a very flexible and powerful policy (“it’s the Strategy Design Pattern!” you say, eh?) dynamically from some external configuration.
Instead of Conclusion
I have stopped understanding why technical publications feel obligated to follow the commonplace writing shtantz:
- Introduction, blah, blah
- Part One, blah, blah
- Part Two, blah blah
- …
- Conclusion, blah, blah
Why can’t we software engineers, just share our thoughts as they are hoping that those who need to understand, will?
Fortunately, thanks to open, not yet fully commercialized publication platforms like Hacker Noon, we still can.
Design patterns and generic programming in Python work, and work very well. One just needs to understand the rules of the game in order not to fall into the over-engineering trap.
If you want to debate this assertion, or if you have found any mistake in my reasoning, drop me a line.
Previously published at https://python.plainenglish.io/generic-composite-in-python-4b88d6727ad0