Sunday, July 26, 2015

Economy of Means: On the Elimination of Inheritance (6/6)


Method call forwarding: a language extension

For a brief moment, allow me to dream that extensions could be easily and instantaneously incorporated into the Java language. It is a dangerous idea, because one never knows how new features will interact with already existing aspects of the language. And it is certain that human beings, as a group, are extremely innovative, too much for their own good. So one cannot easily predict how new constructs will be abused of. Still, I would take my chances and wish for the following:
  • package internal visibility for interfaces methods,
  • automatic call forwarding, a new language construct studied extensively in this paper.
Let me show you how the code presented last in the previous section would be simplified:
public interface Component {
    public void setBackgroundColor(Color color);
    Box computeBox(int x, int y);
    void draw(int x, int y, int width, int height, Graphics canvas);
}

public HorizontalLayoutContainer implements Component {
    private Background background;
    private int padding;
    private List<Component> components;

    forward to this.background;

    public HorizontalLayoutContainer() {
        this.background = new Background();
        this.padding = 0;
        this.components = new ArrayList<Component>();
    }

    Box computeBox(int x, int y) {
        int x = location.getX();
        int y = location.getY();
        int width = 0;
        if (!this.components.isEmpty()) {
            width = -this.padding;
        }
        int height = 0;
        List<Box> content = new ArrayList<Box>();
        for (Component component: this.components) {
            Box box = component.computeBox(x + width, y);
            content.add(box);
            width = width + box.getWidth + this.padding;
            height = Math.max(height, box.getHeight());
        }
        return new Box(x, y, width, height, this, content);
    }

    public void setPadding(int padding) {
        this.padding = padding;
    }

    public void add(Component component) {
        this.components.add(component);
    }

    public void remove(Component component) {
        this.components.remove(component);
    }
}

public Label implements Component {
    private Background background;
    private String text;
    private Font font;
    private Color textColor;

    forward to this.background;

    public Label(Font font) {
        this.background = new Background();
        this.text = "";
        this.font = font;
        this.textColor = Color.BLACK;
    }

    Box computeBox(int x, int y, Graphics canvas) {
        FontMetrics metrics = graphics.getFontMetrics(this.font);
        int height = metrics.getHeight();
        int width = metrics.stringWidth(text);
        return new Box(x, y, width, height, this);
    }

    void draw(int x, int y, int width, int height, Graphics canvas) {
        this.background.draw(x, y, width, height, canvas);
        canvas.setColor(this.textColor);
        canvas.setFont(this.font);
        canvas.drawString(this.text, x, y + height);
    }

    public void setText(String text) {
        this.text = text;
    }

    public void setTextColor(Color color) {
        this.textColor = color;
    }
}

// all the other classes remain unchanged
Line forward to this.background; means that any call to a method which is not directly defined in the class, will be automatically forwarded to instance background. In practice, for class HorizontalLayoutContainer this concerns both methods draw and setBackgroundColor. Whereas in class Label, this is only for method setBackgroundColor. The code of method draw in class Label shows how method overriding is simply achieved by standard composition.
Even though keyword forward to is only syntactic sugar for what was previously manually achieved, it reduces the cost of modifying the program. Suppose, we wish to add a new method which is shared by all components. All we need to do is declare this new method signature on interface Component, and implement its code in class Background. The components themselves are left untouched: there is no need to painstakingly wire the additional call for each of them.
The principal advantage of replacing inheritance by automatic call forwarding is simply this: if the wrong design decision is made, the code is only one step away from a design that uses composition only. This is less costly to unravel than entanglements found in code filled with misuses of class inheritance.


A systematic translation

As we have seen throughout the previous posts on the topic, a combination of class composition, interface inheritance and automatic call forwarding, can often advantageously replace class inheritance. But, is it truly always the case? Isn't there the risk of a dramatic rise in syntax volume and a resulting escalation of maintenance costs? Most importantly, can the exact same API be always presented to the external user? In order to convince you so, I will sketch a code transformation that systematically removes class inheritance. However, for concision sake, I will indulge in a few simplifications:
  • all fields are assumed to be private and accessed via methods.
  • package internal access modifier can be treated exactly like the public visibility modifier. It will thus not be discussed.
  • protected access modifier will not include package internal visibility (this is one of the many subtle differences between Java and C#)
First, let us recapitulate everything that an inheritance relationship of B from A enables:
  1. an instance of B has the signature (interface) of A: it offers all public methods of A and can be put in a collection of objects of type A,
  2. a method that belongs to A is written only once and then provided by all descendants, thus allowing code reuse in the whole hierarchy,
  3. a method declared as abstract in A can be implemented anywhere lower in the class hierarchy, for instance in B,
  4. B can call any non private method of A through keyword super,
  5. a constructor of B can transmit parameters to a constructor of A,
  6. class B can redefine (override) methods of A,
  7. if code in A calls one of its method which is overridden in B, then it is the version in B which gets executed (this language feature is called dynamic method dispatch),
  8. code in B can call the instance-protected methods of A on the same instance (accessible via this or super),
  9. code in B can also call the class-protected methods of any other instance of A (accessible via a method or constructor parameter of type A).
Basic inheritance
A working design which covers points 1 through 3 involves:
  • an interface IA with all the visible (both abstract and concrete) methods of A,
  • a concrete class A' with the code of all concrete methods of A,
  • a class B' with the code of B.
If class A is not abstract, then A' is marked as implementing IA. Class B' differs heavily from B in that inheritance is replaced by composition:
  • all its constructors create a new instance of A' and store this instance in some new field (say superClass),
  • automatic call forwarding is performed onto this.superClass,
  • lastly it is marked as implementing interface IA.

Method override
Point 4 to 6 are easy: methods overridden in B are simply defined in B' and any occurrence of super in B is replaced by a reference to field this.superClass.
Dynamic dispatch
Point 7 is rather tricky. Generally speaking, a method call that goes in the opposite direction of the class hierarchy is a sign of a design flaw; especially when the method called is abstract. In this case, the parent class should most probably be split and the strategy pattern applied (as was shown previously). However, this insight is not enough: how should the parent class be split? Indeed, nothing prevents cycles in the call graph between methods of the same class.
Hopefully, we can aim for something simpler. All that is really necessary is for the parent class to hold a reference to its descendant:
  • all A' constructors expect an additional parameter of type IA,
  • this parameter is kept in a new field, say actualThis,
  • all references to this within the code of A' are re-routed via this.actualThis so that calls reach the correct implementation.
Class B' would need to pass itself (this) when calling any constructor of A'. Note that passing this to a constructor is a clear code smell: at least now, the dependence cycle is explicit.

Inheritance chain
I am all for flat hierarchies! Still does the previous transformation apply for any arbitrary level of inheritance depth?
Let us suppose that class C extends class B. Class B' is produced the way class A' was, and class C' the way B' was:
  • an interface IB with the visible signature of class B is introduced,
  • class B implements interface B',
  • its constructors get an additional parameter of type IB, which is stored in an additional field (actualThis),
  • all occurrences to this are replaced by reference to this new field,
  • etc, etc...
All seems to go seamlessly. But, a detail is missing. Maybe you already spot the flaw? It is already present with an inheritance depth of only 1? What if the external user of the class hierarchy needs to instantiate class B' (or class A' for that matter) directly? What is she supposed to pass to the actualThis constructor parameter?
The fix is easy but dull. Every constructor must be doubled: one version expect parameter actualThis, the other assigns this to actualThis instead.

