Generics & Parametric Polymorphism

Generics (also called parametric polymorphism) allow functions and classes to work with any type while maintaining type safety. Instead of writing separate functions for each type, you write one generic function.

Syntax

fun identity<T>(x: T): T {
    return x;
}

print identity(42);        // T = number, returns number
print identity("hello");   // T = string, returns string

The <T> declares a type parameter. When the function is called, T is instantiated with the actual argument type.

Why Generics Matter

Without generics, you would need separate functions:

fun identityNumber(x: number): number { return x; }
fun identityString(x: string): string { return x; }

Or use any, losing type safety:

fun identity(x: any): any { return x; }
var n: number = identity("oops");  // no error — but wrong!

Generics give you both: one function, full type safety.

Type Variable Instantiation

When identity(42) is called, the type checker:

1. Creates a fresh type variable T
2. Unifies T with the argument type number
3. The return type is T, which is now number

This reuses the unification algorithm from Hindley-Milner inference.

Constraints on Type Parameters

Some operations only make sense for certain types. We can add type bounds:

fun add<T: number>(a: T, b: T): T {
    return a + b;   // + requires numeric types
}

Without the bound, add("hello", "world") would type-check but + on strings might not be supported as addition.

How Languages Implement Generics

• Java: erasure — generics are removed at compile time, runtime uses Object
• C#/.NET: reification — generics exist at runtime, specialized code for value types
• C++: templates — essentially copy-paste at compile time, producing specialized code for each type
• Rust: monomorphization — like C++ templates, generic functions are compiled into specialized versions

For our interpreter, we use erasure — generic types are checked at compile time and then ignored during execution.

Multiple Type Parameters

Functions can have multiple type parameters:

fun pair<A, B>(first: A, second: B): Pair<A, B> {
    // ...
}

Your Task

Add generic type parameters to functions, implement instantiation through unification, and verify type correctness for generic function calls.