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