Protected methods
Now we get to the delicate matter of protected methods (points 8 and 9). In Java, accessibility modifier protected really encompasses two distinct aspects: access on the same instance (through this), or access to a distinct instance (through a method parameter).
I wonder if there are any concrete cases that can demonstrate the necessity of class-protected accessibility. Especially considering the fact that class-private combined with instance-protected might always prove to be a sufficient alternative. If you happen to find any real example, please let me know! Anyway, if we still wish to keep this aspect, then we must extend Java with allow class-protected methods in interfaces. The design described in the previous section applies. The external user of the class hierarchy never sees class A', but always interface IA instead. Hence, all method parameters that have type A in class B, are declared with interface IA in class B'.
On the other hand, if we consider instance-protected accessibility only, then a more elaborate design allows us to completely bypass keyword protected:
  • interface IAP contains the public (and package internal) methods of class A,
  • interface IA extends IAP and adds all the protected methods of class A,
  • interface IBP publishes the externally visible (public and package internal) methods of class B.
  • a factory creates instances of A' and B' for an external user, and hides their actual types under the public interfaces IAP and IBP.


Expunged of inheritance the language becomes much easier to learn. Many keywords with rather complex semantics become unnecessary: override, abstract, extends, final, super. That is why I would happily trade inheritance for automatic call forwarding. This seems also to be the choice of the Go language designers, albeit presented a bit differently: Go has embedded types.
In any case, various recent programming languages are experimenting horizontal reuse as an alternative way to assemble fragments of behaviors. Here is an incomplete list:

Loops of Zen

The missing zero symbol

Conventional (crowd) wisdom seems to esteem programming languages which are geared with all the latest fancy gadgets. On the contrary, I believe programming languages should have a central paradigm and a few orthogonal constructs to support this paradigm. A minimalist, yet well-thought, language, does not waste your time evaluating the strengths and weaknesses of each of its numerous primitives. It helps you solve your problems, instead of having you solve its own design issues. The inheritance vs. composition opposition is a major dilemma of classical object-oriented languages. Even though, most object oriented tutorials put a lot of emphasis on the concept of inheritance, the mantra to prefer composition over inheritance can also be quite often encountered. Even Java's creator, James Gosling, wonders about class inheritance.
I believe (and I am not alone, see this) we can make an even stronger claim: inheritance packs too many aspects at once (see A systematic translation for a detailed discussion). It is extremely rare for all these aspects to be required together. Hence, using inheritance couples classes more than is desirable and leads to monolithic code. Hopefully, it is possible to rephrase most programs without any, or at least very few class hierarchies.
With the help of small concrete examples, I have shown some techniques that allow to advantageously replace the various aspects of inheritance by alternative, more precise, designs:
Eliminating inheritance, exposes the hidden, yet true, complexity of a design. It leads to a more focused, more precise, more intelligible code base. With smaller, decoupled, reusable components, the source code becomes more malleable.
Primitive numeral systems were lacking a symbol for zero. In exchange, they had several symbols for large numbers like ten, a hundred, a thousand. Inheritance and a host of related complex notions (abstract, override, protected, super, final) are exactly like these large numbers: unnecessary nuisance. Maybe automatic call forwarding will prove to be the missing zero. In any case, together with interface inheritance and composition, it offers a simple yet powerful alternative. A language with these primitives would be the truly minimalist approach, a real economy of means.


Zhou Bi Suan Jing

Sunday, July 5, 2015

Economy of Means: On the Elimination of Inheritance (5/6)


Object happy families



Happy families card game

In the previous example, the various characters (Witch or Cauldron) were accessed only through the signature of their common parent class (Character). This is exactly what made our refactoring possible: all characters could be encoded using the parent class only.
This is not always the case. Consider various objects that share some common behaviour. Sometimes, they are grouped together; then only the common methods can be called. But sometimes, they are individually set up and then the specific interfaces must be accessed. That is an ideal case for inheritance, with both the union and reuse aspects intertwined.
In the next example, I draw inspiration from the java Abstract Window Toolkit (AWT), a library of graphical components. We consider a baby version of such a graphical library. It only offers two components: a Label and an HorizontalLayoutContainer. The Label displays one line of text, while the HorizontalLayoutContainer arranges components horizontally, inserting some padding between each. Some methods are shared by all components. For instance, method setBackgroundColor allows to choose the background color of any component. These methods are defined on a base element called Component. Whether Component is an abstract class or an interface does not matter from the external perspective of the library user. We postpone this decision until implementation time. The library user wants to be able to declare and assemble components in order to paint them on some canvas (class Graphics). In addition, she might need to dynamically change the aspect of her graphical interface, without having to build everything from scratch. To fulfill these needs, the public signature of the library classes might look like this:
Component
  void paint(Graphics)
  void setBackgroundColor(Color)

HorizontalLayoutContainer(): Component
  void setPadding(int)
  void add(Component)
  void remove(Component)

Label(): Component
  void setText(String)
  void setTextColor(Color)
