Lesson 6.9 — Implementing generics: monomorphization, erasure, dictionary passing¶

Techniques: monomorphization — compile a separate copy of each generic function for every combination of type arguments it is used at (C++ templates [Str94, Ch. 15; CLANG-TemplateInst], Rust [RUSTC-Mono], Swift's and GHC's specializers); erasure with a uniform (boxed) representation — compile each generic function once, with every type variable replaced by its bound and casts inserted at use sites (Java's GJ design [BOSW98; JAVAC-TransTypes]; OCaml's and Haskell's uniform representation); dictionary passing and witness tables — compile once and pass the operations a type variable needs as an extra run-time argument (Haskell type classes [WB89], Swift protocols [Pes24; SWIFT-GenProto]) · Pebble implements: none — Pebble has no generics (its only polymorphism is the builtin print); this lesson is theory and real compilers, and it prepares Chapter 7 (inference of polymorphic types) and Chapter 15 (code size and inlining) · Drills: none (quiz items mono-instances, erasure-checkcast, dictionary-translation are computational) · Prerequisites: Lessons 6.3, 6.5 (bounds and variance) · Time: 3 hours

A type checker for generic code proves that biggest<T> is correct for every T with a <. The back end then has to produce machine code, and machine code is not generic: adding two ints and comparing two doubles are different instructions, and an array of doubles and an array of pointers have different layouts. There are three answers, each shipped by a major language: copy the function per type (C++, Rust), make every type look the same by boxing and compile once (Java, OCaml), or compile once and pass the type-specific operations as data (Haskell, Swift). They trade code size, run time, separate compilation and what the language can express; real compilers mix them.

1. Problem and motivation¶

Monomorphization¶

The problem. Generic code should run as fast as hand-written code for each type — std::sort on ints should compare with one instruction, and Vec<f64> should store unboxed doubles. C++ templates achieve this by instantiating the template for each set of template arguments: the body is copied with the arguments substituted and compiled as ordinary code [Str94, Ch. 15]. Rust does the same after type checking, collecting every generic function instance reachable from non-generic code [RUSTC-Mono]. The costs are code size (one copy per instance), compile time (each copy is optimized separately), and a restriction on the language: the set of instances must be finite and known at compile time.

Erasure and uniform representation¶

The problem. Java 5 had to add generics to a language with a large installed base of compiled libraries and a virtual machine that knew nothing about type parameters. GJ's answer was erasure: type-check with generics, then replace every type variable by its bound (Object, or Comparable for T extends Comparable<T>), and insert casts where the erased type is too general; one class file serves all instantiations, and old non-generic code links with new generic code [BOSW98]. The price is that primitive types cannot be type arguments without boxing (List<Integer>, not List<int>), and that type arguments do not exist at run time (new T[], instanceof List<String> are impossible). ML-family languages use the same uniform representation for a different reason: every value is one machine word, a small integer or a pointer, so polymorphic code needs no type information at all.

Dictionary passing and witness tables¶

The problem. Erasure works for code that treats T values as opaque. sum :: Num a => [a] -> a must add them, and the addition for Int is not the one for Double. Wadler and Blott's translation of type classes makes each constraint Num a an extra argument, a dictionary — a record of the class's methods for the type at hand — so sum is compiled once and calls (+) through the dictionary [WB89]. Swift uses the same idea for protocols with witness tables, plus type metadata that carries size and alignment so that generic code can copy and store unboxed values of unknown type [Pes24]. The price is an indirect call per operation, unless the optimizer specializes.

2. Definitions and algorithms¶

Definition 6.9.1 (Generic function, instance, instantiation graph)

A generic function $f\langle \alpha_1, \ldots, \alpha_k\rangle$ has type parameters $\alpha_i$ (possibly with bounds or constraints). A call site in the body of $g\langle \beta_1, \ldots \rangle$ calls $f\langle \sigma_1, \ldots, \sigma_k\rangle$ with type expressions $\sigma_i$ over $g$'s parameters. An instance is $f\langle \tau_1, \ldots, \tau_k\rangle$ with closed types $\tau_i$. The instantiation graph has an edge from instance $g\langle \vec\rho\rangle$ to $f\langle \vec\sigma[\vec\beta := \vec\rho]\rangle$ for every call site; the roots are the non-generic functions (main, exported symbols).

Monomorphization¶

Algorithm 6.9.2 (Monomorphization by worklist collection)

Input: a type-checked program; its roots.
Output: the set of instances reachable from the roots, each compiled as a non-generic function with its type arguments substituted.
Precondition: every call site's type arguments are known after type checking (explicit or inferred).
Postcondition: the output is exactly the set of instances reachable in the instantiation graph; the program terminates with the same behavior when every generic call is redirected to its instance (Theorem 6.9.7 for when the set is finite).
Invariant: every instance in done has had all its call sites visited or is in work.

work ← roots;  done ← ∅
while work ≠ ∅:
    take i = f⟨τ1..τk⟩ from work
    if i ∈ done: continue
    done ← done ∪ {i}
    body ← f's body with α1..αk := τ1..τk          # substitute
    emit body as a new function named mangle(f, τ1..τk)
    for each call site g⟨σ1..σm⟩ in body:          # σ are now closed
        work ← work ∪ { g⟨σ1..σm⟩ }
return done

rustc's collector [RUSTC-Mono] is this worklist over MIR (MonoItems); Clang instantiates on demand while type checking, re-checking the substituted body [CLANG-TemplateInst].

Erasure and uniform representation¶

Definition 6.9.3 (Erasure; uniform representation)

The erasure $|\tau|$ of a type replaces every type variable by the erasure of its bound (its leftmost bound; Object if none) and drops type arguments: $|\alpha| = |\mathrm{bound}(\alpha)|$, $|C\langle\vec\tau\rangle| = C$. A representation is uniform if values of every type that can instantiate a type variable have the same size and calling convention — in Java, references; primitive types enter by boxing (int ↦ Integer).

Algorithm 6.9.4 (Erasure translation with cast insertion [BOSW98])

Input: a type-checked generic program; the static type $\tau$ of every expression.
Output: a non-generic program in which each generic class and method appears once.
Precondition: the source has no unchecked conversions (no raw types, no unchecked casts).
Postcondition: every inserted cast succeeds at run time, and the erased program computes what the source computes (Theorem 6.9.8).
Invariant: each translated expression $e'$ has static type $|\tau|$ or a subtype of it, where $\tau$ is the source type.

function Erase(e, τ):                     # τ is e's source type
    e' ← e with every declared type T replaced by |T|, subexpressions erased recursively
    if e is a method call, field read or array read whose declared (generic) result type
       erases to something more general than |τ|:
        e' ← (|τ|) e'                     # checkcast
    if e is a primitive used where a type variable is expected:   e' ← box(e')
    if e is a boxed value used where a primitive is expected:     e' ← unbox(e')
    return e'
