In-Depth

Integrating Extension and Specialization Inheritance

• By Walid Al-Ahmad, Eric Steegmans
• December 1, 2001

Inheritance is an important feature of object-oriented programming languages (OOPLs) because it supports the construction of reusable and flexible software. The goals of inheritance have not yet been reached; there is still no consensus on the requirements and supporting mechanisms of inheritance. Many authors have provided guidelines for the proper uses of inheritance and warnings against the improper uses of inheritance.^{1,2,3,4,5,6,7} However, many of these guidelines need to be enforced by the language to fully benefit from this vital mechanism. Our work is a step in that direction.

Software developers use inheritance for two reasons, namely to express conceptual relationships between classes or to share code between classes. We use the terms conceptual modeling, extension inheritance, and subtyping interchangeably. The same applies to the terms code reuse, specialization inheritance, and subclassing. Each of these uses seems to have its usefulness and legitimacy. Current OOPLs, however, differ in their view of these two issues, which has led to two schools of thought regarding the objectives of inheritance in the first place. The first perspective, represented by languages like Beta (a successor of Simula)⁸ puts much emphasis on modeling of specialized concepts. The second perspective, represented by languages like Smalltalk,⁹ puts emphasis on code reuse. The inheritance mechanism of Beta is a good attempt to enforce the language view of inheritance. Likewise, the Smalltalk's inheritance mechanism is an interesting attempt to impose its specific view of inheritance.

We believe inheritance hierarchies that reflect conceptual modeling among classes will benefit more from the inheritance mechanism; they are usually easy to understand, maintain, use, and extend. Real-world concepts may not necessarily be described in taxonomies like in botany and zoology. The conceptual structuring relevant to modeling can conflict with code reuse. For instance, circles are special cases of ellipses, not the other way around. Also, we can reason that ostriches are special kinds of birds that cannot fly. We must also admit that many classes in real-world systems exist (e.g., stacks and lists) that reflect no conceptual relationships.

Smalltalk and Beta are two extreme cases. The Smalltalk's inheritance mechanism is too flexible that haphazard inheritance cannot be avoided by the language rules. For example, a display method in class PERSON may be redefined in class EMPLOYEE to display the time of the day. There is no semantic conformance between the subclass and its superclass, a requirement of the modeling perspective of inheritance. On the other hand, the Beta approach is more disciplined, because the use of the inner construct ensures a degree of semantic compatibility between the subclass and the superclass. This approach enhances modeling but at the expense of flexibility and reusability, two key issues of the OO paradigm. Code reuse in Beta is considered a result of good class structures. The inheritance mechanisms of Smalltalk and Beta demonstrate the fact that using inheritance only for code reuse limits the expressiveness of inheritance for modeling, and using inheritance only for modeling limits the flexibility of inheritance for code reuse. To get maximum reusability one should sacrifice modeling and vice versa. The problem of these two approaches is that each loses the benefits of the other. We believe that both are needed and should coexist in an OO language. Our main objective is to demonstrate that these two viewpoints of inheritance can be integrated in an OOPL. We'll introduce new language constructs and mechanisms to help achieve this goal.

We'll begin with a brief introduction of the background of the problem. Then we will introduce the necessary building blocks for the integration of the two perspectives of inheritance; the component, read and write methods, and the suppress mechanism. We'll probe into a detailed explanation of how the integration process will be realized and offer a comparison with other work. Finally, we'll conclude with a glimpse of future work.

Background
In literature, one encounters the terms subclassing and implementation inheritance, among others, to refer to the use of inheritance as a means for code reuse. The terms subtyping, interface inheritance, and behavioral inheritance are also used to refer to the use of inheritance as a means for conceptual modeling. Specialization expressed by the classical "is-a" relationship is still another relation that is sometimes considered distinct from the former relationships.¹⁰ In our approach toward the integration of the main uses of inheritance (subtyping and subclassing) in OOPLs, the two inheritance relationships should always be specialization complying with the "is-a" relationship. The "is-a" relationship is considered a criterion to justify the use of inheritance in the first place. The language must exclude any use of inheritance that does not reflect the correct "is-a" relationship.

