Lab 3: The First Evaluator (Milestone 1)

Background

You will write src/interp/eval.rs and make this work:

$ echo '10 + 20 * 3' > t.ember && ember run t.ember
70

That is Milestone 1. The pipeline is complete end to end for the first time: characters, tokens, tree, value.

This evaluator is not a throwaway. It becomes the reference implementation — the semantic oracle that the bytecode VM is tested against in Lab 12. Write it to be obviously correct, not fast.

Why This Lab Matters

It closes the loop. Until something runs, every earlier decision is a hypothesis.
Post-order traversal is evaluation order, and evaluation order is a language semantic you are now defining. Once side effects exist (Lab 7), it is observable.
The arithmetic rules you write here are the specification that the VM must match, byte for byte, for the next twelve weeks. They are also the first place Ember's semantics can silently diverge from Lua's — so every rule gets checked against lua.

Prerequisites

Labs 1–2 complete.
The AST, Concept 2 (traversal).
Lua 5.4 installed, for the comparison loop in Step 4.

Predict First

2 ^ 2 — integer 4 or float 4.0?
7 // 2 and -7 // 2 — what are they?
7 % -3 and -7 % 3 — what are they, and what determines the sign?
1 // 0 versus 1 / 0 versus 1.0 // 0 — which of these is an error?
math.maxinteger + 1 — error, float, or wrap?
-math.mininteger — what?
0/0 — what does it print, and is that answer the same on every machine?

Write all seven down. You will check them against lua in Step 4, and at least two will surprise you.

Step 1: A Minimal `Value`

Concept. Runtime values are a tagged union.

Goal. Just enough to hold arithmetic results. The full type set is Lab 4.

#![allow(unused)]
fn main() {
// src/value.rs
#[derive(Copy, Clone, Debug, PartialEq)]
pub enum Value {
    Integer(i64),
    Float(f64),
}

impl std::fmt::Display for Value {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            // Lua's tostring for floats always shows it IS a float: 4.0, not 4.
            // %.14g is what Lua 5.4 uses (LUAI_NUMFFORMAT), and matching it now
            // means the golden tests do not churn in Lab 4.
            Value::Integer(i) => write!(f, "{i}"),
            Value::Float(x) if x.fract() == 0.0 && x.is_finite() => write!(f, "{x:.1}"),
            Value::Float(x) => write!(f, "{}", format_g14(*x)),
        }
    }
}
}

Note: Printing floats is a surprising amount of the difficulty in matching another language's output. Lua 5.4 formats with "%.14g" and then appends .0 if the result looks like an integer. Run lua -e 'print(0.1+0.2, 1e15, 1e16, 2^53)' and make your formatter agree. Do it now, because every golden test in the curriculum compares printed output.

Step 2: The Evaluator Skeleton

Concept. Post-order traversal.

#![allow(unused)]
fn main() {
// src/interp/eval.rs
pub struct Interp { /* scopes arrive in Lab 5 */ }

impl Interp {
    pub fn eval_expr(&mut self, e: &Expr) -> Result<Value> {
        match e {
            Expr::Int   { value, .. } => Ok(Value::Integer(*value)),
            Expr::Float { value, .. } => Ok(Value::Float(*value)),

            Expr::Unary { op, operand, span } => {
                let v = self.eval_expr(operand)?;
                self.unary_op(*op, v, *span)
            }

            Expr::Binary { op, lhs, rhs, span } => {
                let l = self.eval_expr(lhs)?;      // ← LEFT first.
                let r = self.eval_expr(rhs)?;      // ← THEN right.
                self.binary_op(*op, l, r, *span)   // ← THEN the operator.
                // Those three lines define Ember's evaluation order. Write it in
                // docs/architecture.md; the compiler in §3 must emit code that
                // reproduces it exactly or the differential tests fail.
            }

            other => Err(EmberError {
                kind: ErrorKind::Runtime,
                message: format!("{} is not supported yet", node_name(other)),
                span: Some(other.span()), traceback: Vec::new() }),
        }
    }
}
}