The traditional implementation of such an API would use inheritance and could look like this:
package not.at.school.gui;

Box {
    private int x;
    private int y;
    private int width;
    private int height;
    private Component component;
    private Collection<Box> content;

    Box(int x, int y, int width, int height, Component component) {
        this(x, y, width, height, component, new ArrayList<Box>());
    }

    Box(int x, int y, int width, int height, Component component, 
        Collection<Box> content) {
        this.x = x;
        this.y = y;
        this.width = width;
        this.height = height;
        this.component = component;
        this.content = content;
    }

    void paint(Graphics canvas) {
        this.component.draw(this.bounds, canvas);
        for (Box box: content) {
            box.paint(canvas);
        }
    }

    int getWidth() {
        return this.width;
    }

    int getHeight() {
        return this.height;
    }
}

public abstract Component {
    private Color backgroundColor;

    Component() {
        this.backgroundColor = Color.WHITE;
    }

    void draw(int x, int y, int width, int height, Graphics canvas) {
        canvas.setColor(this.backgroundColor);
        canvas.fillRect(x, y, width, height);
    }

    abstract Box computeBox(int x, int y);

    public void paint(Graphics canvas) {
        Box box = this.computeBox(0, 0);
        box.paint(canvas);
    }

    public void setBackgroundColor(Color color) {
        this.backgroundColor = color;
    }
}

public HorizontalLayoutContainer extends Component {
    private int padding;
    private List<Component> components;

    public HorizontalLayoutContainer() {
        super();
        this.padding = 0;
        this.components = new ArrayList<Component>();
    }

    override Box computeBox(int x, int y) {
        int x = location.getX();
        int y = location.getY();
        int width = 0;
        if (!this.components.isEmpty()) {
            width = -this.padding;
        }
        int height = 0;
        List<Box> content = new ArrayList<Box>();
        for (Component component: this.components) {
            Box box = component.computeBox(x + width, y);
            content.add(box);
            width = width + box.getWidth() + this.padding;
            height = Math.max(height, box.getHeight());
        }
        return new Box(x, y, width, height, this, content);
    }

    public void setPadding(int padding) {
        this.padding = padding;
    }

    public void add(Component component) {
        this.components.add(component);
    }

    public void remove(Component component) {
        this.components.remove(component);
    }
}

public Label extends Component {
    private String text;
    private Font font;
    private Color textColor;

    public Label(Font font) {
        super();
        this.text = "";
        this.font = font;
        this.textColor = Color.BLACK;
    }

    override void draw(int x, int y, int width, int height, 
                       Graphics canvas) {
        super.draw(x, y, width, height, canvas);
        canvas.setColor(this.textColor);
        canvas.setFont(this.font);
        canvas.drawString(this.text, x, y + height);
    }

    override Box computeBox(int x, int y, Graphics canvas) {
        FontMetrics metrics = graphics.getFontMetrics(this.font);
        int height = metrics.getHeight();
        int width = metrics.stringWidth(text);
        return new Box(x, y, width, height, this);
    }

    public void setText(String text) {
        this.text = text;
    }

    public void setTextColor(Color color) {
        this.textColor = color;
    }
}
Painting is a two-step process:
  • first the bounds (the x and y position as well as the width and height) of all components are computed from bottom to top,
  • then components are individually drawn going from top to bottom.
This ensures that components are stacked in the right order: backgrounds are filled before texts are drawn. All dynamic properties (bounds and sub-boxes) of a drawn component are carried by a distinct class Box. I prefer this to the traditional AWT implementation where components carry both their declaration and dynamic properties. Because of this design choice, some properties (such as the dimensions) of the AWT components are invalid until drawn.
There is an anecdoctical implementation difficulty with method draw of class Label. On the screen, y-coordinates increase downward, but strings are rendered above the baseline. Hence, when drawing text, the text height must be added to the y-coordinate.
Please take note of the access modifiers: they have been carefully picked so as to make this implementation work, while at the same time restricting external user to access only the minimal API. In order to do so:
  • all classes belong to package not.at.school.gui,
  • all fields are private,
  • methods and classes which need to be accessed from outside the package are public,
  • all remaining methods and classes are package internal.
Component is an abstract class. It includes both the signature of methods common to all components (such as abstract method computeBox), as well as the shared implementation of some methods (such as draw, paint and setBackgroundColor). So, let us play the refactoring without inheritance game once again and see where this leads us to.




As previously explained in Revisiting keyword abstract, abstract classes tend to rely on their descendant classes. So is also the case for Component whose method paint calls abstract method computeBox. We are first going to eliminate this reverse dependence relationship by applying the strategy pattern. We split Component in two by introducing a new class Renderer whose only responsibility is to paint components. This changes the external API of our package, but in my opinion to the better. Why should the Component be in charge of painting itself? APIs with more structure, and smaller classes are usually easier to understand. Here is the code which is modified to perform this first rewrite step:
public Renderer {
    private Graphics canvas;

    public Renderer(Graphics canvas) {
        this.canvas = canvas;
    }

    public void paint(Component component) {
        Box box = component.computeBox(0, 0);
        box.paint(canvas);
    }
}

public abstract Component {
    private Color backgroundColor;

    Component() {
        this.backgroundColor = Color.WHITE;
    }

    void draw(int x, int y, int width, int height, Graphics canvas) {
        canvas.setColor(this.backgroundColor);
        canvas.fillRect(x, y, width, height);
    }

    abstract Box computeBox(int x, int y);

    public void setBackgroundColor(Color color) {
        this.backgroundColor = color;
    }
}
Next we further split base class Component to distinguish the common signature definition from the code reuse aspects. Ideally, this should lead to, on one hand, an interface, and on the other hand a concrete class.
However, Component interface consists in two kinds of methods:
  • Some methods, such as setBackgroundColor, are part of the public API. An external user should be able to call them.
  • Other methods, such as computeBox and draw, are implementation details, only necessary for the code to be functional.
Unfortunately, for whatever reason, Java interfaces do not let you declare methods as package internal. Making all methods public, would unnecessarily burden the external user with useless knowledge about the internal implementation details. So we prefer a fully abstract class, with some methods public and other package internal.
We decide to name the new concrete class Background. It contains the implementation of two methods:
  • method draw fills an opaque rectangle with the component's background color,
  • while method setBackgroundColor allows to choose this color.
