Milestone M2

Environments and Binding

Part III gave the evaluator names. The environment supplies each name’s value, let binds one over the rest of a block, lexical scope fixes how far a binding reaches, and the representation makes a lookup through nested scopes work. This milestone puts them into the evaluator: two arms of eval_expr that read a variable and evaluate a block, and the run of the language grows from single expressions to programs that name their intermediate values.

The codebase, the toolchain, and the build loop are the ones Milestone M1 set up; this milestone adds two arms to the same eval_expr. If you have not built the starter yet, do that first — M1 is required to be completed and correct before this milestone can be completed.

To-dos

grep -rn 'todo_m2!' src lists exactly what this milestone asks for — the two arms left as holes after M1:

// src/interp/eval.rs — the two M2 arms of eval_expr
Expr::Var(..)   => todo_m2!("E-Var"),
Expr::Block(..) => todo_m2!("E-Block / E-Let / E-Seq"),

These are the first arms that consult the env parameter. Through M1 it was carried unused, kept quiet by a let _ = env; at the top of eval_expr; delete that line once an arm reads from env, or the lint will point out that it is now redundant.

Milestone specification

Below each row gives the form, semantic rule, and the value (or error) each new construct this milestone adds:

Form	Rule	Evaluates to
`x`	`E-Var`	the value the environment binds to `x`; stuck if none
`let x = e;` (block item)	`E-Let`	binds `x` over the rest of the block
`e;` (block item)	`E-Seq`	runs `e` and discards its value
`{ … e }` (trailing)	`E-Block`	the value of the trailing expression
`{ }` (empty, or ends in `;`)	`E-Empty`	`()`

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

Two contracts hold across the block. The environment is read-only: a let never rewrites an existing binding — it adds one that shadows the old, so the nearest binding of a name wins — and extend produces a child scope while leaving its parent untouched. That is why a binding reaches exactly the rest of its block and no further: the scope a block grows is discarded when the block ends, and the caller’s environment is the one it started with. And a block aborts at a stuck item: if an item gets stuck, the ? carries the error straight out with that item’s span, and the items after it never run.

Implementing Milestone M2

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

Variant	Fields	Covers
`Expr::Var`	`(Name, Span)`	a variable reference
`Expr::Block`	`(Vec<Stmt>, Option<Box<Expr>>, Span)`	items, then an optional tail

A block’s items are Stmt values, of two kinds:

enum Stmt {
    Let(Name, Option<Ty>, Expr, Span),   // a binding; the Option<Ty>
    Expr(Expr),                          // is an annotation, ignored here
}

The Option<Ty> on a Let is an optional type annotation; the evaluator ignores it — it is read by the type checker we implement in Part VI.

Two tools do the work of both arms:

Look a name up with env.lookup(name), which returns Some(v) when the name is in scope and None when it is not. A miss is the stuck case: return RuntimeError::UnboundVariable { name, span }, carrying the offending variable’s own span.
Extend a scope with env.extend(name, value), which returns a new environment with one more binding and leaves the one it was called on unchanged.

A block threads that second tool through its items. Start from env, and walk the items in order: a Stmt::Let evaluates its right-hand side in the current scope and then extends the scope with the new binding for the items that follow; a Stmt::Expr evaluates its expression in the current scope and drops the value. The trailing expression, if there is one, is evaluated in the scope the items built and is the block’s value; a block with no trailing expression is Value::Unit. Because extend returns a child rather than mutating in place, the growing scope is local to the block — nothing you do to it reaches the environment the block was entered with.

E-Var you have already seen worked in the Environments chapter’s build section; the block arm is the same environment threading that chapter describes, carried out one item at a time.

Worked examples

An expression, the environment it needs, and the value it evaluates to:

x            (x bound to 5)          ⇓ 5
{ let x = 2; x + 3 }                 ⇓ 5
{ let x = 1; let x = x + 1; x }      ⇓ 2      (shadowing)
{ 1; 2; 3 }                          ⇓ 3      (the trailing expression)
{ let x = 5; }                       ⇓ ()     (ends in a binding)
{ }                                  ⇓ ()

And expressions with no value, which halt the run:

y            (y unbound)             ⇓ stuck  (UnboundVariable)
{ { let x = 1; x }; x }              ⇓ stuck  (x's scope ended at the inner })
{ z; 1 }                             ⇓ stuck  (z unbound; the block aborts at z)

How to know it works

cargo m2 runs the provided milestone M2 tests, and — because the milestones are cumulative — the M1 tests along with them, so a change that breaks the expression fragment shows up here too. Each test builds an Expr and checks the Value it evaluates to, or, for a stuck test, the error’s variant and the span it blames. The builders var, block, let_, and expr_stmt join the M1 ones, and env_with and eval_in evaluate an expression under a starting environment, so a check reads close to the rule it exercises:

// { let x = 2; x + 3 }  ⇓  5
let b = block(vec![let_("x", int(2, 1), 0)],
              Some(binary(Add, var("x", 2), int(3, 3), 4)), 5);
assert_eq!(value_of(&b), Value::Int(5));

// x, with x bound to 5, reads its binding
let env = env_with(&[("x", Value::Int(5))]);
assert_eq!(eval_in(&var("x", 0), &env).unwrap(), Value::Int(5));

// y is unbound: UnboundVariable at its span
assert!(matches!(stuck(&var("y", 3)),
    RuntimeError::UnboundVariable { .. }));

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

Design problems

The evaluator takes an environment in but never hands one back, while Part IV's store will be threaded both in and out. Given the Rc-chained representation, why does discarding a block's bindings when it ends cost nothing?

Evaluating an expression cannot change what a name is bound to, so the environment is an input the evaluator reads and never an output it revises — extend builds a child scope for the code under a binding and returns it downward, and nothing propagates a new environment back up. In the representation, a scope is a small node that holds its own bindings and an Rc pointer to its parent, and extend allocates one such node in front of the current chain. When a block ends, evaluation simply stops using the child node and goes on with the parent chain it already held; there is no unwinding to do and nothing to copy back, because the parent was never altered. Discarding the block’s bindings is just dropping a reference to the front of the chain. The store is threaded out precisely because it is changed by evaluation, and that is the distinction Part IV turns on.

A block let x = e_1; rest computes the same value as applying λx. rest to e_1. Since the two agree, why does the milestone still implement a block arm rather than desugaring let to a function call?

The equivalence, which is Landin’s, holds because both evaluate e_1, bind the result to x, and evaluate the body in the extended environment — the block arm’s extend is exactly the environment step a function call will make when Part V arrives. Bridger keeps let a form of its own because binding is available from the first block a program writes, before functions exist, so the evaluator needs a rule for it that does not depend on a feature two parts away; desugaring let to a call would make the whole binding mechanism wait on closures. It costs one arm now and buys blocks that stand on their own. The equivalence pays off: when the closure rule lands, it extends the environment as this arm does, so there is one binding mechanism, reached by two forms.

Using only the variables and blocks of this milestone — no mutation — can you write a program whose result depends on the order in which two bindings are evaluated? If not, what would you need?

You cannot. A let’s right-hand side is evaluated in the environment before the binding is added, and the environment is read-only, so evaluating one binding cannot change what a later binding sees except by putting a value in scope under a name — and a name, once bound, denotes that one value wherever it is read. Two bindings that do not mention each other are independent, and one that mentions the other reads a fixed value, not a value the second could have altered. Order becomes observable only once a step can change something a later step reads — a cell whose contents one binding writes and another reads — which is the mutation of Part IV. Until then the language is order-insensitive in this sense, which is exactly what a read-only environment buys and what the threaded store gives up.

Bridger allows a block to bind a name that is already in scope, shadowing the earlier binding; some languages reject a second binding of the same name in one scope. What does each choice make easy, and what does each rule out?

Allowing shadowing lets a block reuse one name across a series of related values — let x = read(); let x = trim(x); let x = parse(x) — without inventing x1, x2, x3, and each let may define the name in terms of the value it held before, since the right-hand side is evaluated before the new binding is added. What it gives up is a check: a name accidentally reused, where a fresh one was meant, is silently accepted rather than flagged. A language that rejects the second binding turns that accident into a compile error, at the cost of the deliberate reuse, which must then be spelled with a new name or an explicit mutation. The trade is a convenience against a class of caught mistake; Bridger takes the convenience, and its scope rules make the shadow’s reach exactly the rest of the block, so an inner shadow is gone once the block ends.

Keyboard shortcuts