Back to series
· 8 min read

Generics and Parametric Polymorphism


I. What Are Generics

Generics is a mechanism that allows a program to use type parameters when defining functions, classes, interfaces, and data structures.

Traditional code usually requires writing duplicate implementations for different types:

class IntBox {
    private int value;

    public void set(int value) {
        this.value = value;
    }

    public int get() {
        return value;
    }
}

class StringBox {
    private String value;

    public void set(String value) {
        this.value = value;
    }

    public String get() {
        return value;
    }
}

The business logic of these two classes is almost identical; the only difference is the type of data being stored.

Generics can abstract the type into a parameter:

class Box<T> {
    private T value;

    public void set(T value) {
        this.value = value;
    }

    public T get() {
        return value;
    }
}

When using it, you specify the concrete type:

Box<Integer> intBox = new Box<>();
intBox.set(100);

Box<String> stringBox = new Box<>();
stringBox.set("hello");

Where:

  • T is a type parameter.
  • Integer and String are type arguments.
  • Box<T> is a generic type.
  • Box<Integer> and Box<String> are parameterized types.

The core of generics is not simply reusing code, but enabling code reuse while preserving type information and type constraints.

II. Parametric Polymorphism

Parametric polymorphism is a polymorphism mechanism that allows a program to describe a family of types using type parameters and, by substituting the type parameters, obtain implementations that work for different types.

For example:

public static <T> T identity(T value) {
    return value;
}

This function does not care whether the parameter is a String, an Integer, or some other type; it only requires that the input and output maintain the same type relationship.

Calling it:

String name = identity("Alice");
Integer age = identity(18);
Double score = identity(99.5);

The same function can be applied to many types.

1. Core Characteristics of Parametric Polymorphism

Type parameterization

Type variables are used to represent types that are not yet determined.

Unified implementation

Different types share the same set of algorithmic logic, rather than each type having its own copy of the implementation.

Preservation of type relationships

The relationships of type parameters across inputs, outputs, and data structures are constrained by the type system.

Type safety

In statically typed languages, the compiler can check whether the use of type parameters is valid.

2. The Relationship Between Generics and Parametric Polymorphism

The two are closely related, but they sit at different conceptual levels.

Concept Focus Example
Generics The type parameter mechanism provided by the language List<T>
Parametric polymorphism The polymorphic capability enabled by type parameters identity<T>(T)
Type parameter The type variable in a definition T
Type argument The concrete type supplied at the point of use String
Parameterized type The type after type parameters have been substituted List<String>

Generics are usually one important implementation form of parametric polymorphism in programming languages.

However, generics are not implemented in exactly the same way in every language. Some languages support full parametric polymorphism, while others achieve similar capabilities through type erasure, monomorphization, or other compilation mechanisms.

III. The Basic Components of Generics

1. Type Parameter

A type parameter is a placeholder type used when defining generics.

Common naming conventions:

Name Common meaning
T Type, a generic type
E Element, a collection element
K Key, the key type
V Value, the value type
N Number, a numeric type
R Return, the return type
S, U Other type parameters

These are only naming conventions, not something enforced by the language.

For example:

class Pair<K, V> {
    private K key;
    private V value;

    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }
}

Here there are two independent type parameters:

  • K describes the type of the key.
  • V describes the type of the value.

2. Type Arguments

A type argument is the concrete type supplied when using a generic type.

Pair<String, Integer> pair =
    new Pair<>("age", 18);

The correspondence:

Type parameter Type argument
K String
V Integer

Type parameters belong to the generic definition; type arguments belong to the generic use.

3. Generic Methods

Generics can be used not only on classes, but also on standalone methods.

public static <T> void print(T value) {
    System.out.println(value);
}

The <T> here declares the method's own type parameter.

The type parameters of a generic method and those of a class are two different levels.

class Processor<T> {

    public T process(T value) {
        return value;
    }

    public <R> R convert(T value, Function<T, R> converter) {
        return converter.apply(value);
    }
}

Where:

  • T is a class-level type parameter.
  • R is a method-level type parameter.

The method-level R can be inferred independently of the class-level T.

4. Generic Interfaces

interface Repository<T, ID> {
    T findById(ID id);

    void save(T entity);

    void deleteById(ID id);
}

When implementing it, you can specify concrete types:

