Milestone M3

Control Flow and Mutation

Part IV let the language do things. A cell in the store holds a value that changes, if chooses a course of action, while and for repeat one, and return carries a value out past the code around it. This milestone puts them into the evaluator, and the run of the language grows from computing a value to changing state and controlling the order in which it changes.

The codebase, the toolchain, and the build loop are the ones Milestone M1 set up. What is new here on the provided side is the store: a Store that lives on the interpreter, with three operations — allocate a cell, read one, write one — and a Value::Ref that carries a cell’s location. It is the state the mutation forms act on, described in full in the Mutation chapter’s build section.

To-dos

grep -rn 'todo_m3!' src lists five arms left as holes after M2:

// src/interp/eval.rs — the five M3 arms of eval_expr
Expr::If(..)     => todo_m3!("E-If"),
Expr::While(..)  => todo_m3!("E-While"),
Expr::For(..)    => todo_m3!("E-For"),
Expr::Assign(..) => todo_m3!("E-Assign"),
Expr::Return(..) => todo_m3!("E-Return"),

Two more cases are not on that list. ref and deref are UnOp variants, so they are two new arms of the match inside Expr::Unary — the arm you filled at M1 for -e and not e, whose stub was labelled “ref & deref join at M3”. The grep under-counts M3 by exactly those two: seven forms in all, five of them their own Expr variant and two of them cases of an existing one.

Milestone specification

Each form this milestone adds, the rule that gives it meaning, and the case that leaves it stuck:

Form	Rule	Stuck when
`if c { … } else { … }`	`E-If`	`c` is not a `Bool`
`ref e`	`E-Ref`	—
`deref e`	`E-Deref`	`e` is not a reference
`e1 := e2`	`E-Assign`	`e1` is not a reference
`while c { … }`	`E-While`	`c` is not a `Bool`
`for x in e { … }`	`E-For`	`e` is not a list
`return e`	`E-Return`	—

The full rules are in Mutation and References and Conditionals and Loops; this table is the checklist your evaluator is measured against, not a second statement of them. What each form evaluates to — the branch’s value for if, a fresh reference for ref, () for the effectful forms — is the subject of the contracts below.

Three contracts hold across these arms. The effectful forms yield unit: :=, while, and for each evaluate to (), and an else-less if does too when its condition is false. A loop discards its body’s value each turn — a while body runs for its effect on the store, a for body for its effect once per element, and the loop’s own value is (). And a return leaves on a channel of its own: it is not an ordinary value the arms combine but a control transfer that travels straight out through the loops and blocks in its way, abandoning the iterations that would have followed.

Implementing Milestone M3

Destructure each arm’s .. into the fields you need:

Variant	Fields	Covers
`Expr::If`	`(Box<Expr>, Box<Expr>, Option<Box<Expr>>, Span)`	cond, then, optional else
`Expr::While`	`(Box<Expr>, Box<Expr>, Span)`	condition, body
`Expr::For`	`(Name, Box<Expr>, Box<Expr>, Span)`	bound name, iterable, body
`Expr::Assign`	`(Box<Expr>, Box<Expr>, Span)`	the cell (left), the value (right)
`Expr::Return`	`(Box<Expr>, Span)`	the returned expression
`Expr::Unary`	`(UnOp, Box<Expr>, Span)`	now also `UnOp::Ref`, `UnOp::Deref`

The store is reached through the interpreter, self.store, and its three operations are the three mutation forms:

ref e evaluates e and calls self.store.alloc(v), which makes a fresh cell and returns its Loc; the value the form returns is Value::Ref(loc).
deref e evaluates e to a Value::Ref(loc) and returns self.store.read(loc).
e1 := e2 evaluates e1 to a Value::Ref(loc), then e2 to a value, calls self.store.write(loc, v), and returns Value::Unit.

A deref or := whose operand is not a Value::Ref is stuck — a RuntimeError::TypeError built with Ty::reference(..) for the expected type. The rules of the Mutation chapter thread a store in and a store out; the interpreter keeps the store on itself and mutates it in place, so alloc and write are the step from one store to the next.

The control forms match the value they branch on:

if evaluates its condition; on Value::Bool(true) it evaluates the then-branch, on Value::Bool(false) the else-branch — or Value::Unit when there is none. Only the branch taken is evaluated. A non-boolean condition is stuck.
while is a host loop: re-evaluate the condition each turn, run the body while it is Value::Bool(true) (the body’s value taken with ? and dropped), and stop with Value::Unit when it is false. A non-boolean condition is stuck.
for evaluates its iterable to a Value::List, then walks it, evaluating the body once per element in env.extend(x, item) — a fresh binding of x each turn, discarded after — and yields Value::Unit. An iterable that is not a list is stuck.
return e evaluates e and leaves through the return channel: Err(Control::Return(v)). This is the second variant of Control, beside the Control::Raise an error rides (error handling). Because a loop body runs with ?, a return in the body carries straight out of the host loop, which is what abandons the remaining iterations.

At this milestone a return has no enclosing function to catch it — that boundary arrives with functions in Part V. Reaching a return where none is allowed is ruled out before the program runs, so the evaluator’s job is only to raise the channel; nothing in this milestone catches it.

Worked examples

A program, and the value it evaluates to:

if true { 1 } else { 2 }             ⇓ 1
if false { 9 }                       ⇓ ()   (else-less, condition false)
deref (ref 5)                        ⇓ 5

let r = ref 0;
r := 7;
deref r                              ⇓ 7    (write, then read it back)

let a = ref 1;
let b = a;                           // b holds the same cell as a
b := 9;
deref a                              ⇓ 9    (aliasing)

let i = ref 0;
while deref i < 3 { i := deref i + 1 };
deref i                              ⇓ 3

