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
dynamickeyword, 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, stringThe first call in this example illustrates a common misconception: overload resolution always uses the static type, so the compiler selects
Describe(object)even thoughorefers 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
dynamicis 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.
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.
| 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 ofApplyToBothfrom 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 also a shape, so the set of circles is included in the set of shapes. The interesting question is what makes one type a subtype of another. Programming languages answer it in three main ways, described in Sections 5.1–5.3.
5.1 Structural and Nominal Subtyping
In C#, Circle is a subtype of Shape only because its declaration says so. A class with exactly the same members but no : Shape in its declaration is not a subtype. This is nominal subtyping – the subtype relation is established by declared names.
The alternative is structural subtyping – the subtype relation follows from the shape of the types alone [8]. A record type with more fields is a subtype of a record type with fewer, as long as the shared fields agree. TypeScript works this way:
type HasX = { x: number };
const colorPoint = { x: 1, y: 2, color: "red" };
const p: HasX = colorPoint; // accepted: colorPoint has an x field, nothing else is required
Both kinds of subtyping extend to function types, and C# exposes the rule through variance on delegates. A function can safely replace another if it accepts more general arguments and returns more specific results:
Func<Shape, Circle> fromShape = s => new Circle(s.Area());
Func<Circle, Shape> f = fromShape; // compiles: Func is contravariant in its argument and covariant in its result
The argument position is contravariant – the subtype relation on arguments is reversed – and the result position is covariant – the subtype relation on results is preserved. This rule is what makes the next section's problem appear.
5.2 Inheritance Versus Subtyping
Object-oriented languages usually tie two different ideas together. Inheritance – a mechanism for building one class's implementation from another's. Subtyping – a relation that decides where a value may be used. In C#, every subclass is automatically a subtype of its base class, but the two ideas can come apart [9].
The classic example is a method that takes an argument of the receiver's own type, called a binary method:
class Point(int x)
{
public int X => x;
public virtual bool Equal(Point other) => X == other.X;
}
class ColorPoint(int x, string color) : Point(x)
{
public string Color => color;
// public override bool Equal(ColorPoint other) // not allowed: the parameter type must stay Point
public override bool Equal(Point other) =>
other is ColorPoint cp && X == cp.X && Color == cp.Color;
}
Ideally, ColorPoint.Equal would take a ColorPoint, since comparing colors only makes sense between two colored points. But narrowing the parameter type breaks the contravariance rule from Section 5.1: code that holds a Point reference could pass a plain Point to a method that expects a ColorPoint. A ColorPoint with such a method would inherit from Point without being a subtype of it. C# avoids the contradiction by forbidding the narrowing, which is why the override above has to fall back on a run-time type test. Eiffel, which does allow this kind of narrowing, has a well-known type-safety gap at exactly this point.
5.3 Behavioral Subtyping
Matching signatures are not enough for safe substitution. The following code compiles without warnings:
class FixedPoint(int x)
{
protected int _x = x;
public int X => _x; // documented guarantee: X never changes
}
class MovablePoint(int x) : FixedPoint(x)
{
public void Move(int dx) => _x += dx;
}
Code that receives a FixedPoint may rely on X staying the same, for example by caching it. Passing a MovablePoint breaks that assumption, even though the type checker sees nothing wrong. Behavioral subtyping closes this gap – a subtype must preserve every property that can be proved about its supertype, not just the method signatures [10]. These properties include invariants, the preconditions and postconditions of each method, and history constraints, which describe how an object's state may change over its lifetime. "X never changes" is a history constraint, and MovablePoint violates it.
This requirement is widely known as the Liskov Substitution Principle. Its best-known illustration, a Square that inherits from a mutable Rectangle, fails for the same reason: setting the width of a square also changes its height, which code written against Rectangle does not expect.
The three notions of subtyping compare as follows:
| Notion of subtyping | Basis of the relation | Checked by | Example languages |
|---|---|---|---|
| Structural | Shape of the types | Type checker | TypeScript, Go interfaces, OCaml objects |
| Nominal | Declared inheritance or implementation | Type checker | C#, Java, C++ |
| Behavioral | Specified behavior | The developer, through design, contracts, and tests | Any language |
6 AD HOC POLYMORPHISM
6.1 Overloading
Let's go back to the Twice example from Section 1.2 and look at it closer:
static int Twice(int x) => x * 2;
static string Twice(string s) => s + s;
Twice(21); // calls Twice(int)
Twice("ab"); // calls Twice(string)
The two methods share a name, but nothing else: they have different bodies and different types, and the compiler decides which one to call at each call site. Renaming them makes the overloading disappear without changing what the program does:
static int TwiceInt(int x) => x * 2;
static string TwiceString(string s) => s + s;
TwiceInt(21);
TwiceString("ab");
This is why ad hoc polymorphism is considered polymorphism only in appearance (Section 3.1): a simple compile-time translation removes it entirely [2]. The same holds for operator overloading, such as the predefined + on int and double or a user-defined operator + on a Vector type.
6.2 Coercion
Let's look at the Half example from Section 1.2 once more:
static double Half(double x) => x / 2;
Half(5); // the int 5 is converted to the double 5.0
Half has exactly one implementation, written for double. The call works with an int only because the compiler inserts a conversion. C# also lets you define such conversions for your own types:
readonly record struct Meters(double Value)
{
public static implicit operator Meters(double v) => new(v);
}
static Meters Stretch(Meters m) => new(m.Value * 2);
Stretch(5.0); // the double 5.0 is converted to Meters
From the call site alone, overloading and coercion are often indistinguishable [2]:
double d = 3 + 4.0;
This line can be explained in two ways: as one of several overloaded + operators, one for each combination of int and double, or as a single double + double operator preceded by a conversion of 3. C# actually uses both. The language defines a set of overloaded + operators for its numeric types, and overload resolution picks double + double after converting 3 to 3.0.
6.3 Type Classes and Generic Math
Plain overloading has a limitation: a generic method cannot use it. Inside Sum<T>, there is no + that works for an arbitrary T, because the compiler resolves overloads statically and T is unknown. Type classes solve this by turning a set of overloaded operations into a constraint that a type parameter can carry [12]. They first appeared in Haskell and today underlie Rust traits and Scala implicits.
C# gained the same capability in C# 11, through static abstract interface members. The generic math interfaces in .NET use it:
using System.Numerics;
static T Sum<T>(IEnumerable<T> xs) where T : INumber<T>
{
T total = T.Zero;
foreach (var x in xs) total += x;
return total;
}
Sum(new[] { 1, 2, 3 }); // 6, using int addition
Sum(new[] { 1.5, 2.5 }); // 4.0, using double addition
Sum is generic, but + still does something different for each type, so the polymorphism is ad hoc. What has changed is that the set of types is no longer fixed in advance: any type that implements INumber<T> qualifies.
The standard way to compile type classes shows why this works. Each constraint becomes an extra argument, called a dictionary – an object that carries the implementations of the constrained operations. Written by hand in C#, the translation looks like this:
interface IAdditive<T> { T Zero { get; } T Add(T a, T b); } // the dictionary
sealed class IntAdditive : IAdditive<int>
{
public int Zero => 0;
public int Add(int a, int b) => a + b;
}
static T Sum<T>(IEnumerable<T> xs, IAdditive<T> d)
{
T total = d.Zero;
foreach (var x in xs) total = d.Add(total, x);
return total;
}
Sum(new[] { 1, 2, 3 }, new IntAdditive()); // 6
After the translation, Sum is ordinary parametric code: it never inspects T, and all type-specific behavior arrives through the dictionary. Type classes thus bring ad hoc polymorphism into the framework of parametric polymorphism, reconnecting the two kinds that Strachey separated in 1967.
7 BOUNDARY CASES
There are mechanisms and concepts in different programming languages that don't fit the four forms as neatly:
| Mechanism | Cardelli–Wegner form | Binding time |
|---|---|---|
| ML and Haskell polymorphic functions | Parametric (universal) | Compile time checking; one compiled body |
| C# and Java generics | Parametric; bounded when constrained with where T : C or T extends C
|
Compile time checking |
| C# generic math, Haskell type classes, Rust traits | Ad hoc, structured as in Section 6.3 | Implementations selected at compile time |
| C++ templates | Parametric in form; ad hoc in effect | Compile time, per instantiation |
The syntax of a mechanism does not determine its category. Section 4.3 shows that every well-behaved function of type ∀T. T → T is the identity. C++ templates break this through explicit specialization, which permits a different definition for a particular type argument:
template <typename T> T identity(T x) { return x; }
template <> int identity<int>(int x) { return x + 1; } // legal specialization
C# generics break it too. Let's go back to Id from Section 1.1 one last time and add a run-time type test, which is legal on values of a type parameter:
static T Id<T>(T x) => x is int i ? (T)(object)(i + 1) : x; // compiles; not the identity for int
Neither mechanism therefore satisfies parametricity in the sense of Section 4.3. In C#, Java, and C++ alike, free theorems hold only for code that avoids type tests, reflection, and specialization.
8 FURTHER READING
The sources below cover the material of this article in more depth:
- Cardelli and Wegner [2] – the original taxonomy and the quantifiers behind it.
- Wadler [7] – an accessible introduction to parametricity and free theorems, followed by Reynolds [6] for the underlying theory.
- Milner [5] – let-polymorphism and type inference.
- Wadler and Blott [12] – type classes as structured ad hoc polymorphism.
- Cardelli [8], Cook, Hill, and Canning [9], and Liskov and Wing [10] – structural subtyping, inheritance versus subtyping, and behavioral subtyping.
- Pierce [13] – the standard textbook, covering subtyping, System F, existential types, and bounded quantification in one framework. Pierce [14] and Harper [15] continue from there, and Cardelli [16] is a compact survey of the same ground.
- Abadi and Cardelli [11] – the most complete formal account of objects, subtyping, and variance.
- Strachey [1], Girard [3], and Reynolds [4] – the historical primary sources.
REFERENCES
- Strachey, "Fundamental Concepts in Programming Languages". Lecture notes, International Summer School in Computer Programming, Copenhagen, 1967. Reprinted in Higher-Order and Symbolic Computation 13(1–2):11–49, 2000.
- Cardelli & Wegner, "On Understanding Types, Data Abstraction, and Polymorphism". ACM Computing Surveys 17(4):471–522, 1985. DOI: 10.1145/6041.6042.
- Girard, "Interprétation fonctionnelle et élimination des coupures de l'arithmétique d'ordre supérieur". Thèse de Doctorat d'État, Université Paris VII, 1972.
- Reynolds, "Towards a Theory of Type Structure". Programming Symposium (Colloque sur la Programmation), Lecture Notes in Computer Science 19, pp. 408–425. Springer, 1974.
- Milner, "A Theory of Type Polymorphism in Programming". Journal of Computer and System Sciences 17(3):348–375, 1978.
- Reynolds, "Types, Abstraction and Parametric Polymorphism". Information Processing 83 (IFIP Congress), pp. 513–523. North-Holland, 1983. The link is a bibliographic record; the proceedings carry no DOI.
- Wadler, "Theorems for Free!". Proceedings of the Fourth International Conference on Functional Programming Languages and Computer Architecture (FPCA '89), pp. 347–359. ACM, 1989.
- Cardelli, "A Semantics of Multiple Inheritance". Semantics of Data Types, Lecture Notes in Computer Science 173, pp. 51–67. Springer, 1984. Extended version in Information and Computation 76(2–3):138–164, 1988 (linked).
- Cook, Hill & Canning, "Inheritance Is Not Subtyping". Proceedings of the 17th ACM Symposium on Principles of Programming Languages (POPL '90), pp. 125–135. ACM, 1990.
- Liskov & Wing, "A Behavioral Notion of Subtyping". ACM Transactions on Programming Languages and Systems 16(6):1811–1841, 1994.
- Abadi & Cardelli, A Theory of Objects. Monographs in Computer Science. Springer, 1996.
- Wadler & Blott, "How to Make Ad-Hoc Polymorphism Less Ad Hoc". Proceedings of the 16th ACM Symposium on Principles of Programming Languages (POPL '89), pp. 60–76. ACM, 1989.
- Pierce, Types and Programming Languages. MIT Press, 2002.
- Pierce (ed.), Advanced Topics in Types and Programming Languages. MIT Press, 2005.
- Harper, Practical Foundations for Programming Languages, 2nd ed. Cambridge University Press, 2016.
- Cardelli, "Type Systems". In A. B. Tucker (ed.), The Computer Science and Engineering Handbook, Chapter 103. CRC Press, 1997; 2nd ed., Chapter 97, 2004.

Top comments (0)