OCaml Type Checker Implementation Tutorial | Static Type Checking

This section covers advanced type inference features for practical programming languages. The let binding rule infers a type, generalizes it, adds it to the context, and infers the body type—forcing generalization at let bindings. Letrec extends this to recursive definitions by generating a meta variable, adding the binding to the context before checking the body, and solving the resulting equation. Performance optimizations include grouped instantiation/generalization and lambda/let ranking that store generalization information directly on meta variables rather than searching the entire context.

Let expressions are the most complex type checking rule. When type checking let x:t1 = e1 in e2, we first verify that e1 has type t1 in the current static environment (checking the programmer's type annotation). Then, we recursively type check e2 in a new static environment that extends the current one by binding x to t1. The result type of the entire let expression is the type of e2.

Recursive let expressions (where the bound variable is used in its own body) require special handling. The checker must extend the environment with the variable bound to a type variable, then type check the body in this extended environment. This allows the recursive call to use the function's type.

For first-class functions to be a true language feature, the type system must know about functions and functions must know about their types. This creates a tight coupling between the ability to hold a function and represent it in the type system. Functions can point back to themselves in the type hierarchy (recursive functions), which is a dimensionality that most type systems don't have.

Named records with field names require exact name-type matching for equivalence. Pointers are constructed as 'pointer T' for objects pointing to type T objects. Function types use D → R notation, where D is the domain (input types) and R is the range (output type). Higher-order functions returning other functions use nested arrow notation (e.g., 'integer → (real → character)'). A type system is a collection of rules assigning type expressions to program objects, implemented via syntax-directed definitions. The type checker implements these rules, with complexity increasing with type system strength.

Parametric polymorphism allows single function implementations to work with arguments of different types using type variables (lowercase). The identity function 'id :: a -> a' works on any type. Type variables must be instantiated by the same type in all occurrences. Functions like 'length' work on lists of any element type because the implementation doesn't depend on element values. Type unification determines if a function can be applied by finding type variable instantiations that make expected and actual types equal. This enables generic programming where one implementation serves multiple types, reducing code duplication while maintaining type safety.

System F extends untyped lambda calculus with polymorphism through type variables (α, β, γ), type abstraction, and type application. The motivation comes from the identity function λx.x, which should work with any type, not just specific ones like Bool. Type variables represent 'any type' and allow functions to be generic. For independent variables, distinct type variables are needed (α for x, β for y), giving types like α → β → α × β.

ReasonML supports parametric polymorphism through type variables (written as 'a' or 'b'). The speaker explained that when a function is defined without specific types, the compiler creates type variables that are resolved when the function is called. This allows functions to work with any type while maintaining type safety. Learning ReasonML requires significant time investment, with a developer familiar with React potentially becoming productive within a month.

The Hindley-Milner type inference algorithm is a three-step process for automatically determining types in statically typed functional languages: (1) assign type variables to all AST nodes, (2) generate constraints based on language constructs (function applications produce t1 → t2, lambdas produce τ → τ', etc.), and (3) solve these constraints using unification, which decomposes complex type equalities into simpler ones. The algorithm handles polymorphism by generalizing over unconstrained type variables, and includes an 'occurs check' to prevent infinite type recursion. This approach guarantees the principal type property, always inferring the most general type possible, and is EXPTIME-complete in complexity.

This major section presents the practical implementation of unification algorithms and extends the type system to support polymorphism. The algorithm handles four cases: empty sets return identity substitution; base types require syntactic equality; compound types require matching constructors and recursively unifying arguments; meta variables require occurs check before substitution. The occurs check prevents infinite recursion by ensuring meta variables don't appear in their own substitution targets. Performance optimizations are discussed including mutable variables for efficient substitution, union-find data structures for equivalence classes, and graph-based approaches with topological sorting. The section then extends to polymorphism through type schemes (∀α.T), introducing free type variable computation and the instantiate function to remove ∀ quantifiers by substituting fresh meta variables.

This section demonstrates the complete integration of parsing and type checking. The instructor shows how to combine the parser and type checker to take a string, parse it into an unchecked term, type check it with an empty context, and return a Sigma type containing the type and well-typed term. The case expression is used for pattern matching on term constructors with dependent types. The instructor demonstrates the complete pipeline with examples like 'lambda any not' (which succeeds) and 'lambda any not applied to n' (which fails with a type error). The forget origin function transforms checked terms into simple pairs of type and well-typed term for further processing. This demonstrates the full pipeline from source code to verified well-typed terms.

The type checker sits after parsing and semantic analysis but before intermediate code generation. Input is a parse tree; output is an annotated parse tree with type information. Type checking verifies operators receive compatible operands (e.g., '+' requires numeric operands), array indices are integers, and indexing applies only to arrays. Challenges include operator overloading (same operator with different meanings) and polymorphism (same function name with different parameter types). The checker must determine which version of overloaded functions is being referenced based on actual arguments.

The processing pipeline for programming languages involves three main stages: lexical analysis (tokenizer/scanner) groups characters into tokens with types and values; syntactic analysis (parser) validates token order and produces an Abstract Syntax Tree (AST); and semantic analysis (type checker) verifies correctness. The AST serves as input to either a code generator (producing bytecode or machine code) or an interpreter. This pipeline enables transformation from human-readable source code to executable programs.

A complete compiler integrates three stages: tokenizer, parser, and generator. The tokenizer breaks source code into tokens. The parser builds an AST from tokens according to grammar rules. The generator produces target code from the AST. Each stage passes its output to the next stage, forming a pipeline. Error handling occurs at each stage, with failures propagating up the pipeline to indicate where parsing or generation failed.

The GHC compiler front-end transforms source code through several stages: (1) The renamer resolves lexical scopes by replacing names with unique IDs and generates a type environment with all types and type classes. (2) Strongly connected component analysis identifies mutually recursive binding groups, allowing proper handling of mutual recursion. (3) The type checker performs a second SCC analysis on type signatures to enable refined type checking. (4) The desugarer converts the abstract syntax tree into a compact core language representation, preserving the type environment. This pipeline maintains type information throughout while progressively transforming the program into an optimized intermediate form.

Milner's slogan 'well-typed programs do not go wrong' captures type soundness: well-typed programs never get stuck during evaluation. Formally, if E has type T under empty environment, then for any E' such that E steps to E', either E' is a value or E' can take another step. Progress and preservation prove this: progress ensures well-typed programs can always take a step, preservation ensures types are preserved during evaluation. Logical relations provide a semantic alternative, defining families of relations indexed by types that capture which values and expressions 'behave like' their claimed types. For Bool, V_Bool contains true and false. For function types T1->T2, V contains Lambdas whose bodies belong to the expression relation for T2 under extended environments. Expressions belong to the relation if when irreducible, they belong to the appropriate value relation. This ensures functions behave correctly when applied to well-behaved inputs.

Type soundness is a mathematical property ensuring that if type checking succeeds, the program never crashes. This differs from type safety and requires formal proof. The Lean theorem prover can prove type soundness by defining operational semantics with 'fuel' (step limits) to ensure termination. EY's type soundness was proven by porting the interpreter to Lean, defining type rules, and proving preservation and progress theorems. This demonstrates that profound results about code behavior can be established statically through formal verification, going beyond what testing can achieve.

Type safety in System F is proven via progress and preservation. Progress states that for a closed term e with type a in empty contexts, either e is a value or e steps to e'. Preservation states that if e has type a and e steps to e', then e' also has type a. Progress is proven by induction on typing derivations, with new cases for big lambdas and type applications. The canonical forms property states that values are either little lambda x dot e or big lambda alpha dot e. For type applications, if e is a value of type for all alpha dot b, it must be big lambda alpha dot e', and the for all evaluation rule substitutes a for alpha in e'.

Syntactic type soundness (progress and preservation) proves that well-typed programs cannot get stuck, but fails to verify data abstraction guarantees or safe encapsulation of unsafe language features; semantic type soundness provides a stronger theorem by defining types as semantic predicates on values and proving that typing rules are sound lemmas about these models, enabling verification of data abstraction mechanisms and safe encapsulation of unsafe code through frameworks like Iris that abstract away complex step-indexed reasoning.

Preservation (subject reduction) ensures that reducing an expression maintains its type, preventing sudden type changes during evaluation. Progress ensures well-typed programs never get stuck—they always have a way to make progress toward a value. Small step semantics makes progress easier to express, while big step semantics struggles with distinguishing non-terminating from stuck terms.