Implementing Algorithm W for Hindley-Milner Type Inference in TypeScript

Added:

Bidirectional Type Inference and the Limits of Global HM

While Algorithm W is a classic approach to global type inference, it has significant drawbacks. It is notorious for poor error localization, where a type mismatch in one part of the program triggers a confusing error message far away. To mitigate this, alternative formulations like Algorithm M or bidirectional type inference are often preferred in modern compiler design. Furthermore, pure Hindley-Milner inference does not scale to languages with structural subtyping, overloading, or ad-hoc polymorphism—features core to TypeScript itself. Instead of global inference, modern languages (including TypeScript) rely on bidirectional type checking, where type information flows both top-down (expected types) and bottom-up (synthesized types). This alternative paradigm provides highly localized error messages, handles subtyping elegantly, and avoids the complexity and performance bottlenecks associated with global unification algorithms like Algorithm W.

Familiarity with the Lambda Calculus and Abstract Syntax Trees (ASTs) for representing program structure.
Understanding the basics of Parametric Polymorphism and the distinction between monomorphic and polymorphic types.
Knowledge of Robinson's Unification Algorithm and how substitution works to solve type equations.
Intermediate proficiency in TypeScript, particularly using discriminated unions to represent algebraic data types and writing recursive functions.
Implementing Algorithm J, an imperative and more efficient variation of Algorithm W that uses mutable state (type variables with union-find) to avoid explicit substitutions.
Extending the type inference engine to support advanced language features like Row Polymorphism, Type Classes, or Higher-Kinded Types.
Exploring Bidirectional Type Inference to handle language features that pure Hindley-Milner struggles with, such as subtyping or explicit type annotations.
Integrating the implemented type checker into a complete toy compiler or interpreter pipeline (from lexing/parsing to execution).
1.7K views37likes19:46@adam-jonesOriginal Release: 2023-02-22

Algorithm W is a type inference algorithm for Hindley-Milner type systems that automatically determines the most general type of an expression by recursively processing four expression cases: variable expressions (lookup in typing environment), abstraction expressions (introduce new type variable for parameter and form function type), application expressions (unify function type with argument type), and let-in expressions (generalize type over context to enable polymorphism). The algorithm returns a substitution that captures type constraints and a monotype representing the inferred type, enabling type inference without explicit type annotations.