Type Systems and Generics

Keywords

type systems, generics, templates, traits, static typing, gradual typing, structural typing, nominal typing, type inference, variance, monomorphization, type erasure, metaprogramming, polymorphism

Introduction

The same bug arrived three times in one quarter, in three different languages, on three different teams that never spoke to each other — and that coincidence is the whole reason this chapter exists.

The first team ran a Python service whose cache was, by every comment and variable name, a dictionary of user records. One Tuesday a request pulled an entry, called .name on it, and got an AttributeError: somewhere upstream a code path had stored a primary-key integer where a user object belonged. Nothing had complained when it was written. The error surfaced months later, far from the line that caused it, in code that had done nothing wrong.

The second team ran the identical service in Java. Their cache was declared Map<String, User> — typed, checked, safe. Except a “convenience” loader written under deadline took a raw Map to avoid threading the generic signature through four call sites, and on one rare path it put a Long where a User belonged. The compiler said nothing it couldn’t say: a raw map accepts any Object. Months later a read fired a ClassCastException — from a cast the compiler had inserted on the developer’s behalf and then erased the type behind.

The third team had it in TypeScript. They maintained three near-identical User interfaces — database row, API response, edit-form state — by hand. Someone added a phoneNumber field, updated two of the three, and shipped. The phone number saved to the database and silently vanished every time a user edited their profile, because the form’s type didn’t know the field existed. Three copies that could disagree, and one finally did.

Three languages, three “the type drifted and the failure surfaced far away” incidents — and three completely different underlying mechanisms. Python checks types when it runs, if at all. Java checks them at compile time and then throws them away. TypeScript checks structure, not names, and erases everything before the JavaScript runs. The same class of bug, expressed through three different machines. This chapter is about those machines: how six languages answer the question “what is a type, when is it checked, and what survives to run time” — and why understanding the answer in one language makes you faster in all the others.

The Core Insight

Every type system is a machine that answers two questions, and almost every difference between languages is a different answer to one of them.

The first question is when. When does a type error surface — while the program runs, or before it ever does? This is the dynamic-to-static spectrum. At one end, Python checks nothing until the offending line executes (and a wrong type is a run-time TypeError). In the middle sit the gradual systems — Python with a checker like mypy, and TypeScript — where annotations are optional, checked before the program runs, and then erased, leaving plain code that carries no type information at all. At the far end sit the static languages — Go, Java, C++, Rust — where a wrong type is a compile error that simply never ships.

The second question is what survives. Once you have generic code — a List of T, a function over “any orderable type” — what does the compiler actually produce? There are exactly three answers, and every language picks one. Type erasure (Java, TypeScript): check the types, insert the casts, throw the parameter away — one body serves every type, and at run time the type is gone. Monomorphization (C++, Rust, Go in part): stamp out a separate, fully specialized copy of the code for each concrete type — the abstraction evaporates and what runs is as fast as hand-written code. Structural constraints (Go interfaces, TypeScript shapes): constrain a type by the operations it supports rather than the name it was given, and dispatch through an interface when the concrete type isn’t known.

Hold those two axes in your head and the entire landscape becomes legible. The “same idea, different machinery” pattern repeats at every level: a List of strings, a function bounded to “things that can be compared,” a way to ask “is this type orderable” — each one shows up in all six languages, implemented six ways, with six different cost profiles. Learn the axes once and you stop relearning generics per language; you start translating between them.

A mental model

Picture a type system as a bouncer with a memory policy.

Every bouncer checks IDs at the door — that is type-checking, and even Python does it, just inside the club, the moment you try to do something with a value. What separates the languages is two further choices. First, where the door is: a static language checks at the entrance (compile time) and turns away anyone who doesn’t qualify; a dynamic language lets everyone in and checks only when they try to order a drink (run time). Second, what the bouncer remembers. A Java or TypeScript bouncer is meticulous at the door and then keeps no record inside — the wristband is checked and discarded, so at run time nobody can ask what type anyone was admitted as (this is erasure). A C++ or Rust bouncer doesn’t just check the ID; it stamps out a dedicated, private room for each type that walks in, furnished exactly for that type (monomorphization). A Go bouncer doesn’t check names at all; it checks whether you can do the things the club requires — can you Read, can you Write — and admits anyone who can, regardless of who they are (structural typing).

Figure 3.1 lays this out as one picture: the when axis across the top, the what survives machinery across the bottom, and the four-named-but-one idea of bounded constraints tying them together. Keep it open as you read — every section below is one region of that map.

When to reach for static, gradual, or dynamic typing

The spectrum is not a quality ranking. Each region is the right answer for a different job, and mature engineers move along it deliberately rather than defaulting to whatever their primary language enforces.

Reach for dynamic typing when iteration speed dominates and the cost of a run-time type error is low and local — exploratory data analysis, a one-off script, a notebook, glue code you will read once. Python earns its place here precisely because it gets out of your way; demanding type proofs before you know what you’re building is friction with no payoff.

Reach for gradual typing when a codebase outgrows “small enough to hold in your head” but you can’t or won’t rewrite it. This is the most common real-world position: a Python service that adds mypy and Protocols to its public boundaries while leaving the glue untyped, or a JavaScript front-end migrated to TypeScript file by file. Gradual typing lets you buy safety incrementally, paying for proof exactly where bugs are expensive and skipping it where they aren’t.

Reach for static typing when the program is large, long-lived, edited by many people, or performance-critical — and especially when a type error in production is expensive. The compiler becomes a tireless reviewer that checks every refactor against every call site before a single test runs. Within static, the further choice is what the generics cost: Java and TypeScript erase (small binaries, runtime introspection limits); C++ and Rust monomorphize (zero run-time cost, larger binaries, slower builds); Go interfaces and TypeScript shapes constrain structurally (maximum decoupling, often one indirection per call). The decision diagram in Figure 3.1 is the map; the rest of this chapter is the territory.

What you’ll learn

Why the dynamic-to-static spectrum is really two axes — when types are checked and what survives to run time — and how to place any language on both
The difference between nominal typing (satisfy an interface by declaring it) and structural typing (satisfy it by having the right shape), and which languages choose which
How parametric polymorphism is implemented four ways — Java’s type erasure, C++’s and Rust’s monomorphization, Go’s type parameters, and TypeScript’s generics — and the cost each one pays
How the single idea of bounded quantification wears four names: Rust trait bounds, C++20 concepts, Java bounded wildcards (PECS), and TypeScript extends constraints
What variance is, why Java forces you to spell it with wildcards while other languages infer or fix it, and the rule that keeps it sound
How type inference ranges from var/auto local inference to TypeScript’s pervasive flow analysis, and where each stops
What type-level programming is — TypeScript’s conditional and mapped types, C++ template metaprogramming, Rust associated types — and where its leverage and its footguns both live

Prerequisites

Software Engineering Overview — the role of a type system as a design and verification tool, and the build-vs-runtime distinction this chapter leans on constantly
TypeScript Fundamentals — generics (<T>), keyof, unions and intersections, and the idea that a type is a set of values
Rust Fundamentals — basic generic syntax, Option/Result, and enough trait vocabulary to read a bounded signature

Two axes, six languages

Before any code, fix the map. The two questions from the Core Insight — when are types checked, and what survives to run time — sort the six languages cleanly, and the sort is more useful than any per-language list of features. The first table places each language on the when axis.

Language	When checked	A wrong type is…	Position
Python (bare)	Run time only	a `TypeError` when the line executes	Dynamic
Python + mypy	Compile-ish (checker) + run time	a checker error; runs anyway if you ignore it	Gradual
TypeScript	Compile time, then erased	a `tsc` error; the JS runs with no types	Gradual
Go	Compile time	a compile error; never ships	Static
Java	Compile time, then erased	a compile error (or a later `ClassCastException`)	Static, erased
C++	Compile time	a compile error	Static
Rust	Compile time	a compile error	Static

The crucial subtlety hiding in that table is that “static” and “erased” are independent. Java is fully static — the compiler rejects strings.add(42) — and yet its generics erase, so at run time a List<String> and a List<Integer> are the same class. TypeScript is gradual and also erases. C++ and Rust are static and don’t erase: they monomorphize, producing real per-type code. Erasure is about the what survives axis, not the when checked axis, and conflating the two is the single most common confusion in this whole subject.

That second axis — what the compiler does with generic code — is where the languages diverge most sharply, and it is the spine of everything that follows.

Language	Generics implemented by	Survives to run time?	Run-time cost	Pays in
Java	Type erasure	No — type gone, casts inserted	Indirection on bounded reads	Lost run-time type info
TypeScript	Erasure (full)	No — types vanish entirely	None (it’s just JS)	No run-time enforcement at all
C++	Monomorphization (templates)	Yes — a copy per type	Zero	Binary size, build time
Rust	Monomorphization (generics + traits)	Yes — a copy per type	Zero (static dispatch)	Binary size, build time
Go	Monomorphization + dictionaries (hybrid)	Partly	Small	Some indirection
Go / TS (interfaces)	Structural constraints	Interface value at run time	One indirection per call	Flexibility for a vtable hop

Read the two tables together and you have the chapter in miniature: the when table is about safety and ergonomics, the what survives table is about cost and capability, and every language is a point in that two-dimensional space. The rest of this chapter walks the regions.

Dynamic, gradual, static: the same `add` three ways

