Module E - Polymorphism

Polymorphism

Types | History | Ad-Hoc | Universal | In-Class Practice | Exercises



Polymorphism means many forms.  Polymorphism describes the flexibility that allows association of variables, objects and functions with different data types.  A polymorphic object may be associated with a variety of data types.  A polymorphic function may accept arguments of different data type.  Conversely, monomorphism means one form.  A monomorphic object may be associated with one and only one data type.  A monomorphic function may accept arguments only of the prescribed data type. 

Both C and C++ exhibit polymorphism in differing degrees. 


Types

Central to the implementation of polymorphism is the concept of type.  A type describes how to interpret the bits stored in memory.  Primitive data types describe how variables are stored, while classes describe how objects are stored.  Most programming languages have some form of data typing. 

A type also defines the set of admissible operations on the bits stored in memory.  Each type admits a finite set of operations.  Any operation outside this set is unacceptable.  For example, the modulus of a double type with respect to an int constant is unacceptable because it is undefined for the double type. 

A type may be associated with a variable or object at compile time or at run time.  A type that is associated at compile time is called a static type.  A static type does not change throughout the lifetime of the variable or object.  A type that is associated at run time is called a dynamic type.  The dynamic type of a variable or object may change during execution of a program. 

In C++, the dynamic type of an object may vary with the execution path through a program.  Rather than declare the object as an instance of a class, we may declare a pointer to the object and leave the object's dynamic type for definition later.  The pointer will hold the address of the object once memory has been allocated.  Such objects are polymorphic. 

Type Checking

Typing limits the set of operations that are admissible on a variable or object.  Type checking is extremely helpful in discovering bugs.  A variable's or object's type may be checked either at compile time or at run time. 

Compilers check for static type consistency on monomorphic variables and objects.  A variable declared as a primitive data type is monomorphic.  An object declared as an instance of a class is also monomorphic.  This is the default response in C++. 

With polymorphic objects, the compiler may insert type checking code to be executed at run time.  This is called dynamic type checking. 


History

Strachey

The concept of polymorphism dates back four decades.  In 1967, Christopher Strachey distinguished

  • functions that work differently on different argument types from
  • functions that work uniformly on a range of argument types. 
He defined the former as "ad-hoc" and the latter as "parametric":

"Ad-Hoc polymorphism is obtained when a function works, or appears to work, on several different types (which may not exhibit a common structure) and may behave in unrelated ways for each type.  Parametric polymorphism is obtained when a function works uniformly on a range of types; these types normally exhibit some common structure."

Christopher Strachey, "Fundamental concepts in programming languages", Lecture Notes for International Summer School in Computer Programming, Copenhagen, August 1967.

Cardelli and Wegner

In 1985, Cardelli and Wegner refined Strachey's distinction into one between

  • functions that work on an finite set of different and potentially unrelated types and
  • functions that work on a potentially infinite number of types with all types involved sharing a common structure. 
Cardelli and Wegner distinguished the finite branch further into
  • overloading and
  • coercion
and the infinite branch further into
  • inclusion and
  • parametric
Note their introduction of inclusion polymorphism.

Luca Cardelli and Peter Wegner, "On Understanding Types, Data Abstraction, and Polymorphism", Computing Surveys, Volume 17, Number 4, pp. 471-522, December 1985.

We shall work with their classification. 


Ad-Hoc Polymorphism

Most programming languages exhibit some ad-hoc polymorphism.  For example, C automatically promotes argument types in function calls.  A programmer can call the same function with a variety of argument types.  The variety of arguments is limited. 

Overloading

Overloading redefines a function using the same name but a different signature.  C++ admits overloading.  C does not.  A distinct function definition exist for each signature.  Consider, for example, addition.  The language defines this operation between two variables of a primitive data type.  We define the operation between two objects of a class by overloading the addition operator for operands that are objects of that class.  When a programmer adds two objects that are instances of the class, the compiler will apply the definition that we have provided, rather than the definitions that hold for primitive data types. 

