The idea: types nobody wrote

In OCaml or Haskell you can write fun x -> x + 1 with no types at all, and the compiler still knows it is int -> int. This is type inference. The method most of these languages use is Hindley-Milner. It works in two phases. First it gives every node of the expression tree an unknown type, a type variable t1, t2, …, and writes down what each node's rule says about them as equations. Then it solves the equations by unification. The answer is a substitution S, a table "t4 is int, t1 is int -> int, …" (Demo 1).

Three steps for fun x -> x + 1. Left: the tree with fun x : t1, + : t3, x : t4 and 1 : t5, and x gets t2. Middle: six constraints, C1 t4 = t2, C2 t5 = int, C3 t4 = int, C4 t5 = int, C5 t3 = int, C6 t1 = t2 -> t3, each marked bind except C4, marked same. Right: the substitution t4, t5, t2 and t3 map to int and t1 maps to int -> int, so the type of the function is int -> int.
A variable per node, an equation per rule, and S tells what every variable is.

The tree is what the parser builds (see LL(1) parsing). Inference is part of the semantic analysis phase in the compiler pipeline.

Phase 1: constraints from each node

Press Generate. The page walks the tree from the top. Each node gets the next fresh variable, and a fun also gives its parameter one. The parameter goes into the environment, the list of names in scope with their types. When a node's children are done, the node's rule flies to the constraint list:

Node (its variable t)Constraints
literal 1 or truet = int, or t = bool
use of a parameter x of type txt = tx
fun x -> et = tx -> te
f a (apply)tf = ta -> t
e1 + e2t1 = int, t2 = int, t = int
if c then a else btc = bool, ta = tb, t = ta

The rule for apply is the key one. It does not look up a type for f. It says f must be some function from the argument's type to the result's type. For fun x -> x + 1 this gives 6 constraints over 5 variables.

Phase 2: unification

Press Unify. The page takes the open constraints from top to bottom. It first applies S to both sides, so variables that are already known get replaced. The line under the list shows the result. Then one of five cases applies:

A table of five unification cases. Both sides equal, int = int: drop it. A variable not inside the other side, t4 = t2: bind t4 to t2 in S. Two arrows, t8 -> t8 = t9 -> t6: split into t8 = t9 and t8 = t6. A variable inside itself, t2 = t2 -> t3: the occurs check fails, no type. Different shapes, int = bool: clash, no type.
Drop, bind or split until nothing is left, or stop at the first error.

When the page binds a variable, it also replaces that variable inside every entry already in S. So S never has a known variable on a right side, and reading a type off S takes one look. A split puts the two new constraints right under the old one. In Demo 2 (twice, fun f -> fun x -> f (f x)) the two uses of f give 7 constraints; one of them is arrow = arrow and splits into 2 more, so 9 in total and 8 entries in S.

A clash means two different type shapes must be equal. (fun x -> x + 1) true needs x to be int because of the +, and bool because of the argument. Unification stops at int = bool (Demo 4). Real compilers report this as "this expression has type bool but an expression was expected of type int".

The occurs check

In fun x -> x x, x is applied to itself. Its type t2 must be a function that takes t2: the page gets t2 = t2 -> t3 (Demo 5). Binding t2 to a type that contains t2 would make an infinite type, t2 = (t2 -> t3) -> t3 = … with no end. So before every bind, unification checks that the variable does not occur in the other side. Here it does, and the expression has no type.

The most general type

When unification finishes, apply S to the root's variable. Some variables may be left over, bound to nothing. Nothing in the program forces them, so they can be any type. The page renames them 'a, 'b, … as OCaml prints them. Demo 2 ends with ('a -> 'a) -> 'a -> 'a and Demo 3 (compose, fun f -> fun g -> fun x -> f (g x)) with ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b. Unification only binds what an equation demands, so this is the most general type (the principal type): every other correct type, like (int -> int) -> int -> int, is an instance of it. Functions of several arguments come out curried; see closures and currying.

let-polymorphism: generalize, then copy