# plus: a bridge method in a subclass whose override's erased signature differs

Dictionary passing and witness tables¶

Definition 6.9.5 (Class, instance, dictionary)

A class $C\,\alpha$ declares method signatures $m_i : \tau_i$ mentioning $\alpha$. An instance $C\,T$ gives implementations for $\alpha := T$. The dictionary type $D_C\,\alpha$ is the record $\{m_1 : \tau_1, \ldots, m_n : \tau_n\}$, and each instance $C\,T$ becomes a record value $d_{C,T} : D_C\,T$. A constrained type $\forall \alpha.\, C\,\alpha \Rightarrow \tau$ is translated to $\forall \alpha.\, D_C\,\alpha \to \tau$.

Algorithm 6.9.6 (Dictionary-passing translation [WB89])

Input: a typing derivation of a program with classes (each overloaded use of a method $m$ at type $\tau$ resolved to a constraint $C\,\tau$).
Output: the program in a language without classes.
Precondition: every constraint $C\,\tau$ in the derivation is entailed by an instance declaration or by a constraint in scope; instances do not overlap (coherence).
Postcondition: the output is well typed with the translated types (Theorem 6.9.9).
Invariant: the translation environment maps every constraint in scope to a variable holding its dictionary.

function Tr(e):
    case e of
        method m at constraint C τ:      return Dict(C τ).m
        generic f used at τ with constraints C1 τ1 .. Cn τn:
                                         return f Dict(C1 τ1) .. Dict(Cn τn)
        definition f :: C α ⇒ τ = body:  return f = λ(dC : D_C α). Tr(body)   # dC in scope for C α
        otherwise: recurse