The part that matters. let l = ...?; let r = ...?; is a semantic decision, not obvious code. Lua's manual does not guarantee operand evaluation order; Ember does, because determinism is a product requirement. It becomes observable in Lab 7, when f() + g() can print.

On recursion depth: eval_expr recurses once per AST node, so a deeply nested expression could overflow the Rust stack — except that the parser's MAX_PARSE_DEPTH already bounds tree depth at 200. One guard, three hazards: parser stack, Drop recursion, and evaluator stack. That chain breaks in Lab 7 when script function calls start consuming Rust stack independently of tree depth, and that is where the evaluator gets its own counter.

Step 3: Arithmetic, Following Lua 5.4

Concept. In a language with two numeric subtypes, every operator needs a promotion rule, and the rules are not uniform.

#![allow(unused)]
fn main() {
fn binary_op(&mut self, op: BinOp, l: Value, r: Value, span: Span) -> Result<Value> {
    use Value::*;
    Ok(match op {
        // + - *  : integer-preserving. Both integers → integer, WRAPPING.
        BinOp::Add => match (l, r) {
            (Integer(a), Integer(b)) => Integer(a.wrapping_add(b)),
            _ => Float(as_float(l)? + as_float(r)?),
        },
        BinOp::Sub => match (l, r) {
            (Integer(a), Integer(b)) => Integer(a.wrapping_sub(b)),
            _ => Float(as_float(l)? - as_float(r)?),
        },
        BinOp::Mul => match (l, r) {
            (Integer(a), Integer(b)) => Integer(a.wrapping_mul(b)),
            _ => Float(as_float(l)? * as_float(r)?),
        },

        // /  : ALWAYS float. 4 / 2 is 2.0, not 2.
        BinOp::Div => Float(as_float(l)? / as_float(r)?),

        // ^  : ALWAYS float. 2 ^ 2 is 4.0.
        BinOp::Pow => Float(as_float(l)?.powf(as_float(r)?)),

        // // : FLOOR division. Integer//integer is integer, and //0 is an ERROR.
        BinOp::IDiv => match (l, r) {
            (Integer(_), Integer(0)) =>
                return Err(rt(span, "attempt to perform 'n//0'")),
            (Integer(a), Integer(b)) => Integer(a.div_euclid(b)),
            _ => Float((as_float(l)? / as_float(r)?).floor()),
        },

        // %  : result takes the sign of the DIVISOR, per a - floor(a/b)*b.
        BinOp::Mod => match (l, r) {
            (Integer(_), Integer(0)) =>
                return Err(rt(span, "attempt to perform 'n%%0'")),
            (Integer(a), Integer(b)) => Integer(a.rem_euclid(b) * if b < 0 && a.rem_euclid(b) != 0
                                                { 1 } else { 1 }),   // see the warning below
            _ => { let (a, b) = (as_float(l)?, as_float(r)?); Float(a - (a / b).floor() * b) }
        },
        _ => return Err(rt(span, "operator not supported yet")),
    })
}

fn unary_op(&mut self, op: UnOp, v: Value, span: Span) -> Result<Value> {
    Ok(match (op, v) {
        // Negating i64::MIN WRAPS to itself, exactly as in Lua.
        (UnOp::Neg, Value::Integer(a)) => Value::Integer(a.wrapping_neg()),
        (UnOp::Neg, Value::Float(x))   => Value::Float(-x),
        _ => return Err(rt(span, "unsupported unary operator")),
    })
}
}

Warning: The Mod integer arm above is deliberately written wrong-looking, because Rust's %, rem_euclid, and div_euclid do not all match Lua. Rust's % truncates toward zero (-7 % 3 == -1); Lua's % floors (-7 % 3 == 2). rem_euclid is always non-negative (7.rem_euclid(-3) == 1), which is also not Lua (7 % -3 == -2). Work out the correct expression yourself, then verify every combination of signs against lua. This is one of the two places in Section 1 where copying the obvious standard-library function gives a subtly wrong language. The other is div_euclid for // — check -7 // 2 and 7 // -2 too.

