Generics & Parametric Polymorphism

So far every function in our language has had a fixed type for each parameter: fun add(x: number, y: number): number. But a function like identity — one that just hands its argument back — shouldn't have to be rewritten once per type:

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

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

T here is a type variable (a type parameter): a placeholder that stands for "whatever type gets passed in at this call site." This is parametric polymorphism — one function definition, many concrete instantiations — as opposed to ad-hoc polymorphism (overloading), where you'd write a separate identity per type.

Type variables and instantiation

When the parser sees fun identity<T>(x: T): T, it records T as a bound type parameter for that function's scope, and stores the signature with T left abstract — the params and return type are still type expressions, just ones that can mention T instead of only concrete types like number or string.

The interesting work happens at the call site. Each call to a generic function creates a fresh copy of its type variables (so two calls to identity don't interfere with each other), then unifies those fresh variables against the types of the actual arguments:

1. Instantiate identity<T> with a fresh variable, say T0.
2. The parameter type becomes T0; unify T0 with the type of the argument (42 → number). Unification binds T0 = number.
3. Substitute that binding into the return type (T0), giving number as the result type of this call.

This binding-and-substitution process is exactly the algorithm used by Hindley–Milner type inference (the basis of ML, Haskell, and Rust's type inference) — you don't need the full algorithm here, but the shape is the same: generalize a definition over type variables, then instantiate + unify at each use.

Multiple type parameters and constraints

Generics extend naturally to more than one variable:

fun pair<A, B>(a: A, b: B): Pair<A, B> { ... }

Here two independent type variables get solved independently from the two arguments — pair(1, "hi") instantiates A = number, B = string.

A subtlety to watch for: if the same type variable appears in multiple parameter positions (fun same<T>(a: T, b: T): bool), unification must agree across all occurrences. If a gets bound to number and b's actual argument is a string, that's a type error — the two uses of T must resolve to the same concrete type.

Edge cases

• Unbound type variables: if T never appears in any parameter (only in the body or return position with no way to infer it from arguments), the type checker has nothing to unify against. Real languages either require an explicit type argument (identity<number>(...)) or reject the definition.
• Nested generics: a generic function calling another generic function needs its own type variables threaded through correctly — don't reuse the same name across unrelated instantiations.
• Nil/null arguments: a literal nil argument often can't determine T on its own; you may need to fall back to context (e.g., the expected return type) or report an error.

Your exercise: extend the type checker so that generic function declarations are parsed with their type parameter list, and each call site infers concrete types by unifying parameter types against argument types, substituting the result into the return type.