function Dict(C τ):
    if a variable d is in scope for C τ:        return d
    if τ = T τ' and an instance  (C' τ' ⇒ C (T τ')) exists:
                                                return d_{C,T} Dict(C' τ')   # instance with a context
    if τ = T and an instance C T exists:        return d_{C,T}

GHC's Core shows the result: a function with a Num a constraint takes an argument $dNum (§7). Swift's witness table is the dictionary of a protocol conformance, emitted by FragileWitnessTableBuilder (via IRGenModule::emitSILWitnessTable) [SWIFT-GenProto].

3. Worked examples¶

Monomorphization¶

Algorithm 6.9.2 on the §7 Rust program, whose roots are the exported use_ints and use_floats:

Step	Take	New work
1	`use_ints`	`biggest::<i32>`
2	`use_floats`	`biggest::<f64>`
3	`biggest::<i32>`	`<i32 as PartialOrd>::lt`, slice indexing at `i32` (library instances)
4	`biggest::<f64>`	the same at `f64`

Two copies of biggest are emitted — exactly the two symbols llvm-nm lists in the box. The polymorphic-recursive depth<T> of the box calls depth::<(T,)>: from root instance depth::<u8> the worklist produces depth::<(u8,)>, depth::<((u8,),)>, … and never empties; rustc stops at its recursion limit.

Erasure and uniform representation¶

In the §7 Java class, Box<T extends Comparable<T>> erases T to Comparable (its bound), so get() has descriptor ()Ljava/lang/Comparable;. In use(), b.get() has source type Integer, more precise than Comparable, so Algorithm 6.9.4 inserts checkcast Integer; b.get() + … needs an int, so it also unboxes with intValue(); new Box<>(42) boxes with Integer.valueOf. Three kinds of inserted code, all visible in javap -c.

Dictionary passing and witness tables¶

sumSq :: Num a => [a] -> a translates to a function of a dictionary dNum : D_Num a and a list; x * x becomes (dNum.*) x x. useInt = sumSq at a := Int becomes sumSq $fNumInt — the instance dictionary for Num Int. That is GHC's Core at -O0 in §7, character for character up to naming: sumSq = \ @a $dNum xs -> sum $fFoldable[] $dNum (map (\ x -> * $dNum x x) xs) and useInt = sumSq $fNumInt.

4. Invariants and correctness¶

Monomorphization¶

Theorem 6.9.7 (Monomorphization terminates for non-expansive programs)

Call a program non-expansive if, in every strongly connected component of the call graph of generic functions, every call site from a function of the component to a function of the same component has type arguments that are type parameters of the caller or closed types. Then Algorithm 6.9.2 terminates on it. Conversely, if some cycle of the call graph passes a type argument that strictly contains the caller's parameter (as depth<(T,)> from depth<T>), and the cycle is reachable from a root with the recursion's guard not statically known false, the worklist is infinite.

Proof

