Algorithm W
You'll learn the classic algorithm that automatically infers types by walking through your code and solving constraints.
What is Algorithm W?
Algorithm W is the workhorse implementation of the Hindley-Milner type system. While the previous lesson explained what unification does (matching type variables with concrete types), Algorithm W is the how—the actual procedure that visits each expression in your program, generates type constraints, and unifies them to discover the most general type.
Think of it like a detective solving a case: Algorithm W walks through the crime scene (your code), collecting clues (type constraints from each expression), then pieces them together (unification) until the full picture emerges.
How Algorithm W Works
The algorithm processes expressions recursively:
- Visit a literal (like
42): instantly know its type (Int) - Visit a variable (
x): look up its type in the environment - Visit a function application (
f arg):- Infer the type of
f - Infer the type of
arg - Unify
f's type witharg_type -> fresh_result_type - Return
result_type
- Infer the type of
- Visit a lambda (
λx. body):- Create a fresh type variable for
x - Infer the body's type with
xin scope - Return
x_type -> body_type
- Create a fresh type variable for
At each step, unification updates our knowledge, potentially substituting type variables with concrete types or more specific polymorphic types.
Why It Matters
Algorithm W proves that automatic type inference is decidable—you don't need to annotate every variable. The compiler can figure it out by following this systematic traversal-and-constraint-solving process.
Key Takeaway: Algorithm W is the recursive traversal procedure that infers types by visiting each expression, generating constraints, and unifying them to find the most general type automatically.