ACCU Home page ACCU Conference Page
Search Contact us ACCU at Flickr ACCU at GitHib ACCU at Google+ ACCU at Facebook ACCU at Linked-in ACCU at Twitter Skip Navigation

pinPolymorphism In Object-Oriented Languages

Overload Journal #32 - Jun 1999 + Design of applications and programs   Author: Ulrich W. Eisenecker

Introduction

Polymorphism is a complex feature especially, but not only, of object-oriented programming. It interacts with other language features. Thus, it is useful to take a look at the other concepts of object-oriented programming:

  • encapsulation,

  • class,

  • attribute,

  • method,

  • exemplar,

  • message,

  • inheritance, and

  • object identity.

Encapsulation means that data and appropriate functions form a whole. It is usually combined with information hiding. The data of an object are completely hidden. They can be accessed only by using the functions defined for the object. Both principles were introduced by the concept of Abstract Data Type (ADT, fig. 1).

From data and functions to an Abstract Data Type

Figure 1. From data and functions to an Abstract Data Type

The class serves as a blue-print for objects. It defines the attributes and functions of an object. The data of an object are called attributes and its functions are called methods. The object created from a blue-print is called exemplar or instance (fig. 2). All exemplars of a class share all their methods, but each instance has its own set of data[1].

A class and its exemplars

Figure 2. A class and its exemplars

An exemplar is activated by sending a message. If the exemplar does understand the message, the appropriate method is executed (fig. 3). There are a number of synonyms for message in other object-oriented programming and modeling languages.

Messages and methods

Figure 3. Messages and methods

With inheritance it is not necessary to define a new class entirely from scratch. Instead it can be derived from an existing class (fig. 4). A general rule of object-oriented programming is that derived classes can define new attributes and new methods. It is not possible to get rid of inherited attributes and methods. But the implementation of an inherited method can be replaced by a new implementation. This is called overriding. Inheritance can be applied for reuse. In statically typed programming languages, a class defines also a type. In these languages, a derived class is a subtype of the supertype which is defined by the base class. Subtypes are normally compatible to their supertypes. Inheritance is often overemphasized in literature. But polymorphism is of greater importance since it helps to reduce dependencies. On the contrary, inheritance sometimes introduces even harmful dependencies between classes.

Inheritance

Figure 4. Inheritance

Object identity means that each exemplar is unique and thus can be distinguished from others. There are many ways to realize object identity.

Due to the limited space, this introduction can not go into more detail. For a deeper insight and a profound criticism of object-oriented concepts the reader is referred to [Eis96]. The following sections exclusively focus on polymorphism.

Schema of Cardelli and Wegner

In object-oriented programming, polymorphism (from Greek: "occurring in many forms") means that different exemplars respond to the same message by executing the appropriate method.

Cardelli and Wegner [CW85] examine polymorphism from the perspective of language design (fig. 5). They distinguish universal and ad-hoc polymorphism as high-level categories. In universal polymorphism, the same code applies to different types. In ad-hoc polymorphism, different code may be executed for different types. Parametric polymorphism requires type parameters, e.g. templates in C++ or generics in Ada. Parametric polymorphism is the heart of generic programming. Inclusion polymorphism relies on inheritance and subtyping. Both forms of polymorphism will be discussed in detail below.

Overloading means that functions of the same name may be implemented differently for different types. E.g. the operator "+" has different implementations for adding integral numbers and for adding floating point numbers. Coercion is the automatic application of built-in or user-defined type conversions. E.g. when adding an integral and a floating point number the integral number is promoted automatically to a floating point number by the compiler. Overloading and coercion may conflict if an appropriate conversion and an overloaded function are available at the same time.

Schema of Cardelli and Wegner [CW85]

Figure 5. Schema of Cardelli and Wegner [CW85]

Polymorphism in C++

C++ offers all forms of polymorphism described by Cardelli and Wegner. C++ allows overloading of functions or methods and user-defined type conversions. Both parametric and inclusion polymorphism are relevant for object-oriented programming. Templates are used for parametric programming in C++ (listing 1). The template function test<>() defines the common code to be used with the template parameter T[2]. T can be substituted by any of class A or B. The substituting classes do not need to be related by inheritance. Hence inheritance is not relevant here. From the perspective of test<>() it is only important that the function hello() is defined for the actual parameter of T. This is verified during compile or link time. Calling hello<>() is bound statically. Hence an error will be reported before run time.

Listing 1: Parametric polymorphism in C++