Here is the result of this refactoring step:
public abstract Component {
    public abstract void setBackgroundColor(Color color);
    abstract Box computeBox(int x, int y);
    abstract void draw(int x, int y, int width, int height, 
                       Graphics canvas);
}

Background {
    private Color backgroundColor;

    Background() {
        this.backgroundColor = Color.WHITE;
    }

    void draw(int x, int y, int width, int height, Graphics canvas) {
        canvas.setColor(this.backgroundColor);
        canvas.fillRect(x, y, width, height);
    }

    void setBackgroundColor(Color color) {
        this.backgroundColor = color;
    }
}
Next, we are able to replace the inheritance, by a delegation to Background, in both leaf components:
public HorizontalLayoutContainer extends Component {
    private Background background;
    private int padding;
    private List<Component> components;

    public HorizontalLayoutContainer() {
        this.background = new Background();
        this.padding = 0;
        this.components = new ArrayList<Component>();
    }

    override public void setBackgroundColor(Color color) {
        this.background.setBackgroundColor(color);
    }

    override void draw(int x, int y, int width, int height, 
                       Graphics canvas) {
        this.background.draw(x, y, width, height, canvas);
    }

    // the rest of the code remains unchanged...
}

public Label extends Component {
    private Background background;
    private String text;
    private Font font;
    private Color textColor;    

    public Label(Font font) {
        this.background = new Background();
        this.text = "";
        this.font = font;
        this.textColor = Color.BLACK;
    }

    override public void setBackgroundColor(Color color) {
        this.background.setBackgroundColor(color);
    }

    override void draw(int x, int y, int width, int height,
                       Graphics canvas) {
        this.background.draw(x, y, width, height, canvas);
        canvas.setColor(this.textColor);
        canvas.setFont(this.font);
        canvas.drawString(this.text, x, y + height);
    }

    // the rest of the code remains unchanged...
}
To recapitulate, here is the final code that results from the application of all the rewrite steps that were just described:
package not.at.school.gui;

Box {
    private int x;
    private int y;
    private int width;
    private int height;
    private Component component;
    private Collection<Box> content;

    Box(int x, int y, int width, int height, Component component) {
        this(x, y, width, height, component, new ArrayList<Box>());
    }

    Box(int x, int y, int width, int height, Component component,
        Collection<Box> content) {
        this.x = x;
        this.y = y;
        this.width = width;
        this.height = height;
        this.component = component;
        this.content = content;
    }

    void paint(Graphics canvas) {
        this.component.draw(this.bounds, canvas);
        for (Box box: content) {
            box.paint(canvas);
        }
    }

    int getWidth() {
        return this.width;
    }

    int getHeight() {
        return this.height;
    }
}

public Renderer {
    private Graphics canvas;

    public Renderer(Graphics canvas) {
        this.canvas = canvas;
    }

    public void paint(Component component) {
        Box box = component.computeBox(0, 0);
        box.paint(canvas);
    }
}

public abstract Component {
    public abstract void setBackgroundColor(Color color);
    abstract Box computeBox(int x, int y);
    abstract void draw(int x, int y, int width, int height, 
                       Graphics canvas);
}

Background {
    private Color backgroundColor;

    Background() {
        this.backgroundColor = Color.WHITE;
    }

    void draw(int x, int y, int width, int height, Graphics canvas) {
        canvas.setColor(this.backgroundColor);
        canvas.fillRect(x, y, width, height);
    }

    void setBackgroundColor(Color color) {
        this.backgroundColor = color;
    }
}

public HorizontalLayoutContainer extends Component {
    private Background background;
    private int padding;
    private List<Component> components;

    public HorizontalLayoutContainer() {
        this.background = new Background();
        this.padding = 0;
        this.components = new ArrayList<Component>();
    }

    override Box computeBox(int x, int y) {
        int x = location.getX();
        int y = location.getY();
        int width = 0;
        if (!this.components.isEmpty()) {
            width = -this.padding;
        }
        int height = 0;
        List<Box> content = new ArrayList<Box>();
        for (Component component: this.components) {
            Box box = component.computeBox(x + width, y);
            content.add(box);
            width = width + box.getWidth() + this.padding;
            height = Math.max(height, box.getHeight());
        }
        return new Box(x, y, width, height, this, content);
    }

    override void draw(int x, int y, int width, int height,
                       Graphics canvas) {
        this.background.draw(x, y, width, height, canvas);
    }

    override public void setBackgroundColor(Color color) {
        this.background.setBackgroundColor(color);
    }

    public void setPadding(int padding) {
        this.padding = padding;
    }

    public void add(Component component) {
        this.components.add(component);
    }

    public void remove(Component component) {
        this.components.remove(component);
    }
}

public Label extends Component {
    private Background background;
    private String text;
    private Font font;
    private Color textColor;

    public Label(Font font) {
        this.background = new Background();
        this.text = "";
        this.font = font;
        this.textColor = Color.BLACK;
    }

    override Box computeBox(int x, int y, Graphics canvas) {
        FontMetrics metrics = graphics.getFontMetrics(this.font);
        int height = metrics.getHeight();
        int width = metrics.stringWidth(text);
        return new Box(x, y, width, height, this);
    }

    override void draw(int x, int y, int width, int height,
                       Graphics canvas) {
        this.background.draw(x, y, width, height, canvas);
        canvas.setColor(this.textColor);
        canvas.setFont(this.font);
        canvas.drawString(this.text, x, y + height);
    }

    override public void setBackgroundColor(Color color) {
        this.background.setBackgroundColor(color);
    }

    public void setText(String text) {
        this.text = text;
    }

    public void setTextColor(Color color) {
        this.textColor = color;
    }
}
Does this alternative implementation really look that much insane ? By avoiding inheritance and several related complex concepts, this code strives to follow a philosophy of economy of means. I personaly like it.
Admittedly, it is a real pity that Java interfaces do not accept package internal methods. This would eliminate some spurious syntax (the presence of override and abstract keywords).
Other than that, the main disadvantage of this kind of code consists in the cost of having to write all method forwarding by hand (see the definition of method setBackgroundColor in both leaf classes). With just a small extension to the Java programming language we could improve on that. If you are interested, please read the discussion in the next section.


