A type checker processes `let f x = x + 1` with no type annotations. It assigns type variable α to x. What constraint does the `+` operation generate?
Aα = float, because + in most languages operates on floating-point numbers by default
Bα = int, because + requires operands of the same type and 1 is an integer literal, so x must also be int
CA type error, because x has no annotation and the checker cannot proceed without one
DNo constraint — type variables are left unresolved until the function is called with a concrete argument
Constraint-based type checking generates constraints from how values are used, not from annotations. The + operator requires both operands to have the same numeric type; since 1 is an integer literal with type int, the constraint α = int is generated. The solver then records this constraint and, when it processes the whole program, it knows f takes an int and returns an int — without any annotation from the programmer. This is precisely the power of constraint-based type inference.
Question 2 Multiple Choice
What is the key architectural advantage of separating constraint generation from constraint solving in type checking?
AIt makes type checking faster because constraints can be checked in parallel during lexical analysis
BIt allows the type system to be extended with new constraint forms (subtyping, trait bounds, refinements) without rewriting the core solver
CIt eliminates the need for garbage collection because type variables are automatically freed after constraint solving
DIt ensures that programs without explicit type annotations are always rejected, which improves code documentation
Separation of concerns is the key benefit. The constraint generator is language-specific: it knows the syntax and what constraints each construct implies. The solver is language-agnostic: it just solves constraint systems. Adding a new type system feature — say, subtyping or a trait bound — means adding new constraint forms to the generator. The solver can often handle these without modification, or with local extensions. This modular design is why so many different languages (OCaml, Haskell, Rust, TypeScript) can use variations of the same underlying constraint-solving machinery.
Question 3 True / False
Constraint-based type checking requires programmers to write explicit type annotations for nearly every function parameter and variable in order to generate constraints.
TTrue
FFalse
Answer: False
The whole point of constraint-based type checking is that it works without annotations. The compiler assigns fresh type variables to unannotated expressions and generates constraints from how those expressions are used. Unification then solves the constraints, inferring concrete types. Languages like OCaml and Haskell allow entire programs to be written without a single type annotation — the constraint solver infers everything. Annotations are permitted and can help both the programmer and the compiler, but they are not required.
Question 4 True / False
In constraint-based type checking, unification finds the most general substitution that makes two type expressions equal, and reports a type error when no such substitution exists.
TTrue
FFalse
Answer: True
Unification is the core solving mechanism. Given two type expressions (e.g., α → int and bool → β), unification finds the unique most-general unifier: α = bool, β = int. 'Most general' means it avoids unnecessary commitments — it never specializes a type variable beyond what is required. When unification fails (e.g., trying to unify int with bool), no substitution can reconcile them, which means the constraints are unsatisfiable — the program has a type error. The constraint that generated the conflict is tracked back to the source expression to produce the error message.
Question 5 Short Answer
Why does constraint-based type checking enable type inference for unannotated code, while traditional syntax-directed type checking does not?
Think about your answer, then reveal below.
Model answer: Traditional syntax-directed type checking checks each AST node locally and immediately — if the type of an expression is not yet known (because there is no annotation), it fails. Constraint-based checking instead assigns fresh type variables to unknown expressions and generates constraints describing what relationships those variables must satisfy. These constraints are collected across the entire program. The solver then has a global view and can propagate information bidirectionally: learning from how a variable is used in the body of a function what type the parameter must have, even though the parameter had no annotation. Unification solves all constraints simultaneously, yielding inferred types throughout.
The contrast is between local (node-by-node) and global (whole-program) reasoning. Syntax-directed checking cannot reason globally because it makes decisions immediately at each node. Constraint generation defers all decisions until the full constraint system is assembled, then solves once — allowing information from later parts of the code to influence earlier parts.