079: Lambda Calculus Interpreter

Difficulty: 4 Level: Advanced Evaluate a minimal functional language — closures, application, and environments — using Rust enums.

The Problem This Solves

Every time you write a function in any language, you're using lambda calculus. Understanding how to implement it is the foundation for: building your own scripting language, understanding how closures capture environments in Rust and OCaml, and seeing why garbage collection and ownership interact with closures in fundamentally different ways. This example implements a tiny lambda calculus with integers, variables, lambda abstraction (`\x -> body`), function application, and addition. The interpreter uses an environment model (a list of variable bindings) to evaluate expressions. When a lambda is created, it captures the current environment — that's what makes it a closure. The practical applications are immediate: embedded DSLs for rule engines, configuration languages, and formula evaluators all reduce to this pattern.

The Intuition

Lambda calculus has three constructs:

Variable: `x` — look up a name in the environment
Abstraction: `\x -> body` — create a function that takes `x` and returns `body`
Application: `f arg` — call function `f` with argument `arg`

Everything else (booleans, numbers, pairs, lists) can be encoded in pure lambda calculus using Church encoding — but for a practical interpreter we add integers and addition directly. The environment is a list of `(name, value)` pairs. Looking up a variable means scanning the list from the end (most recent binding wins — this handles `let`-like shadowing). When a lambda is created, it captures a snapshot of the current environment. This snapshot becomes part of the closure's value. The key ownership question: when you create a closure `\x -> x + y` in an environment where `y = 5`, you need to store that `y = 5` binding inside the closure. In OCaml, the garbage collector manages this — the environment is shared by reference. In Rust, the closure owns a clone of the environment. This means creating closures is O(n) in the environment size — a trade-off for memory safety without GC.

How It Works in Rust

#[derive(Clone, Debug, PartialEq)]
pub enum Expr {
 Int(i64),
 Var(String),
 Lam(String, Box<Expr>),        // Box: recursive type must have known size
 App(Box<Expr>, Box<Expr>),
 Add(Box<Expr>, Box<Expr>),
}

#[derive(Clone, Debug, PartialEq)]
pub enum Value {
 VInt(i64),
 VClosure(String, Box<Expr>, Env),  // closure captures its environment
}

type Env = Vec<(String, Value)>;       // association list: [(name, value)]

The interpreter — each arm returns a `Result<Value, String>` for error handling:

pub fn eval(env: &Env, expr: &Expr) -> Result<Value, String> {
 match expr {
     Expr::Int(n) => Ok(Value::VInt(*n)),

     Expr::Var(x) => env.iter().rev()  // scan from end (most recent binding first)
         .find(|(k, _)| k == x)
         .map(|(_, v)| v.clone())
         .ok_or_else(|| format!("unbound variable: {}", x)),

     // Lam: capture the current environment — this is the closure
     Expr::Lam(x, body) => Ok(Value::VClosure(x.clone(), body.clone(), env.clone())),

     // App: evaluate function, evaluate argument, extend the closure's environment
     Expr::App(f, arg) => {
         let fv = eval(env, f)?;
         let av = eval(env, arg)?;
         match fv {
             Value::VClosure(x, body, mut cenv) => {
                 cenv.push((x, av));     // bind the argument in the closure's env
                 eval(&cenv, &body)      // evaluate body in extended environment
             }
             _ => Err("not a function".into()),
         }
     }

     Expr::Add(a, b) => match (eval(env, a)?, eval(env, b)?) {
         (Value::VInt(x), Value::VInt(y)) => Ok(Value::VInt(x + y)),
         _ => Err("type error in add".into()),
     },
 }
}

Example: applying the identity function `(\x -> x) 42`:

let identity_app = Expr::App(
 Box::new(Expr::Lam("x".into(), Box::new(Expr::Var("x".into())))),
 Box::new(Expr::Int(42)),
);
assert_eq!(eval(&vec![], &identity_app), Ok(Value::VInt(42)));

What This Unlocks

Embedding DSLs: this pattern is the core of every rule engine, formula evaluator, and scripting language embedded in Rust applications.
Understanding closures: see exactly how closures capture environments — the `env.clone()` in `Lam` makes the capture concrete and visible.
Foundation for type checkers: add a type annotation field to `Expr` and a `type_check` function alongside `eval` — you now have a typed lambda calculus.

Key Differences

Concept	OCaml	Rust
Recursive types	`type expr = Lam of string * expr` — allowed directly	Requires `Box<Expr>` to give the enum a finite size
Closure capture	Environment shared by reference (GC)	`env.clone()` — full copy at closure creation time
Variable lookup	`List.assoc` (raises `Not_found`)	`iter().rev().find()` + `.ok_or_else()`
Error handling	Exceptions (`Not_found`, custom)	`Result<Value, String>` + `?` operator
Sharing expression trees	`Gc` or `Rc` for sharing subtrees	`Box` owns exclusively; use `Rc<Expr>` for sharing

/// Simple Lambda Calculus Interpreter
///
/// Ownership insight: The expression tree uses Box for recursive types.
/// Environments clone values because closures capture their environment.

#[derive(Clone, Debug, PartialEq)]
pub enum Expr {
    Int(i64),
    Var(String),
    Lam(String, Box<Expr>),
    App(Box<Expr>, Box<Expr>),
    Add(Box<Expr>, Box<Expr>),
}

#[derive(Clone, Debug, PartialEq)]
pub enum Value {
    VInt(i64),
    VClosure(String, Box<Expr>, Env),
}

type Env = Vec<(String, Value)>;