Some authors have realized the need to deviate from the rigid postulate that all inheritance hierarchies should be subtyping. In Inheritance and the Development of Encapsulation Software Components,¹¹ Snyder suggests inheritance can be used both as a technique for specialization and as a technique for implementation. It is a technique for specialization because objects of a subclass must obey the semantics of the superclass, i.e., subclasses are not permitted to exclude an inherited operation from its external interface. It is also a technique for implementation in the sense that excluding inherited operations is both reasonable and useful as in the example of deriving class STACK from class DEQUE. Class STACK inherits the implementation of DEQUE, but is not a specialization of it. That is, it does not provide all operations of DEQUE. Snyder further argues that many OOPLs relate subtyping to inheritance, e.g., a class X is a subtype of class Y if X is a subclass of Y. He concludes that subtyping should not be tied to inheritance. It should be based on behavior instead. Thus, if the instances of class X meet the external interface of Y, then X is subtype of Y. For example, STACK inherits from DEQUE, but is not a subtype of it, as the behavior of objects of STACK is incompatible with interface of DEQUE. On the other hand, DEQUE is a subtype of STACK, but does not inherit from it. The author is right in saying that excluding inherited operations is both reasonable and useful, and we will see later how the semantics of the superclass is obeyed after the exclusion of operations. In our approach to inheritance, DEQUE will be an extension to QUEUE and STACK is a specialization of a view of QUEUE, namely a DEQUE.

Elements of the Integration
The component construct, the read and write methods, as well as the suppress mechanism, form the building blocks for our approach to integrating the two perspectives of inheritance. They also narrow the gap between the two viewpoints of inheritance. These language constructs have been explained in previous work.^12–14

The Component Construct
Basically, a component is an abstraction mechanism similar to a class in that it contains closely related data members and a set of operations to manipulate them.¹ It differs from a class in that it cannot be instantiated, i.e., cannot have objects. In this respect, it is like a Java interface. Such a component is independent of any class and thus can be included in any class. The data members of the component represent characteristics that might be shared by many different and unrelated classes, possibly belonging to different inheritance hierarchies. The smaller the number of data members in a component, the more the chance for reuse by a large number of classes. Listing 1 shows an example of the definition of a component containing a single data member. Note that we use the Eiffel notation for illustrative purposes.

component HEIGHT feature
    height : REAL
    setHeight (ht : REAL) do height := ht end
    changeHeight (delta : REAL) do height := height + delta end
    -- other possible operations
end

All objects having a height may own the component HEIGHT. Now, assuming proper definitions for the three components NAME, BIRTHDATE, and ADDRESS exist, we can define a base class, say PERSON that may include such a component. The combine clause means that the base class consists of four components, namely NAME, BIRTHDATE, ADDRESS, and HEIGHT (see Listing 2). Other components can also be added to this list later. Combination does not assemble the class. The task of assembling a complete class will be done using the view construct as shown in Listing 2. The base class PERSON is an abstract class and thus may not have objects. An object must belong to some view. The constructor is introduced in the base class to indicate that any object of any view of a person is, in fact, an object of class PERSON. The combine clause indicates that the NAME, BIRTHDATE, ADDRESS, and HEIGHT components are part of the class PERSON. It lists all components (enclosed between curly braces and separated by commas) that can be used by a view of the class.

abstract class PERSON combine
   {NAME, BIRTHDATE, ADDRESS, HEIGHT}
creation make
feature
      abstract make(name : STRING, dob : DATE,
         adr : ADDRESS, ht : REAL) is
    -- other constructors, if any
end
view AVIEW is PERSON
   {NAME, ADDRESS, BIRTHDATE, HEIGHT}
      feature
                make(name : STRING, dob : DATE, adr :
                    ADDRESS, ht : REAL ) is
                do Name := name; BirthDate := dob; Address := adr;
                    Height := ht end
