Variables and scopes
Last step’s evaluator computes every expression in the grammar, but the
four arms that mention names all refuse to run — and x; failing with
undefined variable \x`was the honest outcome, because there was nowhere forxto be *defined*. This step gives the interpreter a memory. AnEnvironmentholds the names a program has made and the values they carry, and the two walking functions carry it with them as they go. By the end,vardeclares,=assigns, blocks shadow, and awhile` loop finally has something to change.
Where the reader starts
Section titled “Where the reader starts”The previous step is published and tagged, so start from its end state:
git checkout interpreter-ch05cargo run -qStill one file, src/main.rs. The scanner and the parser are untouched;
nothing above the evaluator moves. The changes are: both walking
functions gain a second parameter, the blocked name arms become real
ones, a new environment section sits between RuntimeError and the
evaluator, and main runs a new set of programs. At the end, the same
command at the interpreter-ch06 tag runs variables, loops and scoped
blocks.
The chain
Section titled “The chain”The textbook picture is a linked chain of maps: the current scope points
at the scope that encloses it, and looking up a name walks outward until
somebody answers. In Rust the same chain is a stack — a Vec of maps,
innermost last:
struct Environment { scopes: Vec<HashMap<String, Value>>,}A parent-pointer chain is the classic shape, and a Rust version with
Option<Box<Environment>> exists — but entering a block means moving
the whole chain in and out of the tree, and the borrow checker makes
that dance noisy. A stack is the same chain laid out in memory. Push a
scope on block entry, pop it on exit, and “walking the chain” is
iterating the Vec backwards. The three moves the language needs:
impl Environment { fn new() -> Self { Environment { scopes: vec![HashMap::new()], } }
// `var`: a name appears in the innermost scope, shadowing anything // of the same name further out fn define(&mut self, name: String, value: Value) { self.scopes.last_mut().unwrap().insert(name, value); }
// reading walks the chain from the top down and returns the first // match; a missing name is the caller's error to report fn get(&self, name: &str) -> Option<Value> { for scope in self.scopes.iter().rev() { if let Some(value) = scope.get(name) { return Some(value.clone()); } } None }
// assignment also walks the chain, but it can only *update* a scope // that already has the name — `count = 1` inside a block writes to // the outer binding, or fails if no scope down the chain has it fn assign(&mut self, name: &str, value: Value) -> bool { for scope in self.scopes.iter_mut().rev() { if scope.contains_key(name) { scope.insert(name.to_string(), value); return true; } } false }}Shadowing falls out of the iteration order — no code anywhere says the
word “shadow”. get returns the first match walking outwards, so an
inner var x simply hides the outer one until its scope dies. And
assign is deliberately narrower than define: assignment never
creates a binding, it can only update one some scope already has. That
one rule is the difference between
var count = 0;and
count = 0;— the second is a runtime error unless a count exists somewhere down
the chain, which is the guard that catches a misspelled name instead of
silently inventing a second variable.
Plugging the arms
Section titled “Plugging the arms”evaluate and execute now both take the environment as their second
parameter — &mut Environment, because assignment and var write to
it — and every recursive call passes it down, including the arms that
do not need it. Last step’s blocked arms become real ones:
Expr::Variable(name) => env.get(name).ok_or(RuntimeError { message: format!("undefined variable `{name}`"), }), Expr::Assign { name, value } => { // assignment is an expression: its value is the value // assigned, which is what makes `a = b = 2` parse and work // with no extra machinery — the parser already made `=` // right-associative, and the value just falls through let value = evaluate(value, env)?; if env.assign(name, value.clone()) { Ok(value) } else { Err(RuntimeError { message: format!("undefined variable `{name}`"), }) } }Assign returning a value is not an extra feature the evaluator grew —
it is a consequence of the grammar. The parser made = an expression
two steps ago (right-associative, binding loosest), so a = b = 2 is
already a tree whose node produces the assigned value. The evaluator
just declines to throw it away.
Declarations are the mirror image:
Stmt::Var { name, init } => { // the initializer evaluates first, in the scope the name // is about to live in — so `var x = x;` reads the outer // `x`, the way most dynamic languages do let value = evaluate(init, env)?; env.define(name.clone(), value); Ok(()) }One statement left changes the shape of the environment rather than its contents:
// A block is a scope: push a fresh map, run the body, pop it — even when// a statement in the middle fails, so the caller's environment comes// back exactly the way it went in.fn execute_scoped(statements: &[Stmt], env: &mut Environment) -> Result<(), RuntimeError> { env.scopes.push(HashMap::new()); let result = statements.iter().try_for_each(|s| execute(s, env)); env.scopes.pop(); result}That is why the pop happens before the result is returned: a runtime
error in the middle of a block unwinds the scope anyway, and the
caller’s environment comes back exactly the way it went in. if and
while need nothing of the sort — their bodies are ordinary statements
(usually blocks, which scope themselves), so their arms only gained the
extra argument.
Call stays blocked. The callee and its arguments still evaluate, in
the order a real call would use, and then the arm reports a number cannot be called — still true, because nothing in the language is
callable yet. That is the next step’s machinery, and it is the only
variant the environment did not unlock.
A loop that changes
Section titled “A loop that changes”Last step’s awkward admission: every while loop either ran zero times
or never ended, because nothing could change between iterations. Now:
var total = 0;var i = 1;while (i <= 5) { total = total + i; i = i + 1;}total;The transcript doubles as a trace. Each assignment statement prints its
value — assignment is an expression, remember — so every iteration
leaves two lines: the new total, then the new i. 1, 2, 3, 3, 6, 4, 10, 5, 15, 6, then the loop stops with i at 6, and the final
total; prints 15.
The same read explains the block demo:
var count = 0;{ count = count + 1; count = count + 1;}prints 1 and 2 — both writes reached the outer binding, because the
block contains no var count and assign keeps walking. Contrast it
with the shadowing demo in the output below, where var x = "inner"
creates a binding the block does own, and the outer x is exactly
where it was when the block ends.
The whole file
Section titled “The whole file”This is the complete src/main.rs for this step. The scanner and the
parser are unchanged from last step; the environment section, the new
signatures and the unblocked arms are new:
//! birch, step 6: variables and scopes.//!//! A tree-walking evaluator with an environment: `evaluate` turns an//! `Expr` into a `Value`, `execute` walks statements, and both carry a//! `&mut Environment` — a stack of scopes that gives the language//! somewhere to put things. `var`, assignment, name lookup and block//! scoping all work now; functions are one step away.
use std::collections::HashMap;
#[derive(Debug, Clone, PartialEq)]enum TokenKind { // keywords Var, Fun, If, Else, While, Return, True, False, Nil, And, Or, // literals Ident, Number, Str, // punctuation LeftParen, RightParen, LeftBrace, RightBrace, LeftBracket, RightBracket, Comma, Semicolon, // operators Assign, Bang, BangEqual, EqualEqual, Greater, GreaterEqual, Less, LessEqual, Plus, Minus, Star, Slash, Percent, // end of input Eof,}
#[derive(Clone)]struct Token { kind: TokenKind, lexeme: String, line: usize, col: usize,}
struct ScanError { line: usize, col: usize, message: String,}
struct Scanner { chars: Vec<char>, start: usize, // first char of the token being scanned current: usize, line: usize, col: usize, tokens: Vec<Token>, errors: Vec<ScanError>,}
impl Scanner { fn new(source: &str) -> Self { Scanner { chars: source.chars().collect(), start: 0, current: 0, line: 1, col: 1, tokens: Vec::new(), errors: Vec::new(), } }
fn scan_tokens(mut self) -> (Vec<Token>, Vec<ScanError>) { while !self.at_end() { self.start = self.current; self.scan_token(); } self.tokens.push(Token { kind: TokenKind::Eof, lexeme: String::new(), line: self.line, col: self.col, }); (self.tokens, self.errors) }
fn scan_token(&mut self) { let line = self.line; let col = self.col; let c = self.advance(); match c { '(' => self.add(TokenKind::LeftParen, line, col), ')' => self.add(TokenKind::RightParen, line, col), '{' => self.add(TokenKind::LeftBrace, line, col), '}' => self.add(TokenKind::RightBrace, line, col), '[' => self.add(TokenKind::LeftBracket, line, col), ']' => self.add(TokenKind::RightBracket, line, col), ',' => self.add(TokenKind::Comma, line, col), ';' => self.add(TokenKind::Semicolon, line, col), '+' => self.add(TokenKind::Plus, line, col), '-' => self.add(TokenKind::Minus, line, col), '*' => self.add(TokenKind::Star, line, col), '%' => self.add(TokenKind::Percent, line, col), '/' => { if self.match_next('/') { // a comment runs to the end of the line while self.peek() != Some('\n') && self.peek().is_some() { self.advance(); } } else { self.add(TokenKind::Slash, line, col); } } '=' => { let kind = if self.match_next('=') { TokenKind::EqualEqual } else { TokenKind::Assign }; self.add(kind, line, col); } '!' => { let kind = if self.match_next('=') { TokenKind::BangEqual } else { TokenKind::Bang }; self.add(kind, line, col); } '<' => { let kind = if self.match_next('=') { TokenKind::LessEqual } else { TokenKind::Less }; self.add(kind, line, col); } '>' => { let kind = if self.match_next('=') { TokenKind::GreaterEqual } else { TokenKind::Greater }; self.add(kind, line, col); } '"' => self.string(line, col), c if c.is_ascii_digit() => self.number(line, col), c if c.is_ascii_alphabetic() || c == '_' => self.identifier(line, col), c if c.is_whitespace() => { if c == '\n' { self.line += 1; self.col = 1; } } other => self.errors.push(ScanError { line, col, message: format!("unexpected character `{other}`"), }), } }
fn string(&mut self, line: usize, col: usize) { loop { match self.peek() { Some('"') => { self.advance(); self.add(TokenKind::Str, line, col); return; } Some('\n') | None => { self.errors.push(ScanError { line, col, message: String::from("unterminated string"), }); return; } Some(_) => { self.advance(); } } } }
fn number(&mut self, line: usize, col: usize) { while self.peek().is_some_and(|c| c.is_ascii_digit()) { self.advance(); } // a fraction, but only when the dot is followed by a digit: // `1.5` is one number, `1..3` is `1`, `.`, `.3` if self.peek() == Some('.') && self.peek2().is_some_and(|c| c.is_ascii_digit()) { self.advance(); // the dot while self.peek().is_some_and(|c| c.is_ascii_digit()) { self.advance(); } } self.add(TokenKind::Number, line, col); }
fn identifier(&mut self, line: usize, col: usize) { while self .peek() .is_some_and(|c| c.is_ascii_alphanumeric() || c == '_') { self.advance(); } let word: String = self.chars[self.start..self.current].iter().collect(); self.add(keyword(&word), line, col); }
// -- cursor helpers -------------------------------------------------
fn at_end(&self) -> bool { self.current >= self.chars.len() }
fn advance(&mut self) -> char { let c = self.chars[self.current]; self.current += 1; self.col += 1; c }
fn peek(&self) -> Option<char> { self.chars.get(self.current).copied() }
fn peek2(&self) -> Option<char> { self.chars.get(self.current + 1).copied() }
fn match_next(&mut self, expected: char) -> bool { if self.peek() == Some(expected) { self.advance(); true } else { false } }
fn add(&mut self, kind: TokenKind, line: usize, col: usize) { let lexeme: String = self.chars[self.start..self.current].iter().collect(); self.tokens.push(Token { kind, lexeme, line, col, }); }}
fn keyword(word: &str) -> TokenKind { match word { "var" => TokenKind::Var, "fun" => TokenKind::Fun, "if" => TokenKind::If, "else" => TokenKind::Else, "while" => TokenKind::While, "return" => TokenKind::Return, "true" => TokenKind::True, "false" => TokenKind::False, "nil" => TokenKind::Nil, "and" => TokenKind::And, "or" => TokenKind::Or, _ => TokenKind::Ident, }}
// ------------------------------------------------------------- the tree
// One variant per shape an expression can take. Every field that would// make the enum infinitely sized holds a `Box`; fields already behind a// `Vec` or an `Option` break the recursion for free.#[derive(Debug)]enum Expr { Number(f64), Str(String), Bool(bool), Nil, Variable(String), Unary { op: TokenKind, operand: Box<Expr> }, Binary { op: TokenKind, left: Box<Expr>, right: Box<Expr> }, Logical { op: TokenKind, left: Box<Expr>, right: Box<Expr> }, Assign { name: String, value: Box<Expr> }, Call { callee: Box<Expr>, args: Vec<Expr> }, Index { object: Box<Expr>, index: Box<Expr> }, List(Vec<Expr>),}
// One variant per shape a statement can take. `if` and `while` hold a// single statement each, so the statement type recurses through `Box`// too; a block's `Vec<Stmt>` needs no box of its own.#[derive(Debug)]enum Stmt { Var { name: String, init: Expr }, Fun { name: String, params: Vec<String>, body: Vec<Stmt> }, Expression(Expr), If { condition: Expr, then_branch: Box<Stmt>, else_branch: Option<Box<Stmt>> }, While { condition: Expr, body: Box<Stmt> }, Return { value: Option<Expr> }, Block(Vec<Stmt>),}
// ------------------------------------------------------------ the parser
struct ParseError { line: usize, col: usize, message: String,}
struct Parser { tokens: Vec<Token>, pos: usize,}
// binds tighter than every infix operator, so `-n * 2` groups as `(-n) * 2`const UNARY: u8 = 9;
impl Parser { fn new(tokens: Vec<Token>) -> Self { Parser { tokens, pos: 0 } }
// program → declaration* EOF fn program(&mut self) -> Result<Vec<Stmt>, ParseError> { let mut declarations = Vec::new(); while self.peek().kind != TokenKind::Eof { declarations.push(self.declaration()?); } Ok(declarations) }
// declaration → varDecl | funDecl | statement fn declaration(&mut self) -> Result<Stmt, ParseError> { match self.peek().kind { TokenKind::Var => self.var_declaration(), TokenKind::Fun => self.fun_declaration(), _ => self.statement(), } }
// varDecl → "var" IDENT "=" expression ";" fn var_declaration(&mut self) -> Result<Stmt, ParseError> { self.advance(); // the `var` let name = self.expect_ident("a variable name")?; self.expect(TokenKind::Assign, "`=`")?; let init = self.expression(0)?; self.expect(TokenKind::Semicolon, "`;`")?; Ok(Stmt::Var { name, init }) }
// funDecl → "fun" IDENT "(" parameters? ")" block fn fun_declaration(&mut self) -> Result<Stmt, ParseError> { self.advance(); // the `fun` let name = self.expect_ident("a function name")?; self.expect(TokenKind::LeftParen, "`(`")?; let mut params = Vec::new(); if self.peek().kind != TokenKind::RightParen { loop { params.push(self.expect_ident("a parameter name")?); if !self.match_kind(TokenKind::Comma) { break; } } } self.expect(TokenKind::RightParen, "`)`")?; let body = self.block()?; Ok(Stmt::Fun { name, params, body }) }
// statement → exprStmt | ifStmt | whileStmt | returnStmt | block fn statement(&mut self) -> Result<Stmt, ParseError> { match self.peek().kind { TokenKind::If => self.if_statement(), TokenKind::While => self.while_statement(), TokenKind::Return => self.return_statement(), TokenKind::LeftBrace => Ok(Stmt::Block(self.block()?)), _ => { let expr = self.expression(0)?; self.expect(TokenKind::Semicolon, "`;`")?; Ok(Stmt::Expression(expr)) } } }
// ifStmt → "if" "(" expression ")" statement ("else" statement)? fn if_statement(&mut self) -> Result<Stmt, ParseError> { self.advance(); // the `if` self.expect(TokenKind::LeftParen, "`(`")?; let condition = self.expression(0)?; self.expect(TokenKind::RightParen, "`)`")?; let then_branch = Box::new(self.statement()?); let else_branch = if self.match_kind(TokenKind::Else) { Some(Box::new(self.statement()?)) } else { None }; Ok(Stmt::If { condition, then_branch, else_branch }) }
// whileStmt → "while" "(" expression ")" statement fn while_statement(&mut self) -> Result<Stmt, ParseError> { self.advance(); // the `while` self.expect(TokenKind::LeftParen, "`(`")?; let condition = self.expression(0)?; self.expect(TokenKind::RightParen, "`)`")?; let body = Box::new(self.statement()?); Ok(Stmt::While { condition, body }) }
// returnStmt → "return" expression? ";" fn return_statement(&mut self) -> Result<Stmt, ParseError> { self.advance(); // the `return` let value = if self.peek().kind == TokenKind::Semicolon { None } else { Some(self.expression(0)?) }; self.expect(TokenKind::Semicolon, "`;`")?; Ok(Stmt::Return { value }) }
// block → "{" declaration* "}" fn block(&mut self) -> Result<Vec<Stmt>, ParseError> { self.expect(TokenKind::LeftBrace, "`{`")?; let mut body = Vec::new(); while self.peek().kind != TokenKind::RightBrace && self.peek().kind != TokenKind::Eof { body.push(self.declaration()?); } self.expect(TokenKind::RightBrace, "`}`")?; Ok(body) }
// The Pratt loop from two steps ago, building nodes. fn expression(&mut self, min_prec: u8) -> Result<Expr, ParseError> { let mut lhs = self.prefix()?; loop { // calls and indexes bind tighter than anything in the table: // they hug whatever is on their left, whatever the minimum match self.peek().kind { TokenKind::LeftParen => { self.pos += 1; let mut args = Vec::new(); if self.peek().kind != TokenKind::RightParen { loop { args.push(self.expression(0)?); if !self.match_kind(TokenKind::Comma) { break; } } } self.expect(TokenKind::RightParen, "`)`")?; lhs = Expr::Call { callee: Box::new(lhs), args }; continue; } TokenKind::LeftBracket => { self.pos += 1; let index = self.expression(0)?; self.expect(TokenKind::RightBracket, "`]`")?; lhs = Expr::Index { object: Box::new(lhs), index: Box::new(index) }; continue; } _ => {} } let Some((left, right)) = self.infix_binding_power() else { break; }; if left < min_prec { break; } let op = self.advance(); if op.kind == TokenKind::Assign { // the check that needed a bool threaded through every // level two steps ago is now a question about the node let Expr::Variable(name) = lhs else { return Err(ParseError { line: op.line, col: op.col, message: String::from("invalid assignment target"), }); }; let value = self.expression(right)?; lhs = Expr::Assign { name, value: Box::new(value) }; continue; } let rhs = self.expression(right)?; lhs = if op.kind == TokenKind::And || op.kind == TokenKind::Or { // a separate variant: `and`/`or` short-circuit, and the // tree records that Expr::Logical { op: op.kind, left: Box::new(lhs), right: Box::new(rhs) } } else { Expr::Binary { op: op.kind, left: Box::new(lhs), right: Box::new(rhs) } }; } Ok(lhs) }
// Infix binding powers, lowest row first. A pair is (left, right): // parsing the right side with `right` as its minimum is what makes // associativity work. `left + 1` stops the right side before another // operator of the same row — left-associative. `=` is the one // right-associative operator, so its right power sits below its left. fn infix_binding_power(&self) -> Option<(u8, u8)> { Some(match self.peek().kind { TokenKind::Assign => (1, 0), TokenKind::Or => (2, 3), TokenKind::And => (3, 4), TokenKind::EqualEqual | TokenKind::BangEqual => (4, 5), TokenKind::Less | TokenKind::LessEqual | TokenKind::Greater | TokenKind::GreaterEqual => (5, 6), TokenKind::Plus | TokenKind::Minus => (6, 7), TokenKind::Star | TokenKind::Slash | TokenKind::Percent => (7, 8), _ => return None, }) }
fn prefix(&mut self) -> Result<Expr, ParseError> { let token = self.advance(); match token.kind { TokenKind::Number => { // the scanner only ever hands over digit strings, so // this parse cannot fail let value: f64 = token.lexeme.parse().unwrap(); Ok(Expr::Number(value)) } TokenKind::Str => { // strip the two quote characters the scanner kept Ok(Expr::Str(token.lexeme[1..token.lexeme.len() - 1].to_string())) } TokenKind::True => Ok(Expr::Bool(true)), TokenKind::False => Ok(Expr::Bool(false)), TokenKind::Nil => Ok(Expr::Nil), TokenKind::Ident => Ok(Expr::Variable(token.lexeme)), TokenKind::Minus | TokenKind::Bang => { let operand = self.expression(UNARY)?; Ok(Expr::Unary { op: token.kind, operand: Box::new(operand) }) } TokenKind::LeftParen => { // no Grouping variant: the tree's shape *is* the grouping, // the parentheses have done their job once the inner // expression is built let inner = self.expression(0)?; self.expect(TokenKind::RightParen, "`)`")?; Ok(inner) } TokenKind::LeftBracket => { let mut items = Vec::new(); if self.peek().kind != TokenKind::RightBracket { loop { items.push(self.expression(0)?); if !self.match_kind(TokenKind::Comma) { break; } } } self.expect(TokenKind::RightBracket, "`]`")?; Ok(Expr::List(items)) } _ => Err(ParseError { line: token.line, col: token.col, message: if token.kind == TokenKind::Eof { String::from("expected an expression, found the end of input") } else { format!("expected an expression, found `{}`", token.lexeme) }, }), } }
fn peek(&self) -> &Token { &self.tokens[self.pos] }
fn advance(&mut self) -> Token { let token = self.tokens[self.pos].clone(); if token.kind != TokenKind::Eof { self.pos += 1; } token }
fn match_kind(&mut self, kind: TokenKind) -> bool { if self.peek().kind == kind { self.pos += 1; true } else { false } }
fn expect(&mut self, kind: TokenKind, what: &str) -> Result<Token, ParseError> { let token = self.advance(); if token.kind == kind { return Ok(token); } let message = if token.kind == TokenKind::Eof { format!("expected {what}, found the end of input") } else { format!("expected {what}, found `{}`", token.lexeme) }; Err(ParseError { line: token.line, col: token.col, message, }) }
fn expect_ident(&mut self, what: &str) -> Result<String, ParseError> { let token = self.expect(TokenKind::Ident, what)?; Ok(token.lexeme) }}
// ------------------------------------------------------------ the values
// What an expression evaluates *to*. The tree describes computation; a// value is the thing computation produces. One enum again, and this one// has no recursion at all: values are flat.#[derive(Debug, Clone, PartialEq)]enum Value { Number(f64), Str(String), Bool(bool), Nil, List(Vec<Value>),}
impl Value { // everything is true except `nil` and `false` themselves — the // rule Python and Lua use, and the shortest one to explain fn is_truthy(&self) -> bool { !matches!(self, Value::Nil | Value::Bool(false)) }}
// `Debug` would print `Number(7.0)`; the language's own printer should// print `7`. This impl is what makes values look like *birch* values.impl std::fmt::Display for Value { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { match self { Value::Number(n) => write!(f, "{n}"), Value::Str(s) => write!(f, "{s}"), Value::Bool(b) => write!(f, "{b}"), Value::Nil => write!(f, "nil"), Value::List(items) => { write!(f, "[")?; for (i, item) in items.iter().enumerate() { if i > 0 { write!(f, ", ")?; } write!(f, "{item}")?; } write!(f, "]") } } }}
// The word for a value in error messages: "got a string and a number"// beats "got Str and Number".fn type_name(value: &Value) -> &'static str { match value { Value::Number(_) => "a number", Value::Str(_) => "a string", Value::Bool(_) => "a bool", Value::Nil => "nil", Value::List(_) => "a list", }}
// The tree stores operators as `TokenKind`, which has no `Display` —// and no position either, which is why runtime errors below cannot say// where they happened.fn operator_text(kind: &TokenKind) -> &'static str { match kind { TokenKind::Plus => "+", TokenKind::Minus => "-", TokenKind::Star => "*", TokenKind::Slash => "/", TokenKind::Percent => "%", TokenKind::Less => "<", TokenKind::LessEqual => "<=", TokenKind::Greater => ">", TokenKind::GreaterEqual => ">=", TokenKind::Bang => "!", _ => "?", }}
struct RuntimeError { message: String,}
// ------------------------------------------------------- the environment
// The interpreter's memory. One scope is one map of names to values, and// the stack of scopes *is* the chain the classic interpreter picture// draws: a name is looked up in the innermost scope first, then the one// below it, and so on down to the global scope at the bottom.struct Environment { scopes: Vec<HashMap<String, Value>>,}
impl Environment { fn new() -> Self { Environment { scopes: vec![HashMap::new()], } }
// `var`: a name appears in the innermost scope, shadowing anything // of the same name further out fn define(&mut self, name: String, value: Value) { self.scopes.last_mut().unwrap().insert(name, value); }
// reading walks the chain from the top down and returns the first // match; a missing name is the caller's error to report fn get(&self, name: &str) -> Option<Value> { for scope in self.scopes.iter().rev() { if let Some(value) = scope.get(name) { return Some(value.clone()); } } None }
// assignment also walks the chain, but it can only *update* a scope // that already has the name — `count = 1` inside a block writes to // the outer binding, or fails if no scope down the chain has it fn assign(&mut self, name: &str, value: Value) -> bool { for scope in self.scopes.iter_mut().rev() { if scope.contains_key(name) { scope.insert(name.to_string(), value); return true; } } false }}
// --------------------------------------------------------- the evaluator
// One function per half of the grammar, each one a `match` over the// enum the parser builds. The shape of the code is the shape of the// tree: children are evaluated first (post-order), then the operator// acts on the values that came back. Both functions now carry the// environment with them, so any node that mentions a name can reach it.fn evaluate(expr: &Expr, env: &mut Environment) -> Result<Value, RuntimeError> { match expr { Expr::Number(n) => Ok(Value::Number(*n)), Expr::Str(s) => Ok(Value::Str(s.clone())), Expr::Bool(b) => Ok(Value::Bool(*b)), Expr::Nil => Ok(Value::Nil), Expr::List(items) => { let mut values = Vec::with_capacity(items.len()); for item in items { values.push(evaluate(item, env)?); } Ok(Value::List(values)) } Expr::Unary { op, operand } => { let value = evaluate(operand, env)?; match op { TokenKind::Minus => match value { Value::Number(n) => Ok(Value::Number(-n)), _ => Err(RuntimeError { message: format!("`-` needs a number, got {}", type_name(&value)), }), }, // `!` accepts anything: the question is only truthiness TokenKind::Bang => Ok(Value::Bool(!value.is_truthy())), _ => unreachable!("the parser only builds Unary from `-` and `!`"), } } Expr::Binary { op, left, right } => { // both operands are evaluated first: `Binary` is the eager // half, `Logical` below is the half that can skip let l = evaluate(left, env)?; let r = evaluate(right, env)?; match op { TokenKind::Plus => match (&l, &r) { // one operator, two behaviours: numbers add, // strings concatenate — anything else is a runtime // error, not a silent coercion (Value::Number(a), Value::Number(b)) => Ok(Value::Number(a + b)), (Value::Str(a), Value::Str(b)) => Ok(Value::Str(format!("{a}{b}"))), _ => Err(RuntimeError { message: format!( "`+` needs two numbers or two strings, got {} and {}", type_name(&l), type_name(&r) ), }), }, TokenKind::Minus | TokenKind::Star | TokenKind::Slash | TokenKind::Percent => { let (Value::Number(a), Value::Number(b)) = (&l, &r) else { return Err(RuntimeError { message: format!( "`{}` needs two numbers, got {} and {}", operator_text(op), type_name(&l), type_name(&r) ), }); }; let value = match op { TokenKind::Slash | TokenKind::Percent if *b == 0.0 => { // f64 division would happily return `inf` // or `NaN`; the language refuses instead return Err(RuntimeError { message: String::from("division by zero"), }); } TokenKind::Minus => a - b, TokenKind::Star => a * b, TokenKind::Slash => a / b, _ => a % b, }; Ok(Value::Number(value)) } TokenKind::Less | TokenKind::LessEqual | TokenKind::Greater | TokenKind::GreaterEqual => { let (Value::Number(a), Value::Number(b)) = (&l, &r) else { return Err(RuntimeError { message: format!( "`{}` needs two numbers, got {} and {}", operator_text(op), type_name(&l), type_name(&r) ), }); }; Ok(Value::Bool(match op { TokenKind::Less => a < b, TokenKind::LessEqual => a <= b, TokenKind::Greater => a > b, _ => a >= b, })) } // derived `PartialEq` gives the right answer across // variants for free: `1 == "1"` is simply false, no // coercion, no error TokenKind::EqualEqual => Ok(Value::Bool(l == r)), TokenKind::BangEqual => Ok(Value::Bool(l != r)), _ => unreachable!( "the parser only builds Binary from the operators above" ), } } Expr::Logical { op, left, right } => { let value = evaluate(left, env)?; let decided = match op { // `and`: a falsey left has already decided the result TokenKind::And => !value.is_truthy(), // `or`: a truthy left has already decided the result TokenKind::Or => value.is_truthy(), _ => unreachable!("the parser only builds Logical from `and` and `or`"), }; // the result is the deciding operand's *value*, so // `nil or "fallback"` is "fallback" — and when the left // decides, the right is never evaluated at all if decided { Ok(value) } else { evaluate(right, env) } } // Two name-reading arms, both real now. `Variable` asks the // environment; `Assign` evaluates its right side, then asks the // environment to update the first scope down the chain that // already has the name. `Call` is the one variant still // blocked — nothing in the language is callable yet. Expr::Variable(name) => env.get(name).ok_or(RuntimeError { message: format!("undefined variable `{name}`"), }), Expr::Assign { name, value } => { // assignment is an expression: its value is the value // assigned, which is what makes `a = b = 2` parse and work // with no extra machinery — the parser already made `=` // right-associative, and the value just falls through let value = evaluate(value, env)?; if env.assign(name, value.clone()) { Ok(value) } else { Err(RuntimeError { message: format!("undefined variable `{name}`"), }) } } Expr::Call { callee, args } => { // the callee evaluates first, so an unknown name reports // itself, then the arguments — the order a real call would // use; only the call itself is missing let callee = evaluate(callee, env)?; for arg in args { evaluate(arg, env)?; } Err(RuntimeError { message: format!("a {} cannot be called", type_name(&callee)), }) } Expr::Index { object, index } => { // indexing needs no environment: both sides evaluate to // plain values, so this variant works in full today let object = evaluate(object, env)?; let index = evaluate(index, env)?; match (object, index) { (Value::List(items), Value::Number(n)) => { if n.fract() != 0.0 || n < 0.0 { return Err(RuntimeError { message: format!("list indices must be whole numbers, got {n}"), }); } let i = n as usize; items.get(i).cloned().ok_or(RuntimeError { message: format!( "index {i} is out of bounds, the list has {} elements", items.len() ), }) } (object, Value::Number(_)) => Err(RuntimeError { message: format!( "only lists can be indexed, got {}", type_name(&object) ), }), (object, index) => Err(RuntimeError { message: format!( "list indices must be numbers, got {} (indexing {})", type_name(&index), type_name(&object) ), }), } } }}
fn execute(stmt: &Stmt, env: &mut Environment) -> Result<(), RuntimeError> { match stmt { // an expression statement evaluates and prints its value — the // cheapest way to watch the interpreter work until the REPL // step gives the language a real read-eval-print loop Stmt::Expression(expr) => { let value = evaluate(expr, env)?; println!("{value}"); Ok(()) } // `if`, `while` and blocks need no state: their conditions and // bodies are plain subtrees, so they work in full today Stmt::If { condition, then_branch, else_branch } => { if evaluate(condition, env)?.is_truthy() { execute(then_branch, env) } else if let Some(else_branch) = else_branch { execute(else_branch, env) } else { Ok(()) } } Stmt::While { condition, body } => { while evaluate(condition, env)?.is_truthy() { execute(body, env)?; } Ok(()) } // a block is the one statement that changes the environment: // its body runs in a freshly pushed scope, which dies with it Stmt::Block(statements) => execute_scoped(statements, env), // `var` works now. The two statements that remain need more // than storage: `fun` has nowhere to store the function, and // `return` has no call to return from. Both arrive with the // call machinery in the next step. Stmt::Var { name, init } => { // the initializer evaluates first, in the scope the name // is about to live in — so `var x = x;` reads the outer // `x`, the way most dynamic languages do let value = evaluate(init, env)?; env.define(name.clone(), value); Ok(()) } Stmt::Fun { name, params, body } => { // one check that needs no storage: two parameters with the // same name could never be told apart let mut seen: Vec<&str> = Vec::new(); for param in params { if seen.contains(¶m.as_str()) { return Err(RuntimeError { message: format!("duplicate parameter `{param}` in `{name}`"), }); } seen.push(param); } // the body cannot run yet — a `return` in it has no call // to return from — but naming it, instead of skipping it // with `..`, keeps the tree fully read let _ = body; Err(RuntimeError { message: format!("cannot define `{name}`: functions are not implemented yet"), }) } Stmt::Return { value } => { // the returned expression still evaluates; only the // "where does it go" half is missing if let Some(value) = value { evaluate(value, env)?; } Err(RuntimeError { message: String::from("return outside of a function"), }) } }}
// A block is a scope: push a fresh map, run the body, pop it — even when// a statement in the middle fails, so the caller's environment comes// back exactly the way it went in.fn execute_scoped(statements: &[Stmt], env: &mut Environment) -> Result<(), RuntimeError> { env.scopes.push(HashMap::new()); let result = statements.iter().try_for_each(|s| execute(s, env)); env.scopes.pop(); result}
fn main() { let sources = [ // the program from last step, still running — the evaluator // grew a parameter, not a behaviour change r#"1 + 2 * 3;"na" + "na";!(1 == 2);[10, 20, 30][1];if (2 > 1) "big"; else "small";"#, // variables: define, then reassign. The assignment statement // prints a value because assignment *is* an expression — its // value is the value assigned r#"var greeting = "hello";greeting = greeting + ", world";"#, // a loop now has something to change: the total lives in the // outer scope, the body updates it with plain `=` "var total = 0;var i = 1;while (i <= 5) { total = total + i; i = i + 1;}total;", // a block is a scope: its own `var` shadows, and dies with it r#"var x = "outer";{ var x = "inner"; x;}x;"#, // assignment without `var` reaches outward: both writes land // on the one binding the block can see but not replace "var count = 0;{ count = count + 1; count = count + 1;}", // redeclaring in the same scope overwrites "var a = 1;var a = 2;a;", // errors: a name nobody defined, and an assignment whose // target exists in no scope down the chain "missing;", r#"{ undone = 3; }"#, // the not-implemented half, one step away now "fun add(a, b) { return a + b; }", "return 1;", ];
for source in sources { println!("{source}"); let (tokens, errors) = Scanner::new(source).scan_tokens(); if !errors.is_empty() { for e in &errors { println!(" scan error: {}:{} {}", e.line, e.col, e.message); } continue; } match Parser::new(tokens).program() { Ok(statements) => { // one environment per script; a runtime error aborts // the whole snippet, so nothing leaks between them let mut env = Environment::new(); for statement in &statements { if let Err(e) = execute(statement, &mut env) { println!(" runtime error: {}", e.message); // a script stops at the first uncaught error break; } } } Err(e) => println!(" parse error: {}:{} {}", e.line, e.col, e.message), } }}Run this in the Rust Playground
Running it
Section titled “Running it”cargo run -qEach snippet runs as its own script with its own environment — a runtime error aborts that snippet and nothing leaks into the next:
1 + 2 * 3;"na" + "na";!(1 == 2);[10, 20, 30][1];if (2 > 1) "big"; else "small";7nanatrue20bigvar greeting = "hello";greeting = greeting + ", world";hello, worldvar total = 0;var i = 1;while (i <= 5) { total = total + i; i = i + 1;}total;12336410515615var x = "outer";{ var x = "inner"; x;}x;inneroutervar count = 0;{ count = count + 1; count = count + 1;}12var a = 1;var a = 2;a;2missing; runtime error: undefined variable `missing`{ undone = 3; } runtime error: undefined variable `undone`fun add(a, b) { return a + b; } runtime error: cannot define `add`: functions are not implemented yetreturn 1; runtime error: return outside of a functionTwo errors at the bottom are worth reading as a pair. missing; fails
because no scope anywhere holds the name. { undone = 3; } fails for a
subtler reason: the block’s scope is real, but assign refuses to
create a binding in it, so the walk reaches the global scope, finds
nothing, and reports the name — exactly the guard the last section
promised. And fun add(a, b) still refuses, now with a message that
dates it: functions are one step away, not missing forever.
Where this leaves the track
Section titled “Where this leaves the track”birch at interpreter-ch06 scans, parses, evaluates and remembers.
Variables, assignment, blocks and loops all run; what remains is the
half of the grammar that needs more than storage — fun bodies cannot
run, and return outside of a function is the literal truth. The next
step, Control flow and functions, adds the call machinery: a value
that can be called, a call stack, and what return returns to.
Until then, the track overview has the full
itinerary.