class A
{ public:
   void hello() const 
   { cout << "Exemplar of A" << endl; 
   }
}; 
class B 
{ public:
   void hello() const 
   { cout << "Exemplar of B" << endl; 
   } 
};
template <class T>
void test(const T& v) 
{ v.hello(); 
};
// ... 
A a; 
B b;
test(a);
test(b);

Inclusion polymorphism has three requirements in C++ (listing 2):

  • Inheritance,

  • virtual functions, and

  • and call by reference or call by pointer.

Class A defines a virtual function hello(). Class B is derived from A and overwrites the inherited implementation of hello(). An exemplar of A or a derived class is passed to the function test() by reference[3]. Depending on the class of the actual exemplar during run time, the appropriate implementation of hello() is selected and executed. This technique is called late or dynamic binding. Even in this case the compiler can detect errors. Only if B is a subtype of A, i.e. it is derived publicly, an implementation of hello() is available. The compiler would report a type error if B was not a direct or indirect descendant of A. Obviously inclusion polymorphism interacts closely with the type system and inheritance. A further discussion of parametric and inclusion polymorphism can be found in [Eis95].

Listing 2: Inclusion polymorphism in C++

class A
{ public:
   virtual void hello() const 
   { cout << "Exemplar of A" << endl; 
   } 
};
class B: public A 
{ public: 
   void hello() const
   { cout << "Exemplar of B" << endl; 
   } 
};
void test(const A& v) 
{ v.hello(); 
};
// ...

A a; 
B b; 
test(a); 
test(b); 

Variations of the preceding example will be used to demonstrate overloading and coercion. Overloading requires different implementations of test() for A and B (listing 3). As with parametric polymorphism inheritance is not relevant here. It is important to note that even hello() must not be present in both classes. Having hello() in A and hi() in B we could implement test(const A& a) as a.hello() and test(const B& b) as b.hi(). Depending on the actual type of the parameter the compiler selects the appropriate implementation of test(). If no test()-function matches (and coercion does not apply), an error will be reported at compile time.

Listing 3: Overloading in C++

class A
{ public:
   void hello() const 
   { cout << "Exemplar of A" << endl; 
   }
}; 

class B 
{ public:
   void hello() const 
   { cout << "Exemplar of B" << endl; 
   } 
};

void test(const A& v) 
{ v.hello(); 
};

void test(const B& v) 
{ v.hello(); 
};

// ...
A a; 
B b;
test(a);
test(b);

In coercion polymorphism we have only one implementation of test(), e.g. using A as the type of its parameter. Now there are two mutual exclusive ways to implement coercion. We have to provide either a type conversion constructor in A which takes a B as argument and creates an A (listing 4) or a type conversion operator in B which returns an A if needed (listing 5). If both forms of conversion are present the compiler can not resolve this conflict and reports an error.

Listing 4: Coercion in C++ using a type conversion constructor

class B 
{ public:
   void hello() const 
   { cout << "Exemplar of B" << endl; 
   } 
};

class A
{ public:
   A(const B&) {} // type conversion constructor
   A() {}         // standard constructor
   void hello() const 
   { cout << "Exemplar of A" << endl; 
   }
}; 

void test(const A& v) 
{ v.hello(); 
};

// ...
A a; 
B b;
test(a);
test(b); // b "changes" to an A here

Listing 5: Coercion in C++ using a type conversion operator

class A
{ public:
   void hello() const 
   { cout << "Exemplar of A" << endl; 
   }
}; 

class B 
{ public:
   void hello() const 
   { cout << "Exemplar of B" << endl; 
   } 
   operator A() const
   { return A(); // return an A
   }
};

void test(const A& v) 
{ v.hello(); 
};

// ...

A a; 
B b;
test(a);
test(b); // b "changes" to an A here

Polymorphism in Java

Java offers only inclusion polymorphism which works exactly as in C++. In Java all classes are either direct or indirect descendants of the common base class Object. Hence all exemplars understand the messages defined for Object. Listing 6 shows some obvious differences between C++ and Java. In Java every method is virtual by default. Objects are always passed by reference and there are no free functions. There are several proposals for introducing parametric polymorphism into Java [EC98].

Listing 6: Inclusion polymorphism in Java

class A { 
  public void hello() { 
    System.out.println("Exemplar of A"); 
  } 
}
class B extends A { 
  public void hello() { 
    System.out.println("Exemplar of B"); 
  } 
}
class Test { 
  public static void execute(A a) { 
    a.hello(); 
  } 
}
public class TestApp { 
  public static void main(String[] args) { 
    A a = new A(); 
    B b = new B(); 
    Test.execute(a); 
    Test.execute(b); 
  } 
}

