The Tree-Walking Interpreter

Now we have an AST representing our program's structure. The interpreter executes this tree by walking through it and performing the operations.

How Tree-Walking Works

The interpreter visits each AST node and:

1. Expressions: Evaluates to a value
2. Statements: Performs side effects (print, variable assignment, control flow)

AST Node: Binary { left: Number(2), op: Plus, right: Number(3) }
   ↓
Evaluate left: 2
Evaluate right: 3
Apply operator: 2 + 3
   ↓
Result: 5

Lux Runtime Values

Define runtime values in src/interpreter.rs:

use std::collections::HashMap;
use std::rc::Rc;
use std::cell::RefCell;
use crate::ast::*;
use crate::environment::Environment;

#[derive(Debug, Clone)]
pub enum Value {
    Number(f64),
    String(String),
    Bool(bool),
    Nil,
    List(Rc<RefCell<Vec<Value>>>),
    Function {
        params: Vec<String>,
        body: Vec<Stmt>,
        closure: Rc<RefCell<Environment>>,
    },
    NativeFunction {
        name: String,
        arity: usize,
        func: fn(&[Value]) -> Result<Value, String>,
    },
}

impl PartialEq for Value {
    fn eq(&self, other: &Self) -> bool {
        match (self, other) {
            (Value::Number(a), Value::Number(b)) => a == b,
            (Value::String(a), Value::String(b)) => a == b,
            (Value::Bool(a), Value::Bool(b)) => a == b,
            (Value::Nil, Value::Nil) => true,
            _ => false,
        }
    }
}

impl Value {
    pub fn to_string(&self) -> String {
        match self {
            Value::Number(n) => {
                if n.fract() == 0.0 {
                    format!("{}", n as i64)
                } else {
                    format!("{}", n)
                }
            }
            Value::String(s) => s.clone(),
            Value::Bool(b) => b.to_string(),
            Value::Nil => "nil".to_string(),
            Value::List(items) => {
                let items = items.borrow();
                let strs: Vec<String> = items.iter().map(|v| v.to_string()).collect();
                format!("[{}]", strs.join(", "))
            }
            Value::Function { params, .. } => {
                format!("<function({})>", params.len())
            }
            Value::NativeFunction { name, .. } => {
                format!("<native function {}>", name)
            }
        }
    }

    pub fn is_truthy(&self) -> bool {
        match self {
            Value::Nil => false,
            Value::Bool(b) => *b,
            _ => true,
        }
    }

    pub fn type_name(&self) -> &str {
        match self {
            Value::Number(_) => "number",
            Value::String(_) => "string",
            Value::Bool(_) => "bool",
            Value::Nil => "nil",
            Value::List(_) => "list",
            Value::Function { .. } => "function",
            Value::NativeFunction { .. } => "function",
        }
    }
}

The Environment (Variable Storage)

Create src/environment.rs for managing variables and scopes:

use std::collections::HashMap;
use std::rc::Rc;
use std::cell::RefCell;
use crate::interpreter::Value;

pub struct Environment {
    values: HashMap<String, Value>,
    parent: Option<Rc<RefCell<Environment>>>,
}

impl Environment {
    pub fn new() -> Self {
        Environment {
            values: HashMap::new(),
            parent: None,
        }
    }

    pub fn with_parent(parent: Rc<RefCell<Environment>>) -> Self {
        Environment {
            values: HashMap::new(),
            parent: Some(parent),
        }
    }

    pub fn define(&mut self, name: String, value: Value) {
        self.values.insert(name, value);
    }

    pub fn get(&self, name: &str) -> Result<Value, String> {
        if let Some(value) = self.values.get(name) {
            Ok(value.clone())
        } else if let Some(parent) = &self.parent {
            parent.borrow().get(name)
        } else {
            Err(format!("Undefined variable '{}'", name))
        }
    }

    pub fn assign(&mut self, name: &str, value: Value) -> Result<(), String> {
        if self.values.contains_key(name) {
            self.values.insert(name.to_string(), value);
            Ok(())
        } else if let Some(parent) = &self.parent {
            parent.borrow_mut().assign(name, value)
        } else {
            Err(format!("Undefined variable '{}'", name))
        }
    }
}

How Scoping Works

Environments form a chain:

let x = 10;          // Global environment: { x: 10 }

fn outer() {
    let y = 20;      // Outer environment: { y: 20 }, parent: global
    
    fn inner() {
        let z = 30;  // Inner environment: { z: 30 }, parent: outer
        print x + y + z;  // Looks up: inner → outer → global
    }
}

