Type Checking — Catching Errors at Compile Time

A type checker walks the AST and verifies that operations are applied to compatible types. It runs after parsing (and resolving) but before code generation.

What the Type Checker Validates

1. Variable assignments: the value must match the declared type

   var x: number = "hello";  // Type error: expected number, got string
   

2. Function arguments: each argument must match the parameter type

   fun add(a: number, b: number): number { ... }
   add("hello", 42);  // Type error: argument 1: expected number, got string
   

3. Return values: must match the declared return type

   fun greet(): string { return 42; }  // Type error: expected string, got number
   

4. Operator operands: arithmetic requires numbers, concatenation requires strings

   "hello" - 3;  // Type error: operator - requires number operands
   

Type Checking Algorithm

The type checker walks the AST bottom-up, computing the type of each expression:

checkExpression(expr):
    if expr is Literal:
        return typeOf(expr.value)  // number, string, bool, nil
    if expr is Binary:
        leftType = checkExpression(expr.left)
        rightType = checkExpression(expr.right)
        if expr.op in [+, -, *, /]:
            expect(leftType == number and rightType == number)
            return number
        if expr.op in [==, !=]:
            return bool
    if expr is Variable:
        return lookupType(expr.name)
    if expr is Call:
        fnType = checkExpression(expr.callee)
        for i, arg in expr.arguments:
            argType = checkExpression(arg)
            expect(argType == fnType.params[i])
        return fnType.returnType

Subtyping

nil is tricky. Should var x: string = nil; be allowed? Languages handle this differently:

• Kotlin: String is non-nullable; String? is nullable
• TypeScript: string | null is a union type
• Our approach: nil is assignable to any type (simple but less safe)

Multiple Errors

A good type checker reports ALL errors, not just the first one. After finding an error, continue checking the rest of the program. This is more helpful to the programmer than stopping at the first mistake.

How Rust's Type Checker Works

Rust's type checker (called the "borrow checker" for its ownership rules) is one of the most sophisticated. It tracks lifetimes, ownership, and borrowing — preventing memory errors at compile time. Our type checker is much simpler but follows the same basic pattern: walk the AST, compute types, check compatibility.

Your Task

Implement a type checker pass that validates assignments, function calls, return values, and operator usage against declared types.