end
view MYVIEW is PERSON {NAME, BIRTHDATE}
      feature
      make(name : STRING, dob : DATE) is
                do Name := name; BirthDate := dob end
end

Here, the view AVIEW determines the structure of the person objects. A view specifies only the components that are required to determine the structure of the objects. The same application may thus declare more than one view of a class. That is, classes are sets of components that are intended to provide conceptually meaningful descriptive entities. Views on the other hand ensure a flexible and disciplined way of selecting a combination of components. Views are intended to provide generative entities to support object creation in actual programs.

The Read & Write Methods
Allowing access to data members of a class only via read and write methods will solve some of the problems of implementation inheritance such as the overhead in object representation and the need to redefine most of the inherited methods.¹³ Listing 3 illustrates the use of the read & write methods, which are used to query and assign to the instance variables. It also shows the use of the suppress constructs to discard unwanted inherited instance variables. The code uses Eiffel notation for explanatory purposes and uses a simplified version of a class representing a file system. In its general form, a file system can be represented as a graph, in which a file may belong to more than one parent. In a more specialized form, a file system can be represented as a tree, in which a file may belong to only one parent. Thus, we can reduce the object representation at the level of the more specialized class by using the suppress mechanism. The code assumes the definition of a class DIRECTORY and gives an implementation of a few methods.

class GRAPHNODE creation Make
     feature
              -- constructors and other features
              link (dir : DIRECTORY) is
                  do
             wtParents(rdNrParents, dir )
             wtNrParents(rdNrParents + 1)
                   end
       moveFile(from : DIRECTORY, to : DIRECTORY) is
                   local
              i : Integer
                  do
              from
               i := 1
              until i <= rdNrParents and rdParents
                                       /= from loop
               i := i + 1
                              end
                              wtParents(i, to)
                   end
        parents : ARRAY [DIRECTORY];
        nrParents : Integer
feature { NONE }
        wtParents (pos : Integer, dir : DIRECTORY) is do
                      parents.put(dir, pos) end
        rdParents (pos : Integer) : DIRECTORY is do Result :=
                     parents @ pos end
        wtNrParents (no : Integer) is nrParents := no end
        rdNrParents : Integer is Result := nrParents end
end
class TREENODE inherit GRAPHNODE
        rename wtParents as wtParent, rdParents as rdParent
        suppress     Parents <wtParent, rdParent>
                 nrParents < no_op, 1>
         end
feature
        parent : DIRECTORY
        ...
feature { NONE }
       wtParent (pos : Integer, dir : DIRECTORY) is  do parent
        rdParent (pos : Integer) : DIRECTORY is do Result := parent end
end

The definition of the features wtParents(), rdParents(), wtNrParents(), and rdNrParents() in Listing 3 will be generated by the compiler in simple cases.¹³ However, in complex cases it will be the responsibility of the programmer to provide code for them. These methods can be redefined in subclasses and are subject to dynamic binding like any other non-frozen function in Eiffel. The suppress subclause lists inherited attributes that are suppressed in the subclass. It lists, between angled brackets, the read and write methods to use in the code that refers to the suppressed attributes. The read method for the attribute nrParents will return 1 at the level of the subclass TREENODE, and the write method is just the empty operation. In this case the compiler can generate code for the two methods. Through the use of read and write methods, we can reuse inherited operations, which are not needed at the level of the more specialized class. The combination of polymorphism with descendant hiding, the ability to restrict the access rights of inherited operations, is possible. Suppose, for example, we have the following declarations, then the operation link() can be invoked on objects of the two classes without the need to redefine link().

fs1: GRAPHNODE, fs2 : TREENODE
!!fs1.Make(..)
!!fs2.Make(...)
fs1 := fs2; fs1.link(dir) -- OK

Figure 1. (a) Traditional inheritance structure; (b) new approach.

