Week 1 · Lesson 6

The week 1 lab

Build a compiler that parses .uir, type-checks it, runs it, and simplifies it. Write it in your own repo, in the language you picked in the sidebar. You're done when every week 1 test passes and you've written 10 tests of your own.

What you're building

Warm up

Five minutes in .uir before the big build. It makes you use C-style div and mod exactly as your interpreter will have to.

Floor division from C division

div truncates toward zero, so div -7 2 is -3. Python's // floors, so -7 // 2 is -4. Build floor division for i32 params a and b (b is never 0) from div, mod, cmplt, xor, where and add (there's no subtract, so add %q -1).

The two only differ when the remainder is nonzero and its sign differs from b's.

The command-line contract

The grader sees your exit code, your stdout (for simplify), and your stderr (the invalid: and assert failed: lines). A crash is not an answer: exit 2 only counts if stderr has a line starting invalid:, so an uncaught exception (Fatal error: exception ...a Python traceback) fails the test.

commandresult
your.exe run FILEexit 0 if every assert passed. Exit 1 if one failed: print assert failed: %name to stderr, naming the first failure in file order. Exit 2 for an invalid program: a parse error, type error, undefined name, or a runtime error that an assert depends on. Print a line starting invalid: to stderr. Every statement is type checked first. Then asserts run in file order and stop at the first one that fails (exit 1) or errors (exit 2).
your.exe simplify FILEPrint a valid .uir program to stdout that defines %out with the same dtype and shape, and computes the same value wherever the original doesn't error. It's graded on equivalence (every edge value in every param slot, f32 compared bit for bit) and on an op budget, max_ops, counted on the statements you print: duplicate statements count twice, so hash cons your output.

Running the suite

Two tools, two jobs. python tools/serve.py serves these lessons and grades the in-lesson exercises like the one above. tools/test.py grades your compiler against the week's suite. Run these from the root of the course repo:

python tools/test.py --compiler "C:/path/to/your.exe" --week 1
python tools/test.py --compiler "C:/path/to/your.exe" --week 1 -k div     # only tests whose name contains "div"
python tools/test.py --compiler "C:/path/to/your.exe" --week 1 -v         # show what differed
python tools/test.py --compiler "C:/path/to/your.exe" --week 1 --jobs 1   # one test at a time

Pass the built executable (for dune, _build/default/bin/main.exe), not dune exec: the suite runs tests in parallel, and parallel dune exec calls fight over dune's build lock.

Pass your wrapper from lesson 0.7: C:/path/to/my-ml-compiler/mlc.cmd on Windows, or the executable mlc script on macOS and Linux. The runner calls it as mlc.cmd run FILE from the course repo, so the wrapper must find your package from any folder.

Tests live in tests/week1/run/ and tests/week1/simplify/, and you should read them. Each one is a small, readable .uir file.

Write your 10 tests

The real course has students hand in 10 tests every week, graded against an oracle. Do the same: put them in <your compiler repo>/tests/week1/, one .uir file each, starting with a header.

# expect: pass
# C division truncates toward zero, and mod takes the sign of the dividend
%a = div -7 2
%t = assert %a -3
%b = mod -7 2
%u = assert %b -1

# expect: is pass, assert_fail or invalid. A simplify test has no asserts, defines %out, and uses # simplify: max_ops=N. Then check them against the oracle. --check-tests confirms each # expect: header, and for simplify tests it checks that the oracle's own simplifier reaches your max_ops, so you can't write an impossible target:

python tools/test.py --check-tests <your compiler repo>/tests/week1

A good test targets one rule you think someone (maybe you) will get wrong: INT_MIN / -1, nan in max, a nested call that reuses slot 0, an index one past the end. A test that every compiler passes teaches nothing.

