13.5 Polymorphism

At the end of the previous section, we have seen that instances of many different classes were dealt with in the same way. We did not know the exact type of the instances stored in the store container; it was sufficient that they were instances of any class derived from the Particle class.

This feature of the OOP is called polymorphism. Polymorphism means that instances of various classes may be used in the same way - they accept the same messages, so their methods may be called without any regard to the exact type of the instance. In some programming languages (e.g., in Java), this is automatic behavior of the objects (or of their methods), in some programming languages (e.g. in C++) this behavior must be explicitly declared.

There are at least two ways to achieve polymorphic behavior: The use of the inheritance and the use of the interfaces. The interfaces will be discussed in Sect. 13.5.4.

13.5.1 Early and Late Binding

The previous example shows that there are two possible approaches to the resolution of the type of the instance for which the method is called, if the pointer (or reference) to the instance is used:

Late binding gives the class polymorphic behavior. On the other hand, late binding is less effective than early binding, even though the difference may be negligible. (In C++ on PCs, the difference between the late and the early binding is usually one machine instruction per method call.)

Any method that might be overridden in any of the derived classes should use the late binding.

In C++ and other OOP languages in which the late binding must be declared, the classes containing at least one virtual method are called polymorphic classes. Classes without any virtual method are called non-polymorphic classes. In languages like Java, where all the methods use late binding by default, all the classes are polymorphic.

13.5.2 Implementation of the Late Binding

In this subsection, some low level concepts will be discussed. They are not necessary for understanding the basic concepts of the OOP, but they can give better insight in it.

We will explore one the common way of implementation of the late binding, i.e., of the determination of the actual type of the instance for which the method is called.

This is based on the so called virtual method tables. The virtual method table (VMT) is the hidden class data member that is part of any polymorphic class. Any polymorphic class contains exactly one VMT. (The hidden class member is a class member the programmer does not declare - the compiler adds it automatically.)

The VMT is an array containing pointers to all the virtual methods of the class. Any derived class has its own VMT that contains pointers to all the virtual methods (even those that are not overridden in this class). The pointers to the virtual methods in the VMT of the derived class are in the same order as the pointers to corresponding methods in the base class.

Any instance of the polymorphic class contains another hidden data member - the pointer to the VMT. This data member is stored in all the instances at the same place - e.g. at the beginning.

Figure 13.4 illustrates this process for the Particle base class and two derived classes. The values stored in the VMT are set usually at the start of the program or when the class is loaded to the memory. The values of the pointer to the VMT in the instances are set automatically by the constructor.

**Figure 13.4:** Typical implementation of the late binding
$\includegraphics[width=11cm]{text/2-13/Vir04.eps}$

13.5.3 Abstract Class

In some cases, the base class represents such an abstract concept that some operations with instances of this class cannot be implemented. Nevertheless, at least the stub of the corresponding method should be present in the class, because this class is used as a base class and determines the common interface for all the derived classes.

In OOP such a class is called the abstract class and such an operation is called the abstract method. Abstract methods have no implementation (no method body).

It is not allowed to create instances of the abstract classes and it is not allowed to call the abstract methods. It is of course possible to define pointers or references to abstract classes.

The abstract classes serve as base classes. If the derived class does not implement any of the inherited abstract methods, it will be abstract like the base class. The abstract class

Note that the abstract classes are italicized in the UML class diagrams - see e.g. the Particle class in Fig. 13.5.

Example 10 Consider the Particle class defined above. How could the Interact() method be implemented?

For the derived classes, the situation is clear: If it is, e.g., the Photon, the interaction could be the photoelectric effect, the Compton scattering, or some other interaction known to particle physicists; probabilities of these phenomena are determined according to their total effective cross sections. For the other derived classes, there are other well defined possibilities that can be expressed in the program code.

However, there is no general interaction, that could be used to implement the Interact() method of the general Particle. On the other hand, this method must be declared in the Particle class as the part of the common interface of derived classes. If we omit it, the statement

store[i] -> Interact(det);

will not compile, because store[i] is the pointer to the Particle class that does not contain such a method.

So, the Interact() method should be declared as abstract (in C++, the abstract methods are called pure virtual methods). In the following revision of the Particle class, we omit all other parts of that class that are unchanged.

