Typesspec

Ad-Hoc Polymorphism: One Name, Different Code

Overloading, operator overloading, type classes, traits, concepts and protocols are one idea: different code per type behind one name. The interesting question is not the syntax but what each does to compilation — resolution, monomorphization or a dictionary.

The question

When one name means different code for different types, who decides which code runs, and when?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

A name bound to a *set* of implementations plus a resolution rule, rather than to a single body. The question this form answers: given the operand or argument types at this call site, which implementation was meant? In most designs the answer is computed at compile time and recorded on the AST node, which is what distinguishes it from the runtime question [[devirtualization]] tries to answer.

What this phase may assume or do

Overload resolution must select exactly one best candidate. If two candidates are equally good the program is ill-formed and the compiler must report ambiguity — never pick arbitrarily, because an arbitrary choice would make the program’s meaning depend on declaration order or on which header was included. Where resolution depends on inferred types, the language must fix a direction: resolve overloads before inference or after it, never mutually, or the algorithm may fail to terminate.

Key points

Parametric means the same code for all types; ad-hoc means different code per type. Every other difference follows from that.
Overloading is closed — only the owner of the name may add a candidate. Type classes, traits and structural interfaces are open.
Openness costs coherence rules: Rust’s orphan rule and Haskell’s instance resolution exist to guarantee at most one implementation applies.
Overload resolution must find a unique best candidate; ties are compile errors, because an arbitrary choice would make meaning depend on declaration order.
Three compilation strategies: resolve at the call site (free, closed), monomorphize (fast, large), pass a dictionary (small, one indirect call per operation).
Dictionary passing is why adding a constraint can slow a Haskell function down and why SPECIALIZE can speed it up without changing the algorithm.
Name mangling exists because overloading does: two functions with one name need two symbols.
Operator overloading is defensible when the type really is an instance of the operator’s algebra, and costs local readability everywhere else.

The distinction that matters

Parametric polymorphism means *the same code for all types*. Ad-hoc polymorphism means *different code per type*. Everything else follows from that one difference, including what each one can prove, what each one costs to compile, and where each one’s errors appear.

The word “ad-hoc” is Strachey’s and is not pejorative — it means the behaviour is supplied case by case rather than derived uniformly. You need it constantly: + on integers and on strings genuinely are different machine operations, print for a date and for a matrix genuinely are different code, and no amount of parametricity will produce either.

The two polymorphisms, compared on every axis that differstypical

Axis	Parametric	Ad-hoc
Number of bodies	One, for every type	One per type, or one per constraint instance
What the body knows about T	Nothing — see `[[parametric-polymorphism]]`	Everything about the specific type it was written for
What the signature proves	Free theorems: what the function cannot do	Nothing beyond the shape. Each instance may behave differently.
Who decides which code runs	There is only one code	Overload resolution, instance selection, or a vtable
When that decision is made	N/A	Compile time in most designs; runtime for virtual dispatch and dynamic languages
Compilation strategy	Erase, or monomorphize as an optimization	Resolve at the call site, monomorphize per instance, or pass a dictionary
Where an error appears	At the call site, as a bound violation	At the call site as “no matching candidate” or “ambiguous call”, often listing candidates
Code size	One copy under erasure; N copies under monomorphization	At least N copies by construction — the bodies are different
Extensibility by a third party	Automatic — works for any type	Depends: type classes and traits allow it; overloading in a closed class does not

Four spellings of the same idea

specRust’s orphan rule requires that either the trait or the implementing type be local to the crate, which is how coherence — at most one applicable impl — is guaranteed in the presence of open extension. Haskell enforces coherence through instance resolution and treats overlapping instances as an opt-in extension with documented soundness caveats. Go interfaces are structural by specification, so conformance requires no declaration at all. These are language-level rules, not compiler behaviours.

The mechanisms look different and divide into two families by one question: can a third party add a case for a type they did not define, to an interface they did not define?

Overloading — C++, Java, C#, Swift — binds several declarations to one name and picks by argument types at the call site. It is simple, it is resolved statically, and it is closed: only whoever controls the name can add a candidate.

Type classes and traits — Haskell, Rust, Swift protocols with extensions — separate the *interface* from the *instances*, so anyone can write impl Display for MyType and the operation becomes available. This is the answer to the expression problem in one direction, and it is why Rust and Haskell libraries compose in a way overload-based ones do not. The cost is coherence: the language must guarantee at most one instance applies, which is why Rust has the orphan rule and Haskell has long arguments about overlapping instances.