/// Evaluate an expression in an environment
/// Ownership: env is cloned when creating closures (capturing environment)
pub fn eval(env: &Env, expr: &Expr) -> Result<Value, String> {
    match expr {
        Expr::Int(n) => Ok(Value::VInt(*n)),
        Expr::Var(x) => env
            .iter()
            .rev()
            .find(|(k, _)| k == x)
            .map(|(_, v)| v.clone())
            .ok_or_else(|| format!("unbound variable: {}", x)),
        Expr::Lam(x, body) => Ok(Value::VClosure(x.clone(), body.clone(), env.clone())),
        Expr::App(f, arg) => {
            let fv = eval(env, f)?;
            let av = eval(env, arg)?;
            match fv {
                Value::VClosure(x, body, mut cenv) => {
                    cenv.push((x, av));
                    eval(&cenv, &body)
                }
                _ => Err("not a function".into()),
            }
        }
        Expr::Add(a, b) => match (eval(env, a)?, eval(env, b)?) {
            (Value::VInt(x), Value::VInt(y)) => Ok(Value::VInt(x + y)),
            _ => Err("type error in add".into()),
        },
    }
}

/// Version 2: Using Rc for shared expression trees (avoids deep clones)
/// In production, you'd use Rc<Expr> to share subtrees.

#[cfg(test)]
mod tests {
    use super::*;

    fn int(n: i64) -> Expr { Expr::Int(n) }
    fn var(s: &str) -> Expr { Expr::Var(s.into()) }
    fn lam(s: &str, body: Expr) -> Expr { Expr::Lam(s.into(), Box::new(body)) }
    fn app(f: Expr, a: Expr) -> Expr { Expr::App(Box::new(f), Box::new(a)) }
    fn add(a: Expr, b: Expr) -> Expr { Expr::Add(Box::new(a), Box::new(b)) }

    #[test]
    fn test_integer() {
        assert_eq!(eval(&vec![], &int(42)), Ok(Value::VInt(42)));
    }

    #[test]
    fn test_identity() {
        // (\x -> x) 42
        let e = app(lam("x", var("x")), int(42));
        assert_eq!(eval(&vec![], &e), Ok(Value::VInt(42)));
    }

    #[test]
    fn test_add() {
        // (\x -> x + 1) 41
        let e = app(lam("x", add(var("x"), int(1))), int(41));
        assert_eq!(eval(&vec![], &e), Ok(Value::VInt(42)));
    }

    #[test]
    fn test_nested_lambda() {
        // (\x -> \y -> x + y) 10 32
        let e = app(app(lam("x", lam("y", add(var("x"), var("y")))), int(10)), int(32));
        assert_eq!(eval(&vec![], &e), Ok(Value::VInt(42)));
    }

    #[test]
    fn test_unbound_var() {
        assert!(eval(&vec![], &var("x")).is_err());
    }
}

fn main() {
    println!("{:?}", eval(&vec![], &int(42)), Ok(Value::VInt(42)));
    println!("{:?}", eval(&vec![], &e), Ok(Value::VInt(42)));
    println!("{:?}", eval(&vec![], &e), Ok(Value::VInt(42)));
}

(* Interpreter — Simple Lambda Calculus *)

type expr =
  | Int of int | Var of string
  | Lam of string * expr | App of expr * expr
  | Add of expr * expr

type value = VInt of int | VClosure of string * expr * env
and env = (string * value) list

(* Version 1: Direct recursive interpreter *)
let rec eval env = function
  | Int n -> VInt n
  | Var x -> List.assoc x env
  | Lam (x, body) -> VClosure (x, body, env)
  | App (f, arg) ->
    let fv = eval env f in
    let av = eval env arg in
    (match fv with
     | VClosure (x, body, cenv) -> eval ((x, av) :: cenv) body
     | _ -> failwith "not a function")
  | Add (a, b) ->
    (match eval env a, eval env b with
     | VInt x, VInt y -> VInt (x + y)
     | _ -> failwith "type error")

let () =
  let e = App (Lam ("x", Add (Var "x", Int 1)), Int 41) in
  match eval [] e with VInt n -> assert (n = 42) | _ -> assert false

📊 Detailed Comparison

Lambda Calculus Interpreter — Comparison

Core Insight

Building an interpreter reveals the fundamental difference in how OCaml and Rust handle recursive data and environment capture. OCaml's GC allows free sharing of environments; Rust requires explicit `Box` for recursion and `clone()` for environment capture.

OCaml Approach

`type expr = Int of int | Lam of string * expr | ...` — recursive variants, no boxing needed
`type value = VClosure of string expr env` — closures capture environment by reference (GC)
`List.assoc` for environment lookup
Pattern matching on nested variants is concise

Rust Approach

`enum Expr { Lam(String, Box<Expr>), ... }` — `Box` required for recursive types
`Value::VClosure(String, Box<Expr>, Env)` — environment must be cloned
`env.iter().rev().find()` for lookup (last binding wins)
`Result<Value, String>` for error handling vs OCaml exceptions

Comparison Table

Aspect	OCaml	Rust
Recursive types	Direct	Requires `Box<T>`
Environment	Shared via GC	Cloned on capture
Error handling	`failwith` exception	`Result<T, E>`
Lookup	`List.assoc`	`.iter().rev().find()`
Memory	GC collects cycles	Ownership prevents cycles

Learner Notes

`Box<Expr>` is the Rust idiom for recursive enum variants
Cloning environments is the cost of no-GC; consider `Rc` for sharing
OCaml `and` keyword for mutually recursive types; Rust just uses the type name
Helper constructors (`fn int(n)`, `fn app(f, a)`) make test code readable