The Interpreter Structure

Continue src/interpreter.rs:

pub struct Interpreter {
    environment: Rc<RefCell<Environment>>,
}

impl Interpreter {
    pub fn new() -> Self {
        let mut env = Environment::new();
        
        // Register native functions
        env.define(
            "clock".to_string(),
            Value::NativeFunction {
                name: "clock".to_string(),
                arity: 0,
                func: native_clock,
            },
        );
        
        env.define(
            "len".to_string(),
            Value::NativeFunction {
                name: "len".to_string(),
                arity: 1,
                func: native_len,
            },
        );
        
        env.define(
            "type".to_string(),
            Value::NativeFunction {
                name: "type".to_string(),
                arity: 1,
                func: native_type,
            },
        );
        
        env.define(
            "push".to_string(),
            Value::NativeFunction {
                name: "push".to_string(),
                arity: 2,
                func: native_push,
            },
        );
        
        env.define(
            "pop".to_string(),
            Value::NativeFunction {
                name: "pop".to_string(),
                arity: 1,
                func: native_pop,
            },
        );
        
        env.define(
            "str".to_string(),
            Value::NativeFunction {
                name: "str".to_string(),
                arity: 1,
                func: native_str,
            },
        );
        
        env.define(
            "num".to_string(),
            Value::NativeFunction {
                name: "num".to_string(),
                arity: 1,
                func: native_num,
            },
        );
        
        env.define(
            "input".to_string(),
            Value::NativeFunction {
                name: "input".to_string(),
                arity: 1,
                func: native_input,
            },
        );

        Interpreter {
            environment: Rc::new(RefCell::new(env)),
        }
    }

    pub fn interpret(&mut self, statements: Vec<Stmt>) -> Result<(), String> {
        for stmt in statements {
            self.execute_statement(stmt)?;
        }
        Ok(())
    }

    // ========== Statement Execution ==========

    fn execute_statement(&mut self, stmt: Stmt) -> Result<Option<Value>, String> {
        match stmt {
            Stmt::Expression(expr) => {
                self.evaluate_expression(expr)?;
                Ok(None)
            }

            Stmt::Print(expr) => {
                let value = self.evaluate_expression(expr)?;
                println!("{}", value.to_string());
                Ok(None)
            }

            Stmt::Let { name, value } => {
                let val = self.evaluate_expression(value)?;
                self.environment.borrow_mut().define(name, val);
                Ok(None)
            }

            Stmt::Block(statements) => {
                let new_env = Environment::with_parent(Rc::clone(&self.environment));
                let previous = std::mem::replace(
                    &mut self.environment,
                    Rc::new(RefCell::new(new_env)),
                );

                let mut result = None;
                for stmt in statements {
                    if let Some(val) = self.execute_statement(stmt)? {
                        result = Some(val);
                        break;
                    }
                }

                self.environment = previous;
                Ok(result)
            }

            Stmt::If {
                condition,
                then_branch,
                else_branch,
            } => {
                let cond_value = self.evaluate_expression(condition)?;
                if cond_value.is_truthy() {
                    self.execute_statement(*then_branch)
                } else if let Some(else_stmt) = else_branch {
                    self.execute_statement(*else_stmt)
                } else {
                    Ok(None)
                }
            }

            Stmt::While { condition, body } => {
                while self.evaluate_expression(condition.clone())?.is_truthy() {
                    if let Some(val) = self.execute_statement(*body.clone())? {
                        return Ok(Some(val));
                    }
                }
                Ok(None)
            }

            Stmt::For {
                variable,
                iterable,
                body,
            } => {
                let iter_value = self.evaluate_expression(iterable)?;
                
                let items = match iter_value {
                    Value::List(list) => list.borrow().clone(),
                    _ => return Err(format!("Can only iterate over lists, got {}", iter_value.type_name())),
                };

                for item in items {
                    let new_env = Environment::with_parent(Rc::clone(&self.environment));
                    let previous = std::mem::replace(
                        &mut self.environment,
                        Rc::new(RefCell::new(new_env)),
                    );

                    self.environment.borrow_mut().define(variable.clone(), item);

                    let result = self.execute_statement(*body.clone())?;

                    self.environment = previous;

                    if result.is_some() {
                        return Ok(result);
                    }
                }

                Ok(None)
            }

            Stmt::Function { name, params, body } => {
                let func = Value::Function {
                    params,
                    body,
                    closure: Rc::clone(&self.environment),
                };
                self.environment.borrow_mut().define(name, func);
                Ok(None)
            }

            Stmt::Return(expr) => {
                let value = if let Some(e) = expr {
                    self.evaluate_expression(e)?
                } else {
                    Value::Nil
                };
                Ok(Some(value))
            }
        }
    }

