Monomorphization Is the Dictionary

This part is about a change in the method’s economics. The previous parts built real tools — servers, games, inspectors — to force the language to grow, and each tool cost days. But with the memory model finished and the soundness holes closed, the remaining questions had become precise enough that a ten-minute probe could decide them: write the smallest program that touches the question, measure, and let the number pick the work. This part is six such probes and the nine releases they produced. The first probe was pointed at the language’s biggest open design question, and what it found dissolved the question rather than answering it.

The question, and the measurement that reframed it

The question on file was: does the language need type classes? The generic pairing heap from the previous part had produced the honest measurement — writing generic containers is fine, but threading a comparator closure through every operation is a visible tax, and using < through a type variable is simply impossible: fn a -> fn b -> a < b pinned its arguments to int. The design note drafted for this session proposed a middle path, a dictionary-synthesis scheme at concrete call sites. Then the session started the way sessions here are supposed to start — by reading what the code actually does — and found something better than the proposal: equality already works through type variables, and had for a long time. fn a -> fn b -> a == b is genuinely polymorphic. Nobody had built type classes for it. So the real question was not “how do we add constraints” but “why does equality get away without them?”

Why equality gets away with it

Two mechanisms, both built for other reasons, turn out to jointly play the role of a dictionary. In the interpreter, values at runtime are always concrete, so a structural comparison function just walks them — no type information needed. In the compiled backends, a polymorphic function is monomorphized: every use at a concrete type gets its own specialized instance, and inside that instance’s body the operands of == have concrete types — exactly the situation the derive machinery already handles by emitting a per-type equality function. The scheme carries no constraint because by the time code is generated, there is nothing left to constrain. Haskell passes a dictionary at runtime; this language’s monomorphizer is the dictionary, resolved entirely at compile time. The previous part’s fixes — pristine clones, late promotion to multi-instance — had quietly made this machinery trustworthy. Ordering was blocked by exactly one thing: a historical rule in the type checker that said an unresolved comparand defaults to int.

Deleting the default

The fix was to delete that rule — ordering now unifies its operands and stops, precisely what equality has always done. Programs that used the int default still typecheck, since instantiation covers them; the only suite failures were two assertions that had pinned incidental slot numbers. And the consequences cascaded for free, because the prelude was already written in the honest style: list_sort is defined as list_sort_by with the comparator fn a -> fn b -> a < b — a definition that had been silently int-only and became generic the moment the default died. Sorting a list of tuples now needs no annotation and no comparator. The pairing heap’s hand-written, type-annotated comparator collapsed to one polymorphic line. The compiled code shows the mechanism plainly: the instance calls the derived tuple-compare function, the same one derive-ord built three parts ago.

What was decided by not deciding

It is worth being precise about what this is and is not. There are still no type classes: no way to declare that a type’s ordering is something other than its structure, no constraints in type schemes, no instance declarations. What exists is the derive family — show, JSON, equality, ordering — available on any concrete type and now through any type variable, with monomorphization as the resolution mechanism. That is the third appearance of the same design instinct in this project: uncurrying optimized exactly the saturated call sites; the derive family specializes exactly at concrete types; and now polymorphic ordering resolves exactly where instantiation makes things concrete. Commit to the specific point where the general problem becomes easy, and decline to build the general machinery until a program demonstrates it cannot live without it. The type-class question is still open in the large — user-defined instances remain future work, waiting for their forcing program — but the ergonomic payload it was carrying arrived without it. The next probe was pointed somewhere much less abstract: the live game on the project’s own website, which turned out to have been broken all along.