|< Free Open Study >|
5.10 A Problem with the Use of Inheritance as a Reusability Mechanism
One role of polymorphism is in the creation of reusable, standard components that can be derived into custom components. Beware of the marketing hype that claims that object-oriented designers can take standard components from a reusable library, inherit from them, and produce custom components that optimally reuse the code of the standard component. The following case study is taken from a C++ class library project in which I participated several years ago. In the process of designing a linked list class, I considered the fact that the library was also going to have a sorted linked list class. Early in the design process, I realized that sorted linked lists are special types of linked lists (which are unsorted). I wondered how to get optimal reuse of code from this inheritance relationship, and came up with the design in Figure 5.21.
I then realized that it was not the insert and delete methods that were different梚t was where I performed the insertion and deletion that differed. I abstracted out this difference into a polymorphic function called find and made the function protected. The reason for the protected status is that the find method is not an operation for users of the classes, and so it should not be in the public interface, but the derived class (SortedLinkedList) needs to override it. Thus, it cannot be private. The resultant hierarchy, shown in Figure 5.22, produced optimal reusability of the base class code (or at least as optimal as I could imagine). In the actual library, the LinkedList class consisted of 40 pages of code and documentation, whereas the SortedLinkedList class had only 2 pages, most of it documentation.
It is very common to see protected, polymorphic functions being called from monomorphic functions in the base class (in languages that allow implementors a choice between polymorphic and monomorphic functions). Some developers like to call them the "reusability hooks" of a class. Examples of this type of binding can be viewed through examples of a linked list and a sorted linked list inserting a number. The examples assume a compiled language that supports implementor choices between monomorphic and polymorphic functions.
It appeared that the marketing hype was true. I took a standard component (LinkedList) and created a custom component (SortedLinkedList) with optimal code reusability (see Figure 5.23). Given this fact, it would be possible to sell the library as a collection of class definitions (header files) and object code consisting of the compiled class methods. Customizers of my standard components would not need to know the implementation of my base classes in order to customize them. My balloon suddenly burst when I decided to add a linked ring class to my class library. I realized quickly that linked rings are really just special types of linked lists except the tail pointer of the list points back at the head. I was disappointed to find out that I got zero code reusability. When I implemented the methods of linked list, I iterated over the list by using a conditional test that checked to see if the current pointer into the list was nil (or NULL, i.e., zero, for C++ programmers). If it was nil, then I knew I was at the end of the list. By definition, the linked ring abstraction will never see a nil. Even an operation as simple as traverse(), which prints the elements of a list, was unusable. Given a linked list with the values 10, 20, and 30, traverse would print "(10 20 30)." A linked ring of the same value would print "(10 20 30 10 20 30 . . . )" ad infinitum.
Proponents of the marketing hype argue that the problem is mine, not that of inheritance. Their heuristic is that every separate idea within a method of a base class should be encapsulated in a protected, polymorphic function. It is true that if you follow this heuristic you will always get optimal code reusability. You will also go insane if you try to debug or maintain a base class designed in such a manner. The biggest problem is deciding what constitutes a separate idea. Is dynamically allocating a node of a list, perhaps as part of a copy method, a separate idea? It is not, given the classes we have discussed so far. The picture changes when one starts thinking about doubly linked lists, which contain double_nodes instead of nodes. In short, a derived class is what defines separate ideas in the base class methods. Therefore, unless you know about the derived classes, you cannot provide the necessary hooks in the base class methods. This is the bad news. The good news is that optimal reusability can be achieved with some changes to the implementation details of the base class. The important point is that a customizer needs access to the implementation of a base class. The fact that most, if not all, class libraries are sold in source-code format attests to this fact.
In this example we need to abstract out the testing for the end of lists in the base class methods into a protected polymorphic method called at_end(). The at_end method will simply check against NULL for the LinkedList objects and the SortedLinkedList objects (via inheritance; see Figure 5.24). However, the LinkedRing class will override this method with its own at_end method, which will test the current pointer against the head pointer.
The only party affected by the new polymorphic at_end function is the implementors of the LinkedList class. The users are unaffected, and they are the group we worry about most. Many designers point out that as a class gets older, it picks up more and more of these polymorphic hook functions, which makes it easier to get optimal reuse for free. This is entirely true and is called the maturing of the base class. Consider a sorted linked ring class. All of the necessary code is already defined in the existing classes. We simply take the at_end method of LinkedRing and the find method of SortedLinkedList. It is important to note that a new derived class may require more than one polymorphic hook function to get optimal reusability. In our class library, the doubly linked list class required five additional polymorphic hook functions in order to incorporate its abstraction optimally with that of the linked list class. Once we found the necessary abstractions, we had all of the necessary hooks for SortedDoublyLinkedList, DoublyLinkedRing, and SortedDoublyLinkedRing. In any event, these hooks are always implementation details of the base class.
|< Free Open Study >|