The cleanest way to feel the spectrum is to write the same trivial mistake — adding a number to a list of strings — and watch when each language objects.

In bare Python, nothing objects until something downstream trips over the intruder. The list happily holds mixed types; the failure is deferred to whoever assumes otherwise.

Python (bare — caught at run time, if at all):

names = ["alice", "bob"]
names.append(42)              # no complaint here
greeting = "hi " + names[2]   # TypeError, far from the append

Add a checker and the annotation, and the same code is flagged before it runs — but notice the annotation is advisory. mypy will object; the interpreter will not. This is gradual typing’s defining property: the type layer is a separate, optional pass.

Python (gradual — mypy objects, the interpreter still runs it):

names: list[str] = ["alice", "bob"]
names.append(42)              # mypy: error — int not assignable to str
                              # python: runs fine; the annotation is advisory

TypeScript sits in the same gradual region, but its checker is the default build step, so the error is harder to ignore — and then, importantly, the type vanishes. What ships is JavaScript with no memory that names was ever string[].

TypeScript (gradual — tsc errors, then erases to plain JS):

const names: string[] = ["alice", "bob"];
names.push(42);   // tsc: Argument of type 'number' is not assignable to 'string'
                  // compiled JS: the type is gone; only the array remains

A static language refuses to produce a runnable artifact at all. Go, Java, C++, and Rust each reject this at compile time; there is no “runs anyway.” The difference between them is not whether they catch it but what they keep afterward — which is the next axis.

The lesson of the trio is that “typed vs untyped” is the wrong dichotomy. Python can be typed; TypeScript’s types can be ignored at run time. The real questions are when the check fires and whether you’re allowed to ship past a failure — and gradual typing exists precisely to let a team slide along that axis one module at a time.

Nominal vs structural: how a type satisfies an interface

The next axis cuts across the static languages: when a type claims to satisfy an interface, how is that claim verified? There are two answers, and they shape API design more than almost anything else.

Nominal typing verifies by declared name. A Java class is a Comparable only if it says implements Comparable; a Rust type has a trait only if you write an impl block. The relationship is established at the point of definition, by an explicit declaration, and the type author must opt in.

Structural typing verifies by shape. A Go type satisfies an interface if it has the required methods — no implements, no registration, no inheritance. A TypeScript object matches a type if it has the required fields. The relationship is established structurally, wherever the type is used, and the type author need not even know the interface exists.

The same “this can be drawn” capability, declared four ways, makes the split concrete. Java is nominal — Circle must announce the interface:

interface Drawable { void draw(); }
class Circle implements Drawable {     // must declare it
    public void draw() { /* ... */ }
}

Rust is also nominal, via an explicit impl — but the trait can be written long after the type, and for a type you don’t own:

trait Drawable { fn draw(&self); }
struct Circle { r: f64 }
impl Drawable for Circle {             // explicit impl, but decoupled in time
    fn draw(&self) { /* ... */ }
}

Go is structural — Circle satisfies Drawable for free, by having Draw, with no declaration anywhere connecting them:

type Drawable interface { Draw() }
type Circle struct{ R float64 }
func (c Circle) Draw() { /* ... */ }   // no "implements" — the shape is the contract

TypeScript is structural at the level of object shapes — any value with the right members fits, even an anonymous literal:

interface Drawable { draw(): void; }
const circle = { r: 1, draw() { /* ... */ } };   // never named Drawable
const d: Drawable = circle;                       // …but structurally it is one

The trade-off is real in both directions. Nominal typing makes intent explicit and prevents accidental conformance — two types with a method called close() that mean totally different things won’t be confused, because neither declared the interface. It also gives a stable, searchable answer to “what implements this?” Structural typing maximizes decoupling — you can define a one-method interface at the consumer and have every existing type satisfy it without modification, which is exactly why idiomatic Go interfaces are tiny and live where they’re used. Rust threads the needle: it is nominal (explicit impl) but, unlike Java’s class hierarchy, lets a type implement any number of unrelated traits and lets traits be added after the fact — capability without taxonomy.

Note

Structural typing has a sharp edge worth naming: a type can satisfy an interface by accident. A Go struct that happens to have a String() string method silently becomes a fmt.Stringer, changing how it prints, even if the author never intended it. Nominal systems make that impossible by construction. Neither is “better” — they’re optimizing for different failure modes.

Parametric polymorphism, four ways

Now the heart of the chapter. Parametric polymorphism — writing one piece of code that works uniformly across many types, a List of T, a max over any orderable type — is the feature every modern language has, and the feature each implements completely differently. The differences are not cosmetic; they determine binary size, run-time cost, what you can introspect, and what errors look like. We’ll take them in order of how much survives to run time, from nothing (erasure) to everything (monomorphization).

Java: type erasure

Java generics are a compile-time fiction. The compiler uses the type arguments to check your code rigorously — it rejects strings.add(42), it lets you skip casts on reads — and then it erases them. The bytecode that ships sees only Object, or, if the parameter is bounded, the bound. A List<String> and a List<Integer> are the same class at run time: plain List. There is one ArrayList class, not one per element type.

This is visible in a single line — the kind of fact that explains everything downstream:

List<String>  strings  = new ArrayList<>();
List<Integer> integers = new ArrayList<>();
System.out.println(strings.getClass() == integers.getClass());   // true

The <String> lived only in the compiler. Every read of a List<String> element gets a CHECKCAST String instruction the compiler wrote so you didn’t have to — and that inserted cast is what throws the ClassCastException in the opening story, far from the raw-type line that planted the wrong value. Erasure is also why you cannot write new T() (no T to construct at run time), cannot create a T[] (an array needs a runtime element type to check its stores), and cannot test obj instanceof List<String> (at run time there is only List). Each prohibition is the absence of a runtime type the compiler already discarded. When you genuinely need the type back, you carry it by hand as a Class<T> token — the reified type, re-supplied. Erasure buys backward compatibility and small binaries; it costs you the type at run time. Figure 3.1 places it at the “nothing survives” end of the machinery axis.

TypeScript: full erasure

TypeScript erases even more completely than Java. Java keeps the bound and inserts casts; TypeScript’s types vanish entirely, because the output is JavaScript and JavaScript has no type system to receive them. A generic function is, after compilation, an ordinary untyped JS function. This is liberating and dangerous in equal measure: there is zero run-time cost (the types were never there), and zero run-time enforcement (a value that lies its way past the compiler — via any, an unchecked cast, or untyped JSON — is never caught). The generic itself reads familiarly:

function first<T>(items: T[]): T | undefined {
  return items[0];   // T is checked at compile time, then erased to nothing
}
const n = first([1, 2, 3]);   // T inferred as number; at run time, just JS

The practical consequence is that TypeScript’s safety is entirely a development-time guarantee. It cannot validate data crossing a run-time boundary — which is why schema libraries (Zod and friends) exist: to re-establish, at run time, the types the compiler threw away.

C++ and Rust: monomorphization

Now the opposite end. C++ templates and Rust generics keep everything — by generating a separate, fully specialized copy of the code for each concrete type. This is monomorphization, and it is the same idea in both languages despite different syntax. When you call a generic max with two ints, the compiler stamps out a concrete int max(int, int); call it with doubles and you get a second function. They share source, not object code; each is as fast as a hand-written version because, after instantiation, that is exactly what it is.

C++ calls the pattern a template and the per-type copy an instantiation:

template<typename T>
T max_value(T a, T b) { return (a > b) ? a : b; }   // the stencil

// max_value(3, 5)     -> stamps out int  max_value(int, int)
// max_value(1.0, 2.0) -> stamps out double max_value(double, double)

Rust expresses the same machine with generics constrained by traits — and the trait bound is mandatory, which (as we’ll see under bounds) is the difference that spares Rust C++’s historical error avalanche:

fn max_value<T: PartialOrd>(a: T, b: T) -> T {       // T must be orderable
    if a > b { a } else { b }                        // monomorphized per concrete T
}

The payoff is zero-cost abstraction: a generic call is a direct call the compiler can inline, with no boxing and no virtual dispatch — the genericity exists only in the source. The cost is equally real but it moved: to compile time and binary size, because a template or generic used with twenty types compiles into twenty copies. That is code bloat, the structural cost of monomorphization, and it is why “make everything generic” is a mistake — you are asking the compiler to write a great deal of code.

Go: the hybrid

Go added generics late (1.18, 2022) and chose a middle path on purpose. Rather than committing fully to monomorphization (binary bloat) or erasure (lost performance), the Go compiler can share one generic implementation across types with the same underlying memory shape via a runtime dictionary, while specializing where it pays. A Go generic uses type parameters with constraints, where a constraint is just an interface describing what the type must support:

type Ordered interface { ~int | ~float64 | ~string }   // a constraint set

func Max[T Ordered](a, b T) T {   // T constrained to orderable types
    if a > b { return a }
    return b
}

The ~int syntax means “int or any type whose underlying type is int,” and the union spells out exactly which types qualify — a structural constraint expressed as an interface. Go’s choice reflects its whole philosophy: a pragmatic compromise that keeps binaries reasonable and builds fast, accepting some indirection rather than chasing the last increment of either erasure’s compactness or monomorphization’s speed.

The four-way comparison is the thing to carry away. Same idea — one body of code over many types — four machines: erase and insert casts (Java), erase entirely (TypeScript), stamp out a copy per type (C++, Rust), or share-and-specialize (Go). Each trades run-time cost against binary size against introspection, and no choice is free.

