Polymorphism

Polymorphism is often seen as a characteristic unique to Object Oriented Programming (OOP) or at least one that it thrives in. Many have only seen polymorphism through the lens of an object oriented language and have yet to see other approaches to defining common interfaces.

I'll be using Java and Standard ML (SML) to demonstrate the various types of polymorphism. Java is unique in its pervasiveness throughout professional developers and its usage as a language to teach OOP. SML is unique in that it is a successor to one of the first implementations of a form of polymorphism different from the one used in OOP languages. More on that later.

Subtyping Polymorphism is the form you're likely familiar with and were first introduced to. If we define a type \(T\) with a subtype \(S\), denoted as \(S <: T\), any operation that is well defined for \(T\) is also well defined for \(S\). For example, an interface to implementation class relationship in Java:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

interface Tree {
  boolean isDeciduous;
  void sayBarkColor();
}

class Birch implements Tree {
  boolean isDeciduous = true;
  void sayBarkColor() {
    System.out.println("White");
  }
}

class Pine implements Tree {
  boolean isDeciduous = false;
  void sayBarkColor() {
    System.out.println("Brown");
  }
}

We define a common interface that all subtypes of Tree types will implement. These new subtypes, Birch and Pine, will have their own implementation of isDeciduous and sayBarkColor. In doing this, we don't have to know exactly what tree we are working with, only that it is a subtype of Tree (as long as we remain within the common operations of the interface type).

SML has a similar notion to this in its module system.

We define a signature for a Tree similarly:

1
2
3
4

signature Tree = sig
  val isDeciduous : bool
  val sayBarkColor : unit -> unit
end

And make a Birch structure like:

1
2
3
4

structure Birch : Tree = struct
  val isDeciduous = true
  fun sayBarkColor () = print "Birch\n"
end

Ad Hoc polymorphism is also likely something you're familiar with. Operations that are defined for different types may overload the function and perform different operations based on the types. Take for example, addition overloaded for various types:

1
2
3
4
5
6

class Adding {
  static int add(int a, int b);
  static float add(float a, float b);
  static String add(String a, String b);
  // ...
}

As you can see, add can now be used with int, float, or String without needing to specify which add function to use.

As a programmer, we have to do more leg work to define the body of each implementation of this interface, but it's easier to map a function's semantics to a name mentally. Without ad hoc polymorphism, you may see function names like add_ints and add_floats.

Also, notice how the functions are not restricted beyond requiring a certain return type. The float addition function could return 0.0 in every case or worse, it could modify global state without us knowing.

Ad hoc polymorphism put simply, is having the same function name but many different function bodies.

Parametric polymorphism allows us to write a single function that applies to all types. In SML, the "all types" concept is displayed through a letter prepended with an apostrophe (commonly called "tick") such as 'a or 'b. Further, 'a must be the same type as all other 'a in the function, but could be either the same or different from 'b.

The function type is shown as an arrow in SML, so a function that accepts an int and outputs an int may be written as int -> int. Let's define a function that fulfills this type signature as an example.

1

fun plus_one (n: int) = n + 1

val plus_one = fn : int -> int

We can also let SML infer the type of parameters by leaving out type annotations.

1

fun plus_one n = n + 1

val plus_one = fn : int -> int

Now that we have this in mind, consider the case of appending two lists. The list type is all that matters, not the type of list's content. So intuitively we shouldn't have to define a new append for an int list and a bool list. Let's try to define append and see the type that SML gives us for our function.

1
2
3
4

fun append l1 l2 =
  case l1 of
    [] => l2
  | x::xs => x::(append xs l2)

val append = fn : 'a list -> 'a list -> 'a list

Written mathematically, the type of append is

\begin{equation*} ∀ a . a \texttt{ list} → a \texttt{ list} → a \texttt{ list} \end{equation*}

Telling us that we can apply this to any two lists, as long as the two lists have the same type. Great! That matches our expectations. Let's consider a version with multiple polymorphic types. Consider swapping a tuple (or pair) of elements. Again, we don't need to know the types of the elements inside the tuple. And in this example, it doesn't matter if the pair has two elements of the same type or different.