The rule you are implementing is Lua 5.4 §3.4.1: a % b == a - math.floor(a/b)*b.

Step 4: Check Every Rule Against the Reference

This is the most valuable twenty minutes in the lab. Do not skip it.

#!/usr/bin/env bash
# scripts/compare-arith.sh  — keep this; it grows with every operator you add.
exprs=(
  '10 + 20 * 3'  '2 ^ 2'      '4 / 2'      '7 // 2'    '-7 // 2'
  '7 // -2'      '-7 // -2'   '7 % 3'      '-7 % 3'    '7 % -3'
  '-7 % -3'      '7.5 % 2'    '-7.5 % 2'   '1 / 0'     '-1 / 0'
  '2^63'         '1 << 0'
)
for e in "${exprs[@]}"; do
  lua_out=$(lua -e "print($e)" 2>&1)
  emb_out=$(ember run -e "return $e" 2>&1)
  mark=$([ "$lua_out" = "$emb_out" ] && echo "  ok" || echo "DIFF")
  printf '%s  %-14s lua=%-24s ember=%s\n' "$mark" "$e" "$lua_out" "$emb_out"
done

Also run the ones that must be errors:

for e in '1 // 0' '1 % 0'; do
  printf '%-10s lua: %s\n' "$e" "$(lua -e "print($e)" 2>&1 | tail -1)"
done

Every DIFF is a decision you now have to make, not a bug you automatically fix. 1 << 0 will differ because Ember has no bitwise operators — that is a documented divergence, and it belongs in appendix/lua-differences.md. 7 % -3 differing is a bug. Learn to tell them apart; that judgment is most of what this comparison loop teaches.

Checkpoint question. 2^63 in Lua prints a float. Why can it not be an integer, given that ^ always produces a float anyway? (The question is really: what does math.type(2^63) tell you about when the float-ness is decided — at parse time or at evaluation time?)

Step 5: `ember run`

#![allow(unused)]
fn main() {
fn cmd_run(src: &str, name: &str) -> ExitCode {
    let map = SourceMap::with(name, src);
    let result = ember::lexer::tokenize(src)
        .and_then(|toks| ember::parser::Parser::new(toks).parse_chunk())
        .and_then(|ast| ember::interp::Interp::new().run(&ast));
    match result {
        Ok(Some(v)) => { println!("{v}"); ExitCode::SUCCESS }
        Ok(None)    => ExitCode::SUCCESS,
        Err(e)      => { eprint!("{}", ember::error::render(&e, &map, SourceId(0)));
                         ExitCode::FAILURE }
    }
}
}

Note the shape: three fallible stages chained with and_then, one error type, one renderer. That is the payoff for the decision in Spans and Source Maps to share EmberError across layers. Adding the compiler and VM in Section 3 adds two links to this chain and changes nothing else.

The Trace

The full Milestone 1 pipeline, on one expression. Run every command.

$ echo '10 + 20 * 3' > /tmp/t.ember

Characters

byte:  0 1 2 3 4 5 6 7 8 9 10
       1 0 ␣ + ␣ 2 0 ␣ * ␣ 3

Tokens — ember tokens /tmp/t.ember

   #  span     kind        text
   0  0..2     Int(10)     "10"
   1  3..4     Plus        "+"
   2  5..7     Int(20)     "20"
   3  8..9     Star        "*"
   4  10..11   Int(3)      "3"
   5  11..11   Eof         ""

AST — ember ast /tmp/t.ember

Binary(Add)              @0..11
    Int(10)              @0..2
    Binary(Mul)          @5..11
        Int(20)          @5..7
        Int(3)           @10..11

Evaluation order — post-order, left to right. Number each node by when it produces a value:

              Binary(Add) ⑤ → Integer(70)
             /            \
   Int(10) ① → 10      Binary(Mul) ④ → Integer(60)
                        /          \
              Int(20) ② → 20   Int(3) ③ → 3

Read the numbers: the tree is walked top-down but evaluated bottom-up. The root is the last thing to produce a value and the first thing entered. That inversion is what "post-order" means and it is the reason the compiler in Section 3 emits operand instructions before operator instructions.