Structural interfaces — Go’s interfaces, TypeScript’s structural types — dispatch on whether the type has the right methods, with no declaration of intent. Third-party extension is automatic and accidental conformance is possible; see [[structural-vs-nominal]].

Runtime protocols — Python’s __add__/__radd__, Ruby’s coerce, JavaScript’s Symbol.toPrimitive — do the same dispatch on the values at execution time. Fully open, fully dynamic, and the resolution rules (try the left operand, then the reflected operation on the right) are specified in the language’s data model rather than in a type system.

The same idea in five languages

1C++      void print(int);  void print(std::string);
2         // closed set. Resolution ranks conversion sequences.
3 
4Rust     trait Display { fn fmt(&self, f: &mut Formatter) -> Result; }
5         impl Display for MyType { ... }
6         // open: anyone may add an impl, subject to the orphan rule.
7 
8Haskell  class Show a where show :: a -> String
9         instance Show MyType where show x = ...
10         // open, with coherence enforced by instance resolution.
11 
12Go       type Stringer interface { String() string }
13         // structural: any type with String() string qualifies,
14         // whether or not its author intended it.
15 
16Python   class MyType:
17             def __add__(self, other): ...
18             def __radd__(self, other): ...
19         // runtime protocol: left operand first, then reflected.

The dividing line is not syntax. It is whether a third party can add a case. Overloading says no; type classes, traits and structural interfaces say yes — and each pays for that openness differently, in coherence rules, in accidental conformance, or in errors that only appear at runtime.

What each does to compilation

This is the section that matters for a compilers course, because the three strategies produce genuinely different binaries from source that looks the same.

Overload resolution picks a body at the call site and emits a direct call. Zero runtime cost. Its consequence for the compiler is that the entire candidate set must be *visible* at every call site, which is why C++ requires headers and why [[name-mangling]] exists at all — two functions named print need two different symbols for the linker, and the mangling encodes the parameter types.

Monomorphization generates a specialized copy of the generic body per instantiation, with the constrained operations resolved and inlinable inside it. Fastest code, and the bill is code size and compile time proportional to the number of distinct instantiations. This is Rust’s default and what C++ templates do by construction.

Dictionary passing compiles one body and adds a hidden parameter: a record of the functions the constraint demanded. show :: Show a => a -> String becomes, roughly, show :: ShowDict a -> a -> String. One copy of the code regardless of how many types use it, and one indirect call per constrained operation. Haskell’s default, with SPECIALIZE available to opt into monomorphization where it matters.

The third strategy is worth recognising because it is the same shape as a vtable, and because it explains a performance characteristic people find mysterious: adding a constraint to a Haskell function can make it slower, and adding SPECIALIZE or making it monomorphic can make it dramatically faster, with no change to the algorithm.

Three compilation strategies for one language featureimplementation

Strategy	Resolved when	Runtime cost	Code size	Compile cost	Used by
Overload resolutionspec	At the call site, statically	None — a direct call	One body per declared overload, which the programmer wrote anyway	Ranking conversion sequences; superlinear in candidate count	C++, Java, C#, Swift
Monomorphizationimplementation	At instantiation, statically	None — direct, inlinable calls, unboxed values	One body per distinct instantiation	High: the body is type-checked or codegen’d repeatedly — see `[[monomorphization]]`	Rust generics, C++ templates
Dictionary passingimplementation	At the call site, statically — but the call is indirect	One extra argument, one indirect call per constrained operation	One body total	Low	Haskell by default; Rust `dyn Trait`
Virtual dispatchtypical	At runtime, from the receiver	A vtable load and an indirect call, unless devirtualized	One body per implementation	Low	Java, C#, C++ `virtual`, Go interface values
Runtime protocol lookupimplementation	At runtime, from the value’s tag	A method lookup, amortised by `[[inline-caches]]`	One body per implementation	None	Python, Ruby, JavaScript

Operator overloading, and the honest case against it

specJava’s specification defines + on String and provides no mechanism for user-defined operator overloading; the remove(int) versus remove(Object) ambiguity is a documented consequence of overload resolution preferring the primitive candidate for an untyped integer literal. C++ specifies overload resolution as a ranking over implicit conversion sequences with explicit tie-break rules, and a call with no unique best candidate is ill-formed rather than resolved arbitrarily.

Operator overloading is ad-hoc polymorphism applied to symbols, and it is where the tradeoff is most visible because the syntax is the shortest possible. a + b on a matrix type reads correctly and compiles to the right thing. a + b on a type where + was given some other meaning reads correctly and does something else, and the reader has no local way to tell which they are looking at.