let acc = ref 0;
for x in [1, 2, 3] { acc := deref acc + x };
deref acc                            ⇓ 6

Programs that leave through the return channel rather than with a value:

return 5                             → returns 5
while true { return 7 }              → returns 7   (the loop is abandoned)

And programs with no value, which halt the run:

if 3 { 1 } else { 2 }                ⇓ stuck  (condition is not a Bool)
while 1 { }                          ⇓ stuck  (condition is not a Bool)
for x in 5 { }                       ⇓ stuck  (iterable is not a list)
deref 5                              ⇓ stuck  (deref of a non-reference)
5 := 6                               ⇓ stuck  (assign to a non-reference)

How to know it works

cargo m3 runs the provided milestone M3 tests and, because the milestones are cumulative, the M2 and M1 tests with them. Each test builds an Expr and checks the Value it evaluates to, the error a stuck test blames (its variant and span), or — for a return — the value it carries out. The builders if_, if_else, while_, for_, assign, and return_ join the earlier ones, ref and deref are written as unary(UnOp::Ref, …) and unary(UnOp::Deref, …), and the assertion returned unwraps the return channel where value_of and stuck unwrap a value or an error:

// if true { 1 } else { 2 }  ⇓  1
let e = if_else(boolean(true, 1), int(1, 2), int(2, 3), 0);
assert_eq!(value_of(&e), Value::Int(1));

// deref (ref 5)  ⇓  5   (ref / deref are UnOp::Ref / UnOp::Deref)
let e = unary(UnOp::Deref, unary(UnOp::Ref, int(5, 2), 1), 0);
assert_eq!(value_of(&e), Value::Int(5));

// while true { return 7 }  returns 7 through the return channel
let e = while_(boolean(true, 1), return_(int(7, 3), 2), 0);
assert_eq!(returned(&e), Value::Int(7));

Fill an arm, run cargo m3, and repeat until every M3 test — and every M2 and M1 test — passes.

Design problems

Your eval_expr returns Result<Value, Control>, and a return travels as Err(Control::Return(v)) — the same Err side an error uses. Why carry a return as an Err at all, rather than as an ordinary Value, and how do the two channels stay distinct?

A return has to leave the code around it without that code folding it into a larger value — the 1 + in 1 + return 2 must not add anything, the rest of a block after return must not run, the turns of a loop still to come must not happen. An ordinary Value cannot do that: the arm that receives it would go on and use it. Travelling on the Err side is what gives it that reach — every ? in the evaluator passes an Err straight out untouched, so a return threads out through arithmetic, blocks, and loops alike with no arm having to check for it. It rides the same channel as an error for exactly that shared behaviour: both are non-local exits. They stay distinct as two variants of Control — Raise for an error, which the top level reports and halts on, and Return for a value, which a function boundary in Part V catches and turns back into the call’s result. At this milestone nothing catches Return, so a bare return surfaces at the top; the error-handling chapter is where the Control channel itself is built.

The E-While-True rule names the same while among its premises, and E-Assign threads a store in and a store out; yet your while is a plain host loop and your store is one field mutated in place. What property of the rules lets the implementation drop the recursion and the threading, and where would dropping them go wrong?

Both simplifications rest on the rules being deterministic and single-threaded: evaluation proceeds in one order, each step producing exactly one store that the next step consumes, with no branch of the derivation needing a store some other branch also holds. Because the store is never shared between two live continuations, one mutable field can stand in for the whole sequence $σ, σ_{1}, σ_{2}, \dots$ — writing it in place is indistinguishable from a fresh store, since nothing still refers to the old one. And because E-While-True’s self-reference is a plain tail repetition against the body’s output store, a host loop that re-tests the condition reproduces the finite stack of the rule without the evaluator calling itself. It would go wrong anywhere the derivation forks over a shared store and both forks matter — if a form evaluated a subexpression, then backtracked and evaluated it again from the original store, the in-place store would already carry the first attempt’s writes. Bridger has no such form; the relations of Part VII search, but over their own database rather than the mutable store, which is why they keep a channel apart from it.

Using ref, for, and the list operators of Part II, write a Bridger program that reverses the list [1, 2, 3], and explain why the accumulator is a cell.

let acc = ref [];
for x in [1, 2, 3] {
  acc := x :: deref acc
};
deref acc                            // [3, 2, 1]

The for binds x to 1, then 2, then 3 in turn, and each turn prepends the current element onto the front of the list the cell holds: [] becomes [1], then [2, 1], then [3, 2, 1]. The result comes out reversed because prepending puts the last element seen at the front. The accumulator has to be a cell, not a plain binding, because it must carry a value across the turns of the loop — the binding x is remade each turn and gone by the next, and a let inside the body would be scoped to that one turn. Only a store cell, allocated before the loop and read and written inside it, survives from one element to the next; the loop supplies the repetition and the store supplies the memory.

Bridger has no break. Write a while that scans upward from 0 and stops as soon as it reaches 5, using a second cell as a flag, and say why the flag is needed rather than a bare condition.

let i = ref 0;
let running = ref true;
while deref running {
  if deref i == 5 {
    running := false
  } else {
    i := deref i + 1
  }
};
deref i                              // 5

The loop’s condition tests the flag cell running; the body either clears the flag, which stops the loop on the next test, or steps the counter. A flag is needed because the only way out of a Bridger loop short of running its condition false is return, which would leave the whole enclosing function, not just the loop — there is no break to leave the loop alone. Folding the stopping decision into a cell the condition reads turns “leave early” into “make the condition false early”, which is a step the loop’s own machinery already takes. The cost is the extra cell and the if inside the body; what it keeps is a loop covered entirely by the two while rules, with no second way for control to leave it.

Keyboard shortcuts