Writing a Lisp Interpreter in Rust - Part 3: Evaluation

Published: at 07:00 AM

The Problem

We have an AST. We need to run it.

// We have this tree:
CallExpression("+")
├── Literal(Integer(2))
└── Literal(Integer(3))

// We need this result:
5

But there’s a catch. What about (+ x 3)? Where does x come from? We need a place to store variables - an environment.

Runtime Values vs AST Nodes

The AST describes structure. Runtime values hold actual data.

// AST nodes (structure)
pub enum Form {
    Literal(Literal),
    CallExpression(String),
    Symbol(String),
    List,
    // ...
}

// Runtime values (data)
pub enum RuntimeObject {
    Primitive(Literal),              // 42, "hello", true
    List(Vec<RuntimeObject>),        // [1, 2, 3]
    Function(BuiltInFunction),       // +, -, *, etc.
    RuntimeFunction(Lambda),         // user-defined functions
    Record(HashMap<String, RuntimeObject>),
    NoOp,                           // for def, defn
}

Why separate them? Because Symbol("x") in the AST becomes Primitive(Integer(42)) at runtime - if x is bound to 42.

The Evaluation Algorithm

Evaluation is a big pattern match on the AST node type:

pub fn eval(node: &Node<Form>, env: EnvPointer) -> Result<RuntimeObject> {
    match node.owned_value() {
        Form::Literal(lit) => Ok(lit.into()),  // Literals evaluate to themselves
        
        Form::Symbol(symbol) => env             // Symbols look up their value
            .lookup(&symbol)
            .ok_or(anyhow!("{symbol} is not defined")),
            
        Form::List => eval_list(node, env),     // Lists evaluate their elements
        
        Form::CallExpression(func) => match func.as_str() {
            "if" => eval_if(node, env),         // Special forms
            "def" => def(node, env),
            "defn" => defn(node, env),
            _ => eval_call_expr(func, node, env), // Function calls
        },
        
        Form::Root => {                         // Multiple expressions
            let results: Result<Vec<_>> = node.iter()
                .map(|n| eval(n, env.clone()))
                .collect();
            results?.last().cloned()
                .ok_or_else(|| anyhow!("Empty root"))
        }
        // ...
    }
}

The key insight: evaluation is recursive. To evaluate a node, we often need to evaluate its children first.

Environments: Where Variables Live

An environment maps symbols to values:

pub struct Env {
    vars: RefCell<HashMap<String, RuntimeObject>>,
    parent: Option<Rc<Env>>,
}

Why RefCell? Because we need to mutate the HashMap (adding variables) while multiple references exist.

Why parent? For lexical scoping:

(def x 10)          ; Global env: {x: 10}
(defn f [x]         ; Function env: {x: ?} → Global env
  (+ x 1))          ; Looks up + in parent
(f 5)               ; Function env: {x: 5} → Global env

Variable lookup walks up the chain:

impl Env {
    pub fn lookup(&self, symbol: &str) -> Option<RuntimeObject> {
        if let Some(value) = self.vars.borrow().get(symbol) {
            return Some(value.clone());
        }
        self.parent.as_ref()?.lookup(symbol)
    }
}

Special Forms

Some expressions need custom evaluation rules:

if - Conditional Evaluation

fn eval_if(node: &Node<Form>, env: EnvPointer) -> Result<RuntimeObject> {
    let mut args = node.clone();
    let condition = args.take_first()
        .ok_or_else(|| anyhow!("if needs condition"))?;
    
    let result = eval(&condition, env.clone())?;
    
    let chosen_branch = match result {
        RuntimeObject::Primitive(Literal::Bool(true)) => args.first(),
        RuntimeObject::Primitive(Literal::Bool(false)) => args.last(),
        _ => return Err(anyhow!("if condition must be boolean")),
    }?;
    
    eval(chosen_branch, env)  // Only evaluate the chosen branch!
}

Key: We don’t evaluate both branches - only the one we need.

def - Creating Bindings