The Parakeet and the Mermaid
Henri Matisse


Sunday, June 14, 2015

Economy of Means: On the Elimination of Inheritance (4/6)

Revisiting keyword abstract

In section From template method to strategy, we saw how pattern strategy could help eliminate inheritance.
Let us delve into this topic by considering another example: we are building a game which involves moving characters (class Character) on a 2-dimensional canvas (class Canvas). Each character is represented by a bitmap (class Bitmap) placed at a given position (class Position). A character is drawn on the canvas by method draw. Each character has its unique way of moving around. This is modeled by method move, which changes the character's current position and is called by the game engine at each cycle:
abstract class Character {
    private Position currentPosition;
    private Bitmap bitmap;

    public Character(Position startingPosition, Bitmap bitmap) {
        this.currentPosition = startingPosition;
        this.bitmap = bitmap;
    }

    public void draw(Canvas canvas) {
        canvas.drawImage(this.currentPosition, this.bitmap);
    }

    abstract void move();
}

For sake of simplicity, we present only two kinds of characters: a witch and a cauldron. The witch can appear anywhere randomly within the boundaries of the screen, which are delimited by maximumHeight and maximumWidth:
class Witch extends Character {
    private int maximumHeight;
    private int maximumWidth;

    public Witch(int maximumHeight, int maximumWidth, 
                 ResourceManager resourceManager) {
        super(new Position(0, 0), 
              resourceManager.getBitmapForWitch());
        this.maximumHeight = maximumHeight;
        this.maximumWidth = maximumWidth;
        this.move();
    }

    public void move() {
        int x = Math.random() * this.maximumWidth;
        int y = Math.random() * this.maximumHeight;
        this.currentPosition = new Position(x, y);
    }
}

While the cauldron starts at some initial height and falls down until it reaches the ground, which is placed at some ordinate groundLevel:
class Cauldron extends Character {
    private int groundLevel;

    public Cauldron(Position startingPosition, int groundLevel, 
                    ResourceManager resourceManager) {
        super(startingPosition, 
              resourceManager.getBitmapForCauldron());
        this.groundLevel = groundLevel;
    }

    public void move() {
        int y = this.currentPosition.getY();
        if (y <= this.groundLevel) return;
        int x = this.currentPosition.getX();
        this.currentPosition = new Position(x, y - 1);
    }
}

Abstract base class Character contains the code portions which are common to all characters. The varying parts are encoded in the subclasses. Only, two aspects can vary from a character to another:
  • the movement strategy,
  • the appearance (its bitmap) and initial position on the screen.
In order to eliminate the subclasses and render class Character concrete, we can thus do two things:
  • implement the various movement strategies into autonomous classes,
  • convert the constructor's code into pure data and let a factory do the instantiation job.

First, we introduce an interface for movements:
interface IMovement {
    Position computeNextPosition(Position currentPosition);
}
At the moment, we have two movement strategies:
class RandomAppearance implements IMovement {
    private int maximumHeight;
    private int maximumWidth;

    public RandomAppearance(int maximumHeight, int maximumWidth) {
        this.maximumHeight = maximumHeight;
        this.maximumWidth = maximumWidth;
    }

    public Position computeNextPosition(Position currentPosition) {
        int x = Math.random() * this.maximumWidth;
        int y = Math.random() * this.maximumHeight;
        return new Position(x, y);
    }

class FallingDown implements IMovement {
    private int groundLevel;

    public FallingDown(int groundLevel) {
        this.groundLevel = groundLevel;
    }

    public void computeNextPosition(Position currentPosition) {
        int y = currentPosition.getY();
        if (y <= this.groundLevel) return;
        int x = currentPosition.getX();
        return new Position(x, y - 1);
    }
}

Class Character can be made concrete by changing its constructor signature. It now expects an IMovement as an additional parameter:
class Character {
    private Position currentPosition;
    private Bitmap bitmap;
    private IMovement movementStrategy;

    public Character(Position startingPosition, Bitmap bitmap, 
                     IMovement movementStrategy) {
        this.currentPosition = startingPosition;
        this.bitmap = bitmap;
        this.movementStrategy = movementStrategy;
    }

    public void draw(Canvas canvas) {
        canvas.drawImage(this.currentPosition, this.bitmap);
    }

    void move() {
        this.currentPosition = this.movementStrategy
            .computeNextPosition(this.currentPosition);
    }
}

At last, we replace the two classes by two creation methods available on factory CharacterHatchery:
class CharacterHatchery {
    private ResourceManager resourceManager;

    public CharacterHatchery(ResourceManager resourceManager) {
        this.resourceManager = resourceManager;
    }

    public Character hatchCauldron(Position startingPosition, 
                                    int groundLevel) {
        IMovement strategy = new FallingDown(groundLevel);
        Bitmap bitmap = this.resourceManager.getBitmapForCauldron();
        return new Character(startingPosition, bitmap, strategy);
    }

    public Character hatchWitch(int maximumHeight, 
                                 int maximumWidth) {
        IMovement strategy = 
            new RandomAppearance(maximumHeight, maximumWidth);
        Bitmap bitmap = this.resourceManager.getBitmapForWitch();
        Character witch = 
            new Character(new Position(0, 0), bitmap, strategy);
        witch.move();
        return witch;
    }
}

How much better is this design?
We gained some flexibility: it is easy to define a cauldron which could appear randomly on the screen.

Also, the abstract class was removed. Doing so made the dependence from the Character to its siblings explicit: class Character now holds a reference to interface IMovement. This dependence is reverse from what we would normally expect of an inheritance relationship (which usually goes from subclasses to base class). That is a common side-effect of using keyword abstract: it makes the coupling both ways.

This refactoring reduced the scope of the union as much as was possible: instead of being applied the class Character as a whole, it is restricted to method computeNextPosition only. In the end, we get a large common part with small strategies to plug into. This is exactly the philosophy of the variant data-types found in OCaml.

If you like, another example in the same vein can be read here.




Previous

Saturday, May 30, 2015

Economy of Means: On the Elimination of Inheritance (3/6)

From inheritance to decorator

This is one of the advanced questions I sometimes ask in interviews:
Suppose you have three classes A, B and C. Class A has a method f which performs some task. Classes B and C inherit A. Both classes override method f to add some extra behaviour to the base version. Class B outputs some log:
class B extends A {
    public override void f() {
        super.f(); 
        log("f was called");
    }
}
, while class C increments some counter:
class C extends A {
    private int counter;

