evaluator for untyped lambda calculus

evaluator.rs

use std::boxed::Box;

#[derive(Clone, Debug)]
enum Expr {
    VAR(String),
    APP { func: Box<Expr>, arg: Box<Expr> },
    LAM { arg: String, body: Box<Expr> },
}

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

#[derive(Clone, Debug)]
enum Val {
    Var(String),
    App { func: Box<Val>, arg: Box<Val> },
    Lam(Closure),
}

#[derive(Clone, Debug)]
struct Closure {
    arg: String,
    env: Env,
    body: Expr,
}

fn lookup(env: &Env, key: String) -> Val {
    let e = env.to_vec();
    match e.into_iter().find(|(k, _)| *k == key) {
        None => panic!("key {:?}, not found in environment {:?}", key, env),
        Some((_, v)) => v
    }
}

fn apply_closure(cl: Closure, val: Val) -> Val {
    let mut env = cl.env.to_vec();
    let mut new_env = vec![(cl.arg, val)];

    new_env.append(&mut env);
    eval(&new_env, cl.body)
}

// fn fresh_names(names: Vec<String>, name: String) -> String {
//     if name == "_" { String::from("_") } else {
//         match names.into_iter().find(|x| *x == name) {
//             None => name,
//             Some(x) => x + "'"
//         }
//     }
// }

fn eval(e: &Env, expr: Expr) -> Val {
    match expr {
        Expr::VAR(s) => lookup(e, s),
        Expr::LAM { arg, body } => Val::Lam(Closure { arg, body: *body, env: e.to_vec() }),
        Expr::APP { func, arg } => {
            match (eval(e, *func), eval(e, *arg)) {
                (Val::Lam(cl), u) => apply_closure(cl, u),
                (t, u) => Val::App { func: Box::new(t), arg: Box::new(u)}
            }
        },
    }
}

// Some helper here
fn var(s: &str) -> Expr { Expr::VAR(s.to_owned()) }
fn app(func: Expr, arg: Expr) -> Expr { Expr::APP { func: Box::new(func), arg: Box::new(arg) } }
fn lam(arg: &str, body: Expr) -> Expr { Expr::LAM { arg: arg.to_owned(), body: Box::new(body) } }

fn main() {
    print!("{:?}",
        eval(
            &vec![], app(
                lam("a", var("a")),
                lam("x", var("x"))
            )
        )
    );
}