Compilers implement overloading at compile time.  Typically, they introduce a set of monomorphic functions, one for each definition that we have provided.  Compilers distinguish each definition by internally 'mangling' the function names. 

For example,


 /* Ad-Hoc Polymorphism - Overloading
 *  polymorphismOverloading.cpp
 *  Mar 21 2005
 *  BTP200
 */

 #include <iostream>
 using namespace std;

 // Two function definitions:

 void display() const {
     cout << "No arguments" << endl;
 }
 void display(int a) const {
     cout << "One arguemnt (" << a
          << ')' << endl;
 }

 int main( ) {

     display();
     display(10);

     return 0;
 }


  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
 No arguments
 One argument (10)
  
  
  

Coercion

Coercion converts one type into another as a result of the compiler's attempts to match a function definition to the argument types in a function call.  Language rules define the conversions amongst primitive types, while we specify through constructors and conversion operators the rules that define conversions for objects of our own classes. 

Compilers implement coercion at compile time.  If a compiler succeeds in matching a function call to a function definiton after some coercion(s), the compiler inserts the conversion code for the coercion(s) between the affected argument(s) and the function call proper. 

Coercion may be further subdivided into

  • narrowing and
  • widening (promotion)
conversions as well as
  • implicit and
  • explicit (casting)
conversions. 

For example,


 /* Ad-Hoc Polymorphism - Coercion
 *  polymorphismCoercion.cpp
 *  Mar 21 2005
 *  BTP200
 */

 #include <iostream>
 using namespace std;

 // One function definition:

 void display(int a) const {
     cout << "One arguemnt (" << a
          << ')' << endl;
 }

 int main( ) {

     display(10);
     display(12.6); // narrowing
     display('\n'); // widening

     return 0;
 }


  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
 One argument (10)
 One argument (12)
 One argument (10)
  
  
  

Analysis

Under ad-hoc polymorphism, we use the same syntax with objects of different type.  For example, the same function name accepts several unrelated types as arguments. 

Ad-hoc polymorphism is also called "apparent" polymorphism.  The programmer, who uses a class, sees a single function that can be called using different argument types.  The polymorphism is only apparent because the same function definition does NOT extend to each of the different types.  A separate definition exists for each argument type.  The set of definitions shares the same function name, but contain distinct and possibly totally unrelated logic.  The number of types that a programmer may use with the function name is limited by the number of definitions that the class declaration provides. 

There is not necessarily any common ground amongst the function definitions that share the same function name.  Uniformity is a coincidence rather than the rule under ad-hoc polymorphism. 


Universal Polymorphism

Universal polymorphism differs from ad-hoc polymorphism fundamentally.  Universal polymorphism applies a single function definition to a variety of types.  The algorithm is identical for all types.  One function definition exists regardless of object type.  Universal polymorphism imposes no restrictions on the number of acceptable types and extends over infinitely many types.  Typically, these types typically exhibit some common structure amongst themselves. 

Universal polymorphism is also called true polymorphism.  Cardelli and Wegner subdivided universal polymorphism into inclusion and parametric polymorphism.

Parametric

Parametric polymorphism is implemented at compile time.  Functions receive type parameters.  The type received determines the type that is used within the function itself. 

Parametric polymorphism is also called generic polymorphism. 

Inclusion

Inclusion polymorphism is implemented at run time.  An object may be identified with several different types that are themseves related by an inclusion relation.  Consider a class that is part of an inheritance hierarchy.  The classes in this hierarchy are related to one another through inclusion relations: a class lower in the hierarchy includes a class higher in the hierarchy.  An object of one class in the hierarchy may be identified with another class that is included in the hierarchy. 

Other names for inclusion polymorphism are overriding and sub-typing. 


In-Class Practice

Try the practice problem in the Handout on Polymorphism


Exercises




   Printer Friendly Version of this Page print this page     Top  Go Back to the Top of this Page
Previous Reading  Previous: Derived Classes With Depth Next: Inclusion Polymorphism   Next Reading


  Designed by Chris Szalwinski   Copying From This Site