In this article we'll summarize the classical literature that defines the kinds of polymorphism found in programming languages. As there is a lot of inconsistency in online material, I felt an urge to structurize the knowledge, offering a comprehensive breakdown of polymoprhism into categories, providing links to credible sources. The examples of polymorphism will be given in C#, since it's my primary language.

1 TERMINOLOGY AND CLASSIFICATION

Polymorphism is the property of a program fragment, such as a function, an operator, or a value, that can be used at more than one type. Polymorphic languages are those languages in which some values and variables have more than one type, in contrast to monomorphic languages, in which every value and variable has exactly one type [2].

There are two classifications of polymorphism commonly use:

  • The static/dynamic classification
  • The universal/ad hoc classification

Static/dynamic classification describes when the implementation is selected: at compile time or at run time. Unversal/ad hoc classification describes how the code is shared: one implementation for all types, or a separate implementation for each type.

1.1 Static and Dynamic Polymorphism

The static type of an expression is the type the compiler assigns to it from the source code. The run-time type is the type of the object the expression actually refers to during execution. The two classes of polymorphism differ in which of these types determines the implementation.

  • Static (compile-time) polymorphism selects the implementation from the static types of the arguments. The selection is fixed once the code compiles. The language constructs that fall under static polymorphism:

    • Overloading – a language feature in which several methods share the same name but have different parameter lists. It lets the compiler select the applicable method at compile time based on the static types and number of the arguments.
    static string Describe(int x) => $"int {x}"; static string Describe(string s) => $"string {s}"; Describe(42); // compiler selects Describe(int) Describe("hi"); // compiler selects Describe(string) 
    • Generics – a language feature that lets you define types and methods with type parameters. They let one generic definition be reused with many concrete types while preserving static type safety; at each use site, the compiler infers or checks the type argument and fixes the instantiation during compilation.
    static T Id<T>(T x) => x; Id(42); // T = int Id("hi"); // T = string 
  • Dynamic (run-time) polymorphism selects the implementation from the run-time type of an object. This selection is called dynamic dispatch. The language constructs that fall under dynamic polymorphism:

    • Virtual methods – instance methods declared with the virtual modifier (and their override implementations in derived classes) that participate in runtime dispatch. When such a method is called through a reference, the override associated with the receiver’s run-time type is invoked, regardless of the static type of the reference.
    abstract class Shape { public abstract double Area(); } class Circle(double r) : Shape { public override double Area() => Math.PI * r * r; } class Square(double side) : Shape { public override double Area() => side * side; } Shape s = Random.Shared.Next(2) == 0 ? new Circle(1) : new Square(2); s.Area(); // Circle.Area or Square.Area, selected at run time 
    • The dynamic keyword, which defers overload resolution from compile time to run time.
    static string Describe(object o) => "something"; object o = "hi"; Describe(o); // "something": selected from the static type, object Describe((dynamic)o); // "string hi": selected from the run-time type, string 

    The first call in this example illustrates a common misconception: overload resolution always uses the static type, so the compiler selects Describe(object) even though o refers to a string at run time.

Note

The same distinction appears under the names early binding and late binding, or equivalently static binding and dynamic binding. A binding is the association of a name – a method call, a member access – with the implementation it denotes. Overload resolution and generic instantiation are resolved at compile time and are therefore early-bound; the choice of a virtual override, and every member access on a dynamic expression, is resolved at run time and is therefore late-bound. The pairs overlap closely with static/dynamic polymorphism, but they answer different questions: binding terms describe when a name is resolved, while static/dynamic describe which types a piece of code works for.

1.2 Universal and Ad Hoc Polymorphism

