079 Expert

079 — Lambda Calculus Interpreter

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "079 — Lambda Calculus Interpreter" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. Implement a small-step interpreter for a minimal lambda calculus with integers, variables, lambda abstraction, function application, and addition. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Implement a small-step interpreter for a minimal lambda calculus with integers, variables, lambda abstraction, function application, and addition. The interpreter evaluates Expr trees against an environment, returning Value (integer or closure) — and compare the implementation with OCaml's natural match-based interpreter.

🎯 Learning Outcomes

• Represent recursive expression trees using Box<Expr> for heap allocation

• Use Result<Value, String> for interpreter errors (unbound variable, type error)

• Understand why closures capture environments by clone in this design

• Trace evaluation of beta reduction through pattern matching on VClosure

• Map Rust's enum + Box ADT to OCaml's native recursive algebraic types

• Appreciate when Rc<Expr> would avoid deep clones in shared subtrees

Code Example

#![allow(clippy::all)]
/// 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());
    }
}

(* 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

Key Differences

Aspect	Rust	OCaml
Recursive types	`Box<Expr>` required	Native recursive ADT
Environment	`Vec<(String, Value)>` cloned	`(string * value) list` shared
Closure capture	Explicit `.clone()` of env	Implicit value copy
Error handling	`Result<Value, String>`	`failwith` (exception)
Lookup	`.iter().rev().find()`	`List.assoc`
Code length	~60 lines	~20 lines

The fundamental logic is identical: match on the expression, recurse on sub-expressions, extend the environment for beta reduction. Rust's verbosity comes from explicit heap management and typed error propagation rather than any semantic difference.

OCaml Approach

OCaml's native recursive types require no Box: type expr = Int of int | Lam of string * expr | …. The interpreter is a single let rec eval env = function with four cases. Closure creation captures the current env as an association list (a list value, so structural sharing is free). Variable lookup uses List.assoc. The OCaml version is terser because recursive types need no heap annotation, and closures capture by value naturally. Both implementations share the same logical structure.

Full Source

#![allow(clippy::all)]
/// 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());
    }
}

(* 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

✓ Tests Rust test suite

#[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());
    }
}

Deep 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

Exercises

Add a Let(String, Box<Expr>, Box<Expr>) variant representing let x = e1 in e2, and implement its evaluation as syntactic sugar for App(Lam(x, e2), e1).

Add a Bool(bool) value type and an If(Box<Expr>, Box<Expr>, Box<Expr>) expression with evaluation.

Replace the Vec<(String, Value)> environment with std::collections::HashMap<String, Value> and benchmark the difference on deeply nested environments.

Implement call-by-name semantics: instead of evaluating the argument before passing it, pass the unevaluated Expr and evaluate only when a Var is looked up.

In OCaml, add a Fix (fixed-point combinator) expression to support recursion without a separate let rec and verify it can compute factorial.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust