The Type Checker Pass

A Third Compiler Pass

You now have annotations parsed and attached to the AST (previous lesson) but nothing checks whether the program actually respects them. var x: number = "oops"; parses fine — it's syntactically valid — but it's a type error a good compiler should catch before running anything. That's the job of the type checker: a pass that walks the annotated tree, computes the type of every expression, and compares it against every place a type is declared or expected.

Two Environments: Variables and Functions

The checker needs to track two kinds of bindings as it walks the program:

cur_ret matters because return statements are only valid to check relative to the function they're inside — the same literal return 42; is fine inside a function declared : number and a type error inside one declared : string.

Computing the Type of an Expression

Before you can compare "declared type" against "actual type," you need a function that looks at an expression and says what type it evaluates to. For literals this is direct pattern matching; for names, it's an environment lookup:

Real expression typing has to recurse (a binary + combines the types of both operands, a call's type is the callee's declared return type) — but the core idea is always the same: bottom-up, compute the type of each sub-expression, then check it against what the surrounding context expects.

Checking Each Statement Kind

Three checks cover most of what a first type checker needs:

Declaration — the initializer's computed type must match the annotation:

Assignment — same shape, but looked up against the variable's already-declared type rather than a fresh annotation:

Call — each argument's type must match the corresponding parameter type, positionally, and the arity must match too (a separate error class from a type mismatch — calling with the wrong number of arguments isn't "expected number, got string," it's a different failure entirely).

Return — the returned expression's type must match cur_ret for the function currently being checked; every path through a function should agree with its declared return type.

Error Reporting Discipline

Keep error messages mechanical and consistent — Type error: expected <T>, got <U> — rather than prose. A type checker that's going to be useful to a programmer (or to automated tests, as here) needs errors that are grep-able and predictable, not narratively different each time.

What to build

Implement lit_type plus per-statement checks for decl, assign, function definitions (binding params + return type into self.funs and setting cur_ret while checking the body), and return. Confirm that decl x : number = 42 reports OK, assign x = "oops" reports Type error: expected number, got string, and an unbound name reports Unknown name '<name>' rather than crashing the checker.