Value — ember run /tmp/t.ember

Now do it for the other grouping, and confirm the tree shape is the only thing that changed:

$ ember ast -e '(10 + 20) * 3'   # Mul at the root, Add on the left
$ ember run -e '(10 + 20) * 3'
90

Same tokens (plus two parens), different tree, different answer. Precedence became shape, and shape became order. Write that sentence in docs/learning/04-interpreter.md in your own words.

Expected Output

$ ember run -e 'return 10 + 20 * 3'
70
$ ember run -e 'return 2 ^ 2'
4.0
$ ember run -e 'return 4 / 2'
2.0
$ ember run -e 'return 7 // 2'
3
$ ember run -e 'return -7 % 3'
2
$ ember run -e 'return 1 // 0'
<argv>:1:8: error: attempt to perform 'n//0'

   1 │ return 1 // 0
     │        ^^^^^^

Debugging Steps

`2 ^ 2` prints `4` instead of `4.0`

Either Pow is not forcing a float, or your Display is not distinguishing them. Check both; math.type has no equivalent yet, so print is your only window.

`-7 % 3` gives `-1`

You used Rust's %. It truncates toward zero; Lua floors. See the warning in Step 3.

`7 % -3` gives `1`

You used rem_euclid, which is always non-negative. Lua's result takes the divisor's sign.

`-7 // 2` gives `-3`

