Evaluating expressions
The tree is complete, and nothing reads it. Last step’s build ended in a
row of dead_code warnings — one per field nobody looks at — because the
parser builds nodes and stops. This step gives the nodes something to
do: a tree-walking evaluator, the simplest kind of interpreter there is.
A Value enum says what expressions produce, evaluate walks an Expr
and returns one, execute walks statements. By the end, 1 + 2 * 3;
prints 7, [10, 20, 30][1] prints 20, and false and (1 / 0);
prints false — the division never ran.
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-ch04cargo run -qThat prints the syntax trees from last time. This article stays inside
the same single file, src/main.rs: it adds a Value enum, two
functions — evaluate and execute — and a new main, and touches
nothing above them. The scanner and the parser are byte-identical to the
last step. At the end, the same command at the interpreter-ch05 tag
runs programs instead of printing trees.
What a value is
Section titled “What a value is”The tree describes computation; a value is the thing computation produces. birch needs one more enum for that, and this one has no recursion at all:
#[derive(Debug, Clone, PartialEq)]enum Value { Number(f64), Str(String), Bool(bool), Nil, List(Vec<Value>),}No Box anywhere. Expr needed boxes because an expression contains
expressions; a value contains only smaller values, and a list’s elements
sit behind a Vec anyway. The recursion is gone from the type because
it is gone from the grammar: evaluating a subtree always finishes.
Two small impls ride along. is_truthy fixes the one question if and
! will ask — everything is true except nil and false themselves,
the rule Python and Lua use:
impl Value { fn is_truthy(&self) -> bool { !matches!(self, Value::Nil | Value::Bool(false)) }}And a Display impl, because Debug would print Number(7.0) where
the language should print 7. Without it, every result the interpreter
shows would be wearing Rust’s clothes.
One match per enum
Section titled “One match per enum”The evaluator is two functions, one per half of the grammar, and each is
a match over the enum the parser builds. evaluate takes a reference
to an Expr and hands back either a Value or a RuntimeError:
fn evaluate(expr: &Expr) -> 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)?); } Ok(Value::List(values)) } // ... every other variant, one arm eachThe shape of the code is the shape of the tree. Children are evaluated
first — post-order, the same order the parser built the nodes — and then
the operator acts on the values that came back. Binary evaluates both
operands and dispatches on the operator it stored last step:
Expr::Binary { op, left, right } => { let l = evaluate(left)?; let r = evaluate(right)?; match op { TokenKind::Plus => match (&l, &r) { (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) ), }), }, // Minus, Star, Slash, Percent: numbers only // Less, LessEqual, Greater, GreaterEqual: numbers to Bool // EqualEqual, BangEqual: derived PartialEqThree decisions hide in those arms. + has two behaviours — numbers
add, strings concatenate — and anything else is a runtime error, not a
silent coercion. Division refuses to run at all when the right side is
zero, because f64 would otherwise happily return inf or NaN:
TokenKind::Slash | TokenKind::Percent if *b == 0.0 => { return Err(RuntimeError { message: String::from("division by zero"), });}And equality does nothing at all: the PartialEq the enum derives is
the whole implementation, which makes 1 == "1" simply false — no
coercion, no error, no code.
The half that can skip
Section titled “The half that can skip”Binary is the eager half: both operands evaluate, always. Logical is
the half that decides early, and this is why and and or got their
own variant last step:
Expr::Logical { op, left, right } => { let value = evaluate(left)?; 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`"), }; if decided { Ok(value) } else { evaluate(right) }}Short-circuiting is a fact about evaluation order, and the tree
recorded it as data: one variant for the operators that can skip, one
for the operators that cannot. The result is the deciding operand’s
value, not a Boolean — so nil or "fallback" is "fallback", the
way Python and JavaScript read.
Four arms with nothing to consult
Section titled “Four arms with nothing to consult”Then the match runs out of easy variants. Variable needs an
environment to look names up in; Assign needs the same environment to
store into; Call needs functions to exist as values. None of that
exists yet — the environment is the next step’s subject — but the match
still has to be exhaustive. That is the property this whole track has
been building towards: the compiler will not let an evaluator forget
a node kind. Add an Expr variant anywhere in this file and every
match over Expr stops compiling until it is answered.
So the three blocked variants fail with the errors a reader would
actually hit, and Index — which needs no state at all, because both
sides evaluate to plain values — works in full:
Expr::Variable(name) => Err(RuntimeError { message: format!("undefined variable `{name}`"),}),Expr::Assign { name, value } => { // the right side still evaluates, in the order a real // assignment would use; only the store is missing evaluate(value)?; Err(RuntimeError { message: format!("undefined variable `{name}`"), })}Assign still evaluates its right side first, and Call still
evaluates its callee and arguments, in the order a real call would use —
only the final act is missing. When the environment arrives, these are
the arms it replaces, and nothing else in the evaluator changes.
Errors that say what, not where
Section titled “Errors that say what, not where”RuntimeError is one field:
struct RuntimeError { message: String,}Compare that with ParseError, which carries a line and a column. The
parser can point: it still holds tokens, and tokens have positions. The
evaluator cannot — the tree stores operators as bare TokenKind, and
the nodes carry no positions at all, so a runtime error in a two-hundred
line script says division by zero and leaves the where to the
reader. That is a real limitation and the price of last step’s design,
and it is on the itinerary: the error-reporting step puts positions back
into the tree itself.
Statements: three work now, three cannot
Section titled “Statements: three work now, three cannot”execute mirrors evaluate, one arm per statement:
Stmt::Expression(expr) => { let value = evaluate(expr)?; println!("{value}"); Ok(())}Stmt::If { condition, then_branch, else_branch } => { if evaluate(condition)?.is_truthy() { execute(then_branch) } else if let Some(else_branch) = else_branch { execute(else_branch) } else { Ok(()) }}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. If, While and blocks need no state:
their conditions and bodies are plain subtrees, so they work in full
today. A while loop is worth a second look, though. Looping needs
something to change between iterations, and with no variables nothing
can change — so every loop this step either runs zero times or never
ends. The environment fixes that next step.
The three statements that remain need somewhere to put things: var
evaluates its initializer and then has nowhere to store it, fun has
nowhere to store the function, and return has no call to return from.
Each fails with the message a reader would hit — return outside of a function is the same words every language prints — and all three arms
are what the environment step replaces.
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 values, the evaluator and the
new main are new:
//! birch, step 5: the evaluator.//!//! A tree-walking evaluator: `evaluate` turns an `Expr` into a `Value`,//! `execute` walks statements. Rust's exhaustive matches force a decision//! for every node kind, so the parts that need state which does not exist//! yet — variables, functions — fail with honest runtime errors instead//! of being silently skipped.
#[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 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.fn evaluate(expr: &Expr) -> 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)?); } Ok(Value::List(values)) } Expr::Unary { op, operand } => { let value = evaluate(operand)?; 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)?; let r = evaluate(right)?; 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)?; 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) } } // The four variants below need state the interpreter does not // have yet. An exhaustive match forces an answer for every one // of them now — the compiler will not let an evaluator "forget" // a node kind — so each fails with the error a reader would // actually hit, and the environment step replaces exactly // these arms. Expr::Variable(name) => Err(RuntimeError { message: format!("undefined variable `{name}`"), }), Expr::Assign { name, value } => { // the right side still evaluates, in the order a real // assignment would use; only the store is missing evaluate(value)?; 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)?; for arg in args { evaluate(arg)?; } 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)?; let index = evaluate(index)?; 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) -> 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)?; 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)?.is_truthy() { execute(then_branch) } else if let Some(else_branch) = else_branch { execute(else_branch) } else { Ok(()) } } Stmt::While { condition, body } => { while evaluate(condition)?.is_truthy() { execute(body)?; } Ok(()) } Stmt::Block(statements) => { for statement in statements { execute(statement)?; } Ok(()) } // The three statements that remain need somewhere to put // things: `var` evaluates its initializer and then has nowhere // to store it, `fun` has nowhere to store the function, and // `return` has no call to return from. All three arrive with // the environment in the next step. Stmt::Var { name, init } => { // the initializer still evaluates, in declaration order; // only the store is missing evaluate(init)?; Err(RuntimeError { message: format!("cannot declare `{name}`: there is no environment yet"), }) } 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}`: there is no environment 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)?; } Err(RuntimeError { message: String::from("return outside of a function"), }) } }}
fn main() { let sources = [ // a program: five statements, five values printed in order r#"1 + 2 * 3;"na" + "na";!(1 == 2);[10, 20, 30][1];if (2 > 1) "big"; else "small";"#, // runtime errors: what went wrong, though not yet where r#""count: " + 3;"#, "1 / 0;", // short-circuiting: the right side never runs "false and (1 / 0);", r#"nil or "fallback";"#, // the not-implemented-yet half of the grammar "x;", "var count = 0;", "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) => { for statement in &statements { if let Err(e) = execute(statement) { 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 -qThe program runs each snippet as a script. Expression statements print their values in order; a runtime error stops that snippet at the first failure, the way a script aborts:
1 + 2 * 3;"na" + "na";!(1 == 2);[10, 20, 30][1];if (2 > 1) "big"; else "small";7nanatrue20big"count: " + 3; runtime error: `+` needs two numbers or two strings, got a string and a number1 / 0; runtime error: division by zerofalse and (1 / 0);falsenil or "fallback";fallbackx; runtime error: undefined variable `x`var count = 0; runtime error: cannot declare `count`: there is no environment yetreturn 1; runtime error: return outside of a functionWorth checking against the source. false and (1 / 0); prints false
— not a division error — because the left side decided and the right
side never evaluated. nil or "fallback"; prints fallback for the
same reason read the other way round. And the four runtime errors at the
bottom are the not-implemented-yet half of the grammar failing loudly
instead of silently, exactly as the exhaustive match demanded.
One detail from last step is now settled: the dead_code warnings are
gone. Every field of every node is read — var’s initializer and
return’s value by the evaluator that runs them before reporting that
it cannot store them, fun’s parameters by the one check that needs no
storage (two parameters with the same name could never be told apart),
and fun’s body by being named rather than skipped. The tree is fully
walked.
Where this leaves the track
Section titled “Where this leaves the track”The project at interpreter-ch05 scans, parses and now evaluates the
whole birch grammar — everything, that is, except the parts that need an
environment. x; is undefined because there is nowhere for x to be
defined, and that is precisely the gap. The next step, Variables and
scopes, closes it: a chain of environments that stores values, looks
them up, and gives while loops something to change. Until then, the
track overview has the full itinerary.