In dynamically-typed programming languages, a variable can hold values of any type. The same piece of code can operate on anything given to it. But what about statically-typed languages, where variables are restricted to holding certain types? If we want the same kind of flexibility, we have to start to think more formally.

Polymorphism is the language feature that allows us to have a single name or piece of code which can operate on more than one type, in a way which can be type-checked. We say such code is polymorphic. Almost all languages have polymorphism, even if they don’t let you work with it yourself: the arithmetic and comparison operators +-*/<> are usually polymorphic over a variety of number types.

When working in languages which have polymorphism, the variety of differences means it’s not always easy to understand the fundamental ideas. This article is for those interested in exploring language features and their rationales more generally, while avoiding formal type theory. I’ll be writing with a practical pseudo-code language.

Overloading

The simplest example of a polymorphic function is the identity function

id(x) = x

which simply evaluates to its argument. Ideally, we want this function to work for values of any type.

Our first kind of polymorphism is called function overloading, where we can declare multiple functions of the same name if they have different type signatures. So we could have

id(x: Bool) = x
id(x: Int) = x

etc. and the language would look up the appropriate one at compile time based on the given type.

This can be useful when we want to do different things for each type, but it has many limitations:

• if the function bodies are the same then it’s tedious to copy and paste it for lots of types
• we might not be able to use id for types we didn’t know about in advance; some languages don’t let you overload functions across different modules
• any function which calls id on its arguments and also wants to be polymorphic needs to be overloaded too
• if the language has type coercions, overloading might be unpredictable when we have overloads for coercible types
• if the language has subtyping, several overloads may apply and the one chosen may be unpredictable, or not even clearly defined (Julia struggles with this problem)

In some sense, overloading isn’t “proper” polymorphism; it’s a syntactic convenience which automatically renames functions for us.

Note: Sometimes people talk about single/multiple dispatch as being the run-time equivalent of overloading. It’s difficult to reconcile dispatch with other features because it relies on bending the strict concept of a type slightly. We’ll touch on this later.

Type parameters and constraints

What we want is to say that id can be of type (T) -> T for any type T. For this article, we will write this like:

id: [T](T) -> T
id(x) = x

This is called parametric polymorphism, or generic programming, and T is called a type parameter. When we call id, we have to also specify a type which will be bound to the parameter to create a regular (“monomorphic”) function type. For example, id[Int](1) calls a function of type (Int) -> Int. Usually languages can infer the type parameter from the given argument, so we can just write id(1).

However, we immediately run into a problem: our function body needs to be valid regardless of what type the argument is. What can we do with something of any type? That is, what behaviours do all types have in common? Pretty much nothing! To allow more behaviours, we need to constrain the type parameter T to allow fewer types. There are several ways to do this:

• Look at what is done to the variable in the function body and implicitly constrain to any type which supports those functions/methods. C++ and Julia effectively work like this. (I believe C++ just tries to compile the monomorphised code and sees if it works, but it’s logically the same.)

• Have the programmer explicitly define a set of behaviours ahead of time in what’s called an interface or trait, and constrain the type to that. For example, to write a generic maximum function, we only need to be able to compare the given values, so it could have a type written as

  max[T Comparable](T, T) -> T
  

  where Comparable is the name of the interface which allows comparing by a less-than-or-equal operator. Rust and Haskell work like this.

• Have the programmer specify some set of possible types and automatically constrain to their common behaviours. Go and TypeScript support this.

The specifics will vary, but in general we need be able to check ahead of time that polymorphic function definitions are valid for any type that is given to it. There are a variety of ways to implement these systems; see Implementing and Understanding Type Classes for more info.

Note that if a language has overloaded functions/operators (as many do), we can consider type parameters to be a natural extension of that—if we have the same function f for a variety of types, why shouldn’t we be able to write a function which accepts any type for which we’ve defined f?

(One thing to keep in mind is that accepting type-parametrised functions as inputs to other functions requires extra type checking machinery that few languages implement. Returning type-parametrised functions is more trivial. See here and here for more about this concept of polymorphic rank.)

Subtypes

Formally, in all the examples so far we’ve been considering systems where expressions have one unique type. This changes with the last kind of polymorphism we’ll talk about: subtyping.

To say S is a subtype of T, or S <: T, means that any expression of type S can also be considered of type T, and used anywhere T is expected. Subtyping is familiar to many programmers because of object-oriented programming: when we create a class which inherits from another, we create a subtype of the parent class.

Unfortunately, on its own, subtyping doesn’t give us anywhere near the power of OOP. Say we have an Animal type, which has an age, and a function

setAge: (Animal, Int) -> Animal

which returns a modified copy of the value with a new age. Then say we have a subtype Dog <: Animal.

If we call setAge on a Dog, we won’t get a Dog value back; we’ll get a general Animal. We can substitute our subtype in the function input, but the language doesn’t know for sure that setAge will return a value which can also be considered as our subtype.

What this means is that in OOP, when we have a method that modifies our object or returns a duplicate, that method is technically parametric in the object class. We essentially have

setAge: [T <: Animal](T, Int) -> T

where the constraint specifies that T must be a subtype of Animal.

If S <: T, we can say in general that it is valid to “up cast” any S value to T, but not to “down cast” a T value to S. That said, some languages like C++ and Go do support down casting, because they store run-time information alongside the values which keeps track of which subtype, if any, a value really is underneath its appearance. This lets us write code which says “ok, I know you are an Animal; if you are a Dog, do this; if a Cat, do that;” etc. It’s kind of cheating the system; strictly, types should be determinable in advance, but here we allow values to be more specific than they are in the syntax, and allow the behaviour of a program to dynamically change based on this. This is how dynamic dispatch schemes work.

Another consideration for subtyping is type variance. For types that are made out of other ones, such as function types, there is a question about how the subtyping relation translates to the containing type.

For example, we said above that it was ok to give a Dog as a function parameter of type Animal. But it’s not ok to give an Animal to a function expecting a Dog. Subtypes are more specific, so have additional functions defined on them than their supertypes:

getAge: (Animal) -> Int
getAgeDogYears: (Dog) -> Int

This means that functions which take Animals as inputs are subtypes of those which take Dogs as inputs. Functions are contravariant in their inputs: they reverse the subtype relation.

The other possibilities are covariance, where the subtype relation is kept the same, and invariance, where there is no subtype relation either way. See the Scala book and the Wikipedia page for examples.

As a final note: subtyping and type parameters sometimes solve similar problems, so their differences can be subtle. For example, with subtyping we might be able to define a list of pets of type List[Animal] and put all sorts of creatures in there together, like Dogs, Cats, Parakeets, Snakes, etc. However, if we have a constrained type parameter T <: Animal, then List[T] can only contain Animals of one type. That type can vary between instances of the list, but it can’t vary within it. See C++ ‘Type Erasure’ Explained for an interesting pattern involving both subtyping and parameters.