Lecture 31: Polymorphism

Polymorphism

Pascal and most other languages of the 70's are based on the idea that functions and procedures, and hence, operands have a unique type. Pascal is monomorphic.

Polymorphic functions are functions whose operands can have more than one type. For example:

• Mathematical operators in most programming languages: +, *, -, etc.
• List length

For example, we can define listlen, a function that finds the length of a list in Haskell as follows:

module ListOps (listlen) where
{
    listlen [] = 0;
    listlen (x:xs) = 1 + listlen xs
}

This function should work no matter what type of element is stored in the list!

Ad hoc Polymorphism

Ad hoc polymorphism occurs when an operator works, or appears to work, on several different types (which may not exhibit a common structure) and may behave in unrelated ways on each type. There is no conceptual restriction on ad hoc polymorphism.

• Overloading occurs when the same name is used to refer to more than one function. The proper function is determined through context. Overloading is syntactic.
• Coercion occurs when an operand is converted automatically to an object of the right type either at compile-time or run-time. The proper conversion is determined by context. Coercion is semantic.

For an example of ad hoc polymorphism, consider the following operations:

3	+	4
3.0	+	4
3	+	4.0
3.0	+	4.0

The apparent polymorphism can be explained as:

• The operator + has 4 overloaded meanings, one for each of the four ways it is used.
• The operator + has two overloaded meanings, corresponding to integer and real addition. When the arguments are of different types, the integer argument is coerced to type real.
• The operator + is defined only for reals. Integers are always coerced to type real before the operator is applied.

Most languages that are monomorphic have some features that are polymorphic:

1. Overloading
2. Coercion
3. Subtyping (range restriction in Pascal or similar languages)
4. Value sharing (the null pointer in C++ -- think about how many meanings zero has in C++!)

Universal Polymorphism

Universally polymorphic functions generally work on an infinite number of types (all having a common structure).

Parametric polymorphism:

• Most common in functional programming languages.
• Uniformity is achieved by use of type parameters or variables.
• Executes the same code for arguments of any admissible type.

Consider again the definition of listlen from above. What type does Haskell infer for it?

:type listlen
listlen :: Num a => [b] -> a

Thus len takes a list with elements of type b and returns a number. We call b a type variable since any valid type can be used.

Parametric polymorphism also appears in C++ templates, where you write the code once but instantiate different versions of it based on type parameters.

Inclusion polymorphism

• Occurs in languages that allow subtypes and inheritance.
• An instance of a subtype can be manipulated by the same functions that operate on instances of the supertype.
• A reference (or pointer) of the parent class type can also refer to any child object, meaning that the type of the object being referred to must be determined at runtime.
• This means that a method call may be executed either in the parent or the child class and this decision cannot be made until runtime.

An example of inclusion polymorphism is given by sets, bags, and tuples:

• A set has no repeated members and no order.
• A bag allows repetition, but has no order.
• A tuple (array) has repetition and order.

Since bag and tuple are children of set, they can all be referred to as a type of set. Inclusion polymorphism is the kind you find most often in object-oriented languages. For example, in Java all classes inherit from the java.lang.Object class. Thus, any code you write to work on the "Object" class works on any class without having to handle special cases. Also, any of the objects that you create in Java can be accessed through a reference of type "Object."

Type Classification

This diagram shows one way type systems can be classified.-->

A postscript copy of the diagram is also available.

Last updated at 9:54 am on Friday, August 27, 2004.