Polymorphism in Smalltalk

The situation is different in Smalltalk (listing 6). If a Smalltalk-object receives a message it checks whether it understands the message. If it does, the appropriate method is executed otherwise an exception is raised. In Smalltalk, a message consists of one or more keywords. The complete message forms the selector which corresponds to a signature. Methods with the same signature can be implemented in independent classes, e.g. A>>hello and B>>hello. Even if class Object is a common ancestor of every class in Smalltalk, A and B have no common base class which implements hello. During run time, a variable may hold exemplars of any of these classes and it will behave correctly when receiving the message hello. This form of polymorphism does not depend on a type system or inheritance. It is verified during run time whether a message is known to the receiving object. Hence the compiler can not detect if inappropriate messages are sent to objects. This special form of polymorphism is called signature-based polymorphism as opposed to inclusion polymorphism which is also referred to as inheritance-bound polymorphism [Eis93]. In Smalltalk, every method is in some sense "generic" as C++ templates except that it works at run time too.

Listing 6: Polymorphism in Smalltalk

A>>hello "A inherits from Object - Object does not implement 'hello'" 
    Transcript show: 'Exemplar of A'; cr
B>>hello "A inherits from Object - Object does not implement 'hello'" 
    Transcript show: 'Exemplar of B'; cr
"Execute the following code:"
| v | 
v := A new. 
v hello. 
v := B new. 
v hello 

Summary and Criticism

Polymorphism is an essential feature of object-oriented programming. It comes in several variants and interacts with other language features. The schema of Cardelli and Wegner is well-suited for classifying the various forms of polymorphism in typed languages. But the polymorphism of Smalltalk does not fit into this taxonomy because in some way it combines parametric and inclusion polymorphism by excluding static type checking. This has the consequence that object-oriented design models can be simplified when they are implemented in Smalltalk. The reason is that abstract base classes or interface classes can be omitted entirely. Thus, coupling and complexity of the model are reduced since dependencies of classes due to inheritance relations are eliminated.

It is worth to note that nearly all object-oriented analysis and design methods are implicitly based on inclusion polymorphism or the complete Cardelli/Wegner schema. E.g. the UML offers abstract and parameterized classes. Thus UML-based design models can be easily implemented in C++. For Java it must be decided how to implement the parameterized classes of the UML-model. Using Smalltalk the model can be simplified since abstract and parameterized classes are not required.

References

[CW85] Luca Cardelli and Peter Wegner: On Understanding Types, Data Abstraction and Polymorphism. Computing Surveys, vol. 17, no. 4, December 1985, pp. 471-522

[EC98] Ulrich W. Eisenecker and Krzysztof Czarnecki: Generische Programmierung in Java. JavaSpektrum 6/1998, pp. 34-46

[Eis93] Ulrich W. Eisenecker: Objektorientierung und Wiederverwendbarkeit. In: unix/mail 6/93, pp. 420-429

[Eis95] Ulrich W. Eisenecker: Typisierung und Polymorphie in C++. OBJEKTspektrum 5/1995, pp. 81-83, http://home.t-online.de/home/Ulrich.Eisenecker/cppcol02.htm

[Eis96] Ulrich W. Eisenecker: Grundlagen der Objektorientierung kritisch betrachtet. Talk, GI-Regionalgruppe, Heidelberg 1996, http://www.fh-heidelberg.de/public/eiseneck/ookritik.zip

[GHJV96] Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides: Design Patterns. Addison-Wesley 1995

[MKE92] Antonin Mrázik, Janka Kleinertová, and Ulrich W. Eisenecker: Welten à la OOP. Die Theorie der P-Systeme. In: c't 3/1992, pp. 202-209.



[1] In addition to class/instance-based programming languages, there are also prototype-based languages [MKE92]. They are not discussed here.

[2] More precisely, the code of the template is normally duplicated by the compiler during instantiation. This may lead to the so called code bloat problem.

[3] Instead of passing the object by reference, a pointer to the object can be passed. In both cases the object is not copied. If the object was passed by value, it would be copied. If the types of the passed object and of the value copy are different, the compiler performs a type conversion (provided a subtype relationship exists and a type conversion operator or a type conversion constructor is available). Hence, the polymorphic type of an object gets lost if it is passed by value.

Overload Journal #32 - Jun 1999 + Design of applications and programs