    // ========== Expression Evaluation ==========

    fn evaluate_expression(&mut self, expr: Expr) -> Result<Value, String> {
        match expr {
            Expr::Number(n) => Ok(Value::Number(n)),
            Expr::String(s) => Ok(Value::String(s)),
            Expr::Bool(b) => Ok(Value::Bool(b)),
            Expr::Nil => Ok(Value::Nil),

            Expr::Identifier(name) => self.environment.borrow().get(&name),

            Expr::Unary { op, expr } => {
                let value = self.evaluate_expression(*expr)?;
                match op {
                    UnaryOp::Minus => match value {
                        Value::Number(n) => Ok(Value::Number(-n)),
                        _ => Err(format!("Cannot negate {}", value.type_name())),
                    },
                    UnaryOp::Not => Ok(Value::Bool(!value.is_truthy())),
                }
            }

            Expr::Binary { left, op, right } => {
                let left_val = self.evaluate_expression(*left)?;
                let right_val = self.evaluate_expression(*right)?;
                self.apply_binary_op(left_val, op, right_val)
            }

            Expr::Grouping(expr) => self.evaluate_expression(*expr),

            Expr::Assign { name, value } => {
                let val = self.evaluate_expression(*value)?;
                self.environment.borrow_mut().assign(&name, val.clone())?;
                Ok(val)
            }

            Expr::Call { callee, args } => {
                let func = self.evaluate_expression(*callee)?;
                let mut arg_values = Vec::new();
                for arg in args {
                    arg_values.push(self.evaluate_expression(arg)?);
                }
                self.call_function(func, arg_values)
            }

            Expr::Index { object, index } => {
                let obj_val = self.evaluate_expression(*object)?;
                let idx_val = self.evaluate_expression(*index)?;

                match (obj_val, idx_val) {
                    (Value::List(list), Value::Number(n)) => {
                        let idx = n as usize;
                        let items = list.borrow();
                        items.get(idx)
                            .cloned()
                            .ok_or_else(|| format!("List index {} out of bounds", idx))
                    }
                    (Value::String(s), Value::Number(n)) => {
                        let idx = n as usize;
                        s.chars()
                            .nth(idx)
                            .map(|c| Value::String(c.to_string()))
                            .ok_or_else(|| format!("String index {} out of bounds", idx))
                    }
                    (obj, _) => Err(format!("Cannot index {}", obj.type_name())),
                }
            }

            Expr::List(elements) => {
                let mut values = Vec::new();
                for elem in elements {
                    values.push(self.evaluate_expression(elem)?);
                }
                Ok(Value::List(Rc::new(RefCell::new(values))))
            }

            Expr::Lambda { params, body } => Ok(Value::Function {
                params,
                body,
                closure: Rc::clone(&self.environment),
            }),
        }
    }

    // ========== Binary Operations ==========