A class can combine several components that are of two kinds: basic components and additional components. The basic components together form the initial concept coherently and completely. For instance, the basic component of class QUEUE would contain the core functionality of queues such as Add(), Remove(), isEmpty(), isFull(), and Length(). Figure 1 shows that class QUEUE is extended with new functionality to accommodate the concept of a double-ended queue. There is no class associated with this new functionality. Instead, it is encapsulated in a component called DEQUE.

Class QUEUE will not directly combine the basic component QUEUE as illustrated in Figure 2. Figure 2 also shows that the concept of a stack is a specialization of the concept of a queue, whereas the concept of a deque is an extension to the concept of a queue. This explains why we advocate two separate mechanisms for inheritance. Figure 2 shows three relationships:

1. The extends relationship between components, represented graphically by a single-dashed arrow, implements the code sharing viewpoint of inheritance.
2. The specializes relationship between classes, represented graphically by a continuous arrow, implements the conceptual modeling viewpoint of inheritance.
3. The Combines relationship between classes and components, represented graphically by a double-dashed arrow.

Figure 2. Inheritance for sharing vs. inheritance for modeling.

Our dichotomy of inheritance is paradoxical. On the one hand, extension inheritance promotes both code reuse and conceptual modeling. A component extends another one by adding extra data and methods with complete preservation of the semantics of the extended component. Preservation of semantics is achieved by a method combination mechanism in such a way that the redefining method always invokes the redefined version as defined in the superclass.¹⁴ On the other hand, specialization inheritance also promotes both code reuse and conceptual modeling. The inherited code is reused with slight change to it, and a subclass is derived from a superclass, complying with the "is-a" relationship. Thus, both inheritance relationships are means for code reuse (subclassing) and conceptual modeling (subtyping). In fact, code reuse is what OO is all about. So, it is normal that both types promote and support it. Likewise, we need to have inheritance structures that involve classes related with the "is-a" relationship. Thus, conceptual modeling should also be supported, and this is exactly what we mean by integrating the two views.

Why do we refer to extension inheritance as a code reuse tool and specialization inheritance as a conceptual modeling tool? Because the component construct is a mechanism that largely supports code reuse. There is more code reuse in extension inheritance than in specialization inheritance. Specialization inheritance implements the "special kind of" relationship; the subclass may exclude inherited methods. However, we cannot forbid such inheritance links only because some of the inherited data or methods do not apply to the objects of a subclass. Classical examples are ostrich being a subclass of bird and square being a subclass of rectangle. With the new supporting mechanisms for specialization inheritance, we allow such derivations, thereby enhancing conceptual modeling.

We will demonstrate how the inheritance structure depicted in Figure 2 can be translated into an OOPL. We have chosen the Eiffel language notation for this purpose. Only the specification is given, as the code is straightforward. It should be noted that Eiffel does not support some of the concepts introduced in our approach. So, the code given in the next listings will not necessarily reflect correct Eiffel code.

The Abstraction QUEUE
Let us first start by defining the class QUEUE. In our approach, as mentioned earlier, base classes do not contain data members and methods. Listing 4 shows the specification of the basic components for the class QUEUE. Only basic methods that manipulate the data members of a component are included in the component. If the effect of a method can be achieved by applying one or more methods of the same component, in some order, then this method is not a basic method, and consequently should not be included. At this stage, we are content with these heuristics and guidelines. However, if the effect of a method could be formally described, then such a requirement could be checked. The definition of component QUEUE, as defined in Listing 4, is basically the same as the definition of class QUEUE, except it contains no constructors.

basic component QUEUE
feature
     Head : INTEGER
        -- index of the first available space in queue.
     Front : REAL is
     Add(elm : REAL) is
     Remove is
     IsFull : BOOLEAN is
     IsEmpty : BOOLEAN is
     Length : INTEGER is
feature { NONE }
     Impl : ARRAY[REAL]	
        -- an array of elements of type real.
end

The definition of class QUEUE is given in Listing 5, which provides the necessary constructors. The constructor is specified as abstract because code for constructors is provided by views.