1

fun swap (a, b) = (b, a)

val swap = fn : 'a * 'b -> 'b * 'a

Or, mathematically:

\begin{equation*} ∀ a ∀ b . a × b → b × a \end{equation*}

Parametric polymorphism allows us to write generic functions that apply to many types and all share the same body - thereby saving us from implementing a case for each type. However, perhaps obviously, the functions that can be implemented for every type are not able to use any operation limited to a type. For example, we could not add, check equality, or use an xor op on a parameter without limiting our type. Some systems

Parametric polymorphism been implemented in Java through generics.

Let's put all this new knowledge to the test by making a polymorphic binary search tree. This will require all forms of polymorphism that we've seen to make work.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

// Using generics - parametric polymorphism
// And this <T extends Comparable<? super T>> is subtyping
public class BinarySearchTree<T extends Comparable<? super T>> {
  TreeNode<T> root;
  public BinarySearchTree() {}

  public boolean contains(T value) { return contains(root, value); }

  private boolean contains(TreeNode<T> node, T value) {
    if (node == null) {
      return false;
    }
    int cmp = value.compareTo(node.value);
    if (cmp == 0) {
      return true;
    } else if (cmp < 0) {
      return contains(node.left, value);
    } else {
      return contains(node.right, value);
    }
  }

  // Ad hoc polymorphic with other insert
  public void insert(T value) { insert(root, value); }

  private void insert(TreeNode<T> node, T value) {
    if (node == null) {
      this.root = new TreeNode<>(value);
    }
    int cmp = value.compareTo(node.value);
    if (cmp == 0) {
      return;
    } else if (cmp < 0) {
      if (node.left == null) {
        node.left = new TreeNode<>(value);
      } else {
        insert(node.left, value);
      }
    } else {
      if (node.right == null) {
        node.right = new TreeNode<>(value);
      } else {
        insert(node.right, value);
      }
    }
  }

  // More ad hoc polymorphism!
  public void inorder() { inorder(this.root); }

  private void inorder(TreeNode<T> node) {
    if (node == null)
      return;
    inorder(node.left);
    System.out.println(node.value);
    inorder(node.right);
  }
}

1
2
3
4
5
6
7

public class TreeNode<T extends Comparable<? super T>> {
    public T value;
    public TreeNode<T> left, right;
    public TreeNode<T>(T value) {
        this.value = value;
    }
}

1
2
3
4
5
6
7

public static void main(String[] args) {
    BinarySearchTree<Integer> bst = new BinarySearchTree<>();
    bst.insert(1);
    bst.insert(5);
    bst.insert(100);
    bst.inorder();
}

1
5
100

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

datatype comparison =
    Less
  | Equal
  | Greater

signature COMPARABLE =
  sig
    type t
    val compare: t -> t -> comparison
    val printVal: t -> unit
  end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

functor BinarySearchTree (Val: COMPARABLE) =
struct
type value = Val.t
datatype node
  = Empty
  | Node of value * node * node
val empty = Empty
fun contains Empty _ = false
  | contains (Node (x, l, r)) v =
    case Val.compare x v of
        Equal => true
      | Less => contains l v
      | Greater => contains r v
fun insert (v, node) =
    case node of
        Empty => Node(v, Empty, Empty)
      | Node (x, l, r) =>
        case Val.compare x v of
            Equal => Node (x, l, r)
          | Less => Node(x, l, insert (v, r))
          | Greater => Node(x, insert (v, l), r)
fun inorder node =
    case node of
        Empty => ()
      | Node (x, l, r) => (inorder l; Val.printVal x; inorder r)
end

1
2
3
4
5
6
7
8

structure IntComp : COMPARABLE = struct
type t = int
fun compare l r =
    if l < r then Less
    else if l > r then Greater
    else Equal
fun printVal v = print (Int.toString v ^ "\n")
end

1

structure IntBST = BinarySearchTree(IntComp)

1
2

val my_int_btree = List.foldl IntBST.insert IntBST.empty [1,5,100]
val () = IntBST.inorder my_int_btree

1
5
100