Build it → Monomorphization on a hot path, made concrete: the Project 17: Columnar Query Engine uses static dispatch over column types to keep per-row work inlinable — and falls back to trait objects over operators where types are chosen at run time, the static/dynamic split in one codebase.

Bounded quantification: the same idea, four names

An unbounded type parameter is nearly useless. If T can be anything, you can do almost nothing with it — only the operations every type supports. The power of generics comes from bounds (formally, bounded quantification): “T, but only types that can be ordered,” “T, but only types that can be added.” A bound is a contract in two directions — callers may supply only types that satisfy it, and in return the body may rely on the operations the bound promises.

This single idea wears four names across the languages, and seeing them side by side is the fastest way to internalize that they are the same thing. The bound below — “T must be orderable” — is the canonical example.

Rust — a trait bound, mandatory and checked at the call site:

fn largest<T: Ord>(items: &[T]) -> &T { /* can call .cmp because T: Ord */ }

C++20 — a concept, a named constraint that replaced the unreadable SFINAE idiom:

template<std::totally_ordered T>          // named, checkable, one-line errors
T largest(const std::vector<T>& items);

Java — a bounded type parameter (and, for variance, bounded wildcards):

static <T extends Comparable<T>> T largest(List<T> items) { /* T has compareTo */ }

TypeScript — an extends constraint on the type parameter:

function largest<T extends { compareTo(o: T): number }>(items: T[]): T { /* ... */ }

Four syntaxes, one concept: each constrains T to a capability and unlocks exactly the operations that capability provides. The deep difference is when the bound is checked and how the error reads when it fails, and here the languages tell a striking historical story. Rust and C++20 check the bound at the call site, up front: pass a type that doesn’t satisfy Ord or std::totally_ordered and you get one clean error naming the missing capability — before the generic body is ever instantiated. C++ before concepts did not have this. A template with no constraint deferred every type error to the deepest point it could fail, deep inside the template body, producing the legendary four-hundred-line substitution-failure avalanche for a one-line mistake. Concepts (C++20) fixed it by making the constraint a named, first-class predicate — arriving, late but well, exactly where Rust’s mandatory trait bounds had been all along. The lesson generalizes past any one language: constrain your public generics, and you move the error from the library’s guts to the call site, and from a stack trace to a sentence.

Variance: when is a container of subtypes a container of supertypes?

Bounds answer “what can T be?” Variance answers a subtler question: given that Cat is an Animal, is a List<Cat> a List<Animal>? The intuitive “yes” is, in general, unsound, and how each language handles that is one of the most error-prone corners of type systems.

The reason the intuitive answer is wrong is worth seeing once, concretely. Suppose List<Cat> were a List<Animal>. Then you could assign it to a List<Animal> variable and, through that variable, add(new Dog()) — because a Dog is a valid Animal. Now your List<Cat> contains a Dog, and the next code to read a Cat out of it gets a nasty surprise. To prevent exactly this, languages make generic containers invariant by default: a List<Cat> is simply not a List<Animal>, full stop, even though Cat is an Animal.

Invariance is safe but stifling — it would block the perfectly reasonable “sum any list of numbers.” The fix is to let you opt into variance where it’s sound:

Covariance (? extends T): a producer you only read from. A List<? extends Number> can be a List<Integer> or a List<Double>; you may read Numbers out, but you may not add anything, because the exact element type is unknown.
Contravariance (? super T): a consumer you only write into. A List<? super Integer> accepts Integers for writing, but a read gives back only Object.

Java forces you to spell this out at every use site with wildcards, and the mnemonic is PECS — Producer Extends, Consumer Super. The canonical copy captures all three positions in one signature:

static <T> void copy(List<? extends T> src,   // producer: read T out (covariant)
                     List<? super T>   dst) {  // consumer: write T in (contravariant)
    for (T item : src) dst.add(item);
    // src.add(item);  // REJECTED — src's exact subtype is unknown, adds unsafe
    // T x = dst.get(0);  // REJECTED — a read from dst yields only Object
}

TypeScript handles variance largely by inference — its structural checker computes whether a position is co- or contravariant from how the type parameter is used, and function parameters are (under strict settings) contravariant automatically. C++ templates mostly sidestep variance because each instantiation is an independent type with no subtype relationship to enforce. Rust ties variance to lifetimes and ownership and infers it from a type’s structure rather than asking you to annotate it. The common thread: variance is the rule that keeps a “container of subtypes” from being silently treated as a “container of supertypes” you could corrupt — and the languages differ mainly in whether they make you write it down (Java), infer it (TypeScript, Rust), or rarely need it (C++).

Language	Default	How variance is expressed
Java	Invariant	Explicit use-site wildcards (`? extends` / `? super`, PECS)
TypeScript	Inferred	Computed structurally; params contravariant under strict mode
C++	N/A per instantiation	No subtype relation between instantiations to vary
Rust	Inferred	Derived from structure, tied to lifetimes/ownership
Go	Invariant	No declaration-site variance; interfaces sidestep it

Type inference: how much can the compiler figure out?

A type system you have to spell out completely is a chore; a good one infers. Inference ranges from modest local deduction to whole-program flow analysis, and where a language sits shapes how much annotation noise you live with.

The modest end is local inference: the compiler deduces a variable’s type from its initializer, but signatures must still be annotated. C++’s auto, Java’s var, Go’s :=, and Rust’s let (within a function body) are all this. They eliminate the redundant left-hand-side type while leaving function boundaries explicit:

auto count = items.size();          // C++: deduced from the right-hand side

var users = new ArrayList<User>();  // Java: inferred ArrayList<User>

users := make(map[string]int)       // Go: inferred map[string]int

let total = nums.iter().sum::<i64>(); // Rust: inferred from context + turbofish

The rich end is flow-based, near-whole-expression inference, and TypeScript is its poster child. It infers generic type arguments from usage, narrows types through control flow (if (typeof x === "string") makes x a string in that branch), and propagates types through long chains without annotation. Rust sits between the poles: its inference is powerful — it solves for type parameters from later usage, not just the initializer — descending from the Hindley–Milner tradition of letting the compiler reason globally within a function, though it stops at function signatures by design, which it treats as documentation worth requiring.

The design tension is constant: more inference means less typing and less visual noise, but also less locally obvious code — a variable whose type you must mentally compute, or hover in an editor to see. Every language draws the line somewhere, and the modern consensus is “infer aggressively inside a function, require annotations at its boundaries,” because a signature is read far more often than it’s written and its types are documentation.

Type-level programming: computing with types

At the far reach of every static type system is the realization that the type checker is itself a small programming language — one whose values are types and whose execution happens at compile time. This is type-level programming, and it is where the languages’ expressive ceilings diverge most.

TypeScript’s type system is, famously, a Turing-complete functional language that computes types from types. It has conditionals (T extends U ? X : Y), iteration (mapped types walk a type’s keys), and pattern-matching extraction (infer). This is what powers deriving one type from another so they cannot drift — the cure for the three-User- interfaces bug from the introduction. The API type is the domain type minus a field; the form type is the domain type with every field optional — each computed, not copied:

interface User { id: number; name: string; email: string; passwordHash: string; }

type ApiUser   = Omit<User, "passwordHash">;   // derived: change User, this re-derives
type UserDraft = Partial<User>;                // every field optional, for form state

Omit and Partial are themselves written in the type-level language — Partial<T> is a mapped type that walks T’s keys and adds ? to each. Conditional types plus infer let you extract pieces (ReturnType, Awaited), and template literal types bring the same computation to strings (typed routes from a path string). The leverage is enormous at boundaries — derive an API, a form, and a validator from one source of truth — and a footgun in the middle, where a baroque four-infer-deep type saves three lines of duplication at the cost of an error message no teammate can decode.

C++ reaches the same compile-time-computation ceiling through a different door: template metaprogramming, constexpr functions, and if constexpr, which lets one function body compile entirely different code paths per type, with the untaken branch discarded before it is even type-checked:

template<typename T>
auto describe(T value) {
    if constexpr (std::is_integral_v<T>) return value * 2;        // only path for ints
    else if constexpr (std::is_floating_point_v<T>) return value * 1.5;
    else return value;                                            // illegal-for-int code OK here
}

Rust’s type-level computation is deliberately more restrained — by design, it has no Turing-complete type-level language — but it expresses the most important pattern, associated types, with unusual clarity. An associated type captures “exactly one related type per implementor”: an Iterator yields one element type, so Item is an associated type, not a generic parameter, which keeps signatures clean and forbids the nonsensical “this type is an iterator of both u8 and String”:

trait Iterator {
    type Item;                              // one element type per implementor
    fn next(&mut self) -> Option<Self::Item>;
}

Java and Go sit far down this axis on purpose. Java’s erased generics can’t compute much at the type level — there’s no type to compute with at run time, and the compile-time machinery is intentionally limited. Go went further still, omitting generics entirely for thirteen years and adding only a deliberately minimal version, precisely to avoid the metaprogramming complexity that C++ and TypeScript embrace. The spectrum here is not capability-for-its-own-sake; it is a values choice about how much compile-time cleverness a language wants its users wielding — and the cost, in every case, is paid by whoever has to read the type later.

War story: the type nobody could touch