The defensible position is narrow: overload an operator when the type is genuinely an instance of the algebraic structure the operator denotes — numbers, vectors, matrices, durations, monetary amounts, sets. Rust encodes exactly this by making operators traits (Add, Mul, Index), so overloading one is a deliberate impl with a documented contract. Go declines entirely, on the stated grounds that a reader should be able to tell what a line costs.

The indefensible cases are well known and instructive. C++’s << for stream output overloads a bit-shift for something unrelated, and is defended only by familiarity. Python’s + on lists concatenates while + on NumPy arrays adds elementwise, which means the meaning of a + b depends on a type the reader must already know. And any operator that allocates, blocks or fails turns a line that looks like arithmetic into one that can throw or take milliseconds.

The compilation cost is real too. Every overloadable operator turns an expression node from a fixed rule into a resolution problem, which means the type checker cannot type a + b bottom-up without candidate search, and inference interacts badly — see [[hindley-milner]]’s exclusion of overloading for the same reason.

Java deliberately has no user-defined operator overloading, and specifies + on String as a language rule instead — one exception, written into the specification, rather than an open mechanism.
The classic overload trap is Java’s List.remove(int) versus List.remove(Object): list.remove(1) removes the element at index 1, and list.remove(Integer.valueOf(1)) removes the value 1. Both compile, both are reasonable, and the difference is invisible at a glance.
C++ overload resolution ranks candidates by conversion sequence and has enough tie-breakers to fill a chapter of the standard; a char argument silently preferring an int overload over a long one is a routine surprise.
Ad-hoc dispatch on more than one argument — multiple dispatch, as in Julia and CLOS — is strictly more expressive and strictly harder to compile and to reason about; most languages settled for single dispatch plus overloading because the resolution rules stay explicable.

How it works

The steps, in the order the compiler takes them.

Name resolution finds a *set* of candidates for the name rather than a single declaration — the overload set.
The checker types each argument, then filters the set to the viable candidates: those whose parameter count matches and whose parameter types the arguments can convert to.
Each viable candidate is scored by the implicit conversion sequence required for each argument, using the language’s ranking (exact match beats promotion beats standard conversion beats user-defined conversion).
If exactly one candidate is best on every argument, it is selected and recorded on the call node. If none, report “no matching function”, ideally listing why each candidate failed. If two tie, report ambiguity.
For constrained generics, the equivalent step is instance or impl selection: find the unique implementation of the trait for the instantiating type, subject to the coherence rules.
The back end then emits either a direct call to the selected body, a call into a specialized monomorphized copy, or a load from a dictionary or vtable followed by an indirect call.
The linker needs distinct symbols for same-named functions, which is what [[name-mangling]] encodes.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

A call silently selects a different overload after an unrelated header is included or an implicit conversion is added, and the program’s behaviour changes with no source edit at the call site.
list.remove(1) removes the element at index 1 when the value 1 was meant. Both overloads are reasonable and neither the compiler nor the reader flags it.
A compile error says “no matching function” and lists twelve candidates with no explanation of why each failed — the error message that has cost the C++ community more hours than any other.
Adding an impl in a new crate makes a previously compiling program ambiguous, because two implementations now apply to one type.
A Haskell function is slow, and the reason is a dictionary passed at every call because it was written with a class constraint and never specialized. No profile line points at the dictionary; the time is spread across indirect calls.
A binary is unexpectedly large and slow to build because monomorphization instantiated one generic function for forty types, most of which differ only in a phantom parameter.
A structurally typed interface accidentally matches a type that was never meant to implement it, the method with the matching name does something unrelated, and the wrong behaviour is dispatched with no diagnostic — see [[structural-vs-nominal]].

When it helps

Whenever the behaviour genuinely differs per type. Forcing it through parametric polymorphism produces constraint hierarchies that are harder to read than honest per-type code.
Designing extensible libraries: trait- and type-class-based dispatch lets consumers add support for their own types without modifying yours, which is the difference between a library that composes and one that does not.
Diagnosing a “why is this call slow / large / ambiguous” question, where the answer is almost always which of the three strategies the compiler used.
Understanding why your compiler wants an annotation on an overloaded call: resolution and inference interact, and the annotation breaks the cycle.

When it hurts