    fn apply_binary_op(&self, left: Value, op: BinaryOp, right: Value) -> Result<Value, String> {
        match op {
            BinaryOp::Add => match (left, right) {
                (Value::Number(a), Value::Number(b)) => Ok(Value::Number(a + b)),
                (Value::String(a), Value::String(b)) => Ok(Value::String(a + &b)),
                (Value::String(a), Value::Number(b)) => Ok(Value::String(a + &b.to_string())),
                (Value::Number(a), Value::String(b)) => Ok(Value::String(a.to_string() + &b)),
                (a, b) => Err(format!("Cannot add {} and {}", a.type_name(), b.type_name())),
            },

            BinaryOp::Subtract => match (left, right) {
                (Value::Number(a), Value::Number(b)) => Ok(Value::Number(a - b)),
                (a, b) => Err(format!("Cannot subtract {} and {}", a.type_name(), b.type_name())),
            },

            BinaryOp::Multiply => match (left, right) {
                (Value::Number(a), Value::Number(b)) => Ok(Value::Number(a * b)),
                (a, b) => Err(format!("Cannot multiply {} and {}", a.type_name(), b.type_name())),
            },

            BinaryOp::Divide => match (left, right) {
                (Value::Number(a), Value::Number(b)) => {
                    if b == 0.0 {
                        Err("Division by zero".to_string())
                    } else {
                        Ok(Value::Number(a / b))
                    }
                }
                (a, b) => Err(format!("Cannot divide {} and {}", a.type_name(), b.type_name())),
            },

            BinaryOp::Modulo => match (left, right) {
                (Value::Number(a), Value::Number(b)) => Ok(Value::Number(a % b)),
                (a, b) => Err(format!("Cannot modulo {} and {}", a.type_name(), b.type_name())),
            },

            BinaryOp::Equal => Ok(Value::Bool(left == right)),
            BinaryOp::NotEqual => Ok(Value::Bool(left != right)),

            BinaryOp::Less => match (left, right) {
                (Value::Number(a), Value::Number(b)) => Ok(Value::Bool(a < b)),
                (a, b) => Err(format!("Cannot compare {} and {}", a.type_name(), b.type_name())),
            },

            BinaryOp::LessEqual => match (left, right) {
                (Value::Number(a), Value::Number(b)) => Ok(Value::Bool(a <= b)),
                (a, b) => Err(format!("Cannot compare {} and {}", a.type_name(), b.type_name())),
            },

            BinaryOp::Greater => match (left, right) {
                (Value::Number(a), Value::Number(b)) => Ok(Value::Bool(a > b)),
                (a, b) => Err(format!("Cannot compare {} and {}", a.type_name(), b.type_name())),
            },

            BinaryOp::GreaterEqual => match (left, right) {
                (Value::Number(a), Value::Number(b)) => Ok(Value::Bool(a >= b)),
                (a, b) => Err(format!("Cannot compare {} and {}", a.type_name(), b.type_name())),
            },

            BinaryOp::And => {
                if !left.is_truthy() {
                    Ok(left)
                } else {
                    Ok(right)
                }
            }

            BinaryOp::Or => {
                if left.is_truthy() {
                    Ok(left)
                } else {
                    Ok(right)
                }
            }
        }
    }

    // ========== Function Calls ==========

    fn call_function(&mut self, func: Value, args: Vec<Value>) -> Result<Value, String> {
        match func {
            Value::Function {
                params,
                body,
                closure,
            } => {
                if args.len() != params.len() {
                    return Err(format!(
                        "Function expects {} arguments, got {}",
                        params.len(),
                        args.len()
                    ));
                }

                // Create new environment for function execution
                let new_env = Environment::with_parent(closure);
                let previous = std::mem::replace(
                    &mut self.environment,
                    Rc::new(RefCell::new(new_env)),
                );

                // Bind parameters
                for (param, arg) in params.iter().zip(args.iter()) {
                    self.environment.borrow_mut().define(param.clone(), arg.clone());
                }

                // Execute function body
                let mut result = Value::Nil;
                for stmt in body {
                    if let Some(val) = self.execute_statement(stmt)? {
                        result = val;
                        break;
                    }
                }

                // Restore previous environment
                self.environment = previous;
                Ok(result)
            }

            Value::NativeFunction { arity, func, .. } => {
                if args.len() != arity {
                    return Err(format!(
                        "Native function expects {} arguments, got {}",
                        arity,
                        args.len()
                    ));
                }
                func(&args)
            }

            _ => Err(format!("Cannot call {}", func.type_name())),
        }
    }
}

// ========== Native Functions ==========

fn native_clock(_args: &[Value]) -> Result<Value, String> {
    use std::time::{SystemTime, UNIX_EPOCH};
    let now = SystemTime::now()
        .duration_since(UNIX_EPOCH)
        .unwrap()
        .as_secs_f64();
    Ok(Value::Number(now))
}

fn native_len(args: &[Value]) -> Result<Value, String> {
    match &args[0] {
        Value::String(s) => Ok(Value::Number(s.len() as f64)),
        Value::List(list) => Ok(Value::Number(list.borrow().len() as f64)),
        v => Err(format!("len() requires string or list, got {}", v.type_name())),
    }
}

fn native_type(args: &[Value]) -> Result<Value, String> {
    Ok(Value::String(args[0].type_name().to_string()))
}

fn native_push(args: &[Value]) -> Result<Value, String> {
    match (&args[0], &args[1]) {
        (Value::List(list), value) => {
            list.borrow_mut().push(value.clone());
            Ok(Value::Nil)
        }
        (v, _) => Err(format!("push() requires list, got {}", v.type_name())),
    }
}

