Lecture
Kinds of Relationships
Consider the similarities and differences among the following classes: flowers, daisies, red roses, yellow roses, petals, and ladybugs. We may note the following:
From this simple example it follows that classes, like objects, do not exist in isolation. In every problem domain the key abstractions interact in many interesting ways, and this is what we must reflect in the design [21].
Relationships among classes may mean one of two things. First, they may have something in common. For example, both daisies and roses are kinds of flowers: both have brightly colored petals, both give off a fragrance, and so on. Second, there may be some semantic connection. For example, red roses are more like yellow roses than they are like daisies. But roses and daisies have more in common with each other than flowers do with petals. There is also a symbiotic connection between flowers and ladybugs: ladybugs protect flowers from pests, which in turn serve as food for the ladybugs.
Three basic kinds of relationships among classes are known. First, there is the "generalization/specialization" relationship (the general and the particular), known as "is-a". Roses are flowers, which means that roses are a specialized special case, a subclass, of the more general class "flowers". Second, there is the "whole/part" relationship, known as "part of". Thus, petals are part of flowers. Third, there are semantic, meaning-based relationships, associations. For example, ladybugs are associated with flowers - although one would think they have little in common. Or take this: roses and candles - both can be used to decorate a table.
Programming languages have developed several common approaches to expressing relationships of these three kinds. In particular, most object-oriented languages directly support various combinations of the following kinds of relationships:
Figure 16.4. Relationships among classes
Figure 16.6. Associations with different multiplicities
Of the six kinds of relationships listed, the most general and least definite is association. As we will see in Chapter 6, the analyst usually notes the presence of an association and, gradually refining the design, turns it into some more specialized relationship.An alternative to inheritance is delegation, in which objects are regarded as prototypes that delegate their behavior to related objects. In this way classes become unnecessary [23].
Inheritance is probably to be considered the most interesting semantically. It expresses the relationship of the general and the particular. However, in our experience inheritance alone is not enough to express the whole variety of phenomena and relationships of life. Aggregation, which reflects whole/part relationships among instances of classes, is also useful. It is worth adding the using relationship, which denotes the presence of a link between instances of classes. Dealing with the languages Ada, Eiffel, and C++, we cannot do without instantiation, which, like inheritance, is a specific variety of generalization. "Metaclass" relationships are something quite different, encountered explicitly only in the languages Smalltalk and CLOS. A metaclass is a class of classes, which allows us to treat classes as objects.
Figure 3-4. Association.
Association
Example. Wishing to automate a retail point of sale, we discover two abstractions - products and sales. Figure 3-4 shows the association we perceive in doing so. The class Product is what we sold in some transaction, and the class Sale is the transaction itself, in which several products were sold. Presumably the association works in both directions: given a product, one can get to the transaction in which it was sold, and starting from the transaction, one can find what was sold.
In C++ this can be expressed with the help of what Rumbaugh calls buried pointers. Here are two excerpts from the declarations of the corresponding classes:
class Product;
class Sale;
class Product {
public:
...
protected:
Sale* lastSale;
};
class Sale {
public:
...
protected:
Product** productSold;
};
This is a "one-to-many" association: each product instance relates to only one most recent sale, whereas each instance of Sale may point to a collection of products sold.
Semantic dependencies. As this example shows, an association is a semantic connection. By default it has no direction (unless stated otherwise, an association, as in this example, implies a two-way connection) and it does not explain how the classes communicate with one another (we can only note the semantic dependency by indicating what roles the classes play for each other). Yet this is exactly what we need at the early stage of analysis. So we record the participants, their roles, and (as will be discussed below) the multiplicity of the relationship.
Multiplicity. In the previous example we had a "one-to-many" association. We thereby indicated its multiplicity (that is, roughly speaking, the number of participants). In practice it is important to distinguish three cases of association multiplicity:
A "one-to-one" relationship denotes a very narrow association. For example, in a retail sales system an instance might be the connection between the class Sale and the class CreditCardTransaction: each sale corresponds to exactly one debit of money from a given credit card. "Many-to-many" relationships are not uncommon either. For example, each object of the class Customer (buyer) may initiate a transaction with several objects of the class Saleperson (sales agent), and each sales agent may interact with several customers. As we will see in Chapter 5, all three kinds of multiplicity have variations of various sorts.
Inheritance
Examples. Space probes in flight send to ground stations information about the state of their main systems (for example, power sources and engines) and readings from sensors (such as radiation detectors, mass spectrometers, television cameras, micrometeorite collision detectors, and so on). The entire body of transmitted information is called telemetry data. As a rule, it is transmitted as a data stream consisting of a header (including time stamps and keys for identifying the data that follows) and several packets of data from subsystems and sensors. All of this looks like a simple collection of data of heterogeneous types, so structures suggest themselves for describing each type of telemetry data:
class Time...
struct ElectricalData {
Time timeStamp;
int id;
float fuelCell1Voltage, fuelCell2Voltage;
float fuelCell1Amperes, fuelCell2Amperes;
float currentPower;
};
However, such a description has a number of drawbacks. First, the structure of the class ElectricalData is not protected, that is, a client may cause a change to such important information as timeStamp or currentPower (the power developed by both electrical batteries, which can be computed from the current and the voltage). Second, this structure is completely open, that is, modifications to it (adding new elements to the structure or changing the type of existing elements) affect clients. At the very least, all declarations connected in any way with this structure have to be recompiled. More importantly, making changes to the structure may disrupt the logic of its relationships with clients, and hence the logic of the entire program. In addition, the structure declaration given is very hard to comprehend. Many different actions can be performed on such a structure (transmitting the data, computing a checksum to detect errors, and so on), but none of them will be logically bound to the structure shown. Finally, suppose that analysis of the system requirements has yielded several hundred varieties of telemetry data, comprising the structure shown above and other electrical parameters at various monitoring points of the system. Clearly, declaring so many additional structures would be redundant, both because of the repetition of structures and because of the presence of common processing functions.
A child class may inherit the structure and behavior of its parent classes.
It would be better to create a separate class for each kind of telemetry data, which would allow the data in each class to be protected and tied to the operations performed on it. But this approach does not solve the problem of redundancy.
It is considerably better to build a hierarchy of classes in which more specialized classes are formed from general ones by means of inheritance; for example, as follows:
class TelemetryData {
public:
TelemetryData();
virtual ~TelemetryData();
virtual void transmit();
Time currentTime() const;
protected:
int id;
Time timeStamp;
};
In this example a class has been introduced that has a constructor, a destructor (which descendants may override), and the functions transmit and currentTime, visible to all clients. The protected members id and timeStamp are somewhat better encapsulated - they are accessible only to the class and its subclasses. Note that the function currentTlrne has been made public, thanks to which the value of timeStamp can be read (but not modified).
Now let us deal with ElectricalData:
class ElectricalData : public TelemetryData {
public:
ElectricalData(float v1, float v2, float a1, float a2);
virtual ~ElectricalData();
virtual void.transmit();
float currentPower() const;
protected:
float fuelCell1Voltage, fuelCell2Voltage;
float fuelCell1Amperes, fuelCell2Amperes;
};
This class is a descendant of the class TelemetryData, but the original structure has been extended (by four new members), and the behavior overridden (the function transmit has been changed). In addition, the function currentPower.
Single inheritance. Put simply, inheritance is a relationship among classes in which one class repeats the structure and behavior of another class (single inheritance) or of several other classes (multiple inheritance). The class whose structure and behavior are inherited is called the superclass. Thus, TelemetryData. is the superclass of ElectricalData. A class derived from a superclass is called a subclass. This means that inheritance establishes a hierarchy of the general and the particular among classes. In this sense ElectricalData is a more specialized class of the more general TelemetryData. We have already seen that in a subclass the structure and behavior of the original superclass are extended and overridden. The presence of an inheritance mechanism is what distinguishes object-oriented languages from object-based ones.
A subclass usually extends or restricts the existing structure and behavior of its superclass. For example, the subclass GuardedQueue may add to the behavior of the superclass Queue operations that protect the state of the queue from simultaneous modification by several independent threads. The converse example: the subclass UnselectableDisplayItem may restrict the behavior of its superclass DisplayItem by prohibiting selection of the object on the screen. Often subclasses do both.
The single-inheritance relationships from the superclass TelemetryData are shown in Figure 3-5. The arrows denote the relationship of the general to the particular. In particular, Cameradata is a kind of the class SensorData, which in turn is a kind of the class TelemetryData. The same type of hierarchy is characteristic of semantic networks, which are often used by specialists in pattern recognition and artificial intelligence to organize knowledge bases. In Chapter 4 we will show that the proper organization of a hierarchy of abstractions is a matter of logical classification.
Figure 3-5. Single inheritance.
One may expect that instances will be created for some of the classes in Figure 3-5 and not for others. Objects are most likely to be formed from the most specialized classes ElectricalData and SpectrometerData (such classes are called concrete classes, or the leaves of the hierarchy tree). Forming objects from classes occupying an intermediate position (SensorData or, all the more so, TelemetryData) is less likely. Classes whose instances are not created are called abstract. Subclasses of abstract classes are expected to refine them into a viable abstraction, filling the class with content. In the Smalltalk language a developer can force a subclass to override a method by placing in the implementation of the superclass method a call to the method SubclassResponsibility. If the method is not overridden, an error is generated when it is invoked. Similarly, in C++ it is possible to declare functions as pure virtual. If they are not overridden, an instance of such a class cannot be created.
The most general class in a class hierarchy is called the base class. In most applications there are several base classes, and they reflect the most general abstractions of the problem domain. In fact, especially in C++, a well-made class structure is more a forest of inheritance trees than one multistory inheritance structure with a single root. But in some programming languages a topmost base class is defined, which is the single superclass of all other classes. In the Smalltalk language this role is played by the class object.
A class usually has two kinds of clients:
It is often useful to have different interfaces for them. In particular, we want to show only the externally visible behavior to instance clients, but we need to expose utility functions and representations to subclass clients. This explains the presence of public, protected, and private parts in a class declaration in the C++ language: the developer can clearly separate which members of the class are accessible to instances and which to subclasses. In the Smalltalk language the degree of such separation is smaller: data are visible to subclasses but not to instances, while methods are publicly accessible (private methods can be introduced, but the language does not enforce their protection).
There are serious tensions between the needs of inheritance and those of encapsulation. To a significant extent, inheritance exposes some of a class's secrets to the inheriting class. In practice, to understand how some class works, one often has to study all of its superclasses in their internal detail.
Inheritance implies that subclasses repeat the structures of their superclasses. In the previous example, instances of the class ElectricalData contain the structural members of the superclass (id and timeStamp) and more specialized members (fuelCell1Voltage, fuelCell2Voltage, fuelCell1Amperes, fuelCell2Amperes) [Some object-oriented programming languages, chiefly experimental ones, allow a subclass to reduce the structure of its superclass].
The behavior of superclasses is also inherited. On objects of the class ElectricalData one may use the operations currentTime (inherited from the superclass), currentPower (defined in the class), and transmit (overridden in the subclass). Most languages permit not only inheriting the methods of the superclass, but also adding new ones and overriding existing ones. In Smalltalk any method of a superclass can be overridden in a subclass.
In C++ the degree of control over this is somewhat greater. A function declared virtual (the function transmit in the previous example) may be overridden in a subclass, while the rest (currentTime) may not.
Single polymorphism. Suppose the function transmit of the class TelemetryData is implemented as follows:
void TelemetryData::transmit()
{
// transmit id
// transmit timeStamp
};
In the class ElectricalData the same function is overridden:
void ElectricalData::transmit()
{
TelemetryData::transmit();
// transmit the voltage
// transmit the current
};
This function first calls the identically named function of the superclass by means of its explicitly qualified name TelemetryData::transmit(). That one transmits the packet header (id and timeStamp), after which the subclass transmits its own data.
Let us now define instances of the two classes described above:
TelemetryData telemetry; ElectricalData electrical(5.0, -5.0, 3.0, 7.0);
Now let us define a free procedure:
void transmitFreshData (TelemetryData& d, const Time& t)
{
if (d.currentTime() >= t)
d.transmit();
);
What will happen if the following two statements are executed?
transmitFreshData(telemetry, Time(60)); transmitFreshData(electrical, Time(120));
In the first statement the header already familiar to us will be transmitted. In the second, the same header will be transmitted, plus four floating-point numbers containing the results of the electrical measurements. Why is this so? After all, the function transmitFreshData knows nothing about the class of the object, it simply executes d.transmit()! This was an example of polymorphism. The variable d may denote objects of different classes. These classes have a common superclass and they can respond, albeit in different ways, to one and the same message, understanding its meaning in the same way.
Cardelli and Wegner observed that "conventional typed languages, such as Pascal, are based on the idea that functions and procedures, and hence their operands, have a unique type. Such languages are said to be monomorphic, in the sense that every value and variable can be interpreted to be of one and only one type. In contrast to monomorphism, polymorphism allows values and variables to be of more than one type". The idea of ad hoc polymorphism was first described by Strachey, who had in mind the ability to redefine the meaning of symbols such as "+" as the need arises. In modern programming we call this overloading. For example, in C++ one may define several functions with one and the same name, and they will be distinguished automatically by the number and types of their arguments. The set of these features is called the signature of the function; in the Ada language the type of the return value is added to this list. Strachey also spoke of parametric polymorphism, which we now simply call polymorphism.
In the absence of polymorphism, program code is forced to contain a multitude of case or switch selection statements. For example, in the Pascal language it is impossible to form a hierarchy of telemetry data classes; instead one has to define one large variant record encompassing all the varieties of data. To select a variant one must check a tag that determines the type of the record. In the Pascal language the procedure TransmitFreshData might be written as follows:
const Electrical = 1; Propulsion = 2; Spectrometer = 3; Procedure Transmit_Presh_Data(TheData: Data; The_Time: Time); begin if (The_Data.Current_Time >= The_Time) then case TheData.Kind of Electrical: Transmit_Electrical_Data(The_Data); Propulsion: Transmit_Propulsion_Data(The_Data); end; end;
To introduce a new type of telemetry data, one must modify this variant record, adding the new type to every case statement. In such a situation the likelihood of errors increases, and the design becomes unstable.
Inheritance makes it possible to distinguish varieties of abstractions, and monolithic types become unnecessary. Kaplan and Johnson noted that "polymorphism is most useful when there are several classes with the same protocols". Polymorphism makes it possible to do without selection statements, since objects themselves know their own type.
Inheritance without polymorphism is possible, but not very useful. This can be seen in the example of Ada, where derived types may be declared, but because of the language's monomorphism the operations are rigidly fixed at compile time.
Polymorphism is closely bound up with the mechanism of late binding. With polymorphism, the association of a method with a name is determined only during program execution. In C++ the programmer has the ability to choose between early and late binding of a name to an operation. If a function is virtual, binding will be late and, consequently, the function is polymorphic. If not, binding occurs at compile time and nothing can be changed afterward. The following sidebar is devoted to this question.
Inheritance and typing. Let us consider once again the overriding of the function transmit:
void ElectricalData::transmit()
{
TelemetryData::transmit();
// transmit the voltage
// transmit the current
};
In most object-oriented programming languages, when implementing a subclass method it is permitted to call a method of some superclass directly. As can be seen from the example, this is allowed even when the subclass method has the same name and in fact overrides the superclass method. In Smalltalk a method of a higher-level class is called using the keyword super, while the caller can refer to itself using the keyword self. In C++ a method of any reachable higher-level class can be called by adding the class name as a prefix, forming the qualified name of the method (as with TelemetryData::transmit() in our example). The calling object may refer to itself using the predefined pointer this.
In practice a superclass method is called before or after additional actions. The subclass method refines or supplements the behavior of the superclass [In CLOS these different roles of a method are expressed explicitly with the help of the additional qualifiers :before, :after or :around. A method without an additional qualifier is considered primary and performs the main work that provides the required behavior. A before-method is called before the primary one, an after-method after the primary one, and an around-method acts as a wrapper around the primary method, which is invoked from within it by the function call-next-method].
All the subclasses in Figure 3-5 are also subtypes of the class above them. In particular, ElectricalData is a subtype of TelemetryData. A type system that develops in parallel with inheritance is usual for strongly typed object-oriented languages, including C++. For Smalltalk, which can hardly be considered typed at all, types are of no significance.
| Method lookup
Consider the hierarchy (Figure 3-6) in which there is a base class and three subclasses named circle, Triangle and Rectangle. For the class Rectangle a subclass is in turn defined, SolidRectangle. Suppose that in the class DisplayItem an instance variable theCenter is defined (specifying the coordinates of the center of the image), as well as the following operations:
Figure 3-6. Class diagram of DisplayItem. The class Circle has a variable theRadius and correspondingly operations for setting (set) and reading the value of this variable. For this class the operation draw forms an image of a circle of the given radius centered at the point theCenter. In the class Rectangle there are variables theHeight and theWidth and the corresponding operations for setting and reading their values. The draw operation in this case forms an image of a rectangle of the given height and width centered at the given point theCenter. The subclass SolidRectangle inherits all the features of the class Rectangle, but the draw operation is overridden in this subclass. First the draw of the higher-level class is called, and then the resulting outline is filled with color. Now consider the following program fragment: DisplayItem* items; The call to draw requires polymorphic behavior. We have a heterogeneous array of objects containing pointers to any varieties of DisplayItem. Suppose some client wants them all to draw themselves on the screen. Our approach is to iterate over the elements of the array and send each object pointed to the message draw. The compiler cannot determine which function and from where must be called in doing so, since it is impossible to predict what the elements of the array will point to during program execution. Let us look at how this problem is solved in different object-oriented languages. Since there are no types in Smalltalk, methods are invoked strictly dynamically. When a client sends the message draw to the next receiver, the following happens:
The chief actor in this algorithm is the method dictionary. It is formed when the class is created and, being part of its implementation, is hidden from clients. A method call in Smalltalk takes about 1.5 times as long as a call to a simple subroutine. In commercial versions of Smalltalk method invocation has been sped up by 20-30% by caching access to the dictionary. The operation draw in the subclass solidRectangle represents a special case. We have already noted that first the identically named method of the superclass Rectangle is called. In Smalltalk the keyword super is used to call a superclass method. The lookup for the method super draw begins immediately at the superclass. Deutsch's research gives grounds to believe that polymorphism is not needed in 85% of cases, so a method call can often be reduced to an ordinary procedure call. Duff notes that in such situations the programmer often makes implicit assumptions that would permit early binding. Unfortunately, in untyped languages he has no way of communicating this to the compiler. In more strongly typed languages, such as C++, such a way exists. In these languages the method invocation algorithm differs somewhat from the one described above and makes it possible to shorten the lookup time in many cases while preserving the properties of polymorphism. In C++ operations intended for late binding are declared virtual, and all the rest are handled by the compiler as ordinary subroutine calls. In our example draw is a virtual function, and location is an ordinary one. There is one more device that can be used to gain speed. Non-virtual methods may be declared inline, in which case the corresponding subroutine is not called but is explicitly included in the code in the manner of a macro substitution. To manage virtual functions, C++ uses the concept of the vtable (virtual table), which is formed for each object when it is created (that is, when the object's class is already known). Such a table contains a list of pointers to virtual functions. For example, when an object of the class Rectangle is created, the virtual table will contain an entry for the virtual function draw containing a pointer to the nearest implementation of the function draw in the hierarchy. If in the class DisplayItem there is a virtual function rotate that in the class Rectangle is not overridden, then the corresponding pointer for rotate will remain bound to the class DisplayItem. During program execution an indirect reference occurs through the corresponding pointer and the needed code is executed immediately, without any lookup. The operation draw in the class SolidRectangle represents a special case in the C++ language as well. To call the draw method from the superclass, a special prefix is used indicating where the function is defined. It looks like this: Rectangle::Draw(); Stroustrup's research has shown that a virtual function call is only slightly less efficient than an ordinary function call. For single inheritance a virtual function call requires an additional three or four memory accesses relative to an ordinary call; with multiple inheritance the number of such additional operations is five or six. Finding the needed functions is substantially more complicated in the CLOS language, where additional qualifiers are used: : before, : after, : around. The presence of multiple polymorphism complicates the problem still further. When a method is called in the CLOS language, as a rule the following algorithm is carried out:
|
Parallels between typing and inheritance are to be expected wherever a hierarchy of the general and the particular is intended to express semantic connections among abstractions. Let us again consider the declarations in C++:
TelenetryData telemetry; ElectrycalData electrical(5.0, -5.0, 3.0, 7.0);
The following assignment statement is legitimate:
telemetry = electrical; //electrical is a subtype of telemetry
Although it is formally correct, it is dangerous: any additions to the state of the subclass compared with the state of the superclass are simply sliced off. Thus, the four additional parameters defined in the subclass electrical will be lost in the copying, since there is simply nowhere to record them in the object telemetry of the class TelemetryData.
The following statement is incorrect:
electrical = telemetry; //incorrect: telemetry is not a subtype of electrical
One may conclude that assigning the value of object x to object y is permissible if the type of object x coincides with the type of object y or is a subtype of it.
In most strongly typed programming languages, converting values from one type to another is permitted, but only in those cases where a class/subclass relationship exists between the two types. In the C++ language there is an explicit conversion operator called casting. As a rule, such conversions are used on an object of a specialized class in order to assign its value to an object of a more general class. Such a cast is considered safe, since semantic checking is carried out at compile time. Sometimes operations casting objects of a more general class to specialized classes are necessary. These operations are not reliable from the standpoint of strong typing, since during program execution a mismatch (incompatibility) may arise between the object being cast and the new type [The latest improvements to C++, aimed at dynamic type determination, have mitigated this problem]. However, such conversions are used fairly often in cases where the programmer has a good idea of all the types of the objects. For example, if there are no parameterized types, classes such as set or bag are often created, representing collections of arbitrary objects. They are defined for some base class (this is far safer than using the void* idiom, as we did when defining the class Queue). The iteration operations defined for such a class can only return objects of that base class. Within a specific application the developer may use this class, creating objects only of some specialized subclass, and, knowing exactly what he intends to place in this class, may write the appropriate converter. But this whole elegant construction will collapse at run time if an object of an unexpected type turns up in the collection.
Most strongly typed languages allow applications to optimize the method invocation technique, often reducing message sending to a simple procedure call. If, as in C++, the type hierarchy coincides with the class hierarchy, such optimization is obvious. But it has its drawbacks. Changing the structure or behavior of some superclass may outlaw its subclasses. Here is what Micallef writes about this: "If typing rules are based on inheritance and we rework some class so that its position in the inheritance hierarchy changes, clients of this class may find themselves outlawed from the standpoint of types, in spite of the fact that the external interface of the class remains the same".
This brings us to the fundamental questions of inheritance. As was said above, inheritance is used because objects have something in common or because there is a semantic association between them. Expressing the same thought in different words, Snyder writes: "inheritance can be viewed as a way of managing software reuse, that is, as a simple decision by the developer to borrow useful code. In this case the mechanics of inheritance must be flexible and easily reconfigurable. Another point of view: inheritance reflects a fundamental kinship of abstractions, which cannot be undone". In Smalltalk and CLOS these two aspects are inseparable. C++ is more flexible. In particular, when defining a class its superclass may be declared public (as with ElectricalData in our example). In this case the subclass is considered also a subtype, that is, it undertakes to fulfill all the obligations of the superclass, in particular by providing a subset of the interface compatible with the superclass and by exhibiting behavior indistinguishable from the standpoint of the superclass's clients. But if, when defining a class, its superclass is declared private, this will mean that, while inheriting the structure and behavior of the superclass, the subclass will no longer be its subtype [We may also declare the superclass protected, which yields the same semantics as in the case of a private superclass, except that the public and protected members of such a superclass will be accessible to subclasses]. This means that the public and protected members of the superclass will become private members of the subclass, and consequently they will be inaccessible to lower-level subclasses. In addition, the fact that the subclass will not be a subtype means that the class and the superclass have (generally speaking) incompatible interfaces from the client's standpoint. Let us define a new class:
class InternalElectricalData: private ElectricalData {
public:
InternalElectricalData(float v1, float v2, float a1, float a2);
virtual ~InternalElectricalData();
ElectricalData::currentPower;
};
Here the superclass ElectricalData is declared private. Consequently, its methods, such as, for example, transmit, are inaccessible to clients. Since the class InternalElectricalData is not a subtype of ElectricalData, we can no longer assign instances of the subclass to objects of the superclass, as in the case of declaring the superclass public. Note that the function currentPower has been made visible by explicitly qualifying it. Otherwise it would have remained private. As might be expected, the rules of C++ forbid making an inherited member "more public" in a subclass than it is in the superclass. Thus, the member timeStamp, declared protected in the class TelemetryData, cannot be made public in a subclass by explicitly mentioning it (as was done for the function currentpower).
In the Ada language, derived types are used instead of subtypes to achieve an analogous effect. Defining a subtype does not mean the appearance of a new type, but only a constraint on an existing one. Defining a derived type, on the other hand, creates an independent new type that has a structure borrowed from the original type.
In the next section we will show that inheritance for the purpose of reuse and aggregation to some degree contradict one another.
Multiple inheritance. We have examined the questions connected with single inheritance, that is, when a subclass has exactly one superclass. However, as Vlissides and Linton pointed out: "single inheritance, for all its usefulness, often forces the programmer to choose between two equally attractive classes. This limits the ability to reuse predefined classes and forces the duplication of already existing code. For example, one cannot inherit a graphical element that would be simultaneously a circle and a picture; one has to inherit one of them and add what is needed from the other".
Multiple inheritance is directly supported in the C++ and CLOS languages, and also, to some degree, in Smalltalk. The necessity of multiple inheritance in OOP remains the subject of heated debate. In our experience, multiple inheritance is like a parachute: as a rule you do not need it, but when you suddenly do, it would be a pity not to have it at hand.
Imagine that we need to keep track of various kinds of tangible and intangible property - bank accounts, real estate, stocks, and bonds. Bank accounts may be checking or savings accounts. Stocks and bonds may be classed as securities; managing them is completely different from managing bank accounts, but both accounts and securities are kinds of assets.
However, there are many other useful classifications of the same kinds of property. In some context it may be necessary to distinguish what can be insured (real estate and, to some degree, savings deposits). Another aspect is the ability of property to yield dividends; this is a property common to bank accounts and securities.
Obviously, single inheritance in this case does not reflect reality, so we will have to resort to multiple inheritance [In fact, this is a "litmus test" for multiple inheritance. If we compose a class structure in which the terminal classes (the leaves) can be grouped into sets according to different orthogonal criteria (as in our example, where such criteria were the ability to yield dividends and the possibility of insurance) and these sets overlap, then this is a sign that it is impossible to get by with a single inheritance structure in which there would exist some intermediate classes with the needed behavior. We can remedy the situation by using multiple inheritance to combine the two needed behaviors wherever this is necessary]. The resulting class structure is shown in Figure 3-7. In it the class Security (securities) inherits simultaneously from the classes InterestBearingItem (source of dividends) and Asset (property). Similarly, BankAccount (bank account) inherits from three classes at once: InsurableItem (insurable) and the already familiar Asset and InterestBearingItem.
Here is how this is expressed in C++. First the base classes:
class Asset ... class InsurableItem ... class InterestBearingItem ...
Now the intermediate classes; each inherits from several superclasses:
class BankAccount: public Asset, public InsurableItem, public InterestBearingItem ... class RealEstate: public Asset, public InsurableItem ... class Security: public Asset, public InterestBearingItem ...
Finally, the leaves:
class SavingsAccount: public BankAccount ... class CheckingAccount: public BankAccount ... class Stock: public Security ... class Bond: public Security ...
Figure 3-7. Multiple inheritance.
Designing class structures with multiple inheritance is a difficult task, solved by successive approximations. There are two problems specific to multiple inheritance - how to resolve name conflicts among superclasses and what to do about repeated inheritance.
A name conflict occurs when two or more superclasses happen to have a member (a variable or a method) with the same name. Imagine that both Asset and InsurableItem contain the attribute presentValue, denoting the current value. Since the class RealEstate inherits from both of these classes, how is the inheritance of two operations with one and the same name to be understood? This, in fact, is the chief bane of multiple inheritance: a name conflict may introduce ambiguity into the behavior of a class with several ancestors.
This conflict is combated in three ways. First, the name conflict may be treated as an error and rejected at compile time (this is what Smalltalk and Eiffel do, although in Eiffel the conflict can be resolved by correcting the name). Second, one may consider that identical names denote the same attribute (this is what CLOS does). Third, to eliminate the conflict it is permitted to add prefixes to the names indicating the names of the classes they came from. This approach is adopted in C++ [In C++ a name conflict among the members of a subclass can be resolved by fully qualifying the class member name. Member functions with identical names and signatures are considered semantically identical].
About the second problem, repeated inheritance, Meyer writes the following: "A subtle difficulty in the use of multiple inheritance arises when one class is a descendant of another along more than one line. If a language permits multiple inheritance, sooner or later someone will write a class D that inherits from B and C, which in turn inherit from A. This situation is called repeated inheritance, and it must be handled correctly". Consider the following class:
class MutualFund: public Stock, public Bond ...
which inherits twice from the class security.
The problem of repeated inheritance is solved in three ways. First, one can forbid it, detecting it at compile time. This is done in the Smalltalk and Eiffel languages (but in Eiffel, once again, renaming is allowed in order to eliminate the ambiguity). Second, one can explicitly separate the two copies of the inherited member by adding prefixes in the form of the name of the originating class (this is one of the approaches adopted in C++). Third, one can regard multiple references to one and the same class as denoting one and the same class. This is what is done in C++, where a repeated superclass is defined as a virtual base class. A virtual base class arises when some subclass names another class as its superclass and marks that superclass as virtual to indicate that it is a shared class. Similarly, in the CLOS language repeatedly inherited classes are "shared" using a mechanism called the class precedence list. This list is compiled for each new class, placing in it the class itself and all its superclasses without repetition, on the basis of the following rules:
As a result the inheritance graph turns out to be flat, duplication is eliminated, and it becomes possible to treat the resulting hierarchy as a hierarchy with single inheritance [43]. This strongly resembles a topological sort of the classes. If it is possible, then repeated inheritance is permitted. In theory several equally valid results of the sort may exist, but the algorithm one way or another produces one of them. If, however, the sort is impossible (for example, if cycles arise in the structure), then the class is rejected.
With multiple inheritance a common technique is the creation of mixins (mixin). The idea of mixins comes from the Flavors language: one can combine (mix) small classes in order to build classes with more complex behavior. Hendler writes about this as follows: "a mixin is syntactically no different from a class, but their purposes are different. A mixin is not intended to give rise to independently used instances - it is mixed in with other classes". In Figure 3-7 the classes InsurableItem and interestBearingItem are mixins. Neither of them can exist on its own; they are used to give meaning to other classes [For the CLOS language, when enriching the behavior of existing primary methods it is common practice to build a mixin using only :before- and :after-methods]. Thus, a mixin is a class that expresses not a behavior, but one particular well-defined trait that can be grafted onto other classes through inheritance. Moreover, this trait is usually orthogonal to the intrinsic behavior of the class that inherits it. Classes constructed entirely from mixins are called aggregate classes.
Multiple polymorphism. Let us return to one of the member functions of the class DisplayItem:
virtual void draw();
This operation draws the object on the screen in some context. It is declared virtual, that is, polymorphic, overridable by subclasses. When this operation is called on some object, the program determines what, exactly, is to be executed (see the sidebar above). This is single polymorphism in the sense that the meaning of the message depends on only one parameter, namely, the object on which the operation is invoked.
In fact the operation draw ought to depend on the characteristics of the display system being used, in particular on the graphics mode. For example, in one case we want to obtain a high-resolution image, and in another to get a rough image quickly. We could introduce two different operations, say, drawGraphic and drawText, but this is not quite what we would like. The trouble is that every time a new kind of device has to be taken into account, it must be carried through the entire hierarchy of superclasses of the class DisplayItem.
CLOS has what are known as multimethods. They are polymorphic, that is, their meaning depends on a set of parameters (for example, on the graphics mode and on the object). C++ has no multimethods, so there the idiom known as double dispatching is used.
For example, we could derive a hierarchy of display devices from the base class DisplayDevice, and then define a method of the class DisplayItem as follows:
virtual void draw(DisplayDevice&);
In implementing this method we call graphics operations that are polymorphic with respect to the passed parameter of type DisplayItem, and thus double dispatching takes place: draw first exhibits polymorphic behavior depending on which subclass of the class DisplayItem the object belongs to, and then polymorphism manifests itself depending on which subclass of the class DisplayDevice the argument belongs to. This idiom can be extended to multiple dispatching.
Aggregation
Example. The aggregation relationship between classes bears directly on aggregation between their instances. Let us consider once more the class TemperatureController:
class TemperatureController {
public:
TemperatureController(Location);
~TemratureController();
void process(const TemperatureRamp&);
Minute schedule(const TemperatureRamp&) const;
private:
Heater h;
};
Fig. 3-8. Aggregation.
As is clear from Fig. 3-8, the class TemperatureController is undoubtedly the whole, and an instance of the class Heater is one of its parts. Exactly the same aggregation relationship between instances of these classes is shown in Fig. 3-3.
Physical containment. In the case of the class TemperatureController we have aggregation by value; this variety of physical containment means that an object of the class Heater does not exist apart from the enclosing instance of the class TemperatureController.
Less binding is containment by reference. We could change the private part of TemperatureController as follows [As an alternative we could declare h as a reference to a heater (Heater& in C++), in which case the semantics of initializing and modifying this object would be quite different from the semantics of pointers]:
Heater* h;
In this case the class TemperatureController still denotes the whole, but its part, an instance of the class Heater, is contained in the whole indirectly. Now these objects live separately from one another: we can create and destroy instances of the classes independently. In order to avoid structural dependency through references, it is important to adhere to some convention regarding the creation and destruction of objects, references to which may be held in different places. It must be done by one party only.
Aggregation is directed, like any "whole/part" relationship. The object Heater is part of the object TemperatureController, and not the other way round. The physical containment of one within the other cannot be "cyclic", whereas pointers can be (each of the two objects may contain a pointer to the other).
Of course, as has already been said, aggregation does not require physical containment, either by value or by reference. For example, a shareholder owns shares, but they are not a physical part of him. Moreover, the lifetimes of these objects may be entirely different, although conceptually the whole/part relationship is preserved and each share belongs to the property of its shareholder. Therefore aggregation may be very indirect. For example, an object of the class Shareholder may contain the key of the record about this shareholder in a database of shares. This too is aggregation without physical containment. The "litmus test" for detecting aggregation is this: if (and only if) there is a "whole/part" relationship between objects, then their classes must stand in an aggregation relationship to one another.
Fig. 3-9. The using relationship.
Aggregation is often confused with multiple inheritance. Indeed, in C++ hidden (protected or private) inheritance can almost always be replaced by hidden aggregation of an instance of the superclass. In deciding what you are dealing with - inheritance or aggregation - be careful. If you are not sure that there is a general/particular (is a) relationship, it is better to use aggregation or something else instead of inheritance.
Using
Example. In a recent example the objects rampController and growingRamp illustrated a link between objects which we represented as a using relationship between their classes TemperatureController and TemperatureRamp.
class TemperatureController {
public:
TemperatureController(Location);
~TemperatureController();
void process(const TemperatureRamp&);
Minute schedule(const TemperatureRamp&) const;
private:
Heater h;
};
The class TemperatureRamp is mentioned as part of the signature of the member function process; this gives us grounds to say that the class TemperatureController uses the services of the class TemperatureRamp.
Clients and servers. The using relationship between classes corresponds to a peer-to-peer link between their instances. This is what an association turns into if it emerges that one of its parties (the client) uses the services of the other (the server). An example of client-server relationships is shown in Fig. 3-9.
In fact, one class may use another in different ways. In our example this happens in the signature of an interface function. One can imagine that TemperatureController within the implementation of the function schedule uses, for example, an instance of the class Predictor. The whole/part relationship has nothing to do with it here, since this object is not part of the object TemperatureController, but is only used. In the typical case such a using relationship manifests itself if in the implementation of some operation a local object of the used class is declared.
A strict using relationship is sometimes somewhat restrictive, since the client has access only to the public part of the server's interface. Sometimes for tactical reasons we have to break encapsulation, and this is precisely what "friend" relationships between classes in C++ serve for.
Instantiation
Examples. Our first attempt to construct the class Queue was not particularly successful, since we did not manage to make it type-safe. We can improve our abstraction considerably if we resort to the construct of parameterized classes, which is supported by the languages C++ and Eiffel.
Template
class Queue {
public:
Queue();
Queue(const Queue&);
virtual ~Queue();
virtual Queue& operator=(const Queue&);
virtual int operator==(const Queue&) const;
int operator!=(const Queue&) const;
virtual void clear();
virtual void append(const Item&);
virtual void pop();
virtual void remove(int at);
virtual int length() const;
virtual int isEmpty() const;
virtual const Item& front() const;
virtual int location(const void*);
protected:
...
};
In this new variant the void* idiom is not used; instead, objects are placed into the queue and taken out of it through the class item, declared as a template argument.
A parameterized class cannot have instances until it has been instantiated. Let us declare two concrete queues - a queue of integers and a queue of screen objects:
Queue intQueue; Queue itemQueue;
The objects intQueue and itemQueue are instances of entirely different classes, which do not even have a common superclass. Nevertheless, they are derived from the same parameterized class Queue. For reasons that we shall explain later in chapter 9, in the second case we placed pointers into the queue. Thanks to this, any objects of subclasses of DisplayItem placed into the queue will not be "sliced", but will retain their polymorphic behavior.
Fig. 3-10. Instantiation.
This instantiation is type-safe. By the rules of C++, any attempt to place into the queue or extract from it anything other than, respectively, integers and varieties of DisplayItem.
The relationships between the parameterized class Queue, its instantiation for the class DisplayItem and the instance itemQueue are shown in Fig. 3-10.
Generic classes. There are four basic ways of creating classes such as the parameterized class Queue. First, we can use macro definitions. This is exactly how it was in early C++, but, as Stroustrup writes, "this approach was suitable only for small projects", since macros are clumsy and lie outside the semantics of the language; moreover, with each instantiation a new copy of the program code is created. Second, we can rely on late binding and inheritance, as is done in Smalltalk. With this approach we can build only heterogeneous container classes, since the language has no means of specifying the required class of the container's elements; each element in the container is treated as an instance of some remote base class. The third way is implemented in the languages of the Object Pascal family, which have both strong types and inheritance, but do not support any variety of parameterized classes. In this case one has to create generic containers, as in Smalltalk, but to use an explicit check of an object's type before placing it into the container. Finally, there are parameterized classes proper, which first appeared in CLU. A parameterized class is something like a template for building other classes; the template may be parameterized by other classes, objects or operations. A parameterized class must be instantiated before instances can be created. The mechanism of generic classes exists in C++ and Eiffel.
As can be seen from Fig. 3-10, in order to instantiate the parameterized class Queue we must use another class, for example, DisplayItem. Because of this, the instantiation relationship almost always implies a using relationship.
Meyer points out that inheritance is a more powerful mechanism than generic classes, and that through inheritance one can obtain most of the advantages of generic classes, but not the other way round. It seems to us that it is better when languages support both.
Parameterized classes are useful for far more than just creating containers. For example, Stroustrup notes their significance for generic arithmetic.
In design, generic classes make it possible to express certain properties of class protocols. A class exports the operations that can be performed on its instances. Conversely, the parameterizing argument of a class serves to import classes and values that provide a certain protocol. C++ checks their mutual correspondence at compile time, when instantiation actually takes place. For example, we could define an ordered queue of objects sorted by some criterion. This parameterized class must have an argument (the class Item), and must require of this argument a certain behavior (the presence of an ordering operation). At instantiation, any class that has the appropriate protocol will do as the class Item. Thus the behavior of classes in a family descended from a single parameterized class may vary within very wide limits.
As has been said, every object is an instance of some class. What happens if we try to treat classes themselves as objects? To do this we need to answer the question, what is the class of a class? The answer is a metaclass. In other words, a metaclass is a class whose instances are classes. Metaclasses crown the object model in purely object-oriented languages. Accordingly, they exist in Smalltalk and CLOS, but not in C++.
Here is how Robson motivates the need for metaclasses: "classes provide the programmer with an interface for defining objects. If so, it is desirable that classes themselves also be objects, so that they can be manipulated like all other descriptions".
In languages of the Smalltalk type the primary purpose of a metaclass is to support class variables (which are common to all instances of that class), operations for initializing class variables and for creating the single instance of the metaclass. By convention, a Smalltalk metaclass usually contains examples of the use of its classes. For example, as shown in Fig. 3-11, we could define a class variable nextId for the metaclass TelemetryData in order to produce identifying tags when each instance of TelemetryData is created. Similarly, we could define an operator for generating new instances of the class that would manufacture them, say, in some preallocated memory pool.
Although C++ has no metaclasses, the semantics of its constructors and destructors serves purposes analogous to those that brought metaclasses into being. C++ has facilities for supporting both class variables and metaclass operations. Specifically, in C++ one can declare data members or functions of a class as static (static), which will mean that this element is common to all instances of the class. Static class members in C++ are equivalent to class variables in Smalltalk. A static member function of a class plays the role of metaclass operations in Smalltalk.
As we have already noted, in CLOS the metaclass machinery is even more powerful than in Smalltalk. Through it one can change the very semantics of the elements: class precedence, generic functions and methods. The main advantage is the ability to experiment with other object-oriented paradigms and to create such tools for the developer as class and object browsers.
Fig. 3-11. Metaclasses.
CLOS has a predefined class named standard-class, which is the metaclass for all untyped classes defined by means of defclass. This metaclass has a method make-instance, which creates instances. In addition, all the machinery for working with the class precedence list is defined in it. All of this can be changed.
Methods and generic functions in CLOS can also be regarded as objects. Since they differ somewhat from ordinary objects, the objects corresponding to classes, methods and generic functions are collectively called metaobjects. Every method is an instance of the predefined class standard-method, and every function is an instance of the predefined class standard-generic-function. Since the behavior of these predefined classes can be changed, it is possible to influence the treatment of methods and generic functions.
In computer science a metaobject is an object that manipulates, creates, describes or implements other objects (including itself). The object to which a metaobject refers is called the base object. The information a metaobject can define includes the base object's type, interface, class, methods, attributes, parse tree, and so on. Metaobjects are an example of the concept of reflection in computer science, where a system has access (usually at run time) to its own internal structure. Reflection allows a system, in effect, to rewrite itself on the fly, to change its own implementation as it runs.
The first metaobject protocol was developed in the object-oriented programming language Smalltalk, created at Xerox PARC. The Common Lisp Object System (CLOS) appeared later and was influenced by the Smalltalk protocol, as well as by Brian C. Smith's original research on 3-Lisp as an infinite tower of evaluators. The CLOS model, unlike the Smalltalk model, allows a class to have more than one superclass; this creates additional complexity in such matters as resolving the ancestry of a class hierarchy on a particular object instance. CLOS also permits dynamic multimethod dispatch, which is handled by means of generic functions rather than message passing, as in Smalltalk's single-method dispatch. The most influential book describing the semantics and implementation of the metaobject protocol in Common Lisp is "The Art of the Metaobject Protocol" by Gregor Kiczales et al.
Metaobject protocols are also widely used in software development applications. In practically all commercial CASE environments, reengineering environments and integrated development environments there exists some form of metaobject protocol for representing and manipulating design artifacts.
Comments