When the overloaded name hides a meaningful difference in cost or semantics. + that allocates, == that hits the network, [] that throws — the syntax says cheap and local, and it is neither.
Under heavy monomorphization, where build times and binary size grow with instantiation count and the fix is to move the non-generic part of the body into a non-generic inner function.
When resolution rules become load-bearing. If a program’s behaviour depends on subtle conversion ranking, the next reader — and the next compiler version — may not agree with you.
In a language with structural conformance, where accidental matches make the dispatch target depend on a method name rather than on any declared intent.

What it costs

Every one of these is paid by something.

Open extension via traits and type classes buys third-party extensibility and pays in coherence machinery — orphan rules, instance resolution, and errors that appear only when two crates are combined.
Overloading buys zero-cost static dispatch and pays in a resolution algorithm that must be specified in detail, in errors that list candidates rather than explaining them, and in a call whose meaning can change when the visible candidate set changes.
Monomorphization buys direct, inlinable, unboxed code and pays in binary size and compile time proportional to instantiation count — see [[monomorphization]] for the mitigation.
Dictionary passing buys one compiled body and fast builds and pays an indirect call per constrained operation, which is invisible in a profile because it is spread everywhere rather than concentrated.
Operator overloading buys notation matched to the domain and pays with every reader’s ability to know what a line does without knowing the operand types.

What else you could do

What a different compiler or language does instead, and when that is better.

Parametric polymorphism, where one body serves every type and the type variable proves the body cannot depend on it — see [[parametric-polymorphism]].
Subtype polymorphism with virtual dispatch: one body written against a base type, and the receiver decides at runtime. Different cost profile — one vtable indirection, no code duplication — and different extensibility, since only subtypes participate.
Distinct names: printInt, printString. No resolution rules, no ambiguity, no mangling, and a namespace full of near-duplicates. C did this for decades and it is why <tgmath.h> exists.
Multiple dispatch, as in Julia and CLOS: resolution considers all argument types at runtime. Strictly more expressive, harder to compile, and it makes “which method runs” a question you cannot answer by reading the call site.
Runtime protocol dispatch, as Python and Ruby use: fully open, resolved on values, and specified in the data model rather than the type system — see [[static-vs-dynamic-typing]].

See it for yourself

The flag, dump or tool that shows you this directly.

C++: clang++ -fsyntax-only on an ambiguous call prints the candidate set with the conversion each would require; nm -C (or c++filt) shows the mangled symbols that overloading produced.
Rust: cargo llvm-lines shows which generic functions monomorphized into the most code; -C llvm-args=-print-after-all shows the specialized bodies.
Haskell: -ddump-simpl reveals dictionary arguments as explicit parameters in Core, and -ddump-spec shows what SPECIALIZE produced. This is the fastest way to see dictionary passing as a real mechanism rather than a metaphor.
Java: javap -c on a call site shows which overload the compiler chose, encoded in the method descriptor of the invokevirtual.
Go: go build -gcflags=-m reports interface conversions and escape analysis, showing where a structural dispatch became a runtime one.
Compiler Explorer with two overloads and an argument that requires a conversion — change the argument type by one step and watch the selected symbol change.

Plausible wrong readings

Stated the way a confident engineer states them.

“Overloading and generics are the same feature.” One selects among several bodies; the other has one body. The distinction determines what the signature proves and what the compiler emits.
“Type classes are just interfaces.” Interfaces are declared by the type’s author; instances can be declared by anyone, for types they do not own. That difference is why trait-based ecosystems compose.
“Ad-hoc polymorphism is resolved at runtime.” Overloading, trait selection and instance resolution are all static in the mainstream designs. Virtual dispatch and dynamic protocols are the runtime cases, and they are a subset.
“Monomorphization is what generics mean.” It is one of three strategies. Haskell compiles one body and passes a dictionary; Java erases; Rust monomorphizes. The source looks similar and the binaries do not.
“Operator overloading is bad.” It is a trade. Matrix, money and duration types are better with it; a << that means “write to a stream” is worse with it. Say which case you are in.

Misconceptions

The claim, and what is actually true.

Ad-hoc polymorphism is a weaker form of generics.

They solve different problems. Generics give you one body and a theorem; ad-hoc gives you per-type behaviour that no single body could provide. Most real code needs both, often in the same function via a constrained generic.

A constrained generic is still parametric.

The constraint is exactly the point at which it stops being parametric. <T: Display> grants the body an operation whose implementation differs per T, which is ad-hoc polymorphism wearing generic syntax.

Name mangling is an implementation detail with no design consequence.