The second classification originates with Cardelli and Wegner [2] and is the standard one in type theory. It separates universal from ad hoc polymorphism.

  • Universal polymorphism uses one implementation for an unbounded range of types. The forms of universal polymorphism are:

    • Parametric polymorphism – a form of universal polymorphism in which code is written over one or more type parameters instead of concrete types. The code never inspects values of the parameterized type, so it behaves identically for every type argument.
    static int Count<T>(List<T> items) => items.Count; // same code for List<int>, List<string>, ... 
    • Inclusion polymorphism, also called subtype polymorphism – a form of universal polymorphism in which a value of a subtype can be used wherever a value of its base type is expected. Code written against a base type therefore accepts every subtype of that base type, including subtypes defined later.
    static double TotalArea(IEnumerable<Shape> shapes) => shapes.Sum(s => s.Area()); // accepts Circle, Square, and any other subtype of Shape 
  • Ad hoc polymorphism applies one name to a finite set of possibly unrelated types, usually with separate code for each type. The forms of ad hoc polymorphism are:

    • Overloading – a form of ad hoc polymorphism in which one name denotes several distinct implementations, one for each of a finite set of types or type combinations. Each implementation is written separately, and the choice among them is made at compile time.
    static int Twice(int x) => x * 2; static string Twice(string s) => s + s; 
    • Coercion – a form of ad hoc polymorphism in which a value is implicitly converted to the type that a function expects. The function itself is written for one type, and values of other types are adapted to it rather than handled by separate implementations.
    static double Half(double x) => x / 2; Half(5); // the int 5 is converted to the double 5.0 

1.3 Relationship Between the Two Classifications

The two classifications are independent. The family of a mechanism does not determine its binding time, and the binding time does not determine its family. Every mechanism therefore occupies a position on both axes:

  • Overloading is ad hoc and static.
  • Overloading through dynamic is ad hoc and dynamic.
  • Generics are parametric and static.
  • Virtual methods invoked through a base type are inclusion and dynamic.

Introductory material on object-oriented programming commonly uses "polymorphism" to mean only one of these combinations: virtual methods, that is, inclusion polymorphism with dynamic dispatch. The term "compile-time polymorphism" in the same material usually refers to overloading. Both are genuine forms of polymorphism, and neither covers the whole concept.

2 ORIGIN OF THE TERMINOLOGY

The distinction between two kinds of polymorphism were introduced in Christopher Strachey's lecture notes delivered at the International Summer School in Computer Programming in Copenhagen in 1967 [1]. The notes circulate informally for decades and appear in print in 2000 in a memorial issue of Higher-Order and Symbolic Computation.

Strachey separates the two kinds as follows.

  • Ad hoc polymorphism occurs when a function is defined over several types and behaves differently for each, with no systematic rule relating the argument types to the result type. Arithmetic operators are the characteristic case: integer addition and floating-point addition share a symbol but use different algorithms.
  • Parametric polymorphism occurs when a function is defined over a range of types and acts in the same way for each type. A list-length function is the characteristic case: it counts elements without inspecting them, so its behavior is identical for lists of integers and lists of strings.

length(+)(+)​:∀α. List α→Int:Int→Int→Int:Double→Double→Double​​parametric: one algorithm for every αad hoc: integer additionad hoc: floating-point addition​

I wouldn’t rely on these notes as a definitive source of truth for categorizing polymorphism, as they are informal and contain no type system. Their lasting contribution is the vocabulary itself, which was later widely adopted. The categorization, however, has changed since then, and we’ll look at those changes next.

3 THE CARDELLI–WEGNER TAXONOMY

3.1 Universal and Ad Hoc Polymorphism

The first comprehensive taxonomy came form Cardelli and Wegner in 1985 [2], which refined Strachey's distinction into the classification that serves as the standard reference up to this day. The top-level division separates universal polymorphism, in which a single piece of code works uniformly on a potentially infinite range of types that share a common structure, from ad hoc polymorphism, in which a name works, or appears to work, on a finite set of possibly unrelated types, often by executing different code for each. Universal polymorphism can be regarded as polymorphism in the strict sense and ad hoc polymorphism as an apparent form that a translation step can eliminate.

Each family is further divided into two forms, as shown in Figure 3.1.

Picture 3.1 – The two families of polymorphism and their forms

Form Family Range of types Implementations Characteristic mechanism
Parametric Universal Unbounded; determined by a type parameter One, uniform Generic functions; ∀-types
Inclusion Universal Every subtype of a given type One, written against the supertype Subtyping; subclassing
Overloading Ad hoc Finite and enumerated One per type Overloaded names and operators
Coercion Ad hoc Finite; closed under the available conversions One, plus implicit conversions Implicit numeric widening

3.2 Three Quantifiers

The taxonomy rests on three ideas from type theory, called quantifiers:

1 Universal quantification: generics. Recall the example from Section 1.1:

 static T Id<T>(T x) => x; Id(42); // T = int Id("hi"); // T = string 