abstract class QUEUE  combine QUEUE creation Make
feature
     abstract Make(..)
     -- other constructors and relevant information if any.
end

The Abstraction DEQUE
We use two separate keywords for inheritance, extends for components to implement extension inheritance (inheritance for sharing), and specializes for classes to implement specialization inheritance (inheritance for modeling). In effect, both will use the known techniques for implementing inheritance. We believe that a distinction between true extension inheritance and specialization inheritance should be made at the language (syntactic) level. This approach thus has advantages:

1. Clear understanding of the class hierarchy and the relationship between objects.
2. Avoiding the intermingling of different types of inheritance.
3. Clear, efficient, and elegant implementation of object behavior.

component DEQUE extends QUEUE
feature
     Tail : INTEGER                       -- index to first available space
                                          from other end of the queue.
     Rear : INTEGER is
     AddEnd(elm : REAL) is
     RemoveEnd :  REAL is
end

Definition of Class STACK Based on QUEUE
A stack is a special kind of a (double-ended) queue, where elements are added and deleted from one end (last in first out access policy). We can thus naturally reason that class STACK is a subclass of QUEUE. In a double-ended queue, elements are added and removed from either end, and nowhere else. Class STACK inherits only one part of a double-ended queue and suppresses the other part, which corresponds to addition and deletion from the other end. As discussed earlier, one would argue that this form of inheritance is implementation inheritance (code sharing) rather than a form for conceptual modeling. Indeed, there is code sharing and this probably motivates the use of inheritance in the first place. However, we have said that both of our inheritance relationships (extension and specialization) should manifest and comply with the "is-a" relationship. In addition, our specialization inheritance relationship reflects more the restriction inheritance case and implements the "special kind of" relationship. In the end, inheritance, whether for subtyping or for code sharing, will always reuse pieces of code. The issue here is that a stack is truly a special kind of a queue, namely a double-ended queue, and therefore must be modeled as such.

Related Work
A single inheritance mechanism is not adequate to cover both extension inheritance and specialization inheritance. As explained earlier, each type has its own requirements and represents a different view of inheritance. There are actually many researchers who advocate the idea of separating these two uses of inheritance. A conclusion from "A Methodology of Inheritance,"¹⁵ is that undisciplined use of inheritance is due to the fact that language designers try to keep inheritance simple (it requires just one operator and one language statement). Another research work that suggests separating inheritance into two types is "Uses and Abuses of Inheritance,"¹ where the two types are called module inheritance—a tool to reuse existing behavior in a new module—and type inheritance—a classification mechanism. "Separating the Subtype Hierarchy for the Inheritance of Implementation"¹⁶ also presents two separate hierarchies for subtype and implementation inheritance at language level. POOL,¹⁷ among other OOPLs, supports the separation of subtyping from subclassing. However, all attempts to separate subtyping from subclassing aims at defining a construct for subtyping and another construct for subclassing. Usually the construct for subtyping defines only specification of operations. Take, for example, the interface construct of Java, it only provides the specification of operations. A class must mention which interfaces it implements. Subclassing can be achieved by using classes, but the problems of inheritance will still be there. A component, on the other hand, provides both implementation and specification of operations while complying with the subtyping rules. A component always adds extra behavior and never excludes inherited behavior, in such a way that semantic compatibility is maintained.

We emphasize the fact that there has been much work done regarding the definitions and requirements of the extension (subtyping) relationship,^4,17,18 but little work has been done in terms of language constructs and rules to enforce the requirements. On the other hand, there has been little work done on the specialization (subclassing) relationship, in terms of definitions, requirements, and supporting mechanisms. Our approach deals with the two issues of subtyping and subclassing equally, and provides some building blocks on which further work will be based.¹⁹ It paves the way to a clear and adequate support for the two relationships in OOPLs.

