Introduction to Programming Languages/Universal Polymorphism

Universal Polymorphism

Symbols that are universally polymorphic may assume an infinite number of different types. There are two kinds of universal polymorphism: parametric and subtyping. In the rest of this chapter we will see these variations in more detail.

Parametric Polymorphism

Parametric polymorphism is a feature of routines, names or symbols that can be parameterized in one or more types. This kind of polymorphism lets us to define codes that are generic: they can be instantiated to handle different types. The code below shows the use of a template, the way to implement parametric polymorphism in C++.

#include <iostream>

template <class T>
T GetMax (T a, T b) {
  T result;
  result = (a > b) ? a : b;
  return (result);
}

int main() {
  int i = 5, j = 6, k;
  long l = 10, m = 5, n;
  k = GetMax<int>(i, j);       // type parameter: int
  n = GetMax<long>(l, m);      // type parameter: long
  std::cout << k << std::endl;
  std::cout << n << std::endl;
  return 0;
}

The program above defines a polymorphic function called GetMax (lines 3 to 8). The type variable T, defined in the scope of GetMax, will be replaced by an actual type during the function call. The main function shows two calls to GetMax. The call at line 13 uses the type int whereas at line 14 it uses the type long. The arguments of GetMax are compared using the ">" operator. Therefore, to use this function, it is necessary that the actual type that replaces T implements this kind of comparison. Fortunately, C++ allows us to define this operator to our own types. As an example, the user defined class MyInt, shown below, is a valid type to GetMax, as it implements the greater-than operator:

#include <iostream>
 
class MyInt {
  friend std::ostream & operator<<(std::ostream& os, const MyInt& m) {
    os << m.data;
  }
  friend bool operator >(MyInt& mi1, MyInt& mi2) {
    return mi1.data > mi2.data;
  }
  public:
    MyInt(int i) : data(i) {}
  private:
    const int data;
};

template <class T>
T GetMax (T a, T b) {
  return (a > b) ? a : b;
}

int main () {
  MyInt m1(50), m2(56);
  MyInt mi = GetMax<MyInt>(m1, m2);
  std::cout << mi << std::endl;
  return 0;
}

Parametric polymorphism is present in many different statically typed languages. As an example, the function below, implemented in Java, manipulates a list of generic types. Notice that, even though C++ and Java share similar syntax, parametric polymorphism in these languages is implemented in different ways. In C++ templates, each instance of a parametric function is implemented separately. In other words, the C++ compiler generates a whole new function for each specialization of a polymorphic function. Java's generics only create one implementation for each parameterized function.

public static <E> void printList(List<E> l) {
  for (E e : l) {
    System.out.println(e);
  } 
}

SML implements parametric polymorphism in a way that is similar to Java. Only one instance of each parametric function exists in the entire program. These functions manipulate references to values, instead of the values themselves. The function below, for instance, computes the length of a generic list in SML. Notice that our implementation does not need to known anything about the values stored in the list. It only manipulates the structure of this list, considering any type stored there as a generic reference.

- fun length nil = 0 
=   | length (_::t) = 1 + length t;
val length = fn : 'a list -> int

- length [1, 2, 3];
val it = 3 : int

- length [true, false, true];
val it = 3 : int

- length ["a", "bc", "def"];
val it = 3 : int

Type constructors are similar to functions, but, instead of receiving values as parameters, they receive types, and instead of returning back values, they return types

Parametric polymorphism gives us the idea of a type constructor. A type constructor is a kind of function that receives types, and produces new types. For instance, in the Java program above, we saw the type constructor List<E>. We cannot instantiate a Java object with this type. Instead, we need to use a specialization of it, such as List<Integer>, for instance. So, instantiating List<E> with the type Integer, for instance, is analogous to passing this type to a single-parameter function List<E> that returns back List<Integer>.

Parametric polymorphism is an important mechanism of code reuse. However, not every programming language provides this feature. Parametric polymorphism is absent, for instance, from widely used languages, such as C, Fortran or Pascal. Nevertheless, it is still possible to simulate it using several different strategies. For example, we can simulate parametric polymorphism in C using macros. The program below illustrates this technique. The macro SWAP has a type parameter, similarly to a type constructor. We have instantiated this macro twice, first with int, and then with char*.