A build order that works

  1. Set up your repo

    Make a new folder outside the course repo, then git init inside it. Run dune init project mlc there (lesson 0.6 shows dune).Add the mlc package and the wrapper script from lesson 0.7. Copy templates/AGENTS.md from the course repo into your repo's root: it tells an AI assistant to explain and ask questions but never write your compiler code.

    Checkpoint: dune build succeeds and _build/default/bin/main.exe runs.

    Checkpoint: running the wrapper from the course repo's folder prints your usage message and exits 2.

  2. Parse and print

    Turn every line into (name, op, operands, attributes). Print each statement back in .uir form and check it matches the input line, ignoring spacing and comments.

    Checkpoint: every file in tests/week1/run/ parses or is rejected with exit 2, and none crash.

  3. The hash-consed UOp

    One table keyed on (op, src, arg), with dtype and shape as part of the key. Sources are already unique, so compare them by identity. In OCaml, == is physical equality and = is structural.In Python, is is identity, and == on a dataclass compares every field. Key float constants by their bits, so 0.0 and -0.0 stay apart. Know which one you're using.

    Checkpoint: building add x 1 twice returns the same physical node.

  4. Types

    dtype and shape for every op, following the table in the spec. No implicit conversions.

    Checkpoint: all expect: invalid type-error tests exit 2.

  5. Interpreter

    Evaluate the asserts in file order, with each node computed once. Look these up for your language: how to do 32-bit wrapping arithmetic (OCaml's native int is 63 bits)(Python ints never overflow), and how to round a double to binary32 (OCaml floats are doubles, so see Int32.bits_of_float)(Python floats are doubles, so see struct in lesson 0.7). A deep chain of nodes will hit Python's recursion limit, so walk it with your own stack or raise the limit.

    Checkpoint: the arithmetic tests pass, and the deep shared-DAG test finishes in milliseconds.

  6. call and param

    Evaluate a body with an environment (a map from slot number to value for the current call). Keep the memo per call. Bodies are closed.

    Checkpoint: the nested-call tests pass, including the ones that reuse slot 0.

  7. The rewrite engine

    A sources-first pass that tries rules at each node, repeated until nothing changes. Start with constant folding, using the same op semantics as the interpreter, then add canonicalization.

    Checkpoint: the folding simplify tests pass their max_ops.

  8. Symbolic rules and bounds

    i32 identities, f32-safe identities only, call inlining, then interval bounds and the rules they power.

    Checkpoint: every simplify test passes, including the ones designed to catch x * 0 on f32 and (x * 2) / 2.

  9. Your 10 tests

    Write them, and check them with --check-tests. Then try to break your own compiler with them.

Checklist

The AI policy

This course was built with AI. Your compiler should not be. In your repo (my-ml-compiler), the AGENTS.md says an AI assistant may explain concepts, draw diagrams, and help you debug by asking questions, but must never write or rewrite compiler code. That's in the spirit of the original course's "slop management" theme. The point is the understanding, and you only get it by typing it yourself.

The reference compiler lives in _reference/ in the course repo. The test runner uses it as the oracle, and running it is fine. Never open it. It's written in Python, not OCaml, so a stray glance hands you less, but it would still spoil the puzzles.It's written in Python, like your compiler, so even a stray glance would hand you answers and spoil the puzzles.

Slop compounds

Every later week builds on this code: loads and stores in week 2, loops in week 3, rangeify in week 4. A sloppy UOp type or a simplifier that is "mostly right" will cost you far more later than it saves now. Keep it small, keep it readable, and delete anything you don't understand.

Check yourself

What exit code should run give?

%t = assert 2 3

Exit 0 means every assert passed, 1 means an assert failed, and 2 means the program is invalid. Which one is this?

1, a failing assert, with assert failed: %t on stderr.

And this one?

%a = add 1 1.0
%t = assert %a 2

Look at the dtypes of 1 and 1.0. Does .uir ever convert between them for you?

2. 1 is i32 and 1.0 is f32, and there's no implicit conversion, so it's a type error.

Which assert should the stderr message name?

%a = add 2 3
%t = assert %a 5
%u = assert %a 6
%v = assert %a 7

Asserts are checked in file order. Which one is the first to fail?

%u: the first failing assert in file order. %t passes, and both %u and %v fail.

You're stuck on a failing nested-call test. What can an AI assistant do in your compiler repo?

Look back at the AI policy in your repo's AGENTS.md: explaining is allowed, writing your compiler code is not.

Explaining, drawing and asking questions are all fine. Writing or rewriting compiler code isn't, and neither is the reference.