Milestone M1

The Expression Evaluator

Part II built the pieces of an evaluator: the values it produces, the walk that produces them, the failures it reports, and the rules that fix what each expression means. This milestone puts them together into a working evaluator for the expression fragment, and gives you a way to know it runs correctly.

The codebase

The starter is one interpreter that you grow across the milestones. Nearly all of it is provided and frozen — the parser, the value and error types, the environment and the store — so your effort goes into meaning rather than the plumbing that would have you fighting the borrow checker. The files that matter here:

src/
  ast.rs            the Expr tree and its companion types    (provided)
  interp/
    eval.rs         eval_expr — YOUR file
    value.rs        the Value type, and type_of              (provided)
    error.rs        RuntimeError and Control                 (provided)
    env.rs          the environment (used from M2)           (provided)
    store.rs        the store (used from M4)                 (provided)
  parser/           source text -> Expr                      (provided)
  types/            the type checker (M5)                    (deferred)
  relations/        the Datalog fragment (M6)                (deferred)

Most work happens in one method, which you grow a little each milestone:

pub fn eval_expr(&mut self, e: &Expr, env: &Env) -> Result<Value, Control>

Every Expr variant already has a match arm. The ones you have not reached yet are milestone-tagged holes — a todo_mN!(…) that compiles as any type but stops the run if reached — so the crate builds from the first clone with nothing written. As you fill an arm, you replace its hole with the rule’s implementation. To read the shape of any provided type — Value, Expr, RuntimeError — while you work, build the API docs and open them in your browser:

cargo doc --no-deps --open

Setting up

Install the Rust toolchain from rustup — it brings cargo, the formatter, and the linter — and confirm it runs:

cargo --version

Clone the starter repository, then build it once. A fresh clone builds green, because every hole compiles:

cd bridger-interpreter
cargo build

From there, the loop you repeat on every milestone:

cargo m1                                    # run the Milestone-1 tests
cargo fmt                                   # format your code
cargo clippy --all-targets -- -D warnings   # lint

cargo m1 is short for cargo test --features m1 — the tests you should pass in Milestone M1. The milestones are cumulative. So cargo m2 will run the tests for Milestone M2 and Milestone M1.

Finding the holes

Every place you write code is a macro named for its milestone, so a search lists exactly what a milestone asks for:

grep -rn 'todo_m1!' src

turns up the six arms of eval_expr — and in general, grep -rn 'todo_mN!' src is Milestone N’s checklist. The six for M1:

// src/interp/eval.rs — the six M1 arms of eval_expr
Expr::Lit(..)    => todo_m1!("E-Lit"),
Expr::Unary(..)  => todo_m1!("E-Neg / E-Not"),
Expr::Binary(..) => todo_m1!("E-Arith/Ord/Eq, E-And/Or, E-Concat, E-Cons"),
Expr::Tuple(..)  => todo_m1!("E-Tuple"),
Expr::List(..)   => todo_m1!("E-List"),
Expr::Proj(..)   => todo_m1!("E-Proj"),

Every other Expr variant is a hole tagged for a later milestone, which is why the crate compiles with none of them written.

The specification you must satisfy

Each expression form, the rule that gives it meaning, and the case that leaves it stuck:

The full rules are in the Program Semantics chapter; this table is the checklist your evaluator is measured against, not a second statement of them.

Three contracts hold across every arm. On success an arm returns Ok(v); when the expression is stuck it returns Err(Control::Raise(…)) carrying the RuntimeError and the span of the node the rule blames — the interpreter reports rather than panics. and and or short-circuit: the right operand is evaluated only when the left has not already settled the result. And integer arithmetic wraps modulo $2^{64}$, as the values chapter fixed.

Implementing the arms

Destructure each arm’s .. into the fields you need. The M1 variants and what they carry:

BinOp names the operator: Add Sub Mul Div Mod for arithmetic, Eq Ne Lt Le Gt Ge for comparison, And Or, Concat for ++, and Cons for ::.

Three tools do the work of every arm:

• Evaluate a subexpression with self.eval_expr(sub, env)?. The ? sends a stuck operand straight out, so an arm only handles the case where its operands produced values.
• Build the result — Value::Int, Value::Bool, Value::Str, Value::Tuple, Value::List. Integer arithmetic uses the wrapping operations (i64::wrapping_add, wrapping_mul, …), since the reference fixes 64-bit wraparound.
• Report a stuck expression — return RuntimeError::TypeError { expected, found, span } or RuntimeError::DivByZero { span }. The provided type_of(&v) gives the found type, Ty::int() / Ty::bool() / … name the expected one, and span is the offending node’s. A From<RuntimeError> for Control is provided, so .into() (or ?) lifts a RuntimeError into the Control::Raise the signature returns.

You have already seen this in Part II: the Add arm is worked in full, and Div and and show the divisor guard and short-circuiting. The rest of M1 is the same shape, one arm at a time.

Worked examples

An expression, and the value it evaluates to:

1 + 2 * 3          ⇓ 7
-(3 - 5)           ⇓ 2
7 / 2              ⇓ 3          (integer division)
7 % 2              ⇓ 1
2 < 3              ⇓ true
(1, 2) == (1, 2)   ⇓ true       (structural)
"ab" ++ "cd"       ⇓ "abcd"
[1, 2] ++ [3]      ⇓ [1, 2, 3]
0 :: [1, 2]        ⇓ [0, 1, 2]
(10, 20).1         ⇓ 20
false and (1 / 0)  ⇓ false      (right operand never evaluated)

And expressions with no value, which halt the run:

1 + true      ⇓ stuck   (an Int operator met a Bool)
5 / 0         ⇓ stuck   (division by zero)
"a" ++ [1]    ⇓ stuck   (++ needs both strings or both lists)
(1, 2).5      ⇓ stuck   (projection past the end of a 2-tuple)

How to know it works

cargo m1 runs the set of provided milestone M1 tests; all pass means the fragment is likely correct. Each test builds an Expr and calls eval_expr on it — one rule at a time. A value test checks the Value; a stuck test checks the error’s variant, its expected/found types, and the span it blames, but not its wording. The builders (int, binary, tuple, …) and the assertions value_of and stuck come with the repository, so a check reads close to the rule it exercises:

// 1 + 2 * 3  ⇓  7
let e = binary(Add, int(1, 0), binary(Mul, int(2, 2), int(3, 4), 3), 1);
assert_eq!(value_of(&e), Value::Int(7));

// 1 + true  is stuck: an Int operator met a Bool
let bad = binary(Add, int(1, 0), boolean(true, 2), 1);
assert!(matches!(stuck(&bad), RuntimeError::TypeError { .. }));

Fill an arm, run cargo m1, and repeat until the all M1 tests pass.

Design problems