#include <stdio.h>
#define SWAP(T, X, Y) {T __aux = X; X = Y; Y = __aux;}
int main() {
  int i0 = 0, i1 = 1;
  char *c0 = "Hello, ", *c1 = "World!";
  SWAP(int, i0, i1);
  SWAP(char*, c0, c1);
  printf("%d, %d\n", i0, i1);
  printf("%s, %s\n", c0, c1);
}

Subtyping Polymorphism

A well-known property present in object oriented languages is the Liskov's Substitution Principle. This principle says that in any situation in which the left-hand-side of an assignment expects a type T, it can also receive a type S, as long as S is subtype of T. Programming languages that follow the Liskov's Substitution Principle are said to provide subtyping polymorphism. The program below, written in Java, illustrates this kind of polymorphism. The three classes, String, Integer and LinkedList are subclasses of Object. Therefore, the function print can receive, as actual parameters, objects that are instances of any of these three classes.

import java.util.LinkedList;
public class Sub {
  public static void print(Object o) {
    System.out.println(o);
  }
  public static void main(String[] a) {
    print(new String("dcc024"));
    print(new Integer(42));
    print(new LinkedList<Integer>());
  }
}

Subtyping polymorphism works because if S is subtype of T, then S meets the contract expected by T. In other words, any property of the type T is also present in its subtype S. In the example above, the function print expects types that "know" how to convert themselves into strings. In Java, any type that has the property toString() has this knowledge. Given that this property is present in the class Object, it is also present in all the other classes that, according to the language's semantics, are subtypes of Object.

A simple hierarchy of classes in Java. In Java, if S is a subclass of class T, then S is a subtype of T.

There are two basic mechanisms that programming languages use to define the subtype relation. The most common is nominal subtyping. Languages such as Java, C#, C++ and Object Pascal are all based on nominal subtyping. According to this system, the developer must explicitly state, in the declaration of S, that S is subtype of T. As an example, the code below illustrates a chain of subtypes in the Java programming language. In Java, the keyword extends is used to determine that a class is subtype of another class.

  class Animal {
    public void eat() {
      System.out.println(this + " is eating");
    }
    public String toString () {
      return "Animal";
    }
  }
  class Mammal extends Animal {
    public void suckMilk() {
      System.out.println(this + " is sucking");
    }
    public void eat() {
      suckMilk();
    }
  }
  class Dog extends Mammal {
    public void bark() {
      System.out.println(this + " is barking");
    }
    public String toString () {
      return "Dog";
    }
  }

The other mechanism used to create subtyping relations is structural subtyping. This strategy is less common than nominal subtyping. One of the most well-known programming languages that foster structural subtyping is ocaml. The code below, written in this language, defines two objects, x and y. Notice that, even though these objects have not being explicitly declared with the same type, they contain the same interface, i.e., they both implement the methods get_x and set_x. Thus, any code that expects one of these objects can receive the other.

let x =
   object
     val mutable x = 5
     method get_x = x
     method set_x y = x <- y
   end;;

let y =
   object
     method get_x = 2
     method set_x y = Printf.printf "%d\n" y
   end;;

For instance, a function let set_to_10 a = a#set_x 10;; can receive either x or y, e.g., set_to_10 x and set_to_10 y are valid calls. In fact, any object that provides the property set_x can be passed to set_to_10, even if the object has not the same interface as x or y. We illustrate this last statement with the code below: In other words, if an object O provides all the properties of another object P, then we say that O is subtype of P. Notice that the programmer does not need to explicitly state this subtyping relation.

let z =
   object
     method blahblah = 2.5
     method set_x y = Printf.printf "%d\n" y
   end;;

set_to_10 z;;

In general, if S is a subtype of T, then S contains more properties than T. For instance, in our class hierarchy, in Java, instances of Mammal have all the properties of Animal, and, in addition to these properties, instances of Mammal also have the property suckMilk, which does not exist in Animal. The figure below illustrates this fact. The figure shows that the set of properties of a type is a subset of the set of properties of the subtype.

Nevertheless, there exist more instances of the supertype than instances of the subtype. If S is a subtype of T, then every instance of S is also an instance of T, whereas the contrary is not valid. The figure below illustrates this observation.

← Ad Hoc Polymorphism