Without polymorphism, even the identity function has to be written once per type, as IdInt(int x), IdBool(bool x), and so on, with identical bodies. The generic Id<T> replaces all of them with one definition.

In type theory, Id has the type ∀T. T → T, read "for every type T, a function from T to T". Here T is a type variable, a placeholder that ranges over types, and a type of this form is universally quantified. Supplying a concrete type, as in Id<int>, is called instantiation.

The formal calculus behind universal quantification is System F, discovered independently by Girard [3] and Reynolds [4] in the early 1970s. Section 4 looks at it in more detail.

2 Existential quantification: hidden representations. A universal type says "this works for every type". Its mirror image, an existential type ∃T. …, says "there is some type here, but you don't get to know which". In C#, the closest everyday equivalent is an interface backed by private state:

 public interface IPoint { int GetX(); } sealed class IntPoint : IPoint { private readonly int _x; public IntPoint(int x) => _x = x; public int GetX() => _x; } sealed class TuplePoint : IPoint { private readonly (int X, int Y) _coords; public TuplePoint(int x, int y) => _coords = (x, y); public int GetX() => _coords.X; } 

Code that receives an IPoint can call GetX, but it isn't supposed to care whether an int or a tuple is inside, so one implementation can replace the other without breaking callers. That is the idea of an abstract data type.

3 Subtyping and bounded quantification: constrained generics. A type S is a subtype of T, written S ≤ T, when a value of type S is acceptable wherever a value of type T is expected. Here Point and ColorPoint are both subtypes of IHasX:

 public interface IHasX { int X { get; } } public record Point(int X) : IHasX; public record ColorPoint(int X, string Color) : IHasX; static IHasX Rightmost(IHasX a, IHasX b) => a.X >= b.X ? a : b; 

Rightmost accepts any two values that have an X, which is inclusion polymorphism as described in Section 1.2. Subtyping on its own loses information, though:

 var p = Rightmost(new ColorPoint(1, "red"), new ColorPoint(5, "blue")); Console.WriteLine(p.Color); // compile error: IHasX has no Color 

The returned object is still a ColorPoint, but its static type is only IHasX. Bounded quantification fixes this by combining a type parameter with a subtype constraint:

 static T Rightmost<T>(T a, T b) where T : IHasX => a.X >= b.X ? a : b; var q = Rightmost(new ColorPoint(1, "red"), new ColorPoint(5, "blue")); Console.WriteLine(q.Color); // "blue": T is ColorPoint 

In type theory, this Rightmost has the type ∀T ≤ IHasX. T → T → T, read "for every subtype T of IHasX". Cardelli and Wegner introduced bounded quantification in [2], and C#'s where T : … constraints and Java's <T extends …> are its direct descendants.

The table below summarizes the three quantifiers.

Quantifier Read as C# counterpart Concept Covered in
∀T. … for every type T T Id<T>(T x) Parametric polymorphism Section 4
∃T. … for some hidden type T An interface over private state Abstract data types This section
∀T ≤ S. … for every subtype T of S where T : S Parametric and inclusion polymorphism combined Section 5

4 PARAMETRIC POLYMORPHISM

4.1 System F: The Polymorphic Lambda Calculus

Let's go back to the identity function from Section 3.2 and look at it closer:

static T Id<T>(T x) => x; Id<int>(42); // explicit type argument Id(42); // type argument inferred by the compiler 

The call Id<int>(42) happens in two steps. First, the type argument int is supplied, which turns the generic Id<T> into an ordinary function int → int. Then the value 42 is passed to that function. This two-step view is the core of System F, also called the polymorphic lambda calculus – a minimal formal language in which functions can take types as parameters, exactly like Id<T>, and types are supplied explicitly at each use [3], [4]. System F is the standard formal model of parametric polymorphism.

System F goes further than C# in one important way: a polymorphic function is a value like any other, so it can be passed to and returned from other functions. In C#, a generic method loses its polymorphism as soon as it is turned into a delegate, because a Func<T, T> needs a concrete T:

// Does not compile: T is fixed by the caller, so f cannot accept both an int and a string static (int, string) ApplyToBoth<T>(Func<T, T> f) => (f(42), f("hi")); 

The workaround would be an interface with a generic method, which packages a polymorphic function as an object:

interface IPolyFunc { T Invoke<T>(T x); } sealed class Identity : IPolyFunc { public T Invoke<T>(T x) => x; } static (int, string) ApplyToBoth(IPolyFunc f) => (f.Invoke(42), f.Invoke("hi")); ApplyToBoth(new Identity()); // (42, "hi") 

In System F, ApplyToBoth has the type (∀T. T → T) → (Int, String): the quantifier sits inside the parameter type rather than at the front. Types like this are called higher-rank types. System F supports them directly, and it is even impredicative – a type variable can be instantiated with a polymorphic type, including the type of the identity function itself.

This expressiveness has a price. Type inference for full System F is undecidable, so programs in it have to carry explicit type annotations. The next section describes the restriction that most functional languages adopt to avoid this.

4.2 Let-Polymorphism and Hindley–Milner Inference

C# infers type arguments at call sites, but it cannot infer the type of a polymorphic lambda:

var id = x => x; // does not compile: the type of x cannot be inferred var idInt = (int x) => x; // compiles, but idInt is Func<int, int>, not polymorphic 

The ML family of languages (Standard ML, OCaml, F#, and, with extensions, Haskell) takes a different approach, known as Hindley–Milner type inference [5]. It infers the most general type of every expression without any annotations, at the cost of restricting where polymorphism may appear. Here is the same idea in F#:

let id x = x // inferred type: 'a -> 'a let pair = (id 3, id true) // id is used at int and at bool 

The system has three defining characteristics:

  • Type schemes – quantifiers appear only at the outermost level of a type, as in ∀α. α → α. The higher-rank type of ApplyToBoth from Section 4.1 is not expressible.
  • Let-polymorphism – a definition becomes polymorphic only when it is bound with let. A function parameter stays monomorphic inside the function body, so the following F# expression is rejected, even though it looks equivalent to the one above:
 (fun id -> (id 3, id true)) (fun x -> x) // type error: id cannot be both int -> int and bool -> bool 
  • Principal types – every well-typed expression has a most general type, of which every other valid type is an instance, and the inference algorithm (Algorithm W) always finds it.

The same work proves that well-typed programs cannot go wrong at run time [5]. The table below compares the three approaches.

Property System F Hindley–Milner C#
Quantifier position Anywhere in a type Outermost only Generic methods and types; higher-rank only through interfaces
Type annotations Required Not required Required on lambdas and members; type arguments inferred at call sites
Type inference Undecidable Decidable, with principal types Local, per call site
Impredicativity Yes No No

4.3 Parametricity and Free Theorems

Parametric code never inspects values of the parameterized type, so it behaves identically for every type argument. This property is called parametricity, and it has a surprisingly strong consequence: the type of a parametric function alone restricts what the function can do [6].

Let's take the identity function from Section 4.1 once more. A function with the signature T F<T>(T x) knows nothing about T: it cannot create a new T, compare two values of type T, or call any method on them. The only thing it can return is x itself. The type ∀T. T → T therefore has exactly one well-behaved implementation, the identity.

The same reasoning applies to less trivial signatures. Consider any function of this type:

static List<T> R<T>(List<T> xs) { /* ... */ } 

Since R cannot create or inspect elements of type T, all it can do is rearrange, duplicate, or drop the elements it receives. It follows that applying a function f to every element commutes with R, whatever R actually does:

// For every R of the type above and every function f: R(xs.Select(f).ToList()) // equals R(xs).Select(f) 

Reversing a list, taking its first three elements, and removing every second element all satisfy this equation, and none of them needs a separate proof. Results of this kind follow from the type alone, and are therefore called free theorems [7]. In languages with general recursion, a few free theorems additionally require the functions involved to terminate.

Parametricity is also the precise line between parametric and ad hoc polymorphism: as soon as a function can branch on its type argument, the free theorems stop holding, whatever the syntax looks like. Section 7 shows that both C# generics and C++ templates allow exactly that.

5 INCLUSION POLYMORPHISM

Consider this example from Section 1.1:

abstract class Shape { public abstract double Area(); } class Circle(double r) : Shape { public override double Area() => Math.PI * r * r; } class Square(double side) : Shape { public override double Area() => side * side; } static double TotalArea(IEnumerable<Shape> shapes) => shapes.Sum(s => s.Area()); 

TotalArea accepts circles and squares because Circle ≤ Shape and Square ≤ Shape. The name inclusion comes from reading types as sets of values: every circle is a...