Our approach to the separation not only requires two operators for the two inheritance mechanisms, it also outlines a set of rules to enforce the best uses of inheritance and to prevent possible bad uses. Moreover, some supporting mechanisms are presented in order to help enforce these rules. Our belief is that the guidelines and heuristics found in literature on proper and bad uses of inheritance must be backed by language constructs. We also believe that OOPLs should have good support for both mechanisms to fully benefit from inheritance, and help produce good inheritance structures, which is a major concern of the designers of OO systems.

view DEQUE  is  QUEUE  { DEQUE }
feature
     Make(..) is
end

class STACK specializes DEQUE
     rename ..
     suppress Tail <wtHead, rdHead>
     -- descendant hiding of operations to add and delete items from other end
end

Conclusion and Future Work
We've addressed the issue of integrating the two perspectives of inheritance, code reuse, and conceptual modeling. Central to this issue is the concept of component—the mechanism by which this can be achieved. Code sharing and conceptual modeling are two faces of the same coin, and thus should be supported adequately and efficiently. We have introduced some of the necessary building blocks needed to fulfill this goal. However, there remains to be seen how such language constructs and mechanisms can be incorporated in a language to prove their feasibility. We believe, however, that such mechanisms will not impose undue complexity on language implementation.

References

1. Armstrong, J.M. and R.J. Mitchell. "Uses and Abuses of Inheritance," Software Engineering Journal, 9(1), Jan. 1994.
2. Firesmith D. "Inheritance Guidelines," JOOP, 8(2):67–72, May 1995.
3. Halbert, D.C. and O'Brien, P.D. Using Types and Inheritance in Object-Oriented Programming,". IEEE Software, Sept. 1987.
4. Liskov, Barbara H. and Jeannette M. Wing. "A Behavioral Notion of Subtyping," ACM Transactions on Programming Languages and Systems, Nov. 1994.
5. Magnusson, B. "Code Reuse Considered Harmful," JOOP, 4(3): 8, November 1991.
6. Rumbaugh, J. "Disinherited! Examples of Misuse of Inheritance," JOOP, 5(9): 22–24, February 1993.
7. Taivalsaari, A. "On the Notion of Inheritance," ACM Computing Surveys, September 1996.
8. Madsen O.L. et al., Object-Oriented Programming in the Beta Language, Addison–Wesley, Wokingham, England, 1993.
9. Goldberg, A. and D. Robson. Smalltalk-80, The Language and Its Implementation, Addison–Wesley, Reading, MA, 1989.
10. Lalonde, W. and J. Pugh." Subclassing =/ subtyping =/ is-a," JOOP, 3(5):57–62, January 1991.
11. Snyder, A. "Inheritance and the Development of Encapsulated Software Components," in Research Directions in Object-Oriented Programming, Ed. P. Wegner, MIT Press, 1987.
12. Al-Ahmad, W. and E. Steegmans. "A New Approach to Extension Inheritance," JOOP, 12(3):20–28, June 1999.
13. Al-Ahmad, W. and E. Steegmans. "Improving Support for Specialization Inheritance," JOOP, 11(8), 1999.
14. Al-Ahmad W. and Steegmans E., Specialization of Behavior: Comparison, Critique, and a New Approach, JOOP, 10(9), 1998.
15. Breu R., "A Methodology of Inheritance," Software-Concepts and Tools, 16, 1995.
16. Porter, H. "Separating the Subtype Hierarchy from the Inheritance of Implementation," JOOP, 4(9): 20–29, February, 1992.
17. America, P. and F. van der Linden. "A Parallel Object-Oriented Language with Inheritance and Subtyping," in Proceedings of OOPSLA/ECOOP '90, Ed. N. Meyrowitz, ACM Press, 1990.
18. Bar-David, Tsvi. "Practical Consequences of Formal Definitions of Inheritance," JOOP, 5(4): 43–49, July/August 1992.
19. Al-Ahmad W. and Steegmans E., Inheritance in Object-Oriented Languages: Requirements and Supporting Mechanisms, JOOP, 12(8), 1998.