Week 1 · Lesson 2
The .uir format, and running it
.uir is the text form of a UOp graph: one node per line. Your first milestone is an interpreter (a program that runs another program directly instead of translating it). It reads the file, builds hash-consed nodes, type-checks them, evaluates what the asserts need, and exits with the right code.
Everything here summarizes spec/uir-week1.md. The official course hasn't published its grammar yet, so this one is ours and provisional. If this page and the spec disagree, the spec wins.
Anatomy of a line
- One statement per line, always
%name = op operand* key=value*. - Names are letters, digits and underscores. Define a name above its first use, and only once. So the file is already in a valid evaluation order.
- An operand is a
%nameor a literal. A literal is just an inlineconst.
| you write | it means |
|---|---|
3, -7 | const, dtype i32 (must fit in 32 bits) |
1.5, 2e3, inf, -inf, nan | const, dtype f32 (any . or e makes it a float) |
true, false | const, dtype bool |
%x = const 3 dtype=f32 | an explicit const. This one is 3.0. |
%x = param 0 dtype=i32 declares an input: slot 0, an i32. The exercises in lessons 1 to 4 use this: the tests fill slot 0 (and 1, and so on) with numbers and print what your %out computes. Lesson 5 shows how call fills params inside a program. Until then, think of a param as "a number the test hands in".
Four dtypes, zero conversions
| dtype | values | watch out |
|---|---|---|
void | none | Only assert makes one, and it can't be an operand. |
bool | true, false | What cmplt returns, and what where takes. |
i32 | -2³¹ to 2³¹-1 | add, mul and shl wrap around. |
f32 | IEEE single precision | Rounded to nearest-even after every op. |
add 1.5 1 is a type error, not 2.5. 1 is an i32 and 1.5 is an f32, and binary ops need matching dtypes. Write add 1.5 1.0, or cast one side. C would quietly convert for you. Here, the conversion has to be its own visible node.
Evaluating: sources first
To evaluate a node, first evaluate its sources. Because names are defined before use, the file order is already a topological order: every node comes after its sources. So the simplest correct evaluator is a recursive eval node that evaluates the sources first and caches each result. Calling it on each assert, in file order, only ever touches what the asserts need. (Once call arrives in lesson 5, that cache must be per call, because the same param node means different values in different calls.) Step through it:
Asserts are the roots
A program's outputs are its asserts. They're checked in file order. A node no assert depends on is never evaluated. That makes this a valid program that exits 0, even though it contains a division by zero:
%bad = div 1 0 # never needed
%t = assert 1 1 # the only rootChange the assert to assert %bad 0 and now the bad division is needed. That's a runtime error, so exit 2. Type errors are different: they're found while building nodes, so a type error anywhere in the file is exit 2, used or not.
Exit codes
Your compiler is one program, run from the command line as yourcompiler run FILE. Its exit code says what happened. A second subcommand, simplify, arrives in lessons 3 and 4.
| exit | when | example |
|---|---|---|
0 | every assert passed | %s = add 2 3%t = assert %s 5 |
1 | an assert failed. Print assert failed: %name to stderr for the first one in file order. | %s = add 2 2%t = assert %s 5 |
2 | invalid: a parse error, type error, undefined name, or a runtime error in something an assert needs | %a = add 1.5 1, or%d = div 1 0%t = assert %d 0 |
i32: what a C programmer expects, made exact
Wraparound. add 2147483647 1 is -2147483648. In C, signed overflow is undefined behavior. Here it's defined: the result is reduced mod 2³² into the signed range.
Division truncates toward zero (like C, unlike Python's //). mod is whatever makes a = (a div b) * b + (a mod b) true, so its sign follows a.
| a | b | div a b | mod a b | Python a // b, a % b |
|---|---|---|---|---|
| 7 | 2 | 3 | 1 | 3, 1 |
| -7 | 2 | -3 | -1 | -4, 1 |
| 7 | -2 | -3 | 1 | -4, -1 |
| -2147483648 | -1 | -2147483648 | 0 | 2147483648, 0 (no wrap) |
div or mod by 0 is a runtime error. So is shl by anything outside [0, 31]. shl 1 31 is -2147483648.
i32 division, exactly
Write div32 a b for i32 values held in OCaml ints. Return Some q, where q is the quotient truncated toward zero and wrapped to 32 bits, or None when b = 0. (Lesson 0.6 had a version that raises, but this one returns an option instead. The tests print None as error.)
Write div32(a, b) for i32 values held in Python ints. Return the quotient truncated toward zero and wrapped to 32 bits, or None when b is 0. (Lesson 0.7 had the same drill. This is your chance to check it against the table.)
Check the table above against what your language's own division does. One row needs extra care.
f32: rounding after every step
An f32 has 24 bits of precision. After every op, the exact result is rounded to the nearest representable f32. A tie goes to the even neighbor, like rounding 2.5 to 2 and 3.5 to 4. If your language computes in 64-bit doubles, round back to 32 bits after each op, not once at the end.
2²⁴ = 16777216 is where f32 runs out of integers. add 16777216.0 1.0 is exactly halfway between 16777216 and 16777218, and it rounds to even, giving 16777216.0. The 1 just disappears.
In 64-bit doubles, 0.1 + 0.2 == 0.3 is famously false. In f32 it happens to be true: %s = add 0.1 0.2 then %t = assert %s 0.3 passes. If your interpreter uses doubles and forgets to round, it gets this wrong.
What assert means by "equal"
- i32 and bool compare exactly.
- f32 compares by value, so
0.0equals-0.0. - Two NaNs count as equal, so
assert nan nanpasses. In IEEE,nan == nanis false. Our rule is chosen so tests can say "this should be NaN". maxwith a NaN operand is NaN.cmpltwith a NaN isfalse.
cast rules
cast 3.9 dtype=i32 is 3 and cast -3.9 dtype=i32 is -3, because f32 to i32 truncates toward zero. A NaN, or a value outside the i32 range, is a runtime error. bool to a number gives 0 or 1. A number to bool means "not zero".
Round to f32
OCaml's floatPython's float is a 64-bit double. Write f32, which rounds x to the nearest f32 (ties to even, overflow to inf), and add32, which adds two f32 values a and b the way your interpreter must: compute, then round.
The Int32 module can move a float through its 32-bit bit pattern. Look for bits_of_float.
The struct module can move a float through its 32-bit encoding, as in lesson 0.7. Remember what it does on overflow.
Check yourself
What is div -7 2?
The exact quotient is -3.5. C-style division truncates toward zero, not toward minus infinity.
Truncate toward zero: -3.5 becomes -3. Python's // would give -4.
What is mod -7 2?
Use a - (a div b) * b, with the truncated quotient from the previous quiz.
-7 - (-3)*2 = -1. The sign follows the dividend.
What is add 2147483647 1?
i32 addition wraps around. What comes after the largest i32?
i32 wraps: INT_MAX + 1 = INT_MIN.
What does run exit with for this file?
%a = add 1.5 1
%t = assert %a 2.5Look at the dtypes of the two literals. Does .uir ever convert between them for you?
1 is an i32 literal and 1.5 is f32. There's no implicit conversion, so add rejects mismatched dtypes when the node is built.
Exit code?
%bad = div 1 0
%t = assert 1 1The program's roots are its asserts. Is %bad reachable from one?
No assert depends on %bad, so it's never evaluated. Runtime errors only count when an assert needs the value.
Exit code?
%a = add 2 2
%t = assert %a 5The program parses and type checks. What does the assert compare, and what's the exit code for a false one?
A valid program whose assert is false.
Does this pass?
%s = add 16777216.0 1.0
%t = assert %s 16777216.0f32 has 24 bits of precision, and 16777216 is 2 to the 24th. Can f32 represent 16777217?
When a value sits exactly halfway between two f32 numbers, the tie goes to the one whose last bit is even.
16777217 isn't representable in f32. It's a tie between 16777216 and 16777218, and ties round to even.
Does assert nan nan pass?
IEEE says NaN never equals NaN, but this course's spec defines assert equality on purpose. Check section 3.
The spec defines assert equality so you can test for NaN. Inside the program, cmplt still follows IEEE: any NaN gives false.
What is cast -3.9 dtype=i32?
Casting f32 to i32 truncates toward zero. Which integer is closer to zero, -3 or -4?
Truncate toward zero, not floor. cast 3000000000.0 dtype=i32 would be a runtime error, because it's out of range.
Code it
Absolute value in .uir
Define %out as |x| for the i32 param %x, using cmplt, where and mul. There's no sub or neg op: -x is mul %x -1.
What should |INT_MIN| be when i32 wraps? The tests have an opinion.