class UserRepository implements Repository<User, Long> {

    @Override
    public User findById(Long id) {
        return null;
    }

    @Override
    public void save(User user) {}

    @Override
    public void deleteById(Long id) {}
}

Generic interfaces are well suited to defining general capabilities, leaving the concrete data types to the implementing class.

IV. Type Constraints on Generics

Generics do not mean that a type parameter can be used in any way whatsoever.

Which operations a type parameter can take part in depends on the constraints it satisfies.

For example:

public static <T> T max(T a, T b) {
    return a > b ? a : b;
}

This Java code will not compile, because the compiler does not know whether an arbitrary T supports the greater-than comparison.

You need to add a constraint to the type parameter.

1. Upper Bounds

Java can use extends to specify an upper bound for a type parameter:

public static <T extends Number> double sum(T a, T b) {
    return a.doubleValue() + b.doubleValue();
}

Here, T must be Number or a subtype of it.

Therefore, you can call:

sum(10, 20);
sum(10.5, 20.5);

But you cannot pass a type that does not satisfy the constraint:

sum("10", "20"); // compile error

The purpose of an upper bound constraint is to narrow the valid range of the type parameter, allowing the compiler to determine which capabilities the type has.

2. Multiple Upper Bound Constraints

Java supports multiple upper bounds:

public static <T extends Number & Comparable<T>>
T max(T a, T b) {
    return a.compareTo(b) >= 0 ? a : b;
}

Here, T must simultaneously satisfy:

  • be a subtype of Number.
  • implement Comparable<T>.

Note that in Java multiple upper bounds, the class type must come first, followed by interface types.

3. Lower Bound Constraints (Lower Bounds)

Java wildcards support lower bounds:

List<? super Integer>

This means the list element type is Integer or a supertype of it.

For example:

List<Integer> integers = new ArrayList<>();
List<Number> numbers = new ArrayList<>();
List<Object> objects = new ArrayList<>();

List<? super Integer> a = integers;
List<? super Integer> b = numbers;
List<? super Integer> c = objects;

It is necessary to distinguish:

  • <T extends Number> is a type parameter upper bound.
  • ? extends Number is a wildcard upper bound.
  • ? super Integer is a wildcard lower bound.

Java generic methods can declare upper bounds for type parameters, but cannot directly declare lower bounds for type parameters such as <T super Integer>.

4. The Essence of Constraints

The essence of generic constraints is to restrict the operations available to type parameters.

flowchart TD
    A["Declare generic type parameter T"] --> B["Whether a type constraint exists"]
    B -->|"No"| C["Only capabilities known for T can be used"]
    B -->|"Yes"| D["Check whether the type parameter satisfies the constraint"]
    D --> E{"Whether the constraint is satisfied"}
    E -->|"Yes"| F["Allow use of the capabilities provided by the constraint"]
    E -->|"No"| G["Type check fails"]
    F --> H["Generate or check the generic implementation"]

    style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style B fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style C fill:#E8EDF2,stroke:#B8C3CE,color:#334155
    style D fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style E fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style F fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style G fill:#FBE9E9,stroke:#D9AAAA,color:#334155
    style H fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    linkStyle default stroke:#A3B8AC,stroke-width:1.5px

V. Generics and Variance

A subtype relationship between generic type parameters does not necessarily mean that the generic types as a whole have the same subtype relationship.

Suppose:

Dog <: Animal

You cannot directly infer:

List<Dog> <: List<Animal>

Java generics are invariant by default.

1. Covariance

Covariance means that the subtype relationship of the type parameter has the same direction as the subtype relationship of the generic type as a whole.

List<? extends Animal>

Allows accepting:

List<Dog>
List<Cat>
List<Animal>

Suited for producer scenarios that read data.

2. Contravariance

Contravariance means that the subtype relationship of the generic type as a whole runs in the opposite direction of the subtype relationship of its type parameters.

List<? super Dog>

It can accept:

List<Dog>
List<Animal>
List<Object>

Suited for consumer scenarios that write data.

3. Invariance

The generic type as a whole does not establish any subtype compatibility relationship among its type parameters.

Java's List<T> is invariant.

4. The PECS Principle

The PECS principle is commonly used in Java generic design:

  • Producer Extends: producers use extends.
  • Consumer Super: consumers use super.
