Week 1 · Lesson 5

call, param, stack and index

Week 1 programs can define functions. A function is just a graph with holes in it: param marks a hole, and call fills the holes and evaluates the graph.

The lambda calculus in one paragraph

In the 1930s Alonzo Church showed that a language with only three things (variables, function definitions, and function application) can express any computation. Evaluation is one move, beta reduction: to apply a function, replace its variable with the argument everywhere it appears. (λx. x + 1) 41 becomes 41 + 1 (λx. x + 1 is math notation for "the function taking x to x + 1"). That's exactly what call does to a graph.

param and call

%x    = param 0 dtype=i32     # hole number 0, holds an i32
%body = add %x 1              # a graph with a hole: "x + 1"
%r    = call %body 41         # fill hole 0 with 41 and evaluate
%t    = assert %r 42

call's first source is the body. The rest are the args: arg i fills every param i reachable from the body. Args are checked statically. A missing arg, or one with the wrong dtype or shape, is a type error (exit 2). Extra args are allowed and ignored.

A body is just an ordinary UOp. Nothing marks %body as "a function". It becomes one when a call uses it as src 0. In the graphs below, that src 0 edge is drawn dashed.

Call one body twice

Define %out as x*x + y*y for i32 params x (slot 0) and y (slot 1). Write the squaring once, as a body over its own param 0, and call it twice.

Your body's param 0 and the outer %x are the same hash-consed node. Why is that fine?

Beta reduction on a graph

The spec's nested example, traced. %inner doubles its param. %outer passes its own param 0 into inner's slot 0.

%p0    = param 0 dtype=i32
%inner = mul %p0 2
%outer = call %inner %p0
%r     = call %outer 5
%t     = assert %r 10
Bodies are closed

Substitution walks the body, but it does not walk into the body (src 0) of a nested call. It does walk into that call's args. A nested function's params belong to that function, and the only way to give them a value is through its args.

Why does this matter? Look at this variant, where inner uses slot 0 and outer passes its slot 1:

%p0    = param 0 dtype=i32
%p1    = param 1 dtype=i32
%inner = add %p0 100
%outer = call %inner %p1      # inner's slot 0 := outer's slot 1
%r     = call %outer 1 2      # outer: slot 0 := 1, slot 1 := 2

Done right, outer substitutes into its args only: call %inner 2, which gives 2 + 100 = 102. If your substitution wrongly walked into inner's body too, it would turn inner's %p0 into 1 (outer's slot 0) and get 101.

Code it

Substitution with closed bodies

Here is a toy term language with numbers, params, Add, and Call (body, args). Write subst args t: replace every Param i reachable from t with the i-th element of args.

This is the 101 vs 102 bug from above, on a type small enough to see in one screen. Keep the given show function, because the tests print with it.

Params are hash consed too

%a = param 0 dtype=i32 and %b = param 0 dtype=i32 are the same UOp, even when they're written for two different functions. That's fine: a param doesn't have a value on its own. Its value comes from whichever call is evaluating it right now. So never cache "the value of this node" globally. Cache it per call.

Substitution, as traced above, is the mental model. The usual implementation doesn't build new nodes: it evaluates the body with an environment, a map from slot number to value for the current call, and a fresh cache for that call.

Two more rules. A param evaluated outside of any call has no value, so it's a runtime error (exit 2). And since a call has no side effects (it's pure), the simplifier can always inline it (replace the call with its body, params substituted), whether the args are constants or params: replace it with the substituted body, then keep folding. call %body 41 with %body = add %x 1 simplifies all the way to const 42.

stack and index: rank 1

stack takes scalars of one dtype and adds a new leading axis: stack 10 20 30 has shape (3,) (a shape with one axis of size 3; in .uir text you write it shape=[3]). index x i pops that axis back off and returns one element as a scalar. The index is checked at runtime: i < 0 or i ≥ n is a runtime error.

%s = stack 10 20 30, then %r = index %s i
i =
Shape (3,), so the valid indices are 0, 1 and 2. Try -1 and 3.

ALU ops only take rank-0 operands, so a rank-1 value can only be passed around, indexed, or compared whole with assert. A param can be rank 1 too, which makes it look like an array argument:

%v = param 0 dtype=i32 shape=[3]
%k = param 1 dtype=i32
%f = index %v %k
%s = stack 7 8 9
%r = call %f %s 1             # 8

Rotate with stack and index

Params a, b, c and i are i32. Stack a b c. Compute j = i + 1 with i32 add (so INT_MAX + 1 wraps to INT_MIN), then return the element at j mod 3, fixed into 0, 1, 2. So i = 0 gives b and i = 2 gives a.

The tests include i = 300, i = -2 and i = INT_MAX. Remember that mod keeps the sign of the dividend, and that an out-of-range index is a runtime error.

Check yourself

Predict %r.

%p0    = param 0 dtype=i32
%p1    = param 1 dtype=i32
%inner = add %p0 100
%outer = call %inner %p1
%r     = call %outer 1 2

Outer's call binds outer's slots: p0 = 1, p1 = 2. Which of those does outer hand to inner's slot 0?

102. Outer's slot 1 (which is 2) fills inner's slot 0. Inner's body is never touched by outer's substitution.

Predict %r. Careful with the closed-body rule.

%p0    = param 0 dtype=i32
%inc   = add %p0 1
%twice = call %inc %inc
%r     = call %twice 5

%inc appears twice in call %inc %inc: once as the body and once as the arg. Substitution goes into args but never into bodies.

Evaluate the arg first: %inc with p0 = 5. Then run the body %inc on that result.

7. Calling %twice with 5 substitutes into its arg, %inc, giving 6. The body %inc is left alone. Then call %inc 6 gives 7. The same node is used once as a body and once as an arg, and the two roles never mix.

What does run do with this program?

%x    = param 0 dtype=i32
%body = add %x 1
%r    = call %body
%t    = assert %r 1

The call passes zero args, but the body uses param 0. Is that caught before anything runs, or only when the assert is evaluated?

Every param reachable from the body needs a matching arg, and that's checked statically, before anything runs. It's an invalid program.

How many distinct UOps do these two lines create?

%a = param 0 dtype=i32
%b = param 0 dtype=i32

Hash consing keys a node on (op, src, arg), with dtype and shape as part of the key. Compare the two lines on each of those.

One. Same op, same sources (none), same arg and dtype, so hash consing returns the existing node.

What exit code does run give?

%s = stack 10 20 30
%i = index %s 3
%t = assert %i 30

%s has shape (3,). Which indices are in range, and what kind of error is an out-of-range index?

2. Index 3 is out of range for shape (3,), so it's a runtime error in a value the assert depends on.

Predict %r.

%v = param 0 dtype=i32 shape=[3]
%k = param 1 dtype=i32
%f = index %v %k
%s = stack 7 8 9
%r = call %f %s 1

The call binds %v to the stack and %k to 1. Indexing counts from 0.

8, element 1 of [7 8 9]. The rank-1 arg matches the param's shape=[3].

What does run do with %x = param 0 dtype=i32 followed by %t = assert %x 1?

Is there any call around this param to give slot 0 a value?

There's no call supplying slot 0, so %x has no value. The program is invalid.