    public C() {
        this.counter = 0;
    }

    override public override void f() {
        super.f();
        this.counter++;
    }
}
Now, you would like to instantiate a class which mixes all behaviours together: the base behaviour, the log and the counter increment. How would you do it? I am expecting a clean design, which can easily evolve in the future if needed.

Most candidates will struggle, yet the core idea is again to use a combination of interface and composition in replacement of inheritance. Through a gradual refactoring, we flatten the class hierarchy and introduce the decorator pattern.

First let us define interface I, which declares method f:
interface I {
    void f();
}
Then, we can have all classes implement interface I. Next, we can modify class B so that, instead of inheriting class A, it expects an object with interface I as argument of its constructor. In its implementation of method f, class B calls the base version of method f from this interface rather than from its super-class:
class B implements I {
    private I i;

    B(I i) {
        this.i = i;
    }

    void f() {
        this.i.f(); 
        log("f was called");
    }
}
We do the same with class C:
class C implements I {
    private I i;
    private int counter;

    public C(I i) {
        this.i = i;
        this.counter = 0;
    }

    public void f() {
        this.i.f();
        this.counter++;
    }
}
 
Classes B and C are now both decorators: if we view classes as API transformers, then we can see they both expect an interface I as input, and they both build instances which provide the same interface I, yet adding a layer of behaviour in the middle.

Peeling the onion

Thanks to the decorator pattern, getting any combination we could wish for is extremely easy:
  • new A() provides only f,
  • new B(new A()) provides f and logging,
  • new C(new A()) provides f and statistics,
  • new B(new C(new A())) or new C(new B(new A())) provide f, logging and statistics. 
This design is extensible: one can easily code an additional decorator. It will assemble seamlessly with the other decorators during instantiation.
At last, as was already shown in the previous recipe example, we could, if necessary, implement a factory that offers shortcuts to rapidly instantiate a variety of classes, all implementing interface I.


Avoiding override

As previously mentioned here, overridden methods are sometimes a form of dead code. Indeed, writing some code in the base class only to scratch it in the children, is not very elegant. Hopefully, keyword override can be replaced by the use of interfaces. Here is how.
Let us start again from our canonical hierarchy: class A father of classes B and C. Class A defines a method f, which is overridden in C (but not in B). All other things being equals, it is preferable to create an interface I which defines method f and have class A accept this interface as one of its constructor argument.
Two additional classes which both implement interface I are created out of the definitions of f present in A and C. By splitting our implementation into smaller components, we gained flexibility:
  • We can assemble a class B with the version of method f which was originally present in C, mixed in.
  • Interface I (possibly after some renaming) can now be reused outside of its original context.

Sunday, May 17, 2015

Economy of Means: On the Elimination of Inheritance (2/6)

The path away from inheritance

This section shows more complex designs that are based on inheritance. In each case, I explain how it is possible to avoid inheritance.

Default behaviour

Writing some generic engine that drives plugins is a powerful way to factor code and speed up development. Consider an hypothetical case where plugins would have to comply with the following interface:
interface IEngineEventsListener {
    Statistics processStartup(Car);
    void processAcceleration(Car, int);
    void processDecelaration(Car, int);
    void processStop(Car);
    void processCrash(Car, Crash);
    // etc...
    void processEvent20(Driver driver);
}
As you can see, the interface is quite rich. And it can be pretty tedious to provide a full plugin implementation. Now suppose all actions are optional. So it has been decided to add a class which implements standard default behaviours for every method:
class DefaultEngineEventsListener
                    implements IEngineEventsListener {
    public Statistics processStartup(CarData) {
        /* return some default value */
    }
    public void processAcceleration(CarData, int) {
        /* do nothing */
    }
    // etc...
}
Plugin developers can now inherit from this class and override only the methods for which a specific behaviour is required.
To me, this pattern is acceptable only as long as the default behaviour is empty and there are no method with a return value. Otherwise, overridden methods and default values are a form of dead code. This goes against one of the minimalistic rules:
Never ship code which will not be executed in the production environment.
In practice, actual designs generally tend to belong to one of these two categories:
  • most plugins implement only one method, in which case methods can be registered independently,
  • most plugins implement most methods, in which case cost of implementing the whole interface every time is acceptable.
Additionally, the variety of methods can be reduced by having their signatures converge. Taking this idea to the extreme, one could substitute all methods by only one by merging all data under a common interface (the union type as described previously in section A matter of choice). But then, of course, the burden of type dispatch would shift onto the plugin implementer.
As a last note, less strongly typed programming languages such as python or javascript simply allow partial implementations. Also, the syntax to register individual methods (or closures) tends to be lighter.
 

 

Antagonism between class hierarchy and methods call chain

Let us do some cooking. A WitchSoup is a Recipe. Base class Recipe is abstract since, during initialization, it calls abstract method getAdditionalTasks:
abstract class Recipe {

    private List<Task> _tasks;

    public Recipe() {
        this._tasks = new ArrayList<Task>();
        this._tasks.add(new PrepareUstensils());
        this._tasks.addAll(getAdditionalTasks());
        this._tasks.add(new CleanKitchen());
    }

    abstract List<Task> getAdditionalTasks();

    public execute() {
        for (Task task in this._tasks) {
            task.executes();
        }
    }
}

class WitchSoup extends Recipe {

    public WitchSoup() {
        super();
    }

    List<Task> getAdditionalTasks() {
        List<Task> additionalTasks = new ArrayList<Task>();
        additionalTasks.add(new MeltButter());
        additionalTasks.add(new MashBeans());        
        additionalTasks.add(new Boil());
        return additionalTasks;
    }
}
For some of you, this code may seem awkward. Indeed, it is wrong in more than one way. First, every new recipe will result in the creation of one more class. This leads to extreme verbosity. Second, class Recipe is abstract so it can not be instantiated: it has zero value on its own.
Last and worse, a loop has now been introduced into the classes dependencies. Simple inheritance creates a dependence from a class to its parent. An abstract class also depends on its descendants. Hence, method getAdditionalTasks can be viewed as a callback in the interface which separates WitchSoup from Recipe. As you may have experienced when writing unit tests with mocks, interfaces with callbacks are always harder to reason with. Classes WitchSoup and Recipe are actually very tightly coupled and cannot any longer be thought of as separate entities.

Unfortunately, I sometimes find this pattern in real (admittedly poor) production code (often buried down under a few more obfuscation layers).
Here is how this mess could be cleaned up:
class Recipe {