A platform team’s shared types package contained a single exported utility — call it DeepRecursivePartialReadonlyNonNullable — that recursed into nested objects, made every property optional, marked every property readonly, and stripped null, all in one twelve-line conditional-mapped type. It worked, mostly, and it was the most-feared type in the codebase. When someone added a Map-valued field, the type recursed into the Map’s internals, produced a shape nobody recognized, and tipped over TypeScript’s recursion limit with a TS2589 “excessively deep” error. The on-call engineer spent an afternoon not fixing the bug but understanding the type — then gave up and cast with as, reintroducing exactly the unsafety the type existed to prevent. The fix was to delete it and compose three small, separately-hover-able types applied in sequence. The lesson is the same one C++ learned with its four-hundred-line template errors, in a different language: simple types that compose beat one clever type that doesn’t. Compile-time power that no teammate can read isn’t safety — it’s a wall, and walls get climbed over with as and casts.

Build it → Type-level machinery driving a real system: the Project 18: Compiler / Interpreter implements a type checker and inference engine from scratch — the algorithms behind everything in this section — and the Project 31: ML Compiler uses typed intermediate representations and generic graph passes where the type system is load-bearing for correctness.

Practical exercise

Difficulty: Level I · Level II · Level III

Level I — Place the same program on both axes. Write a tiny Stack of a generic element type in three languages of your choice spanning the spectrum (e.g. Python with type hints, TypeScript, and Rust). For each, answer in one or two sentences: (a) when is a type error caught — run time, checker, or compiler? and (b) what survives to run time — is the element type erased, monomorphized into a per-type copy, or carried in an interface value? Then locate each of your three on Figure 3.1 and confirm your answers match where the diagram places that language. The goal is to feel that “generic stack” is one idea with three machines underneath.
Level II — Bound it, then break it, in two languages. Pick one monomorphizing language (Rust or C++) and one erasing language (Java or TypeScript). In each, write a generic max constrained to “orderable” types — a Rust trait bound, a C++20 concept, a Java bounded type parameter, or a TypeScript extends constraint. Then call it with a type that isn’t orderable (a struct with no comparison) and paste the error. In a paragraph, compare: does the error fire at the call site or deep in the generic body? Does it name the missing capability? Relate the difference to the chapter’s claim that “constrain your public generics” moves errors from a stack trace to a sentence — and to why C++ before concepts produced four-hundred-line avalanches.
Level III — Demonstrate variance and derive a type. Two parts, in the languages that make each natural. (a) Variance: in Java, write the PECS copy(List<? extends T> src, List<? super T> dst), then show by failing compiles exactly why you cannot add to the producer or read a T from the consumer — and explain, with the Cat/Dog argument, the corruption invariance prevents. (b) Derivation: in TypeScript, start from one Order interface and derive an ApiOrder (without an internal field) and an OrderDraft (every field optional) using only type-level operators — no second hand-written interface. Add a field to Order and confirm both derivations update themselves. Then write the harder half as an essay: identify where you would stop adding type-level cleverness, and justify the line in terms of who has to read the types later — the war story’s thesis, applied to your own code.

Summary

A type system is a machine that answers two largely independent questions, and almost every difference between languages is a different answer to one of them. The first is when types are checked — at run time (dynamic Python), at compile time but optional and erased (gradual Python+mypy and TypeScript), or at compile time and mandatory (static Go, Java, C++, Rust). The second is what survives to run time once you write generic code: type erasure throws the parameter away and inserts casts (Java) or vanishes entirely (TypeScript); monomorphization stamps out a fully specialized copy per type for zero-cost abstraction at the price of binary size (C++, Rust); structural constraints match by shape and dispatch through an interface (Go, TypeScript). Across the static languages, a second axis is how a type satisfies an interface — nominally by declaration (Java implements, Rust impl) or structurally by shape (Go, TypeScript). The single idea of bounded quantification appears four times — trait bounds, concepts, bounded wildcards, extends constraints — and the languages that check bounds up front (Rust, C++20) give one-line call-site errors where unconstrained templates once gave avalanches. Variance is the soundness rule that keeps a container of subtypes from being abused as a container of supertypes, spelled explicitly in Java (PECS) and inferred elsewhere. Inference ranges from local (var, auto) to pervasive (TypeScript). And type-level programming is the realization that the checker is itself a compile-time language — most expressive in TypeScript and C++, deliberately restrained in Rust and Go — whose power is leverage at boundaries and a footgun in the middle.

Key takeaways

“Typed vs untyped” is the wrong axis. The real ones are when types are checked (dynamic → gradual → static) and what survives to run time (erasure → structural → monomorphization) — and they’re independent: Java is static and erased.
Generics are implemented four ways: erase-and-cast (Java), erase-entirely (TypeScript), monomorphize (C++, Rust), and a share-or-specialize hybrid (Go). Each trades run-time cost against binary size against introspection.
Nominal typing (declare the interface) prevents accidental conformance and answers “what implements this?”; structural typing (have the shape) maximizes decoupling and tiny consumer-defined interfaces. Rust is nominal-but-decoupled; Go is structural.
Bounded quantification is one idea with four names; the win of checking bounds at the call site is one-line errors — “constrain your public generics.”
Type-level power is leverage at boundaries and a liability in the middle; an unreadable type, like an unreadable template error, gets worked around with a cast and stops being safe at all.

Connections to other chapters

Software Engineering Overview (prerequisite): this chapter is the deep version of the “a type system is a verification tool you choose how much to lean on” idea framed there — the dynamic-to-static spectrum is one of the core language-design axes, made concrete across six languages.
Concurrency and Parallelism Models (extension): Rust’s Send/Sync marker traits turn data-race freedom into a trait bound the compiler checks — the type-system machinery of this chapter becoming the concurrency-safety mechanism of that one. The bounded-quantification idea here is literally what enforces thread safety there.
Memory and Resource Management (sibling): monomorphization’s zero-cost story is inseparable from layout — a Stack<int> stores raw ints inline, an erased List<Integer> boxes them on the heap. The “what survives to run time” axis is a memory decision, and the newtype-and-monomorphization patterns here are why Rust abstractions cost nothing in space either.
Error Handling (sibling): how a language models failure in its types — Rust’s Result<T, E>, TypeScript’s discriminated unions, Java’s checked exceptions — is bounded quantification and variance applied to the error channel; the generics here are what make Result<T, E> a type you can compute with rather than a convention.
Performance and Profiling (extension): the templates-vs-virtual and static-vs-dynamic-dispatch decisions in this chapter are performance decisions there — the inlining and devirtualization that monomorphization enables are exactly what the performance chapter measures, and the “zero-cost” claim is one it puts on a profiler.
Compiler / Interpreter and Columnar Query Engine (projects): a type checker and inference engine are built from scratch in the compiler project, and the static/dynamic dispatch split is load-bearing in the query engine — the abstractions of this chapter as running systems.

Pierce, Types and Programming Languages — the canonical text on type systems: the formal treatment of parametric polymorphism, subtyping, variance, and inference that this chapter surveys informally across languages.
Bloch, Effective Java (3rd ed.), Items 26–33, and Vanderkam, Effective TypeScript, Items 19–33 — the two best practitioners’ guides to generics in an erasing language and a gradually-typed one, read side by side for the contrast.

Deep dives

The Rust Programming Language (Klabnik & Nichols), chapters 10, 17, 19, and Vandevoorde, Josuttis & Gregor, C++ Templates: The Complete Guide (2nd ed.) — the monomorphizing pair: traits + generics in Rust and templates + concepts in C++, the same zero-cost idea worked through in both.
TypeScript Handbook — Conditional and Mapped Types and the Type Challenges puzzle set — the deep end of compile-time type computation, and the best way to build fluency in type-level programming and feel where its footguns live.

Historical context

Wadler & Blott, “How to make ad-hoc polymorphism less ad hoc” (1989) — the paper that introduced type classes in Haskell, the direct ancestor of Rust’s traits and the C++ concepts design; bounded polymorphism resolved at compile time, with coherence as a guarantee.
JSR 14 (Add Generic Types to Java) and the C++20 concepts proposal — two committee documents that record why Java chose erasure (backward compatibility) and why C++ replaced SFINAE rather than patching it (legibility), the clearest window into the trade-offs each language consciously made.

