Polymorphism and Generics

Polymorphism lets a single piece of code operate uniformly over many types, with parametric polymorphism (generics), ad hoc polymorphism (overloading and type classes), and subtype polymorphism as its main forms.

Definition

Polymorphism is the property by which a single function, type, or operation can apply to values of more than one type; parametric polymorphism does so uniformly via type parameters (generics), while ad hoc polymorphism dispatches to type-specific implementations.

Scope

This topic covers the major kinds of polymorphism: parametric polymorphism realized by generics and System F, ad hoc polymorphism via overloading and type classes, and inclusion (subtype) polymorphism. It addresses parametricity and the strong reasoning principles it yields, and how generic abstractions are compiled and constrained.

Core questions

• How do generics provide reuse without sacrificing type safety?
• What is parametricity and what guarantees does it give for free?
• How do type classes systematize ad hoc overloading?
• How are generic definitions compiled, and what constraints can bound type parameters?

Key theories

Parametricity (abstraction theorem)

Reynolds's abstraction theorem shows that parametrically polymorphic functions behave uniformly across types, a property that constrains their possible behavior independently of the concrete type instantiation.

Theorems for free

Wadler showed that the type of a parametrically polymorphic function alone implies free theorems about its behavior, a direct and practical consequence of parametricity.

Type classes for principled overloading

Wadler and Blott introduced type classes, giving ad hoc polymorphism a coherent type-theoretic basis where overloaded operations are resolved by passing implicit dictionaries of method implementations.

Clinical relevance

Generics and polymorphism are central to reusable library design and collection frameworks across modern languages. Type classes and their analogues (traits, concepts, protocols) provide principled, type-safe overloading, while parametricity supports correctness reasoning and compiler optimizations.

History

System F, capturing parametric polymorphism, was discovered independently by Girard and Reynolds in the early 1970s. ML brought polymorphism with inference into practice. Cardelli and Wegner's 1985 survey classified the forms of polymorphism, Reynolds formalized parametricity in 1983, and Wadler and Blott's 1989 type classes shaped overloading in Haskell and influenced traits and concepts elsewhere.

Debates

Erasure versus reified generics

Language implementers debate compiling generics by type erasure, which is simple but loses runtime type information, versus reifying type parameters at runtime, which enables introspection at a cost in complexity and code size.

Key figures

• John Reynolds
• Jean-Yves Girard
• Philip Wadler
• Luca Cardelli
• Robin Milner

Seminal works

• reynolds1983
• wadler1989free
• wadler1989
• cardelli1985

Frequently asked questions

What is the difference between parametric and ad hoc polymorphism?

Parametric polymorphism applies one uniform implementation to all type arguments (as with generics), while ad hoc polymorphism selects a type-specific implementation, as with overloading or type classes.

What does parametricity give us?

Parametricity guarantees that a generic function treats all type instances uniformly, which yields 'free theorems' about its behavior derivable from its type signature alone.