    private List<Task> _tasks;

    public Recipe(List<Task> additionalTasks) {
        this._tasks = new ArrayList<Task>();
        this._tasks.add(new PrepareUstensils());
        this._tasks.addAll(additionalTasks);
        this._tasks.add(new CleanKitchen());
    }

    public execute() {
        for (Task task in this._tasks) {
            task.executes();
        }
    }
}

class RecipeBook {

    Recipe retrieveWitchSoupRecipe() {
        List<Task> additionalTasks = new ArrayList<Task>();
        additionalTasks.add(new MeltButter());
        additionalTasks.add(new MashBeans()); 
        additionalTasks.add(new Boil());
        return new Recipe(additionalTasks);
    }
}
Abstract method getAdditionalTasks was simply replaced by a standard parameter of the Recipe's constructor. As class Recipe is now concrete, the need for WitchSoup or any other specific Recipe descendant disappears. Each recipe is replaced by a different creation method belonging to the factory class RecipeBook. The class hierarchy has flattened dramatically.

Flavor network: graph of ingredients as paired in recipe


From template method to strategy

Let us deepen our understanding of keyword abstract by playing with the template method pattern. In the following code, method accumulate combines all the integers present in its list parameter. It calls the abstract method combine to process integers pairwise. Any combinator can be chosen by implementing various subclasses. For instance, class MaximumAccumulator combines the integers by choosing the maximum, while SumAccumulator performs the addition.
abstract class Accumulator {
    public int accumulate(List<Integer> input) {
        int result = 0;
        for (Integer element in input) {
            combine(result, input);
        }
        return result;
    }

    public abstract int combine(int element1, int element2);
}

class MaximumAccumulator extends Accumulator {
    public int combine(int element1, int element2) {
        if (element1 < element2) return element2;
        return element1;
    }
}

class SumAccumulator extends Accumulator {
    public int combine(int element1, int element2) {
        return element1 + element2;
    }
}
Using pattern strategy we can replace inheritance by both an interface and composition. First we introduce interface Combinator:
interface Combinator {
    int combine(int element1, int element2);
}
Then, the Accumulator class can accept a Combinator as a constructor argument instead of expecting subclasses. The class loses its abstract status:
class Accumulator {

    private Combinator combinator;

    public Accumulator(Combinator combinator) {
        this.combinator = combinator;
    }

    public int accumulate(List<Integer> input) {
        int result = 0;
        for (Integer element in input) {
            this.combinator.combine(result, input);
        }
        return result;
    }
}
At last, classes MaximumAccumator and SumAccumulator can now implement interface Combinator. We also rename them to express their roles more precisely:
class MaximumCombinator implements Combinator {
    public int combine(int element1, int element2) {
        if (element1 < element2) return element2;
        return element1;
    }
}

class SumCombinator implements Combinator {
    public int combine(int element1, int element2) {
        return element1 + element2;
    }
}
As an option, we can also provide the following factory, so that code consumers have an easy way to instantiate different kinds of accumulators:
class AccumulatorFactory() {
    Accumulator createMaximumAccumulator() {
        return new Accumulator(new MaximumCombinator());
    }

    Accumulator createSumAccumulator() {
        return new Accumulator(new SumAccumulator());
    }
}
Note how, by removing class inheritance, the code has improved in several ways:
  • Class Accumulator and implementations of Combinator are not coupled anymore. Now the combinators can be reused outside of this particular context.
  • The responsibilities are more focused. So it is easier to have class names which faithfully express their implementation's intent.
  • Unit testing will be simpler. First, since Accumulator is not abstract anymore, it can now be tested in isolation. Tests of SumAccumulator and MaximumAccumulator would have been unnecessarily complex to write and redundant since they need to exercise the common inherited code twice. Now we can easily test the combinator's code.

By allowing the father's code to call some method defined in its children, the abstract keyword couples classes even more tightly than simple inheritance does. As a first conclusion of this example and the previous one, we can say the abstract keyword represents a strong code smell. As a coding rule, it seems safer to avoid it altogether.
Naval strategy (Yi Sun-sin turtle ship)


A side note on unit testing

The previous example briefly mentioned the topic of writing unit tests. So I am taking this opportunity to quickly discuss the impact of inheritance on tests.

I am a mockist. Writing unit tests the mockist style consists in replacing all dependencies by mock objects. Each mock object behaviour is described on a test by test basis by succinct propositions. The goal is to write tests as unitarily as possible, so that:
  • only few tests fail whenever a code change which breaks past behaviour occurs,
  • after each code change, it is easy to know which test suite should be run to detect potential regressions,
  • tests run faster,
  • and most importantly, the cost of writing and maintaining tests does not escalate with the program's size (or the classes' dependence depth).
So, from the mockist standpoint, inheritance is a problem. Inheritance allows to split code among separate units, but prevents from testing these units in isolation. Tests of the descendants in a class hierarchy are necessarily redundant since they exercise the code of the ancestor's classes multiple times.

Circus by Marc Chagall

Sunday, May 10, 2015

Economy of Means: On the Elimination of Inheritance (1/6)

Introduction

Today I bring an end to a question I have been pondering for more than a decade. It started as soon as my first real-life software projects, at the time in C#:
Should this piece really be coded with inheritance? Wouldn't composition work just fine? On which grounds can the choice be made?