fn native_pop(args: &[Value]) -> Result<Value, String> {
    match &args[0] {
        Value::List(list) => {
            list.borrow_mut()
                .pop()
                .ok_or_else(|| "Cannot pop from empty list".to_string())
        }
        v => Err(format!("pop() requires list, got {}", v.type_name())),
    }
}

fn native_str(args: &[Value]) -> Result<Value, String> {
    Ok(Value::String(args[0].to_string()))
}

fn native_num(args: &[Value]) -> Result<Value, String> {
    match &args[0] {
        Value::Number(n) => Ok(Value::Number(*n)),
        Value::String(s) => s
            .parse::<f64>()
            .map(Value::Number)
            .map_err(|_| format!("Cannot convert '{}' to number", s)),
        Value::Bool(true) => Ok(Value::Number(1.0)),
        Value::Bool(false) => Ok(Value::Number(0.0)),
        v => Err(format!("Cannot convert {} to number", v.type_name())),
    }
}

fn native_input(args: &[Value]) -> Result<Value, String> {
    use std::io::{self, Write};
    
    // Print prompt
    print!("{}", args[0].to_string());
    io::stdout().flush().unwrap();
    
    // Read line
    let mut input = String::new();
    io::stdin()
        .read_line(&mut input)
        .map_err(|e| format!("Failed to read input: {}", e))?;
    
    Ok(Value::String(input.trim().to_string()))
}

Type Coercion Rules

Lux has specific rules for type coercion:

Testing the Interpreter

Update src/main.rs:

mod ast;
mod lexer;
mod parser;
mod environment;
mod interpreter;

use lexer::Lexer;
use parser::Parser;
use interpreter::Interpreter;

fn main() {
    let source = r#"
        let x = 10;
        let y = 20;
        print "x + y = " + str(x + y);
        
        fn factorial(n) {
            if n <= 1 {
                return 1;
            }
            return n * factorial(n - 1);
        }
        
        print "factorial(5) = " + str(factorial(5));
        
        let numbers = [1, 2, 3, 4, 5];
        for n in numbers {
            print n * n;
        }
    "#;

    // Lex
    let mut lexer = Lexer::new(source.to_string());
    let tokens = match lexer.tokenize() {
        Ok(t) => t,
        Err(e) => {
            eprintln!("Lexer error: {}", e);
            return;
        }
    };

    // Parse
    let mut parser = Parser::new(tokens);
    let statements = match parser.parse() {
        Ok(s) => s,
        Err(e) => {
            eprintln!("Parser error: {}", e);
            return;
        }
    };

    // Interpret
    let mut interpreter = Interpreter::new();
    if let Err(e) = interpreter.interpret(statements) {
        eprintln!("Runtime error: {}", e);
    }
}

Run it:

cargo run

Expected output:

x + y = 30
factorial(5) = 120
1
4
9
16
25

Built-in Native Functions

Lux provides 8 native functions:

Runtime Error Handling

The interpreter catches several runtime errors:

let x = 5 / 0;              // Error: Division by zero
let y = "hello" - 5;        // Error: Cannot subtract string and number
let z = unknown_var;        // Error: Undefined variable 'unknown_var'
print factorial();          // Error: Function expects 1 arguments, got 0
let list = [1, 2, 3];
print list[10];             // Error: List index 10 out of bounds

Common Pitfalls

1. Not Cloning Rc/RefCell

// ❌ Wrong: moves closure, can't use it later
let func = Value::Function { closure, ... };

// ✅ Correct: clone the Rc
let func = Value::Function {
    closure: Rc::clone(&closure),
    ...
};

2. Forgetting to Restore Environment

// ❌ Wrong: environment leak
let new_env = Environment::with_parent(self.environment.clone());
self.environment = Rc::new(RefCell::new(new_env));
// ... execute ...
// Forgot to restore!

// ✅ Correct: always restore
let previous = std::mem::replace(&mut self.environment, new_env);
// ... execute ...
self.environment = previous;

3. Not Handling Return Values

// ❌ Wrong: ignores return statement
self.execute_statement(stmt)?;

// ✅ Correct: check for return
if let Some(val) = self.execute_statement(stmt)? {
    return Ok(Some(val));  // Propagate return
}

Performance

Tree-walking interpreters are slow compared to compiled languages, but:

• Good enough: For scripting and DSLs
• Simple: Easy to understand and debug
• Flexible: Easy to add features

Typical performance: 10-100x slower than native code.

Interpreter Summary

What's Next?

Our basic interpreter works! But functions can't capture variables from outer scopes yet. Let's add closures!

→ Continue to Chapter 5: Functions & Closures