In let id = fun x -> x in if id true then id 1 else 2, id is used at bool and at int. That works because let is treated in a special way (Demo 6):

  1. Infer the part after = first and solve its 2 constraints right away. id has type t3 -> t3.
  2. Generalize: t3 appears nowhere else in the environment, so it gets a "for all": id : ∀t3. t3 -> t3.
  3. Instantiate at every use: each use of id gets a fresh copy. id true gets t8 -> t8 and id 1 gets t12 -> t12. t8 becomes bool and t12 becomes int, with no conflict.

The whole run has 17 constraints (13 generated, 4 from 2 splits), S ends with 13 entries, and the type is int.

Left, let id = fun x -> x: id gets the scheme for all t3, t3 -> t3. id true uses a fresh copy t8 -> t8 with t8 = bool, and id 1 a fresh copy t12 -> t12 with t12 = int. Both succeed and the type is int. Right, the same id as a fun parameter: id has one variable t3. id true binds t3 to bool -> t5; id 1 then needs bool -> t5 = int -> t8, which is a clash, bool = int.
A let-bound name gets a fresh copy at each use; a parameter shares one variable.

Now pass the same id as a fun parameter instead: (fun id -> if id true then id 1 else 2) (fun x -> x) (Demo 7). A parameter is never generalized, because the function could be called with any argument. Both uses share one variable t3. The first use makes t3 = bool -> t5, the second needs int -> t8, and the split gives the clash bool = int. This is the limit of Hindley-Milner: functions can be polymorphic, but a function cannot take a polymorphic argument.

Where this runs

LanguageWhat it infers
Standard ML, OCaml, F#Hindley-Milner with let-polymorphism, as on this page; type annotations are optional
HaskellHindley-Milner plus type classes (Num a => a -> a)
Rust, Swift, Kotlin, TypeScript, C++ autoLocal inference inside a function body; function signatures are written by hand

The environment is the compile-time view of scope from static vs dynamic scoping: a name's type comes from the nearest enclosing binder in the source.

See also Three-Address Code, Basic Blocks and Local Optimizations for what the compiler does with a well-typed tree next.

What the page leaves out

The page has only int, bool and function types, and one ML-style expression at a time. It leaves out tuples, lists and user-defined data types, recursion (let rec), the value restriction on generalizing (for references), type classes, union-find with path compression (how real compilers store S quickly), Algorithm W and Algorithm J as the textbooks write them (they mix the two phases, as the page does only at let), error messages that point at the right source line, and type annotations checked against the inferred type.

On the mind map

Open the Java & the JVM mind mapJava & the JVMFrom source to bytecode: translate first, or while runningFrom source to bytecodeStartup and class loading: what happens before main()Startup and class loadingJIT compilers: compile hot code using profilesJIT compilersMemory and GC: find and free unreachable objectsMemory and GCCollections: how java.util stores keysCollectionsThreads and memory model: Java threads on real coresThreads and memory modelSpring framework: a container builds your objectsSpring frameworkCompiler vs interpreterCompiler vs interpretercompile once ahead, or decode every runTiny compilerTiny compilerlexer, parser, code generator, VMThree-address codeThree-address codeFold + copy prop make code dead: 15→13Hindley-Milner inferenceEquations per node, unify into SStatic vs Dynamic ScopingStatic vs Dynamic ScopingWritten-in vs called-from decides xLL(1) ParsingLL(1) ParsingStack top + one token pick the productionLR parsingLR parsingShift tokens, reduce handles bottom upjavacjavacsource to type-checked .class bytecodeLambdas and invokedynamicLambdas and invokedynamicfirst call bootstraps, then links onceOpen the Java & the JVM mind mapJava & the JVMtranslate first, or while runningFrom source to bytecodeCompiler vs interpreterCompiler vs interpretercompile once ahead, or decode every runTiny compilerTiny compilerlexer, parser, code generator, VMThree-address codeThree-address codeFold + copy prop make code dead: 15→13Hindley-Milner inferenceEquations per node, unify into SStatic vs Dynamic ScopingStatic vs Dynamic ScopingWritten-in vs called-from decides xLL(1) ParsingLL(1) ParsingStack top + one token pick the productionLR parsingLR parsingShift tokens, reduce handles bottom upjavacjavacsource to type-checked .class bytecodeLambdas and invokedynamicLambdas and invokedynamicfirst call bootstraps, then links once
This page on the Java & the JVM mind map · 35 pages in 7 branches · open it to see the whole map and test yourself in recall mode.