Python for this course

Install

You need Python 3.10 or newer, because match arrived in 3.10. The course uses only the standard library, so there's nothing else to install. Check what you have:

python --version              # Windows. 3.10 or newer?
python3 --version             # macOS and Linux

If it's missing or too old: on Windows, winget install Python.Python.3.12 (then open a new terminal), or the installer from python.org with "Add python.exe to PATH" ticked. On macOS, brew install python. On Ubuntu or WSL, sudo apt install python3. The course's own tools, tools/serve.py and tools/test.py, run on the same Python.

For an editor, use VS Code with the Python extension. Write type hints on your functions (def wrap32(x: int) -> int). Python ignores them at run time, but the editor uses them to show the type of anything you hover and to flag a None you forgot to handle. In a compiler full of nodes, that catches real bugs.

A project the grader can run

Your compiler is a package: a folder of modules with an __init__.py. A __main__.py inside it is what python -m mlc runs. Make a new folder outside the course repo, like this:

my-ml-compiler/
  mlc/
    __init__.py         # empty: it marks mlc as a package
    __main__.py         # the command line: reads sys.argv, calls the rest, exits
    ...                 # your modules: one per idea, as the weeks go on
  tests/                # your own .uir tests
  mlc.cmd               # Windows wrapper (below)
  mlc                   # macOS and Linux wrapper (below)
  AGENTS.md             # copied from the course's templates/

Each .py file is a module, and inside the package you import siblings by name: from mlc.words import count. Start __main__.py with something that only reads its arguments and sets the exit code:

import sys

def main(argv: list[str]) -> int:
    match argv:
        case ["count", path]:
            with open(path, encoding="utf-8") as f:
                print(len(f.read().splitlines()), "lines")
            return 0
        case _:
            print("usage: mlc count FILE", file=sys.stderr)
            return 2

sys.exit(main(sys.argv[1:]))

sys.argv[0] is the program name, so sys.argv[1:] is the arguments. sys.exit(n) ends the program with status n, which is how the course's test runner learns whether a test passed. print(..., file=sys.stderr) writes to stderr. splitlines() doesn't count an empty line after a final newline, which plain split("\n") does.

The test runner, tools/test.py, runs your compiler as COMPILER run FILE from the course repo's folder. python -m mlc only finds mlc when its parent folder is on Python's path, so give the grader a small wrapper that sets it. On Windows, save this as mlc.cmd next to the mlc folder:

@echo off
set "PYTHONPATH=%~dp0"
python -m mlc %*

%~dp0 is the folder the .cmd file lives in, and %* passes every argument through. The exit code of the last line becomes the wrapper's exit code. On macOS and Linux, save this as mlc and run chmod +x mlc once:

#!/bin/sh
PYTHONPATH="$(dirname "$0")" exec python3 -m mlc "$@"

Then, from the course repo, point the grader at the wrapper:

python tools/test.py --compiler "C:/path/to/my-ml-compiler/mlc.cmd" --week 1     # Windows
python3 tools/test.py --compiler ~/my-ml-compiler/mlc --week 1                   # macOS and Linux

Integers never overflow

A Python int grows as large as it needs to. 2147483647 + 1 is 2147483648, and 2**100 is exact. That's lovely for a calculator and wrong for your compiler: the language you're compiling has a 32-bit i32 that must wrap, the way C's int32_t does. Python won't wrap for you, so you wrap after every operation.

x = 2147483647 + 1                 # 2147483648: no wrap
low = x & 0xFFFFFFFF               # 2147483648: the low 32 bits, read as unsigned
y = low - 2**32 if low >= 2**31 else low    # -2147483648: read as signed
print(x, low, y)

& on a negative int acts as if it had infinitely many sign bits, so -1 & 0xFFFFFFFF is 4294967295. Masking then fixing the sign works for every int. Do it in one helper and call it everywhere an i32 is produced: add, multiply, shift left, negate, and division (yes, division, see below).

>> on a negative int is an arithmetic shift, like C's on signed values. << never drops bits, so 1 << 40 is a 41-bit number until you wrap it.

Division floors, C truncates

Python's // rounds toward negative infinity. C's / on ints rounds toward zero. They agree when the signs agree, or when the division is exact. They disagree when the signs differ and there's a remainder. % follows //, so it takes the sign of the divisor in Python and the sign of the dividend in C.

The Python column uses // where the table says /. Plain / in Python always gives a float: 7 / 2 is 3.5. int(3.5) truncates toward zero, but going through a float is a habit to avoid, since floats can't hold every 64-bit int. Divide the absolute values with // and put the sign back yourself. math.fmod is C's fmod for floats, which truncates like C. And round(2.5) is 2, because Python rounds halves to even.

Floats are doubles

Python's float is a 64-bit double. The course's f32 is single precision. To round a double to the nearest single, pack it into 4 bytes with struct and unpack it again:

import struct

def to_f32(x: float) -> float:
    return struct.unpack("<f", struct.pack("<f", x))[0]

print(repr(0.1), repr(to_f32(0.1)))
# 0.1 0.10000000149011612

"<f" means one little-endian 32-bit float. struct.pack rounds to the nearest single, ties to even, exactly like C's (float) cast. "<I" reads the same 4 bytes as an unsigned int, which is how you get at an f32's bits: struct.unpack("<I", struct.pack("<f", x))[0].

Equal is not the same key

A dict finds a key by its hash and then by ==. That's usually what you want, and for a compiler it hides three traps, because Python considers some different values equal:

print({0.0: "a", -0.0: "b"})       # {0.0: 'b'}: one key, since -0.0 == 0.0
print({1: "a", True: "b"})          # {1: 'b'}: True == 1, and 1 == 1.0 too
nan = float("nan")
d = {nan: "a"}
print(d.get(nan), d.get(float("nan")))   # a None: the same NaN object is found, a new one isn't

In week 1 you'll keep a table from "what a node is" to the node itself, so that building the same node twice returns the one you already have. If its key holds a float constant as a plain float, 0.0 and -0.0 become one node, and they are different f32 values (in C, 1.0f / -0.0f is -inf). A NaN constant never finds itself. An i32 1 and a bool true collide unless the dtype is part of the key. The fix for all three: key on the dtype plus the value's bits, not the value. struct gives you the bits.

NaN also breaks == everywhere else: nan == nan is False. Test for it with math.isnan. Test for -0.0 with math.copysign(1.0, x) < 0, since -0.0 == 0.0.

Frozen dataclasses, == and is

A dataclass writes the boring parts of a class for you: the constructor, a readable repr, and ==. frozen=True makes instances immutable, which is what a node in a graph should be: once built, it never changes.

from dataclasses import dataclass
from enum import Enum

class Suit(Enum):
    HEARTS = 1
    DIAMONDS = 2
    CLUBS = 3
    SPADES = 4

@dataclass(frozen=True)
class Card:
    rank: int        # 2 through 14, where 11 is a Jack and 14 an Ace
    suit: Suit

a = Card(14, Suit.SPADES)
b = Card(14, Suit.SPADES)
print(a == b, a is b)        # True False
print(len({a, b}))           # 1: frozen dataclasses hash by their fields
# a.rank = 2                 # dataclasses.FrozenInstanceError

An enum is a fixed set of named values. Suit.HEARTS is never equal to 1 or to a string, so a typo becomes an error instead of a silent mismatch. Use one for anything with a fixed list of choices, like a set of ops or dtypes.

Python has two equalities. a == b calls the class's __eq__. For a dataclass, that compares every field, and if a field holds another node, it compares that one too, all the way down. On a big graph that can take as long as the graph is big. a is b asks whether they're the very same object in memory, which is one pointer comparison. Remember this distinction. It matters in week 1.

Writing @dataclass(frozen=True, eq=False) keeps the fields immutable but leaves == and hash as identity, the same as is. That's the right choice for a class whose instances you guarantee are unique, and slow structural equality is the wrong one. If you ever key a dict on id(x), keep x alive, because Python reuses the id of an object that has been freed.

match

match takes a value apart by its shape. With one small class per kind of card, each case names a class and pulls out its fields. Dataclasses support positional patterns like Number(n, _) automatically.

@dataclass(frozen=True)
class Number:          # 2 through 10
    n: int
    suit: Suit

@dataclass(frozen=True)
class King:
    suit: Suit

@dataclass(frozen=True)
class Ace:
    suit: Suit

def describe(card) -> str:
    match card:
        case Number(n, Suit.HEARTS) if n >= 9:    # nested pattern plus a guard
            return "a high heart"
        case Ace(Suit.SPADES):
            return "the ace of spades"
        case Number(n, _):
            return f"the number {n}"
        case King() | Ace():                       # either class, any fields
            return "a high card"
        case _:
            raise TypeError(f"not a card: {card!r}")

Cases are tried top to bottom, and the first that matches wins. Number(n, _) binds the first field to n and ignores the second. if n >= 9 is a guard: the case only matches if it's true. Sequence patterns work too: case [first, *rest]: matches a list or tuple with at least one element.

Dicts, sorting, and caches

A dict is your hash table. It keeps keys in insertion order, which makes output reproducible. sorted takes a key function, and a tuple key sorts by its first element, then its second.

counts: dict[str, int] = {}
for word in ["kiwi", "pear", "kiwi"]:
    counts[word] = counts.get(word, 0) + 1
print(counts)                                             # {'kiwi': 2, 'pear': 1}
print(sorted(counts.items(), key=lambda wn: -wn[1]))      # most common first

functools.cache remembers a function's results by its arguments, so a second call with the same arguments returns at once. It's the quickest memo there is. It has two catches. The cache lives as long as the program, so it never forgets. And it keys only on the arguments: if the answer also depends on something else, such as the values bound for the current function call, a global cache will hand back a stale answer. A plain dict that you create, pass around, and drop when you're done is often the better memo.

from functools import cache

@cache
def ways(n: int) -> int:          # ways to climb n stairs, 1 or 2 at a time
    return 1 if n <= 1 else ways(n - 1) + ways(n - 2)

print(ways(90))                     # instant: each n is computed once

Deep graphs and the recursion limit

Python stops any recursion deeper than about 1000 calls with RecursionError. A walk over a graph recurses once per level, and a .uir program can be a chain thousands of nodes long. There are two fixes. sys.setrecursionlimit(100_000) raises the limit, and it's fine for a few thousand levels. The sturdier fix is to keep your own stack in a list:

def total(tree) -> int:            # tree: None, or a tuple (left, value, right)
    stack, out = [tree], 0
    while stack:
        t = stack.pop()
        if t is not None:
            left, value, right = t
            out += value
            stack.append(left)
            stack.append(right)
    return out

The loop does what the recursion would have done, but its "call stack" is an ordinary list, limited only by memory. For a walk that must visit a node's children before the node, push the node back with a "finished" flag before its children, and emit it when it comes off the stack the second time.