Order the components of the call graph topologically, callers before callees (the condensation is acyclic). Claim: for each component $K$, the set of instances of functions of $K$ that the worklist ever creates is finite. By induction along the order. Let $U_K$ be the set of closed types that appear as type arguments of instances entering $K$ from earlier components, together with the closed types written at call sites inside $K$. $U_K$ is finite: finitely many call sites enter $K$, each from a function of an earlier component, of which there are finitely many instances by the induction hypothesis, and each call site maps an instance's type arguments to one tuple of types. Inside $K$, by non-expansiveness each call site's type arguments are parameters of the caller (so they take values from the caller's arguments) or closed types written in $K$; by induction on the number of steps inside $K$, every instance of a function of $K$ has all its type arguments in $U_K$. With $k$ the largest number of type parameters, $K$ has at most $\lvert K \rvert \cdot \lvert U_K \rvert^{k}$ instances. There are finitely many components, so done is finite, and since each instance is taken from work at most once as new and has finitely many call sites, the loop ends. For the converse: along the cycle, the type argument after $n$ rounds contains $n$ nested constructors, so the instances are pairwise distinct; the worklist does not evaluate guards, so it follows the call sites whatever their conditions, and never empties.

Erasure and uniform representation¶

Theorem 6.9.8 (Erasure preserves behavior; inserted casts never fail)

If a program is well typed without unchecked conversions and $e$ evaluates to $v$, then the erasure of $e$ (Algorithm 6.9.4) evaluates to the erasure of $v$, and every cast inserted by the translation succeeds.

Proof sketch (full proof, for Featherweight GJ compiled to Featherweight Java: [IPW01])

By a simulation between source and erased reductions, using two invariants. (1) Type preservation: in the source, every expression's value has a run-time class that is a subtype of the erasure of its static type — this is source type soundness (progress and preservation for the generic calculus, as in Lesson 6.1). (2) Cast safety: a cast $(|\tau|)\,e'$ is inserted only where $e$ has source type $\tau$; by (1), $e$'s value has a class below $|\tau|$, so the checkcast succeeds. Each source reduction step (field access, method invocation, cast) is matched by the same step in the erased program plus possibly one successful inserted cast; method lookup is the same because erasure maps the source's class table to one whose methods (plus bridges) have the erased signatures. Unchecked conversions break (1) — "heap pollution" — which is why the theorem excludes them and javac warns about them.

Dictionary passing and witness tables¶

Theorem 6.9.9 (The dictionary translation is well typed)

If $\Gamma \vdash e : \tau$ in the source with the constraints $P$ in scope, then $\mathrm{Tr}(e)$ is well typed at $|\tau|$ (the translation of types of Definition 6.9.5) in the context $|\Gamma|$ extended with a variable $d_\pi : D_\pi$ for every $\pi \in P$.

Proof

By induction on the typing derivation. Method use $m$ at constraint $C\,\tau$: the precondition says $C\,\tau$ is entailed; by an inner induction on the entailment, $\mathrm{Dict}(C\,\tau)$ has type $D_C\,\tau$ — a variable in scope has it by the extended context; an instance without context is the constant $d_{C,T} : D_C\,T$; an instance with context $C'\,\tau' \Rightarrow C\,(T\,\tau')$ is translated to a function $D_{C'}\,\tau' \to D_C\,(T\,\tau')$ applied to $\mathrm{Dict}(C'\,\tau') : D_{C'}\,\tau'$ (inner hypothesis). Field $m$ of a record of type $D_C\,\tau$ has type $\tau_m[\alpha := \tau]$, the method's type at $\tau$. Generic use of $f : \forall \vec\alpha.\, \vec\pi \Rightarrow \sigma$ at $\vec\tau$: $f$'s translation has type $\forall \vec\alpha.\, D_{\pi_1} \to \cdots \to |\sigma|$; instantiating and applying it to $\mathrm{Dict}(\pi_i[\vec\alpha := \vec\tau])$, each of the right type by the inner induction, gives $|\sigma[\vec\alpha := \vec\tau]|$. Definition of $f :: \vec\pi \Rightarrow \tau$: the body is translated in a context extended with $d_{\pi_i}$, so by the hypothesis it has type $|\tau|$, and the $\lambda$s give $D_{\pi_1} \to \cdots \to |\tau|$, which is the translated type. The remaining rules are unchanged by the translation. Meaning also needs coherence — two derivations of the same term must pick the same dictionaries — which non-overlapping instances guarantee [WB89].

5. Complexity¶

Technique	Code size	Run time per generic operation	Compile time	Variables
Monomorphization	$\sum_{\text{instances}}$ body size; worst case exponential	as hand-written code (static calls, unboxed data, inlinable)	each instance compiled and optimized	instances reachable (Theorem 6.9.7)
Erasure / uniform representation	one copy per generic function	a cast at each generic result; boxing/unboxing of primitives; an indirection per element	one copy	—
Dictionary passing	one copy + one dictionary per instance declaration	an indirect call per method use; value-generic code must handle unknown sizes (Swift metadata)	one copy; specialization optional	constraints per function

Justification. Monomorphization emits each instance once (the done set), so size is the sum over instances; erasure and dictionary passing emit each function once, and pay at run time in the inserted operations of Algorithms 6.9.4 and 6.9.6.

Pathological family. For monomorphization, a chain of $n$ generic functions where $f_i\langle T\rangle$ calls both $f_{i+1}\langle T\rangle$ and $f_{i+1}\langle \mathrm{Box}\langle T\rangle\rangle$ is non-expansive (no cycle) yet has $2^{i}$ instances of $f_i$: $2^{n+1} - 1$ in total. For erasure, a List<Integer> of $n$ elements holds $n$ separately allocated boxes. For dictionary passing, a method called in an inner loop pays an indirect, non-inlinable call per iteration unless specialized.

Scale. Monomorphized generics dominate the compile time and binary size of large C++ and Rust code bases; build-time tools such as -ftime-trace in Clang and cargo llvm-lines exist to find the instances responsible.

Monomorphization¶

Polymorphic recursion is rejected (Rust, C++: recursion limit) or needs a uniform representation for the recursive part.
Sharing identical instances: linkers fold identical machine code (--icf), and instances for types of the same layout can share one copy — Go compiles one copy per "GC shape" and passes a dictionary for the rest, a hybrid with the third technique.

Erasure and uniform representation¶

Reified generics (.NET [KS01]): code shared across reference types, specialized at load time for value types, and type arguments available at run time — the hybrid Java's Project Valhalla aims for.
Tagged uniform representation (OCaml): integers are 63-bit with a tag bit, so polymorphic code needs no boxing for int, only for floats.

Dictionary passing and witness tables¶

Specialization (GHC's SPECIALISE pragma and specialiser [GHC-Specialise], Swift's generic specializer): the optimizer monomorphizes hot instances and removes the dictionary argument; the GHC box shows the worker taking the three Num Int methods it needs as arguments.
Vtables as dictionaries: object-oriented dispatch attaches the dictionary to the value instead of passing it separately; Rust's dyn Trait and Swift's existentials do this, Go interfaces too.

7. In real compilers¶

Monomorphization¶

Clang instantiates biggest<int> in Sema::InstantiateFunctionDefinition [CLANG-TemplateInst]; rustc collects MonoItems in collect_crate_mono_items [RUSTC-Mono].

One copy per type: clang++ 23 and rustc 1.94 symbols, and a polymorphic recursion rustc cannot monomorphize

Reproduce (clang 23.1.2, rustc 1.94.1, llvm-nm from LLVM 23):

mkdir -p rsm && cat > mono.cpp <<'EOF'
template <typename T> T biggest(const T *xs, int n) {
  T best = xs[0];
  for (int i = 1; i < n; ++i)
    if (best < xs[i]) best = xs[i];
  return best;
}
int useInts(const int *p) { return biggest(p, 4); }
double useDoubles(const double *p) { return biggest(p, 4); }
long useLongs(const long *p) { return biggest(p, 4); }
EOF
cat > rsm/mono.rs <<'EOF'
pub fn biggest<T: PartialOrd + Copy>(xs: &[T]) -> T {
    let mut best = xs[0];
    for &x in &xs[1..] { if best < x { best = x; } }
    best
}
pub fn use_ints(v: &[i32]) -> i32 { biggest(v) }
pub fn use_floats(v: &[f64]) -> f64 { biggest(v) }
EOF
cat > rsm/polyrec.rs <<'EOF'
fn depth<T>(x: T, n: u32) -> u32 {
    if n == 0 { 0 } else { 1 + depth((x,), n - 1) }   // T, (T,), ((T,),), ...
}
fn main() { println!("{}", depth(1u8, 3)); }
EOF
clang++-23 -O0 -c mono.cpp -o mono.o && llvm-nm -C mono.o
rustc --edition 2021 --crate-type=lib -C opt-level=0 -C symbol-mangling-version=v0 \
    --emit=obj -o rsm/mono.o rsm/mono.rs && llvm-nm -C rsm/mono.o | grep -E 'biggest|use_'
rustc --edition 2021 rsm/polyrec.rs -o rsm/polyrec 2>&1 | grep '^error' | head -1

Output (complete):

0000000000000020 T useDoubles(double const*)
0000000000000000 W double biggest<double>(double const*, int)
0000000000000000 W int biggest<int>(int const*, int)
0000000000000000 W long biggest<long>(long const*, int)
0000000000000000 T useInts(int const*)
0000000000000040 T useLongs(long const*)
0000000000000000 T mono::biggest::<f64>
0000000000000000 T mono::biggest::<i32>
0000000000000000 T mono::use_floats
0000000000000000 T mono::use_ints
error: reached the recursion limit while instantiating `depth::<(((((((((((((((((((...,),),),),),),),),),),),),),),),),),),)>`

What to notice: one symbol per instance, three in C++ and two in Rust, each a separately compiled function. The C++ instances are weak (W, one per translation unit, merged by the linker: separate compilation paid in duplicate work). The last line is Theorem 6.9.7's converse: depth<T> calls depth<(T,)>, the worklist never empties, and rustc gives up at its recursion limit even though depth(1u8, 3) would only recurse three times at run time.

Erasure and uniform representation¶

javac's TransTypes erases types (retype) and inserts casts (coerce) [JAVAC-TransTypes].

Erasure in javac 21: the descriptor says Comparable, the call site casts back

Reproduce (javac and javap 21):

mkdir -p erase && cat > erase/Box.java <<'EOF'
import java.util.ArrayList;
import java.util.List;

public class Box<T extends Comparable<T>> {
    private T value;
    public Box(T value) { this.value = value; }
    public T get() { return value; }
    public boolean less(T other) { return value.compareTo(other) < 0; }

    static int sum(List<Integer> xs) {
        int s = 0;
        for (int x : xs) s += x;       // unboxing
        return s;
    }
    static int use() {
        Box<Integer> b = new Box<>(42);  // boxing: Integer.valueOf
        List<Integer> xs = new ArrayList<>();
        xs.add(b.get());
        return b.get() + sum(xs);        // a checkcast after the erased get()
    }
}
EOF
javac -d erase/out erase/Box.java 2>&1 | grep -v JAVA_TOOL
javap -s -p -cp erase/out Box 2>&1 | grep -v JAVA_TOOL | sed -n '/public T get/,+1p'
javap -c -p -cp erase/out Box 2>&1 | grep -v JAVA_TOOL | sed -n '/static int use/,$p'

Output (complete):

  public T get();
    descriptor: ()Ljava/lang/Comparable;
  static int use();
    Code:
       0: new           #8                  // class Box
       3: dup
       4: bipush        42
       6: invokestatic  #41                 // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
       9: invokespecial #45                 // Method "<init>":(Ljava/lang/Comparable;)V
      12: astore_0
      13: new           #48                 // class java/util/ArrayList
      16: dup
      17: invokespecial #50                 // Method java/util/ArrayList."<init>":()V
      20: astore_1
      21: aload_1
      22: aload_0
      23: invokevirtual #51                 // Method get:()Ljava/lang/Comparable;
      26: checkcast     #35                 // class java/lang/Integer
      29: invokeinterface #55,  2           // InterfaceMethod java/util/List.add:(Ljava/lang/Object;)Z
      34: pop
      35: aload_0
      36: invokevirtual #51                 // Method get:()Ljava/lang/Comparable;
      39: checkcast     #35                 // class java/lang/Integer
      42: invokevirtual #37                 // Method java/lang/Integer.intValue:()I
      45: aload_1
      46: invokestatic  #59                 // Method sum:(Ljava/util/List;)I
      49: iadd
      50: ireturn
}

