Baby's first type checker

Summary

Austin Z. Henley Associate Teaching Professor Carnegie Mellon University Baby's first type checker 8/31/2025 Have you ever wondered how type checking works? Me too—let's make one! Python allows optional type annotations like this: def foobar(name: str | None) -> str: return "Fizz!" buzz: int = 42 A type checker goes through the code to make sure that the kinds of values you use match what your functions and variables expect. In the example above, it would check if foobar always returns a str. Type checking can catch errors early and also act as documentation. Some languages require type checking before you compile or run your code, like C++, while others, like Python, don't have a built-in type checker at all. Instead you either just wait until you have runtime errors or you use third-party tools, such as Mypy, Pyright, or Pyrefly to type check. Note: Python has an interesting history with typing. If you want to learn more, see the specification for the Python type system, the typing module's documentation, or the PEPs (Python Enhancement Proposals) related to types. Our approach Our baby type checker will take a Python code file, parse it, find type annotations, and then check whether the actual types are compatible with how they are used. Once we know something's type, we propagate it through the program, verifying that the types are used in appropriate ways, while also picking up more type information along the way. Here is an example snippet that we will eventually be able to type check: from __future__ import annotations def greet(name: str | None) -> str: if name is None: return 42 # ❌ int but expected str return "Hello, " + name age: int = "42" # ❌ str but expected int def length(xs: list[int]) -> int: return len(xs) + xs # ❌ cannot add list and int We will support primitive types, containers, functions, assignments, binary operators, indexing, type unions, and a few scenarios of type narrowing. In 350 lines of code, it will catch a surprising number of type ...