High level languages, such as C#, are supposed to make your life easier. They provide succinct syntax for powerful yet simple abstract concepts which are automatically translated, by the compiler or interpreter, into long lists of low level machine instructions. At least, that is the theory. In practice, high-level languages are shipped with a variety of shiny new constructs, which reflect the tastes of their inventor, or the fashion of the time. Junky programmers will just happily jump on the band-wagon, using any gadget to quickly produce what I see as no more than unmaintainable disposable paper software.
On the contrary, thorough programmers, which need to produce larger software (many functionalities, several team members, and at least a few years of maintenance), must painfully learn the correct way to use their tools. The school of thought I adhere to is minimalism. Hence, I personally believe that only a few well-chosen orthogonal constructs in any programming language are always sufficient. Having experienced various flavours (imperative, pure, strongly typed, static, dynamic, modular, object oriented, functional, event-based, declarative, synchronous, relational...), I am not afraid to reduce (mutilate according to language zealots) any programming language syntax in order to unveil its core paradigm. For every construct, I like to decide whether it is possible to do without or at least delineate the precise conditions that make it applicable. The benefits of restricting syntax to its bare minimum are greater code homogeneity, increased readability, and shorter learning curve for team newcomers or language beginners. Isn't reduced risk of astonishment a worthwhile goal in itself?
Here is a list of language options which generate dilemma (at least for me):
  • possibility to omit braces for one-line blocks,
  • initialization next to the field declaration (rather than in the constructor),
  • for loop (rather than while),
  • goto statement (rather than structured programming),
  • global variables (see A case against static),
  • static methods,
  • Long (rather than long),
  • struct (rather than classes in C#),
  • casts (rather than generics/templates),
  • HashMap (rather than Hashtable in Java),
  • objects (rather than modules in OCaml),
  • decorators as annotations (in Python),
  • new (rather than factory constructor in Javascript),
  • ...
Inheritance contributes to the existing plethora of paradoxes of choice.

If class B inherits class A, then it receives all methods and properties of A. Class A is called the base class (or father); class B is the child. From a software design perspective, a class hierarchy with only two elements does not make much value. So let us add another offspring of A named class C. Following UML conventions, this simple canonical hierarchy is represented by the following schema:

In various situations, this triptych, is often, unfortunately, chosen as the design by default. In the following, I will describe alternative and often preferable designs that avoid inheritance. Through these examples we will gradually grasp the true nature of inheritance.

Side note: Although, all code is written with the Java syntax, the same concepts are present in most mainstream object oriented programming languages.

A bit of reductionism

Deaf to YAGNI

In any code base, you sometimes (more than you would ever have wished for) encounter a degenerate class hierarchy. That is a hierarchy with only two members: the father and its son. In the best case, it is an intermediate state after a previous unfinished refactoring session. Just after a dead classes has been removed. But most often, it is a consequence of programmers not living in the present: in anticipation of a future evolution of the software, they just made it unnecessarily complex.
The most recent encounter with this pattern that I remember is this:
  • a class UserManager with most methods abstract,
  • and a single implementation RemoteUserManager.
The cure is easy: merge the two classes and get rid of all unnecessary syntax. In the process, we picked a more telling name for the resulting class by calling it RemoteAuthenticationService.

The future is not easily predicted, even more in software development. Today's preparation for a potential evolution often turns out to be a hindrance in meeting tomorrow's concrete requirements. To make a physical analogy, it is like walking further in a direction because you think that is where you will be asked to go next, but then having to walk back an opposite path when the destination changes.

Euclid said it best:
"In any triangle two sides taken together in any manner are greater than the remaining one."


Simply put, stay focused on implementing just enough code to meet the current required behaviour. It is a safer strategy, by a large margin. At least that is what Yagni says.

DRYing the wrong way

Frequently, small helper functions are found in the parent of a class hierarchy. For instance, a function that converts hours into milliseconds, could belong to a hierarchy of Tasks. Or a function which formats speeds either as kilometers or miles per hour, could be part of a hierarchy of Vehicules.
Coders did that probably because they were in a hurry. It is so easy to move up common code in a parent class. At least, didn't they resort to copy-pasting.

First, as a general rule of thumb, methods which do not access the object state (through keyword "this"), most probably do not belong to the correct class. Helper methods couple the whole hierarchy with unrelated code. Hence, helper methods are clearly not a recommended usage of inheritance and can advantageously be replaced by composition. Composition will let you write less monolithic code by distributing the responsibilities into distinct smaller and reusable class.
However, pulling up helper methods may be a useful intermediate step when refactoring unmaintainable code.

A matter of choice

Sometimes, we want to store different kinds of data in a single collection. For instance, we could have various types of shapes (Triangle, Square, Circle...). Then, we can define a common interface Shape and have all objects implement it. Interface inheritance is the OO way of providing union types.

At other times, various objects must be processed to compute results of similar nature. Building on the previous example, we could need to compute the shapes' respective surfaces. Then, we simply define method computeSurface on the Shape interface and have each shape implement it its own way.
Often, the treatment can not be directly coded inside the objects, but lies somewhere else. Consider, for instance, a compiler which outputs a syntax tree, or a database which accepts commands. In order to be able to code the treatment, some kind of dispatch mechanism is needed. The naive implementation consists in branching according to the object type. Since its recommendation by the GOF, the visitor pattern has become a popular design. However, I find a map from object types to the appropriate treatment proves to be a much more flexible and less intrusive implementation. But that's material for another post.

Interface inheritance also allows the construction of complex recursive data-structures. To give a simple example, consider arithmetic expressions which are comprised of:
  • literals, such as constants integers,
  • compound expressions such as the binary addition of two other expressions.
With these heterogeneous pieces of data unified under a common type, we could easily perform a variety of operations: evaluation into an integer, conversion into a string representation, height count, size (total number of nodes) count, translation to yet some other formalism, symbolic manipulations (such as factorisation)...
And of course, we could also store several expressions into a unique worklist.

The two opposite sides of inheritance


As a summary for this first set of simple examples, I would like to point out that inheritances mainly serves two orthogonal purposes:
  • reuse (or factor) common code or data,
  • union distinct objects under the same type.
More complex inheritance usages are always a subtle combination of these two fundamental aspects in various proportions.
As such, inheritance is a language feature which is not atomic. It can be expressed as a combination of:
  • code composition for the factoring aspect,
  • interface inheritance (or simply duck-typing in more dynamic OO objects) for the union aspect,
  • and some glue code, mainly to forward calls.
As we will see in the following, more complex examples, it proves almost always preferable to break down inheritance into its constituents. The design becomes more focused and readier for change.



Note: In order to make it more easily digestible, this topic will be split into 6 different posts.

 Next