What to notice: T survives in the signature attribute (public T get()) for the compiler, but the descriptor the VM uses is ()Ljava/lang/Comparable; — the bound, Definition 6.9.3. Every call of get() is followed by checkcast Integer (offsets 26 and 39), 42 is boxed by Integer.valueOf (6) and unboxed by intValue (42): the three insertions of Algorithm 6.9.4. List.add takes Object — the erasure of its unbounded E.

Dictionary passing and witness tables¶

GHC's desugarer produces dictionary-passing Core; the specialiser removes dictionaries where it can [GHC-Specialise].

Dictionaries in GHC 9.4 Core, before and after optimization

Reproduce (GHC 9.4.7):

mkdir -p hs && cat > hs/Dict.hs <<'EOF'
module Dict (sumSq, useInt) where

sumSq :: Num a => [a] -> a
sumSq xs = sum (map (\x -> x * x) xs)
{-# NOINLINE sumSq #-}

useInt :: [Int] -> Int
useInt = sumSq
EOF
cd hs
LC_ALL=C.UTF-8 ghc -O0 -fforce-recomp -ddump-simpl -dsuppress-all -dsuppress-uniques -dno-typeable-binds -c Dict.hs | sed '/^$/d'
LC_ALL=C.UTF-8 ghc -O -fforce-recomp -ddump-simpl -dsuppress-all -dsuppress-uniques -dno-typeable-binds -c Dict.hs | sed -n '/^useInt/,$p' | sed '/^$/d'

Output (complete):

==================== Tidy Core ====================
Result size of Tidy Core
  = {terms: 17, types: 21, coercions: 0, joins: 0/0}
sumSq
  = \ @a $dNum xs ->
      sum $fFoldable[] $dNum (map (\ x -> * $dNum x x) xs)
useInt = sumSq $fNumInt
useInt
  = \ xs ->
      $wsumSq $fNumInt_$c+ $fNumInt_$c* $fNumInt_$cfromInteger xs

What to notice: at -O0 the translation of Algorithm 6.9.6 is visible verbatim: sumSq takes the dictionary $dNum after the type argument @a, * is selected from it, and useInt passes the instance dictionary $fNumInt. With -O, the worker/wrapper transformation unpacks the dictionary: the worker $wsumSq receives only the three methods it uses (+, *, fromInteger for Int) — still one copy for all types, but no record to unpack per call.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Monomorphization	Generic code as fast as specialized code; needs a finite instance set (Theorem 6.9.7): no polymorphic recursion, no run-time instantiation	Best run time; code size and compile time grow with instances (exponential worst case)	C++ templates report errors per instance (deep instantiation backtraces); Rust checks the generic body once, before instantiation	Medium: substitution + collector; the optimizer does the rest	C++, Rust, Swift/GHC specialization, Go (partly, by GC shape)
Erasure and uniform representation	One copy; old and new code interoperate; no primitive type arguments and no run-time type arguments	Casts and boxing at run time; the JIT removes many	Errors at the generic definition; heap pollution warnings for unchecked code	Low in the compiler (Algorithm 6.9.4), no VM changes	Java, Kotlin/JVM, Scala, OCaml, Haskell values
Dictionary passing and witness tables	One copy; polymorphic recursion, separate compilation and run-time instantiation all work	An indirect call per method; specialization recovers speed where applied	Errors at the definition, in terms of constraints	Medium: dictionaries, coherence, metadata for unboxed values (Swift)	Haskell, Swift, Rust `dyn Trait`, Go interfaces

Choose monomorphization for systems code where the cost of an indirect call or a box matters and binaries may grow; choose erasure when compatibility with an existing runtime or uniform representation dominates; choose dictionary passing when separate compilation and ABI stability of generic libraries matter (Swift's resilient libraries), and let the optimizer specialize the hot paths.

9. Assessment¶

Technique	Quiz ids	Drill	Flashcard tag	Exercises
Monomorphization	`mono-instances`, `mono-polyrec`	—	`monomorphization`	—
Erasure and uniform representation	`erasure-checkcast`, `erasure-bound`	—	`erasure`	—
Dictionary passing and witness tables	`dictionary-translation`, `ghc-dfun`	—	`dictionary`	—

References¶

See the chapter references.

Technique	Code size	Run time per generic operation	Compile time	Variables
Monomorphization	\(\sum_{\text{instances}}\) body size; worst case exponential	as hand-written code (static calls, unboxed data, inlinable)	each instance compiled and optimized	instances reachable (Theorem 6.9.7)
Erasure / uniform representation	one copy per generic function	a cast at each generic result; boxing/unboxing of primitives; an indirection per element	one copy	—
Dictionary passing	one copy + one dictionary per instance declaration	an indirect call per method use; value-generic code must handle unknown sizes (Swift metadata)	one copy; specialization optional	constraints per function

Lesson 6.9 — Implementing generics: monomorphization, erasure, dictionary passing¶

1. Problem and motivation¶

Monomorphization¶

Erasure and uniform representation¶

Dictionary passing and witness tables¶

2. Definitions and algorithms¶

Monomorphization¶

Erasure and uniform representation¶

Dictionary passing and witness tables¶

3. Worked examples¶

Monomorphization¶

Erasure and uniform representation¶

Dictionary passing and witness tables¶

4. Invariants and correctness¶

Monomorphization¶

Erasure and uniform representation¶

Dictionary passing and witness tables¶

5. Complexity¶

6. Variants and refinements¶

Monomorphization¶

Erasure and uniform representation¶

Dictionary passing and witness tables¶

7. In real compilers¶

Monomorphization¶

Erasure and uniform representation¶

Dictionary passing and witness tables¶

8. Comparison¶

9. Assessment¶

References¶