It exists because overloading does, and its shape determines [[abi-stability]]: two compilers that mangle differently produce object files that cannot be linked, which is why C++ ABI compatibility is a decades-long concern and C’s is not.

Traits and interfaces have the same extensibility.

An interface must be implemented where the type is declared. A trait impl can be written in a third crate for a type from a second crate, subject to the orphan rule. That is the difference between adapting a library and forking it.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

Ad-hoc polymorphism is one name with different code behind it depending on the types involved: + for integers and for strings, print for a date and for a list. It comes in a few flavours — overloading, where several functions share a name; type classes and traits, where anyone can add a case for their own type; and runtime protocols like Python’s __add__. The contrast with generics is simple and worth holding onto: generics are one piece of code that works for every type, ad-hoc is different code for each type. Both are useful, and code often uses them together.

practical

The two practical traps are overload surprises and unnoticed dispatch cost. For the first, be suspicious of any call where a cast, a literal, or an implicit conversion is involved — those are the inputs to resolution, and changing one can change which function runs with no other visible edit. Java’s List.remove(int) versus remove(Object) is the canonical example and is not exotic. For the second, know which strategy your language uses: Rust monomorphizes so generics are free at runtime and expensive at build time; Haskell passes dictionaries so a class constraint costs an indirect call unless you specialize; Java erases and dispatches virtually. When a generic-heavy build is slow or a generic-heavy hot loop is slow, the strategy is nearly always the reason, and the fixes are different in each case.

advanced

Ad-hoc polymorphism is where the expression problem shows up in a compiler course. Overloading and inheritance make it easy to add a new *type* and hard to add a new *operation* to a closed hierarchy; pattern matching over a sum type makes it easy to add an operation and hard to add a type. Type classes and traits are the design that unbundles the two: the interface is a separate declaration, instances live wherever their author likes, and both axes become extensible — at the price of coherence, which is a global property the language must now enforce. Rust’s orphan rule and Haskell’s reluctance to bless overlapping instances are both consequences of that price, and both surface to users as errors that are hard to explain because they are about the whole program rather than the file being edited. When you see a language rule that seems arbitrarily restrictive about where an implementation may be declared, coherence is nearly always the reason, and the alternative is a program whose meaning depends on which crates happened to be linked.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

specC++ specifies overload resolution as a ranking over implicit conversion sequences with defined tie-breakers, and a call with no unique best candidate is ill-formed. Java specifies a three-phase resolution (no boxing/varargs, then boxing, then varargs) and no user-defined operator overloading. Rust specifies coherence through the orphan rule. All three are language rules; a compiler that resolved differently would be non-conforming.

implementationGHC passes dictionaries by default and specializes when instructed with SPECIALIZE, INLINABLE or -fspecialise-aggressively; whether a given constrained function ends up with a dictionary argument or a specialized copy is visible only in Core output and changes with optimization flags and GHC version. Do not assume either strategy for a specific function without looking.

implementationRust monomorphizes generic functions and uses vtable dispatch for dyn Trait. Which one applies is determined by the source (impl Trait/generic parameter versus dyn), so it is under the programmer’s control — but the resulting code size and inlining behaviour differ substantially and are best measured with cargo llvm-lines rather than predicted.

typicalThe claim that virtual dispatch costs a vtable load and an indirect call describes mainstream implementations and is frequently untrue after optimization: a JIT or an LTO build may devirtualize a monomorphic call site entirely — see [[devirtualization]] and [[speculative-optimization]]. Treat the cost as an upper bound that optimizers often remove.

If you were asked this in an interview

What is the difference between parametric and ad-hoc polymorphism? Give one thing each can do that the other cannot.
Why does name mangling exist?
Haskell compiles one body for a constrained function and Rust compiles many. Explain both strategies and when each is the better choice.
What does Rust’s orphan rule prevent, and what does it cost?
list.remove(1) — what does it do in Java, and why is that a hard bug to see?

Connections

Performancecpu-profiling measure-before-optimizing

API Designsdk-design api-granularity

Domains that do not exist yet

Software Design — The expression problem, and choosing between an open hierarchy and a closed sum type
Whether to model variation as subtypes or as cases of one type is a design decision with consequences on both axes of extensibility. This lesson covers what each choice does to compilation; the design judgment belongs there.
Programming Languages & Runtime Internals — Vtables, method caches and how a dynamic language resolves an operator at runtime
The runtime rows of the strategy table are implemented by the runtime: a vtable layout, a method cache, an inline cache. This lesson names the cost; the mechanism is theirs.