Harnessing multiple inheritance
The original version of this article appeared as: Harnessing Multiple Inheritance in JOOP (Journal of Object-Oriented Programming), vol. 1, no. 4, November 1988, pages 48-51. ©101 Communications, included with permission.
In some parts of the object-oriented community, the mere mention of multiple inheritance seems to evoke visions of mysterious, uncharted territories where complexity is the law of the land and treacherous ambiguities lie in cover behind every bush, ready to prey on the poor wandering programmer. The purpose of this month's column is to dispel any such image and show that multiple inheritance is in fact as simple to use as it is powerful.
I tried a few times to understand why anyone would be against multiple inheritance, in the spirit of a recent article in the Los Angeles Times that tried to understand why the majority of inhabitants in a certain Northern California community were against bringing in public electricity. (In that case the answer turned out to be simple: most of them had invested in their own generators.) In the discussions I have had, implementation issues usually come up fairly quickly; after that people will start using strange words like "method combination", and the discussion stops because I don't understand any more.
In Eiffel, life without multiple inheritance would be rather boring. The last column mentioned a particular application -- doing away with global variables -- but the technique is much more general. Actually I can't think of any significant Eiffel system I have seen that did not use it extensively.
To put multiple inheritance in perspective, it is first necessary to recall what inheritance, single as well as multiple, is all about. Inheritance is actually two things: subtyping and module extension.
A class is both a module and a type. As a module, it encapsulates a number of facilities -- features, as they are called in Eiffel -- offered to other classes (clients As a type, it describes a number of possible run-time objects -- its instances.
The connection between the two views is simple: the features offered by the module are precisely the operations available on the instances of the type. For example if we have a class CIRCUIT in our system, it is viewed by other modules as encapsulating a number of features, say impedance, change_impedance, fan_out, switch_on, switch_off and the like. But it is also the description of a number of objects, representing circuits, and the features of the class describe operations (queries or changes) on these objects.
What's so great about inheritance is that it is meaningful from both perspectives. If a class inherits from another, it extends the set of module features; for example a class NMOS_CIRCUIT may add to the features of CIRCUIT new, specific ones such as number_of_layers (query) and add_layer (change). This is the module view. From the type view, this is an example of subtyping: every instance of NMOS_CIRCUIT may also be viewed as an instance of CIRCUIT
So inheritance is the merging of two relations: the "extends" relation (module) and the "is a", or "restricts" relation (type). Extension and restriction may seem at first to be opposite concepts, but in this case the apparent contradiction is easily resolved: an heir extends features and restricts instances. If you ignore either of the two perspectives, you don't get the real power of inheritance.
The "double perspective" approach yields insight into most of the issues commonly raised about inheritance. One such issue is the question of whether designers should be permitted to restrict the descendants' visibility on the features of a class. I happen to hold strong opinions on this matter and will discuss it in a further installment of this column. But for now it suffices to observes that multiple inheritance makes sense from both perspectives.
From the module side one will often want to combine the features provided by more than one class. This is clear even in very simple examples where classes are used to encapsulate a number of related facilities. Assume for example we have a class MATH which contains a number of mathematical routines and a class BASE implementing primitives for database access. Why should the developer of a financial package (say) be barred from writing a class that uses both sets of facilities and thus inherits from MATH as well as BASE?
(Note that the use of classes as a mere packaging mechanism, as with MATH which encapsulates the routines of a mathematical library, is perfectly acceptable although it is clearly tilted towards the "module" side of the module-type tandem. Even here, however, the other perspective makes sense if we view MATH as describing the type whose instances are "objects that have access to the facilities implemented by the mathematical library". Usually the objects of interest are not instances of MATH itself, but those of descendant classes, which have other features beside those inherited from MATH.)
So much for the module view of multiple inheritance. From the type side, the arguments are just as strong. From this perspective, of course, inheritance is nothing else than classification, which lies at the basis of the scientific method since Linnaeus.
In the natural sciences, classification based on tree hierarchies (that is to say, single inheritance) has been fairly successful. Even there, however, the restriction is not always practical. Treatises of botany may use a purely hierarchical classification, but flower-identification books intended for mere mortals use techniques based on multiple decision paths -- not just the theoretical classification but also color, geographical area, season etc.
In the sciences of the artificial, and particularly when we need to describe software objects, tree-structured classifications are simply insufficient. Most objects need to be categorized in more than one way.
A novel that I buy from the bookstore has a certain number of chapters, a certain cast of characters and other properties that might be described as features of class STORY; but it is also a book with a publisher, a price, a weight, an ISBN number and other features of class BOOK. Class NOVEL should inherit from both.
The nmos circuits mentioned above have properties inherited from class CIRCUIT. But if they are used in the design of a certain computer they are also computer parts, with features such as inventory_number, current_stock, order and the like that will naturally be inherited from a class INVENTORY_ITEM.
More concrete examples and their realization in Eiffel will be given later. But it does not take much thought to realize that many objects need to be viewed from more than one perspective. Whenever this is the case, the restriction to at most one line of ancestry is unnatural and will almost certainly lead to undue complexity, destroying the elegant software architectures promoted by object-oriented design. In contrast, multiple inheritance makes it possible to keep each class consistent and simple, and build new ones by extension and combination.
A typical example that arose in the design of the Eiffel Graphical Library involves menus and submenus. (In this example and the ones that follow, some simplifications have been made to keep the discussion simple, but all classes sketched are faithful to the originals except for non-essential details.)
In the graphical library, multiple-entry menus are described by a class MENU, with such features as number_of_entries, display, move_to_next_entry etc. Menu entries are described by a class ENTRY with such features as parent_menu, associated command, execute (a procedure that executes the associated_command) and others.
A nice facility to have in a menu-driven system is what is known as walking menus: when you select certain entries corresponding to non-simple commands, you get a new menu of sub-options, usually displayed next to the primary menu (see figure 1).
With multiple inheritance, this notion is easily modeled: define a class SUBMENU which inherits from both MENU and ENTRY. This is an ideal example of proper use of multiple inheritance: a submenu is certainly a menu, but it is also a menu entry. The combination is a fruitful one; for example, procedure execute (inherited from ENTRY) is redefined for submenus as a procedure that calls display (inherited from MENU), since executing a submenu entry consists of displaying the associated submenu and executing the user's selection in that submenu.
There are other ways to program this example; for example you could define menus as trees of entries. But this is true of any advanced programming technique: you can always do without it. In the end, everything can be programmed on a Turing Machine, or in BASIC. What counts is the quality of the resulting software. Here I don't know of a solution that matches the elegance of the one sketched above.
The practical advantages of the solution retained over the "menus as trees" technique are numerous, as you will see if you try to work out the details of both.
One of the differences is particularly important if you take a software engineering viewpoint and consider these solutions in relation with the software development lifecycle. If the developers first implement simple menus only, and only then realize the need for walking menus, using tree solution means that they must go back to the initial definition of class MENU and rework it extensively. This brings disorder into the development process.
With the multiple inheritance solution, things are quite different. When the developers realize that a new kind of menu is needed, they simply define it by inheritance from MENU and ENTRY. The changes to existing software are minimal. This is an example of one of the key benefits of the object-oriented method, which would have to be renounced in the absence of multiple inheritance.
With respect to the Eiffel environment the discussion is moot anyway since the predefined classes describing various tree implementations in the Basic Eiffel Library rely heavily themselves on multiple inheritance.
Multiple inheritance is appropriate in the above example because SUBMENU is related to both of its parents MENU and ENTRY by a relation which in each case is a true instance of both the "extends" and "is a" relations. The latter relation is particularly relevant: a submenu "is an" entry, in the sense that all entry operations apply to it; but in the same sense it also "is a" menu.
When these conditions are not satisfied, multiple inheritance can of course be misused. In an interesting paper presented at ECOOP 87 (Using Types and Inheritance in Object-Oriented Languages, pp. 23-34), D.C. Halbert and P.D. O'Brien from Digital cite an example of bad design: a class AIRPLANE that inherits from FUSELAGE and ENGINE. As they point out, this is wrong, as it is certainly not true that a plane "is a" fuselage or an engine. On the other hand, all of these classes could legitimately inherit from a class such as AIRPLANE_INVENTORY_ITEM. Clearly class AIRPLANE should be not a descendant but a client of the classes mentioned, that is to say have attributes of the corresponding types.
A similar example was heard at a conference, where an example of multiple inheritance offered by a panelist -- in jest, one may hope -- was the class APPLE_PIE that inherits from APPLE and PIE. Clearly an apple pie "is a" pie but is not an apple. (Of course, if we think of the duck-shaped duck patés found in some charcuterie shops, we may imagine an artistically-inclined baker who similarly devises an apple pie sculpted in the form of an apple. In such a case we might have to revise our judgment.)
In my experience, Eiffel programmers seldom make such mistakes once they have mastered the basic concepts. More frequent are cases when a designer overlooks a valid case for multiple inheritance, which inevitably leads to clumsy and overly complex designs.
But what about name clashes?
Whenever you talk about multiple inheritance, someone is bound to ask sooner or later (usually sooner) what happens in the case of name clashes -- identically named features in two or more parent classes.
No doubt the question is legitimate, but the gravity with which it is asked -- as if it were a deep conceptual issue -- has been an unending source of bewilderment to me. I believe it is one of these cases in which if you only take a minute or two to pose the problem cleanly then the solution follows immediately. (If you don't, you can spend the rest of your life and ten PhD theses on the subject.)
Assume you are in the inheritance-based reusability business and combine classes from two software suppliers, say one in New York and one in London. Sure enough, one day you are going to run into the problem of combining two classes that both have a feature called foo, to use as example one of these nice evocative names that programmers are fond of.
But this is not a conceptual problem! It merely results from an unfortunate choice of names. If the parent programmers had chosen other names, differing by just one letter -- influenced perhaps by local conditions, they might have used zoo in New York and fog in London --, the problem would never have arisen.
This suggests the two key observations on this problem:
The Eiffel technique follows from these comments. We certainly don't want to leave any ambiguity; a class (which should be a clean implementation of an abstract data type) should present to its clients a clean and consistent interface. So if it inherits from two classes with an identically named feature and doesn't do anything about it, it is incorrect and will be rejected by the compiler with a message pointing to the ambiguity and saying in effect: "Won't you make up your mind? Do you want foo from New York or foo from London?" (The actual compiler message, needless to say, uses a more restrained tone.)
To overcome the situation, the designer of the common heir may use the straightforward Eiffel technique of renaming, as illustrated by the following example:
class SANTA_BARBARA inherit LONDON rename foo as fog NEW_YORK rename foo as zoo feature ... end -- class SANTA_BARBARA
Of course it suffices to rename one of the clashing features to remove the ambiguity.
Wendy's story: Windows are rectangles and trees
Renaming is a syntactical technique, which affects the name under which clients of a class refers to its features. This is in contrast with redefinition, which affects the semantics of the routines. The two techniques can be combined, leading to interesting results that fall beyond this discussion.
Although purely syntactical, renaming is not limited in its applications to the resolution of name clashes. Among its other uses, one deserves a particular mention because it sheds more light into the meaning and power of inheritance. This is renaming used to define consistent class interfaces.
The following example is typical. Again, it will illustrate techniques used in the Eiffel Graphical Library. Assume we want to describe rectangular windows that can be arbitrarily nested. The corresponding class, say WINDOW, will have a large number of features, which can be grouped into two categories:
Now let's bring the human side of this story. Let's call Wendy the programmer to whom the supervisor assigns the task of writing class WINDOW; he adds that this looks like a tough job -- there are many features to be written -- and he hopes it will be completed in three months.
But Wendy knows better. She is a good programmer, which often means a lazy programmer, or to use less pejorative terms, one who knows how to wisely allocate time and effort. She realizes that class WINDOW will be large and unmanageable if it includes all features at once. Then she notices that the libraries contain classes RECT_SHAPE and TREE which respectively provide the two categories of features defined above. So she writes the class (figure 2) as
class WINDOW inherit RECT_SHAPE TREE feature ... end -- class WINDOW
All she has to do is fill in the feature clause which describes how to combine features from both parents, and add anything specific to windows. This might take the rest of the day.
The next day she shows up for work and turns in the result. (Or perhaps if she is that clever, and previous experience has convinced her that it won't do her any good to outsmart a supervisor, she takes off to the Galapagos for the rest of the three months.)
Ed's complaint: Interfaces should be consistent
Did Wendy do right? Almost. Enter Ed. As his name indicates, he is writing the text editor for the next century, VI-2001, which uses multiple windows and is really what drives this whole project. His EDITOR class will be a client of WINDOW -- that is to say, it will declare attributes of type WINDOW, create windows and manipulate them by applying features from the official interface (export clause). So the complete picture is that of figure 3.
Now Ed is not in the least interested in how clever Wendy is and how she reuses existing code. What he wants is good implementation of windows.
Unless something is done about the interface, Ed is not going to be happy. Features inherited from TREE, in particular, will bear their tree names: insert_node, remove_node, parent_node and so on. This is not acceptable to a client programmer like Ed who wants good, concrete window terminology.
With renaming, the solution is straightforward. Wendy ought to spend ten more minutes polishing the interface, so that clients of class WINDOW won't need to be aware of its tree ancestry:
class WINDOW inherit RECT_SHAPE rename ... TREE rename insert_node as add_subwindow, remove_node as delete_subwindow, parent_node as superwindow, ... feature ... end -- class WINDOW
Flattening a class
To wrap up this example, it is useful to consider a programming environment issue. It has been said that, paradoxically, inheritance could be an obstacle to reusability, since you cannot pull out a class from its context and distribute it as a stand-alone software component if the class was built using inheritance: you must also pull out all of its ancestors. If this were true, the problem would be particularly acute with multiple inheritance.
In practice, of course, reusable components are usually distributed as libraries rather than individually; we may expect a library to embody the complete inheritance structure for its members. But the thought that we cannot extract a given component independently of any other is still worrying.
Fortunately, the problem is solved in Eiffel -- not by the language but by the supporting environment. The Eiffel tool known as the class flattener takes a class as input and yields as output an equivalent class that does not contain any inheritance clause. Thus if you run
(or, more commonly, click the flat icon in the visual environment) you will get as result a class that has exactly the same features as the above WINDOW class, but with all features inherited from RECT_SHAPE or TREE (or their own ancestors) brought in. Renaming and redefinition are of course taken into account.
The flattener is commonly used for two purposes: for documentation (to produce self-contained class descriptions, in connection with another tool, the short class abstracter), and to deliver stand-alone reusable components.
Taking reusability seriously
As emphasized above, renaming is a purely syntactical technique, and the improvement it brings to class WINDOW may be labeled a cosmetic one. But this kind of cosmetics is essential if we are serious about building software by combination and extension of reusable components.
Inheritance, multiple or not, is primarily a technique for the designers of a class, not for the designers of its clients. The responsibility of a designer is to provide clients with consistent, complete interfaces. To use a class, you should not have to know about its ancestry.
This is a fundamental requirement if multiple inheritance is taken not just as a cute programming trick, but as one of the key reusability techniques that will change the nature of tomorrow's software development.