// Particle as an abstract class
class Particle
{
public:
   // Pure virtual method
   virtual void Interact(Detector *aDetector) = 0;
   // All other public members as before
protected:
   // All data members as before
};

13.5.4 Interfaces

The interface may be defined as a named set of methods and constants. This set may be empty.

The interface represents a way to achieve the polymorphic behavior; it is an alternative to inheritance. This concept is relatively new in OOP; it was first widely used in the Java language.

In languages that support interfaces, any class may declare that it implements the given interface. This means that the class will supply the implementations (bodies) of the methods in the interface.

Note the terminological difference: Even though interfaces are syntactically similar to the classes that contain only public abstract methods, they are not inherited, but they are implemented. In programming languages, that support interfaces, any class may implement many interfaces, even if the language does not support multiple inheritance.

The interface represents the type. If class C implements interfaces I1 and I2, any instance of this class is an instance of type C and also an instance of type I1 and of type I2.

The interface is usually represented by a small circle connected to the class icon in the UML class diagrams (see Fig. 13.5). It may also be represented by a class-like icon marked by the $\ll$ interface $\gg$ label (''stereotype''). Implementation of the interface is represented by a dashed arrow pointing to the implementing class (see Fig. 13.7).

13.5.5 Interfaces in C++

As we have chosen C++ as the language of examples, it is necessary to cover briefly the interfaces in this language. C++ does not support interfaces directly; nevertheless, interfaces may be fully simulated by abstract classes that contain only public abstract (pure virtual) methods, and the interface implementation may be substituted by the inheritance. This will be demonstrated by the following example.

Example 11 The Monte Carlo simulation may be time-consuming and it would be convenient to have the possibility to store the status of the simulation into a file, so that the computation might be interrupted and continued later.

It is clear that all the generated but not yet processed particles should be stored. The status of the particle source, and consequently the status of the random numbers generator, should be stored, too. This is necessary especially for debugging, because it ensures that we could get the same sequence of random number in repeated runs of the program, even if they are interrupted.

It follows that we have at least two different object types belonging to different class hierarchies that have a common feature - they will be stored in a file and later will be restored into their original state. It follows that all the classes involved should have suitable methods, e.g., store() and restore().

The simulated experiment is represented by the Experiment class in the program and to store the experiment status is the task of this class; so we would like to implement in this class the storeObject() method to store objects passed as arguments. It follows that all the parameters - all the objects stored - should be of the same type.

The solution of this dilemma - the method requires objects of the same type as parameters, but we have objects of at least two distinct types belonging to different class hierarchies - is to use a suitable interface that contains the store() and restore() methods. We will use the Storable identifier for this interface. The Source, Generator and Particle classes should be modified as follows:

// Interface simulation in C++
class Storable
{
public:
   virtual void store(ostream&) = 0;
   virtual void restore(istream&) = 0;
};

class Generator: public Storable
               // Interface implementation
{
public:
   virtual void store(ostream& out)
   {/* Store the generator */}
   virtual void restore(istream& in)
   {/* Read the generator and reconstruct it */}
   // ... Other methods and attributes as before
};
class Source: public Storable
               // Interface implementation
{
public:
   virtual void store(ostream& out)
   {/* Store the source */}
   virtual void restore(istream& in)
   {/* Read the source from the file
       and reconstruct it*/}
   // ... Other methods and attributes as before
};

class Particle: public Storable
   // Interface implementation
{
public:
   virtual void store(ostream& out)
   {/* Store the particle */}
   virtual void restore(istream& in)
   {/* Read the particle from the file
       and reconstruct it */}
   // ... Other methods and attributes as before
};

(ostream and istream are base classes for output and input data streams in the standard C++ library). Figure 13.5 shows the revised UML class diagram of these classes.

Note that the Particle class is abstract, so it need not override the methods of the Storable interface. The classes representing the concrete particle types, Electron etc., inherit the implementation of the Storable interface; thus it is not necessary to declare this fact. Of course, if a derived class is not abstract, it must override the methods of this interface.

Implementation of the Storable interface allows us to define the method Experiment::storeObject() as follows:

void Experiment::storeObject(Storable& obj,
                             ostream& out) {
    obj.store(out)
}

Storable interface serves as the common type of all the storable objects - particles as well as random number generators - in the program. This gives us the possibility to treat all these objects in our program in a uniform way.