Rust's integer / truncates; you need floor. div_euclid is also not quite it — check 7.div_euclid(-2) against lua -e 'print(7 // -2)'.

Deeply nested arithmetic overflows the stack

Your parse depth guard is missing or too high. eval_expr inherits its bound from the parser; if the parser allows 100,000 deep, so does the evaluator.

Float formatting differs from Lua in the last digit

Lua uses %.14g. Rust's {} for f64 prints the shortest round-tripping representation, which is better and different. Pick one, write it in appendix/lua-differences.md, and make the golden tests match your choice — not Lua's — from here on.

Experiment

CLAIM. Evaluation order is unobservable in Section 1 and becomes observable the moment there are side effects — so a decision made now, with no way to test it, is locked in by Lab 7.

METHOD. You have no function calls yet, so simulate one: add a temporary Expr::Trace(&str) node that prints its label and returns 1. Evaluate Trace("L") + Trace("R"). Then swap the two let bindings in the Binary arm and evaluate again.

PREDICTION. Before running: does the result change? Does the output change? Which of those two would a test written today catch?

RESULT. Record it. This is the smallest possible demonstration of why untested decisions are still decisions, and it is the argument for writing docs/architecture.md as you go rather than at the end.

Test

#![allow(unused)]
fn main() {
fn eval(src: &str) -> Value {
    let toks = tokenize(src).unwrap();
    let ast = Parser::new(toks).parse_chunk().unwrap();
    Interp::new().run(&ast).unwrap().unwrap()
}

#[test]
fn milestone_1() {
    assert_eq!(eval("return 10 + 20 * 3"),   Value::Integer(70));
    assert_eq!(eval("return (10 + 20) * 3"), Value::Integer(90));
}

#[test]
fn numeric_subtypes_follow_lua_5_4() {
    // Every row verified with: lua -e 'print(EXPR, math.type(EXPR))'
    // Lua 5.4 §3.4.1: / and ^ always produce floats; + - * // % preserve integers.
    assert_eq!(eval("return 4 / 2"),   Value::Float(2.0));    // NOT Integer(2)
    assert_eq!(eval("return 2 ^ 2"),   Value::Float(4.0));    // NOT Integer(4)
    assert_eq!(eval("return 7 // 2"),  Value::Integer(3));
    assert_eq!(eval("return 7 // 2.0"), Value::Float(3.0));
    assert_eq!(eval("return 3 + 0.0"), Value::Float(3.0));
}

#[test]
fn floor_division_and_modulo_signs() {
    // Lua 5.4 §3.4.1: a % b == a - math.floor(a/b)*b, so the result has the
    // sign of the DIVISOR. Rust's % and rem_euclid both disagree; that is the bug
    // this test exists to catch.
    let cases = [("7 // 2", 3i64), ("-7 // 2", -4), ("7 // -2", -4), ("-7 // -2", 3),
                 ("7 % 3", 1),     ("-7 % 3", 2),   ("7 % -3", -2), ("-7 % -3", -1)];
    for (src, want) in cases {
        assert_eq!(eval(&format!("return {src}")), Value::Integer(want),
                   "{src} must follow Lua's floor semantics");
    }
}

#[test]
fn integer_arithmetic_wraps_and_does_not_panic() {
    // Lua 5.4: integer arithmetic wraps. Rust's debug build PANICS on overflow,
    // which would abort a host process — hence wrapping_* everywhere.
    assert_eq!(eval("return 9223372036854775807 + 1"), Value::Integer(i64::MIN));
    assert_eq!(eval("return -9223372036854775807 - 2"), Value::Integer(i64::MAX));
}

#[test]
fn division_by_zero() {
    assert!(matches!(try_eval("return 1 // 0"), Err(e) if e.kind == ErrorKind::Runtime));
    assert!(matches!(try_eval("return 1 % 0"),  Err(e) if e.kind == ErrorKind::Runtime));
    assert_eq!(eval("return 1 / 0"), Value::Float(f64::INFINITY));   // float div is FINE
}
}

cargo test --lib interp
./scripts/compare-arith.sh          # must be all `ok` except documented divergences

Challenge Extensions

Constant folding. Fold Binary(op, Int, Int) into a literal in a post-parse pass. Compare ember ast before and after. Then find the case where naive folding is wrong — hint: 1//0 — and decide whether folding may raise an error at compile time. (Lua folds, and refuses to fold anything that would raise.)
A tiny REPL. Twenty lines: read a line, tokenize, parse, evaluate, print. It will be replaced properly in Lab 25, but having one now makes every later lab faster to explore.
%.14g exactly. Implement Lua's float formatting precisely, including the .0 suffix rule and how it prints 1e16. Test against lua on 50 random floats. This is more annoying than it sounds and it removes a class of golden-test churn.
NaN and infinity. Run lua -e 'print(0/0)' on two different machines or platforms if you can. Note the spelling. Then decide what Ember prints, and write down why a deterministic runtime cannot inherit the platform's answer.
Overflow behavior as a policy. Add an Engine option (looking ahead to §5) selecting wrapping, saturating, or erroring integer arithmetic. Which would a policy engine want? Write the ADR; do not implement it yet.

Deliverables

ember run evaluates 10 + 20 * 3 to 70 and (10 + 20) * 3 to 90.
All eight floor-division/modulo sign cases pass, matching lua.
/ and ^ always produce floats; + - * // % preserve integers; each tested.
Integer overflow wraps and does not panic in a debug build.
1 // 0 and 1 % 0 are runtime errors with spans; 1 / 0 is infinity.
scripts/compare-arith.sh exists, runs clean, and is committed.
Every divergence from Lua found in Step 4 is written in appendix/lua-differences.md with a one-line rationale.
docs/learning/04-interpreter.md written, including the evaluation-order experiment.
docs/architecture.md states Ember's operand evaluation order.

Validation / Self-check

Number the nodes of 10 + 20 * 3 in evaluation order and explain why the root is last.
Which operators always produce floats, which preserve integers, and where is that written down?
State Lua's modulo rule as a formula and show why Rust's % and rem_euclid both fail it.
Why is wrapping_add used rather than +? What would + do in a debug build, and why is that unacceptable for an embedded runtime?
1 // 0 errors but 1 / 0 does not. Why is that consistent rather than arbitrary?
Three hazards are currently prevented by a single guard in the parser. Name them, and name the lab where that chain breaks.
Where is Ember's operand evaluation order decided, and how would you make it observable today?
You find that ember and lua disagree on an expression. Give the two-step procedure for deciding whether it is a bug or a divergence.

Next: Lab 4 — Values and Type Errors.

Open-Source Engineer & Contributor