fn def(node: &Node<Form>, env: EnvPointer) -> Result<RuntimeObject> {
    let mut body = node.clone();
    let symbol = body.take_first()
        .ok_or_else(|| anyhow!("def needs symbol"))?;
    let value_node = body.first()
        .ok_or_else(|| anyhow!("def needs value"))?;
    
    let value = eval(value_node, env.clone())?;  // Evaluate the value
    
    env.vars.borrow_mut()
        .insert(symbol.to_string(), value);       // Store in environment
    
    Ok(RuntimeObject::NoOp)
}

defn - Defining Functions

fn defn(node: &Node<Form>, env: EnvPointer) -> Result<RuntimeObject> {
    // (defn name [args] body)
    let mut parts = node.clone();
    let name = parts.take_first()?;
    let args = parts.take_first()?;
    let body = parts.take_first()?;
    
    // Create a lambda and bind it to the name
    let lambda = build_lambda(args, body, env.clone())?;
    env.vars.borrow_mut().insert(name.to_string(), lambda);
    
    Ok(RuntimeObject::NoOp)
}

Function Calls

Regular function calls evaluate all arguments first:

fn eval_call_expr(name: String, form: &Node<Form>, env: EnvPointer) 
    -> Result<RuntimeObject> {
    // Evaluate all arguments
    let args = eval_children(form, env.clone())?;
    
    // Built-in function?
    if let Some(func) = built_in_functions::FUNCTIONS.get(name.as_str()) {
        return func(&args);
    }
    
    // User-defined function?
    if let Some(RuntimeObject::RuntimeFunction(lambda)) = env.lookup(&name) {
        return lambda.eval(&args);
    }
    
    Err(anyhow!("{name} is not defined"))
}

fn eval_children(form: &Node<Form>, env: EnvPointer) 
    -> Result<Vec<RuntimeObject>> {
    form.iter()
        .map(|child| eval(child, env.clone()))
        .collect()
}

Built-in functions are just Rust functions:

fn add(args: &[RuntimeObject]) -> Result<RuntimeObject> {
    let sum: i32 = args.extract_numbers()?.iter().sum();
    Ok(sum.into())
}

Closures and Lambda

Functions capture their defining environment:

pub struct Lambda {
    args: Vec<String>,
    body: Node<Form>,
    env: Env,  // Captured environment
}

impl Lambda {
    pub fn eval(&self, arg_values: &[RuntimeObject]) -> Result<RuntimeObject> {
        // Create new environment for this call
        self.bind_arguments(arg_values);
        
        // Evaluate body in the new environment
        let results = eval_forest(self.body.clone(), 
                                 Rc::new(self.env.clone()))?;
        results.last().cloned()
            .ok_or_else(|| anyhow!("Empty function body"))
    }
    
    fn bind_arguments(&self, values: &[RuntimeObject]) {
        self.env.vars.borrow_mut().clear();
        self.env.vars.borrow_mut().extend(
            self.args.iter().cloned()
                .zip(values.iter().cloned())
        );
    }
}

This enables closures:

(defn make-adder [x]
  (fn [y] (+ x y)))    ; Captures x

(def add5 (make-adder 5))
(add5 3)               ; Returns 8

Complete Example

Let’s trace through (defn square [x] (* x x)) (square 5):

1. Parse: Two top-level expressions
   ├── CallExpression("defn")
   │   ├── Symbol("square")
   │   ├── List → Symbol("x")
   │   └── CallExpression("*") → Symbol("x"), Symbol("x")
   └── CallExpression("square") → Literal(5)

2. Eval first expression (defn):
   - Create Lambda with args ["x"] and body (* x x)
   - Store in env: {square: Lambda}
   - Return NoOp

3. Eval second expression (square 5):
   - Look up "square" → Lambda
   - Evaluate argument: 5
   - Create new env: {x: 5} → parent env
   - Eval body (* x x) in new env:
     - Look up "*" → built-in multiply
     - Eval args: x → 5, x → 5
     - Call multiply([5, 5]) → 25
   - Return 25

What We Built

We now have a working Lisp interpreter with:

The interpreter is ~170 lines of Rust. The core evaluation logic is just pattern matching and recursion.

From text to tokens to tree to execution - we’ve built a complete programming language.