Type checking

Advanced

Introduction

"Age: " + 30 is a mistake in most languages. Python finds it when the line runs; a statically typed language such as Java, Go, Rust or TypeScript finds it before the program runs at all, in the compiler. That phase is the type checker. It catches a whole class of bugs early, lets editors suggest the right methods, and tells the code generator how big each value is and which machine instructions to use.

How it works

A type checker walks the AST and computes a type for every node, from the leaves up:

  • a number literal has type int, a quoted string str, true and false have type bool;
  • a variable has the type recorded for it in the type environment, which is the symbol table from the previous lesson with a type in each entry; if it is not there, that is an error;
  • an operator node first checks its children, then looks up a type rule for its operator and their types.

Type rules are usually written like this: if a : int and b : int, then a + b : int. A language can give one operator several rules (overloading): + also joins two strings, and * repeats a string. Any combination not covered by a rule is a type error, such as + on an int and a str.

Some constructs have rules about their parts rather than a fixed result. In if c then a else b, used as an expression, c must be bool, and a and b must have the same type, which is then the type of the whole expression.

Many languages do not make you write every type. In let x = 1, the checker can infer that x is an int from the expression and record it, as Go, Rust, Kotlin and TypeScript do.

Python is dynamically typed: the same checks happen while the program runs, on actual values. Tools such as mypy and Pyright add static checking to Python using type hints.

Syntax

def check(node):
    if is_leaf(node):
        return literal_type(node) or env[node]       # or an error
    op, *args = node
    types = [check(arg) for arg in args]             # children first
    return RULES[(op, *types)]                       # or an error

Example

import re

RULES = {
    ("+", "int", "int"): "int",
    ("+", "str", "str"): "str",
    ("-", "int", "int"): "int",
    ("*", "int", "int"): "int",
    ("*", "str", "int"): "str",
    ("<", "int", "int"): "bool",
    ("==", "int", "int"): "bool",
    ("==", "str", "str"): "bool",
    ("and", "bool", "bool"): "bool",
    ("not", "bool"): "bool",
}
env = {"age": "int", "name": "str", "admin": "bool"}


class TypeCheckError(Exception):
    pass


def read(text):
    tokens = re.findall(r'\(|\)|"[^"]*"|[^\s()]+', text)

    def node():
        token = tokens.pop(0)
        if token != "(":
            return token
        items = []
        while tokens[0] != ")":
            items.append(node())
        tokens.pop(0)
        return items

    return node()


def check(node):
    if isinstance(node, str):
        if node.isdigit():
            return "int"
        if node.startswith('"'):
            return "str"
        if node in ("true", "false"):
            return "bool"
        if node in env:
            return env[node]
        raise TypeCheckError(f"{node} is not declared")
    op, *args = node
    types = [check(arg) for arg in args]
    if op == "if":
        if types[0] != "bool":
            raise TypeCheckError(f"the condition of if is {types[0]}, not bool")
        if types[1] != types[2]:
            raise TypeCheckError(f"the branches of if are {types[1]} and {types[2]}")
        return types[1]
    key = (op, *types)
    if key not in RULES:
        raise TypeCheckError(f"{op} cannot take {' and '.join(types)}")
    return RULES[key]


for text in [
    "(+ age 1)",
    "(< (* age 2) 100)",
    '(+ name "!")',
    '(* "ab" 3)',
    "(and admin (< age 18))",
    '(if admin "yes" "no")',
    "(+ age name)",
    "(if age 1 2)",
    '(if admin 1 "no")',
    "(- score 1)",
]:
    try:
        print(f"{text:24} : {check(read(text))}")
    except TypeCheckError as error:
        print(f"{text:24} : error, {error}")
Open in compiler

Line by line

  1. RULES lists every allowed combination of operator and argument types, with the result type.
  2. env is the type environment: three variables and their declared types.
  3. read turns the prefix form into nested lists, as in the earlier tree exercises.
  4. check types the children first, then applies the rule for if or looks up the operator's rule.
  5. The first six expressions are well typed; the last four show the four kinds of error: a bad operator combination, a non-bool condition, mismatched branches and an undeclared name.

Expected result

(+ age 1)                : int
(< (* age 2) 100)        : bool
(+ name "!")             : str
(* "ab" 3)               : str
(and admin (< age 18))   : bool
(if admin "yes" "no")    : str
(+ age name)             : error, + cannot take int and str
(if age 1 2)             : error, the condition of if is int, not bool
(if admin 1 "no")        : error, the branches of if are int and str
(- score 1)              : error, score is not declared

In the real world

The TypeScript compiler is mostly a type checker: it removes the types and emits plain JavaScript. Java, C#, Go and Rust compilers refuse to produce a program with type errors. In Python, mypy and Pyright read type hints and apply the same kind of rules, and editors use the inferred types for completion. The idea extends far: Rust's borrow checker is a kind of type checking for memory safety.

Common mistakes

  • Checking the operator before its children, which gives confusing errors.
  • Forgetting that one operator can have several rules, such as + for numbers and strings.
  • Letting the two branches of a conditional have different types.
  • Reporting only "type error" without saying which operator and which types; good messages name both.

Best practices

  • Keep the type rules in a table, so a new rule is one line.
  • Report the first error with the operator and the types involved.
  • Store the computed type on each AST node; the code generator will need it.

Summary

A type checker computes a type for every expression, bottom-up: literals have fixed types, variables take theirs from the type environment, and operators follow type rules. Combinations without a rule, non-bool conditions and mismatched branches are type errors, found before the program runs in a statically typed language.

Quick check

1. In which order does a type checker handle an operator node?
2. What is the type of (if admin 1 2) when admin is bool?
3. Where does the checker find a variable's type?
4. What is type inference?

Key takeaways

  • A type checker is a tree walk that computes a type for every node from its children's types.
  • An operator is allowed only for the combinations of types its rules list.
  • Conditions must be bool, and both branches of a conditional expression must have the same type.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.