public static void copy(
    List<? extends Animal> source,
    List<? super Animal> target
) {
    for (Animal animal : source) {
        target.add(animal);
    }
}

Here:

  • source is responsible for providing Animal.
  • target is responsible for receiving Animal.

PECS is a practical principle for understanding Java wildcards, but it is not a variance syntax rule that applies to all languages.

6. Implementation Mechanisms of Generics

The syntax of generics is similar, but different languages differ greatly in how they implement them at the compiler and runtime levels.

There are mainly three implementation approaches:

  1. Type Erasure.
  2. Monomorphization.
  3. Retaining generic type information at runtime.

1. Type Erasure

Java generics mainly adopt the type erasure mechanism.

The compiler checks generic type constraints at compile time and erases most generic type parameter information when generating bytecode.

For example:

List<String> names = new ArrayList<>();
names.add("Alice");
String name = names.get(0);

At the bytecode level after compilation, collections mainly use the ordinary List type, with type casts inserted where needed.

This can be simplified and understood as:

List names = new ArrayList();
names.add("Alice");
String name = (String) names.get(0);

This is only an approximate illustration to aid understanding, not the complete actual compilation result.

Type erasure brings several important characteristics:

  • Generic type checking mainly occurs at compile time.
  • Ordinary generic type parameters are usually not retained as independent runtime types.
  • At runtime, generic collections usually cannot directly distinguish List<String> from List<Integer>.
  • The compiler may insert type casts.
  • The compiler may generate bridge methods to maintain generic override and polymorphic behavior.

For example:

List<String> strings = new ArrayList<>();
List<Integer> integers = new ArrayList<>();

System.out.println(strings.getClass() == integers.getClass());
// true

Here, what is compared is the actual class of the collection objects at runtime, not the complete parameterized type at compile time.

Note: Java does not completely discard all generics-related information. Metadata such as Signature in class files can retain part of the generic declaration information for use by compilers, reflection, and tools, but this does not mean that ordinary generic parameters can fully participate in type checking at runtime.

2. Monomorphization

Rust implements generics using monomorphization.

The compiler generates corresponding concrete implementations for different types based on the type parameters actually used.

For example:

fn identity<T>(value: T) -> T {
    value
}

fn main() {
    let a = identity(10);
    let b = identity("hello");
}

The compiler can generate specialized machine code instances for different types.

Conceptually, this can be understood as:

fn identity_i32(value: i32) -> i32 {
    value
}

fn identity_str(value: &str) -> &str {
    value
}

This is only illustrative code explaining the result of monomorphization, not the actual function names generated by the compiler.

Characteristics of monomorphization:

  • Generic implementations can generate specialized code for concrete types.
  • Usually no additional generic type dispatch is needed at runtime.
  • Helps the compiler with inlining and optimization.
  • Instances for different types may increase the final binary size.
  • Compile time may increase with the number of generic instantiations.

C++ templates also use a similar instantiation idea, but their template system's constraints and semantics are not the same as those of Rust generics.

3. Runtime Retention of Generic Information

Some languages or runtimes retain more generic type information.

For example, C# CLR generics support runtime generic type information, and the runtime can distinguish different constructed generic types.

List<string> names = new List<string>();
List<int> numbers = new List<int>();

Console.WriteLine(names.GetType());
Console.WriteLine(numbers.GetType());

The CLR can identify these different constructed generic types at runtime.

However, whether specific machine code generates an independent copy for every type also depends on the runtime implementation and the type parameter situation. You cannot simply assume that C# necessarily generates completely independent machine code for every generic type.

4. Comparison of Three Implementation Mechanisms

Comparison Dimension Type Erasure Monomorphization Runtime Retention of Generic Information
Representative Languages Java Rust, C++ templates C#
Type Checking Compile time Compile time Compile-time and runtime mechanisms working together
Runtime Information for Type Parameters Ordinary type parameters are usually erased Usually reflected through concrete instances Can retain constructed generic type information
Code Generation Implementation after generic erasure Instantiated by concrete type Determined by the runtime implementation
Runtime Dispatch Overhead Usually not increased by generics themselves Usually no generic dynamic dispatch is needed Depends on the specific implementation
Code Size Usually smaller May increase Depends on the runtime strategy