--- title: "Type Systems and Generics" keywords: [type systems, generics, templates, traits, static typing, gradual typing, structural typing, nominal typing, type inference, variance, monomorphization, type erasure, metaprogramming, polymorphism] difficulty: advanced prerequisites: [software-engineering-overview, typescript-fundamentals, rust-fundamentals] estimated_time: "4-5 hours" --- ## Introduction The same bug arrived three times in one quarter, in three different languages, on three different teams that never spoke to each other — and that coincidence is the whole reason this chapter exists. The first team ran a Python service whose cache was, by every comment and variable name, a dictionary of user records. One Tuesday a request pulled an entry, called `.name` on it, and got an `AttributeError`: somewhere upstream a code path had stored a primary-key integer where a user object belonged. Nothing had complained when it was written. The error surfaced months later, far from the line that caused it, in code that had done nothing wrong. The second team ran the identical service in Java. Their cache was declared `Map<String, User>` — typed, checked, safe. Except a "convenience" loader written under deadline took a *raw* `Map` to avoid threading the generic signature through four call sites, and on one rare path it put a `Long` where a `User` belonged. The compiler said nothing it couldn't say: a raw map accepts any `Object`. Months later a read fired a `ClassCastException` — from a cast the compiler had *inserted on the developer's behalf and then erased the type behind*. The third team had it in TypeScript. They maintained three near-identical `User` interfaces — database row, API response, edit-form state — by hand. Someone added a `phoneNumber` field, updated two of the three, and shipped. The phone number saved to the database and silently vanished every time a user edited their profile, because the form's type didn't know the field existed. Three copies that could disagree, and one finally did. Three languages, three "the type drifted and the failure surfaced far away" incidents — and three *completely different* underlying mechanisms. Python checks types when it runs, if at all. Java checks them at compile time and then throws them away. TypeScript checks structure, not names, and erases everything before the JavaScript runs. The same *class* of bug, expressed through three different *machines*. This chapter is about those machines: how six languages answer the question "what is a type, when is it checked, and what survives to run time" — and why understanding the answer in one language makes you faster in all the others. ### The Core Insight Every type system is a machine that answers two questions, and almost every difference between languages is a different answer to one of them. The first question is **when**. When does a type error surface — while the program runs, or before it ever does? This is the dynamic-to-static spectrum. At one end, Python checks nothing until the offending line executes (and a wrong type is a run-time `TypeError`). In the middle sit the *gradual* systems — Python with a checker like mypy, and TypeScript — where annotations are optional, checked before the program runs, and then *erased*, leaving plain code that carries no type information at all. At the far end sit the *static* languages — Go, Java, C++, Rust — where a wrong type is a compile error that simply never ships. The second question is **what survives**. Once you have generic code — a `List` of `T`, a function over "any orderable type" — what does the compiler actually produce? There are exactly three answers, and every language picks one. **Type erasure** (Java, TypeScript): check the types, insert the casts, throw the parameter away — one body serves every type, and at run time the type is gone. **Monomorphization** (C++, Rust, Go in part): stamp out a separate, fully specialized copy of the code for each concrete type — the abstraction evaporates and what runs is as fast as hand-written code. **Structural constraints** (Go interfaces, TypeScript shapes): constrain a type by the *operations it supports* rather than the name it was given, and dispatch through an interface when the concrete type isn't known. Hold those two axes in your head and the entire landscape becomes legible. The "same idea, different machinery" pattern repeats at every level: a `List` of strings, a function bounded to "things that can be compared," a way to ask "is this type orderable" — each one shows up in all six languages, implemented six ways, with six different cost profiles. Learn the axes once and you stop relearning generics per language; you start *translating* between them. ### A mental model Picture a type system as a **bouncer with a memory policy**. Every bouncer checks IDs at the door — that is type-checking, and even Python does it, just *inside* the club, the moment you try to do something with a value. What separates the languages is two further choices. First, *where the door is*: a static language checks at the entrance (compile time) and turns away anyone who doesn't qualify; a dynamic language lets everyone in and checks only when they try to order a drink (run time). Second, *what the bouncer remembers*. A Java or TypeScript bouncer is meticulous at the door and then keeps **no record inside** — the wristband is checked and discarded, so at run time nobody can ask what type anyone was admitted as (this is erasure). A C++ or Rust bouncer doesn't just check the ID; it stamps out a **dedicated, private room** for each type that walks in, furnished exactly for that type (monomorphization). A Go bouncer doesn't check names at all; it checks whether you can *do the things the club requires* — can you `Read`, can you `Write` — and admits anyone who can, regardless of who they are (structural typing). @fig-type-systems lays this out as one picture: the *when* axis across the top, the *what survives* machinery across the bottom, and the four-named-but-one idea of bounded constraints tying them together. Keep it open as you read — every section below is one region of that map. ![The type-system spectrum from dynamic to static, and the three implementations of generics — type erasure, monomorphization, and structural constraints — placed by how much they check at compile time versus run time.](../assets/diagrams/rendered/type_systems.svg){#fig-type-systems .lightbox} ### When to reach for static, gradual, or dynamic typing The spectrum is not a quality ranking. Each region is the right answer for a different job, and mature engineers move along it deliberately rather than defaulting to whatever their primary language enforces. **Reach for dynamic typing** when iteration speed dominates and the cost of a run-time type error is low and local — exploratory data analysis, a one-off script, a notebook, glue code you will read once. Python earns its place here precisely because it gets out of your way; demanding type proofs before you know what you're building is friction with no payoff. **Reach for gradual typing** when a codebase outgrows "small enough to hold in your head" but you can't or won't rewrite it. This is the most common real-world position: a Python service that adds mypy and `Protocol`s to its public boundaries while leaving the glue untyped, or a JavaScript front-end migrated to TypeScript file by file. Gradual typing lets you buy safety incrementally, paying for proof exactly where bugs are expensive and skipping it where they aren't. **Reach for static typing** when the program is large, long-lived, edited by many people, or performance-critical — and especially when a type error in production is expensive. The compiler becomes a tireless reviewer that checks every refactor against every call site before a single test runs. Within static, the further choice is *what the generics cost*: Java and TypeScript erase (small binaries, runtime introspection limits); C++ and Rust monomorphize (zero run-time cost, larger binaries, slower builds); Go interfaces and TypeScript shapes constrain structurally (maximum decoupling, often one indirection per call). The decision diagram in @fig-type-systems is the map; the rest of this chapter is the territory. ### What you'll learn - Why the dynamic-to-static spectrum is really two axes — *when* types are checked and *what survives* to run time — and how to place any language on both - The difference between **nominal** typing (satisfy an interface by declaring it) and **structural** typing (satisfy it by having the right shape), and which languages choose which - How parametric polymorphism is implemented four ways — Java's **type erasure**, C++'s and Rust's **monomorphization**, Go's type parameters, and TypeScript's generics — and the cost each one pays - How the single idea of **bounded quantification** wears four names: Rust trait bounds, C++20 concepts, Java bounded wildcards (PECS), and TypeScript `extends` constraints - What **variance** is, why Java forces you to spell it with wildcards while other languages infer or fix it, and the rule that keeps it sound - How **type inference** ranges from `var`/`auto` local inference to TypeScript's pervasive flow analysis, and where each stops - What **type-level programming** is — TypeScript's conditional and mapped types, C++ template metaprogramming, Rust associated types — and where its leverage and its footguns both live ### Prerequisites - **Software Engineering Overview** — the role of a type system as a design and verification tool, and the build-vs-runtime distinction this chapter leans on constantly - **TypeScript Fundamentals** — generics (`<T>`), `keyof`, unions and intersections, and the idea that a type is a set of values - **Rust Fundamentals** — basic generic syntax, `Option`/`Result`, and enough trait vocabulary to read a bounded signature --- ## Two axes, six languages Before any code, fix the map. The two questions from the Core Insight — *when* are types checked, and *what survives* to run time — sort the six languages cleanly, and the sort is more useful than any per-language list of features. The first table places each language on the *when* axis. | Language | When checked | A wrong type is… | Position | |---|---|---|---| | Python (bare) | Run time only | a `TypeError` when the line executes | Dynamic | | Python + mypy | Compile-ish (checker) + run time | a checker error; runs anyway if you ignore it | Gradual | | TypeScript | Compile time, then erased | a `tsc` error; the JS runs with no types | Gradual | | Go | Compile time | a compile error; never ships | Static | | Java | Compile time, then erased | a compile error (or a later `ClassCastException`) | Static, erased | | C++ | Compile time | a compile error | Static | | Rust | Compile time | a compile error | Static | The crucial subtlety hiding in that table is that "static" and "erased" are *independent*. Java is fully static — the compiler rejects `strings.add(42)` — and yet its generics erase, so at run time a `List<String>` and a `List<Integer>` are the same class. TypeScript is *gradual* and also erases. C++ and Rust are static and *don't* erase: they monomorphize, producing real per-type code. Erasure is about the *what survives* axis, not the *when checked* axis, and conflating the two is the single most common confusion in this whole subject. That second axis — what the compiler does with generic code — is where the languages diverge most sharply, and it is the spine of everything that follows. | Language | Generics implemented by | Survives to run time? | Run-time cost | Pays in | |---|---|---|---|---| | Java | **Type erasure** | No — type gone, casts inserted | Indirection on bounded reads | Lost run-time type info | | TypeScript | **Erasure** (full) | No — types vanish entirely | None (it's just JS) | No run-time enforcement at all | | C++ | **Monomorphization** (templates) | Yes — a copy per type | Zero | Binary size, build time | | Rust | **Monomorphization** (generics + traits) | Yes — a copy per type | Zero (static dispatch) | Binary size, build time | | Go | Monomorphization + dictionaries (hybrid) | Partly | Small | Some indirection | | Go / TS (interfaces) | **Structural constraints** | Interface value at run time | One indirection per call | Flexibility for a vtable hop | Read the two tables together and you have the chapter in miniature: the *when* table is about safety and ergonomics, the *what survives* table is about cost and capability, and every language is a point in that two-dimensional space. The rest of this chapter walks the regions. ## Dynamic, gradual, static: the same `add` three ways The cleanest way to feel the spectrum is to write the same trivial mistake — adding a number to a list of strings — and watch *when* each language objects. In bare Python, nothing objects until something downstream trips over the intruder. The list happily holds mixed types; the failure is deferred to whoever assumes otherwise. Python (bare — caught at run time, if at all): ```python names = ["alice", "bob"] names.append(42) # no complaint here greeting = "hi " + names[2] # TypeError, far from the append ``` Add a checker and the annotation, and the *same code* is flagged before it runs — but notice the annotation is advisory. mypy will object; the interpreter will not. This is gradual typing's defining property: the type layer is a separate, optional pass. Python (gradual — mypy objects, the interpreter still runs it): ```python names: list[str] = ["alice", "bob"] names.append(42) # mypy: error — int not assignable to str # python: runs fine; the annotation is advisory ``` TypeScript sits in the same gradual region, but its checker is the *default* build step, so the error is harder to ignore — and then, importantly, the type vanishes. What ships is JavaScript with no memory that `names` was ever `string[]`. TypeScript (gradual — `tsc` errors, then erases to plain JS): ```typescript const names: string[] = ["alice", "bob"]; names.push(42); // tsc: Argument of type 'number' is not assignable to 'string' // compiled JS: the type is gone; only the array remains ``` A static language refuses to produce a runnable artifact at all. Go, Java, C++, and Rust each reject this at compile time; there is no "runs anyway." The difference between them is not *whether* they catch it but *what they keep* afterward — which is the next axis. The lesson of the trio is that "typed vs untyped" is the wrong dichotomy. Python *can* be typed; TypeScript's types *can* be ignored at run time. The real questions are when the check fires and whether you're allowed to ship past a failure — and gradual typing exists precisely to let a team slide along that axis one module at a time. ## Nominal vs structural: how a type satisfies an interface The next axis cuts across the static languages: when a type claims to satisfy an interface, *how is that claim verified*? There are two answers, and they shape API design more than almost anything else. **Nominal typing** verifies by declared name. A Java class is a `Comparable` only if it *says* `implements Comparable`; a Rust type has a trait only if you write an `impl` block. The relationship is established at the point of definition, by an explicit declaration, and the type author must opt in. **Structural typing** verifies by shape. A Go type satisfies an interface if it has the required methods — no `implements`, no registration, no inheritance. A TypeScript object matches a type if it has the required fields. The relationship is established *structurally*, wherever the type is used, and the type author need not even know the interface exists. The same "this can be drawn" capability, declared four ways, makes the split concrete. Java is nominal — `Circle` must announce the interface: ```java interface Drawable { void draw(); } class Circle implements Drawable { // must declare it public void draw() { /* ... */ } } ``` Rust is also nominal, via an explicit `impl` — but the trait can be written long after the type, and for a type you don't own: ```rust trait Drawable { fn draw(&self); } struct Circle { r: f64 } impl Drawable for Circle { // explicit impl, but decoupled in time fn draw(&self) { /* ... */ } } ``` Go is structural — `Circle` satisfies `Drawable` for free, by having `Draw`, with no declaration anywhere connecting them: ```go type Drawable interface { Draw() } type Circle struct{ R float64 } func (c Circle) Draw() { /* ... */ } // no "implements" — the shape is the contract ``` TypeScript is structural at the level of object shapes — any value with the right members fits, even an anonymous literal: ```typescript interface Drawable { draw(): void; } const circle = { r: 1, draw() { /* ... */ } }; // never named Drawable const d: Drawable = circle; // …but structurally it is one ``` The trade-off is real in both directions. Nominal typing makes intent explicit and prevents *accidental* conformance — two types with a method called `close()` that mean totally different things won't be confused, because neither declared the interface. It also gives a stable, searchable answer to "what implements this?" Structural typing maximizes decoupling — you can define a one-method interface at the *consumer* and have every existing type satisfy it without modification, which is exactly why idiomatic Go interfaces are tiny and live where they're used. Rust threads the needle: it is nominal (explicit `impl`) but, unlike Java's class hierarchy, lets a type implement any number of unrelated traits and lets traits be added after the fact — capability without taxonomy. ::: {.callout-note} Structural typing has a sharp edge worth naming: a type can satisfy an interface *by accident*. A Go struct that happens to have a `String() string` method silently becomes a `fmt.Stringer`, changing how it prints, even if the author never intended it. Nominal systems make that impossible by construction. Neither is "better" — they're optimizing for different failure modes. ::: ## Parametric polymorphism, four ways Now the heart of the chapter. *Parametric polymorphism* — writing one piece of code that works uniformly across many types, a `List` of `T`, a `max` over any orderable type — is the feature every modern language has, and the feature each implements completely differently. The differences are not cosmetic; they determine binary size, run-time cost, what you can introspect, and what errors look like. We'll take them in order of how much survives to run time, from nothing (erasure) to everything (monomorphization). ### Java: type erasure Java generics are a compile-time fiction. The compiler uses the type arguments to check your code rigorously — it rejects `strings.add(42)`, it lets you skip casts on reads — and then it *erases* them. The bytecode that ships sees only `Object`, or, if the parameter is bounded, the bound. A `List<String>` and a `List<Integer>` are the same class at run time: plain `List`. There is one `ArrayList` class, not one per element type. This is visible in a single line — the kind of fact that explains everything downstream: ```java List<String> strings = new ArrayList<>(); List<Integer> integers = new ArrayList<>(); System.out.println(strings.getClass() == integers.getClass()); // true ``` The `<String>` lived only in the compiler. Every read of a `List<String>` element gets a `CHECKCAST String` instruction the compiler wrote so you didn't have to — and *that* inserted cast is what throws the `ClassCastException` in the opening story, far from the raw-type line that planted the wrong value. Erasure is also why you cannot write `new T()` (no `T` to construct at run time), cannot create a `T[]` (an array needs a runtime element type to check its stores), and cannot test `obj instanceof List<String>` (at run time there is only `List`). Each prohibition is the absence of a runtime type the compiler already discarded. When you genuinely need the type back, you carry it by hand as a `Class<T>` token — the reified type, re-supplied. Erasure buys backward compatibility and small binaries; it costs you the type at run time. @fig-type-systems places it at the "nothing survives" end of the machinery axis. ### TypeScript: full erasure TypeScript erases even more completely than Java. Java keeps the bound and inserts casts; TypeScript's types vanish *entirely*, because the output is JavaScript and JavaScript has no type system to receive them. A generic function is, after compilation, an ordinary untyped JS function. This is liberating and dangerous in equal measure: there is zero run-time cost (the types were never there), and zero run-time enforcement (a value that lies its way past the compiler — via `any`, an unchecked cast, or untyped JSON — is never caught). The generic itself reads familiarly: ```typescript function first<T>(items: T[]): T | undefined { return items[0]; // T is checked at compile time, then erased to nothing } const n = first([1, 2, 3]); // T inferred as number; at run time, just JS ``` The practical consequence is that TypeScript's safety is entirely a *development-time* guarantee. It cannot validate data crossing a run-time boundary — which is why schema libraries (Zod and friends) exist: to re-establish, at run time, the types the compiler threw away. ### C++ and Rust: monomorphization Now the opposite end. C++ templates and Rust generics keep *everything* — by generating a separate, fully specialized copy of the code for each concrete type. This is **monomorphization**, and it is the same idea in both languages despite different syntax. When you call a generic `max` with two `int`s, the compiler stamps out a concrete `int max(int, int)`; call it with `double`s and you get a second function. They share source, not object code; each is as fast as a hand-written version because, after instantiation, that is exactly what it is. C++ calls the pattern a *template* and the per-type copy an *instantiation*: ```cpp template<typename T> T max_value(T a, T b) { return (a > b) ? a : b; } // the stencil // max_value(3, 5) -> stamps out int max_value(int, int) // max_value(1.0, 2.0) -> stamps out double max_value(double, double) ``` Rust expresses the same machine with generics constrained by traits — and the trait bound is mandatory, which (as we'll see under bounds) is the difference that spares Rust C++'s historical error avalanche: ```rust fn max_value<T: PartialOrd>(a: T, b: T) -> T { // T must be orderable if a > b { a } else { b } // monomorphized per concrete T } ``` The payoff is **zero-cost abstraction**: a generic call is a *direct* call the compiler can inline, with no boxing and no virtual dispatch — the genericity exists only in the source. The cost is equally real but it *moved*: to compile time and binary size, because a template or generic used with twenty types compiles into twenty copies. That is *code bloat*, the structural cost of monomorphization, and it is why "make everything generic" is a mistake — you are asking the compiler to write a great deal of code. ### Go: the hybrid Go added generics late (1.18, 2022) and chose a middle path on purpose. Rather than committing fully to monomorphization (binary bloat) or erasure (lost performance), the Go compiler can share one generic implementation across types with the same *underlying memory shape* via a runtime dictionary, while specializing where it pays. A Go generic uses *type parameters* with *constraints*, where a constraint is just an interface describing what the type must support: ```go type Ordered interface { ~int | ~float64 | ~string } // a constraint set func Max[T Ordered](a, b T) T { // T constrained to orderable types if a > b { return a } return b } ``` The `~int` syntax means "int or any type whose underlying type is int," and the union spells out exactly which types qualify — a structural constraint expressed as an interface. Go's choice reflects its whole philosophy: a pragmatic compromise that keeps binaries reasonable and builds fast, accepting some indirection rather than chasing the last increment of either erasure's compactness or monomorphization's speed. The four-way comparison is the thing to carry away. *Same idea — one body of code over many types — four machines:* erase and insert casts (Java), erase entirely (TypeScript), stamp out a copy per type (C++, Rust), or share-and-specialize (Go). Each trades run-time cost against binary size against introspection, and no choice is free. > **Build it →** Monomorphization on a hot path, made concrete: the > [Project 17: Columnar Query Engine](https://github.com/jchu0/applied-cs-projects/tree/main/17-columnar-query-engine) > uses static dispatch over column types to keep per-row work inlinable — and falls back > to trait objects over operators where types are chosen at run time, the static/dynamic > split in one codebase. ## Bounded quantification: the same idea, four names An unbounded type parameter is nearly useless. If `T` can be *anything*, you can do almost nothing with it — only the operations every type supports. The power of generics comes from **bounds** (formally, *bounded quantification*): "T, but only types that can be *ordered*," "T, but only types that can be *added*." A bound is a contract in two directions — callers may supply only types that satisfy it, and in return the body may rely on the operations the bound promises. This single idea wears four names across the languages, and seeing them side by side is the fastest way to internalize that they are *the same thing*. The bound below — "T must be orderable" — is the canonical example. Rust — a **trait bound**, mandatory and checked at the call site: ```rust fn largest<T: Ord>(items: &[T]) -> &T { /* can call .cmp because T: Ord */ } ``` C++20 — a **concept**, a named constraint that replaced the unreadable SFINAE idiom: ```cpp template<std::totally_ordered T> // named, checkable, one-line errors T largest(const std::vector<T>& items); ``` Java — a **bounded type parameter** (and, for variance, bounded wildcards): ```java static <T extends Comparable<T>> T largest(List<T> items) { /* T has compareTo */ } ``` TypeScript — an **`extends` constraint** on the type parameter: ```typescript function largest<T extends { compareTo(o: T): number }>(items: T[]): T { /* ... */ } ``` Four syntaxes, one concept: each constrains `T` to a capability and unlocks exactly the operations that capability provides. The deep difference is *when the bound is checked and how the error reads when it fails*, and here the languages tell a striking historical story. Rust and C++20 check the bound **at the call site, up front**: pass a type that doesn't satisfy `Ord` or `std::totally_ordered` and you get one clean error naming the missing capability — *before* the generic body is ever instantiated. C++ *before* concepts did not have this. A template with no constraint deferred every type error to the deepest point it could fail, deep inside the template body, producing the legendary four-hundred-line substitution-failure avalanche for a one-line mistake. Concepts (C++20) fixed it by making the constraint a named, first-class predicate — arriving, late but well, exactly where Rust's mandatory trait bounds had been all along. The lesson generalizes past any one language: *constrain your public generics*, and you move the error from the library's guts to the call site, and from a stack trace to a sentence. ## Variance: when is a container of subtypes a container of supertypes? Bounds answer "what can `T` be?" Variance answers a subtler question: given that `Cat` is an `Animal`, is a `List<Cat>` a `List<Animal>`? The intuitive "yes" is, in general, *unsound*, and how each language handles that is one of the most error-prone corners of type systems. The reason the intuitive answer is wrong is worth seeing once, concretely. Suppose `List<Cat>` *were* a `List<Animal>`. Then you could assign it to a `List<Animal>` variable and, through that variable, `add(new Dog())` — because a `Dog` is a valid `Animal`. Now your `List<Cat>` contains a `Dog`, and the next code to read a `Cat` out of it gets a nasty surprise. To prevent exactly this, languages make generic containers **invariant** by default: a `List<Cat>` is simply *not* a `List<Animal>`, full stop, even though `Cat` is an `Animal`. Invariance is safe but stifling — it would block the perfectly reasonable "sum any list of numbers." The fix is to let you opt into *variance* where it's sound: - **Covariance** (`? extends T`): a producer you only *read* from. A `List<? extends Number>` can be a `List<Integer>` or a `List<Double>`; you may read `Number`s out, but you may not add anything, because the exact element type is unknown. - **Contravariance** (`? super T`): a consumer you only *write* into. A `List<? super Integer>` accepts `Integer`s for writing, but a read gives back only `Object`. Java forces you to spell this out at every use site with wildcards, and the mnemonic is **PECS — Producer Extends, Consumer Super.** The canonical `copy` captures all three positions in one signature: ```java static <T> void copy(List<? extends T> src, // producer: read T out (covariant) List<? super T> dst) { // consumer: write T in (contravariant) for (T item : src) dst.add(item); // src.add(item); // REJECTED — src's exact subtype is unknown, adds unsafe // T x = dst.get(0); // REJECTED — a read from dst yields only Object } ``` TypeScript handles variance largely by *inference* — its structural checker computes whether a position is co- or contravariant from how the type parameter is used, and function parameters are (under strict settings) contravariant automatically. C++ templates mostly sidestep variance because each instantiation is an independent type with no subtype relationship to enforce. Rust ties variance to *lifetimes and ownership* and infers it from a type's structure rather than asking you to annotate it. The common thread: variance is the rule that keeps a "container of subtypes" from being silently treated as a "container of supertypes" you could corrupt — and the languages differ mainly in whether they make you write it down (Java), infer it (TypeScript, Rust), or rarely need it (C++). | Language | Default | How variance is expressed | |---|---|---| | Java | Invariant | Explicit use-site wildcards (`? extends` / `? super`, PECS) | | TypeScript | Inferred | Computed structurally; params contravariant under strict mode | | C++ | N/A per instantiation | No subtype relation between instantiations to vary | | Rust | Inferred | Derived from structure, tied to lifetimes/ownership | | Go | Invariant | No declaration-site variance; interfaces sidestep it | ## Type inference: how much can the compiler figure out? A type system you have to spell out completely is a chore; a good one *infers*. Inference ranges from modest local deduction to whole-program flow analysis, and where a language sits shapes how much annotation noise you live with. The modest end is **local inference**: the compiler deduces a variable's type from its initializer, but signatures must still be annotated. C++'s `auto`, Java's `var`, Go's `:=`, and Rust's `let` (within a function body) are all this. They eliminate the redundant left-hand-side type while leaving function boundaries explicit: ```cpp auto count = items.size(); // C++: deduced from the right-hand side ``` ```java var users = new ArrayList<User>(); // Java: inferred ArrayList<User> ``` ```go users := make(map[string]int) // Go: inferred map[string]int ``` ```rust let total = nums.iter().sum::<i64>(); // Rust: inferred from context + turbofish ``` The rich end is **flow-based, near-whole-expression inference**, and TypeScript is its poster child. It infers generic type arguments from usage, narrows types through control flow (`if (typeof x === "string")` makes `x` a `string` in that branch), and propagates types through long chains without annotation. Rust sits between the poles: its inference is powerful — it solves for type parameters from later usage, not just the initializer — descending from the Hindley–Milner tradition of letting the compiler reason globally within a function, though it stops at function signatures by design, which it treats as documentation worth requiring. The design tension is constant: more inference means less typing and less visual noise, but also less *locally obvious* code — a variable whose type you must mentally compute, or hover in an editor to see. Every language draws the line somewhere, and the modern consensus is "infer aggressively *inside* a function, require annotations *at* its boundaries," because a signature is read far more often than it's written and its types are documentation. ## Type-level programming: computing with types At the far reach of every static type system is the realization that the type checker is itself a small *programming language* — one whose values are types and whose execution happens at compile time. This is **type-level programming**, and it is where the languages' expressive ceilings diverge most. TypeScript's type system is, famously, a Turing-complete functional language that computes types from types. It has conditionals (`T extends U ? X : Y`), iteration (mapped types walk a type's keys), and pattern-matching extraction (`infer`). This is what powers *deriving* one type from another so they cannot drift — the cure for the three-`User`- interfaces bug from the introduction. The API type is the domain type *minus* a field; the form type is the domain type with *every field optional* — each computed, not copied: ```typescript interface User { id: number; name: string; email: string; passwordHash: string; } type ApiUser = Omit<User, "passwordHash">; // derived: change User, this re-derives type UserDraft = Partial<User>; // every field optional, for form state ``` `Omit` and `Partial` are themselves *written in* the type-level language — `Partial<T>` is a mapped type that walks `T`'s keys and adds `?` to each. Conditional types plus `infer` let you extract pieces (`ReturnType`, `Awaited`), and template literal types bring the same computation to strings (typed routes from a path string). The leverage is enormous *at boundaries* — derive an API, a form, and a validator from one source of truth — and a footgun *in the middle*, where a baroque four-`infer`-deep type saves three lines of duplication at the cost of an error message no teammate can decode. C++ reaches the same compile-time-computation ceiling through a different door: *template metaprogramming*, `constexpr` functions, and `if constexpr`, which lets one function body compile entirely different code paths per type, with the untaken branch *discarded* before it is even type-checked: ```cpp template<typename T> auto describe(T value) { if constexpr (std::is_integral_v<T>) return value * 2; // only path for ints else if constexpr (std::is_floating_point_v<T>) return value * 1.5; else return value; // illegal-for-int code OK here } ``` Rust's type-level computation is deliberately more restrained — by design, it has no Turing-complete type-level language — but it expresses the most important pattern, *associated types*, with unusual clarity. An associated type captures "exactly one related type per implementor": an `Iterator` yields one element type, so `Item` is an associated type, not a generic parameter, which keeps signatures clean and forbids the nonsensical "this type is an iterator of both `u8` and `String`": ```rust trait Iterator { type Item; // one element type per implementor fn next(&mut self) -> Option<Self::Item>; } ``` Java and Go sit far down this axis on purpose. Java's erased generics can't compute much at the type level — there's no type to compute *with* at run time, and the compile-time machinery is intentionally limited. Go went further still, omitting generics entirely for thirteen years and adding only a deliberately minimal version, precisely to avoid the metaprogramming complexity that C++ and TypeScript embrace. The spectrum here is not capability-for-its-own-sake; it is a values choice about how much compile-time cleverness a language wants its users wielding — and the cost, in every case, is paid by whoever has to *read* the type later. ::: {.callout-warning} ## War story: the type nobody could touch A platform team's shared types package contained a single exported utility — call it `DeepRecursivePartialReadonlyNonNullable` — that recursed into nested objects, made every property optional, marked every property `readonly`, and stripped `null`, all in one twelve-line conditional-mapped type. It worked, mostly, and it was the most-feared type in the codebase. When someone added a `Map`-valued field, the type recursed into the `Map`'s internals, produced a shape nobody recognized, and tipped over TypeScript's recursion limit with a `TS2589` "excessively deep" error. The on-call engineer spent an afternoon not fixing the bug but *understanding the type* — then gave up and cast with `as`, reintroducing exactly the unsafety the type existed to prevent. The fix was to delete it and compose three small, separately-hover-able types applied in sequence. The lesson is the same one C++ learned with its four-hundred-line template errors, in a different language: *simple types that compose beat one clever type that doesn't.* Compile-time power that no teammate can read isn't safety — it's a wall, and walls get climbed over with `as` and casts. ::: > **Build it →** Type-level machinery driving a real system: the > [Project 18: Compiler / Interpreter](https://github.com/jchu0/applied-cs-projects/tree/main/18-compiler-interpreter) > implements a type checker and inference engine from scratch — the algorithms behind > everything in this section — and the > [Project 31: ML Compiler](https://github.com/jchu0/applied-cs-projects/tree/main/31-ml-compiler) > uses typed intermediate representations and generic graph passes where the type system > is load-bearing for correctness. --- ## Practical exercise **Difficulty:** Level I · Level II · Level III 1. **Level I — Place the same program on both axes.** Write a tiny `Stack` of a generic element type in *three* languages of your choice spanning the spectrum (e.g. Python with type hints, TypeScript, and Rust). For each, answer in one or two sentences: (a) *when* is a type error caught — run time, checker, or compiler? and (b) *what survives* to run time — is the element type erased, monomorphized into a per-type copy, or carried in an interface value? Then locate each of your three on @fig-type-systems and confirm your answers match where the diagram places that language. The goal is to feel that "generic stack" is one idea with three machines underneath. 2. **Level II — Bound it, then break it, in two languages.** Pick one monomorphizing language (Rust or C++) and one erasing language (Java or TypeScript). In each, write a generic `max` constrained to "orderable" types — a Rust trait bound, a C++20 concept, a Java bounded type parameter, or a TypeScript `extends` constraint. Then call it with a type that *isn't* orderable (a struct with no comparison) and paste the error. In a paragraph, compare: does the error fire at the *call site* or deep in the generic body? Does it *name* the missing capability? Relate the difference to the chapter's claim that "constrain your public generics" moves errors from a stack trace to a sentence — and to why C++ before concepts produced four-hundred-line avalanches. 3. **Level III — Demonstrate variance and derive a type.** Two parts, in the languages that make each natural. (a) *Variance:* in Java, write the PECS `copy(List<? extends T> src, List<? super T> dst)`, then show by *failing* compiles exactly why you cannot `add` to the producer or read a `T` from the consumer — and explain, with the `Cat`/`Dog` argument, the corruption invariance prevents. (b) *Derivation:* in TypeScript, start from one `Order` interface and *derive* an `ApiOrder` (without an internal field) and an `OrderDraft` (every field optional) using only type-level operators — no second hand-written interface. Add a field to `Order` and confirm both derivations update themselves. Then write the harder half as an essay: identify where you would *stop* adding type-level cleverness, and justify the line in terms of who has to read the types later — the war story's thesis, applied to your own code. ## Summary A type system is a machine that answers two largely independent questions, and almost every difference between languages is a different answer to one of them. The first is *when* types are checked — at run time (dynamic Python), at compile time but optional and erased (gradual Python+mypy and TypeScript), or at compile time and mandatory (static Go, Java, C++, Rust). The second is *what survives* to run time once you write generic code: **type erasure** throws the parameter away and inserts casts (Java) or vanishes entirely (TypeScript); **monomorphization** stamps out a fully specialized copy per type for zero-cost abstraction at the price of binary size (C++, Rust); **structural constraints** match by shape and dispatch through an interface (Go, TypeScript). Across the static languages, a second axis is *how a type satisfies an interface* — nominally by declaration (Java `implements`, Rust `impl`) or structurally by shape (Go, TypeScript). The single idea of **bounded quantification** appears four times — trait bounds, concepts, bounded wildcards, `extends` constraints — and the languages that check bounds up front (Rust, C++20) give one-line call-site errors where unconstrained templates once gave avalanches. **Variance** is the soundness rule that keeps a container of subtypes from being abused as a container of supertypes, spelled explicitly in Java (PECS) and inferred elsewhere. **Inference** ranges from local (`var`, `auto`) to pervasive (TypeScript). And **type-level programming** is the realization that the checker is itself a compile-time language — most expressive in TypeScript and C++, deliberately restrained in Rust and Go — whose power is leverage at boundaries and a footgun in the middle. ### Key takeaways - "Typed vs untyped" is the wrong axis. The real ones are *when* types are checked (dynamic → gradual → static) and *what survives* to run time (erasure → structural → monomorphization) — and they're independent: Java is static *and* erased. - Generics are implemented four ways: erase-and-cast (Java), erase-entirely (TypeScript), monomorphize (C++, Rust), and a share-or-specialize hybrid (Go). Each trades run-time cost against binary size against introspection. - Nominal typing (declare the interface) prevents accidental conformance and answers "what implements this?"; structural typing (have the shape) maximizes decoupling and tiny consumer-defined interfaces. Rust is nominal-but-decoupled; Go is structural. - Bounded quantification is one idea with four names; the win of checking bounds at the call site is one-line errors — "constrain your public generics." - Type-level power is leverage at boundaries and a liability in the middle; an unreadable type, like an unreadable template error, gets worked around with a cast and stops being safe at all. ### Connections to other chapters - **Software Engineering Overview** (prerequisite): this chapter is the deep version of the "a type system is a verification tool you choose how much to lean on" idea framed there — the dynamic-to-static spectrum is one of the core language-design axes, made concrete across six languages. - **Concurrency and Parallelism Models** (extension): Rust's `Send`/`Sync` *marker traits* turn data-race freedom into a *trait bound the compiler checks* — the type-system machinery of this chapter becoming the concurrency-safety mechanism of that one. The bounded-quantification idea here is literally what enforces thread safety there. - **Memory and Resource Management** (sibling): monomorphization's zero-cost story is inseparable from layout — a `Stack<int>` stores raw `int`s inline, an erased `List<Integer>` boxes them on the heap. The "what survives to run time" axis *is* a memory decision, and the newtype-and-monomorphization patterns here are why Rust abstractions cost nothing in space either. - **Error Handling** (sibling): how a language *models failure* in its types — Rust's `Result<T, E>`, TypeScript's discriminated unions, Java's checked exceptions — is bounded quantification and variance applied to the error channel; the generics here are what make `Result<T, E>` a type you can compute with rather than a convention. - **Performance and Profiling** (extension): the templates-vs-virtual and static-vs-dynamic-dispatch decisions in this chapter *are* performance decisions there — the inlining and devirtualization that monomorphization enables are exactly what the performance chapter measures, and the "zero-cost" claim is one it puts on a profiler. - **Compiler / Interpreter and Columnar Query Engine** (projects): a type checker and inference engine are built from scratch in the compiler project, and the static/dynamic dispatch split is load-bearing in the query engine — the abstractions of this chapter as running systems. ## Further reading ### Essential - Pierce, *Types and Programming Languages* — the canonical text on type systems: the formal treatment of parametric polymorphism, subtyping, variance, and inference that this chapter surveys informally across languages. - Bloch, *Effective Java* (3rd ed.), Items 26–33, and Vanderkam, *Effective TypeScript*, Items 19–33 — the two best practitioners' guides to generics in an erasing language and a gradually-typed one, read side by side for the contrast. ### Deep dives - *The Rust Programming Language* (Klabnik & Nichols), chapters 10, 17, 19, and Vandevoorde, Josuttis & Gregor, *C++ Templates: The Complete Guide* (2nd ed.) — the monomorphizing pair: traits + generics in Rust and templates + concepts in C++, the same zero-cost idea worked through in both. - *TypeScript Handbook — Conditional and Mapped Types* and the *Type Challenges* puzzle set — the deep end of compile-time type computation, and the best way to build fluency in type-level programming and feel where its footguns live. ### Historical context - Wadler & Blott, *"How to make ad-hoc polymorphism less ad hoc"* (1989) — the paper that introduced *type classes* in Haskell, the direct ancestor of Rust's traits and the C++ concepts design; bounded polymorphism resolved at compile time, with coherence as a guarantee. - JSR 14 (*Add Generic Types to Java*) and the *C++20 concepts proposal* — two committee documents that record *why* Java chose erasure (backward compatibility) and *why* C++ replaced SFINAE rather than patching it (legibility), the clearest window into the trade-offs each language consciously made.