Skip to content

Instantly share code, notes, and snippets.

@zypeh
Created December 14, 2020 09:12
Show Gist options
  • Save zypeh/4c39e7fc00d3fc2070d565620b5b74ed to your computer and use it in GitHub Desktop.
Save zypeh/4c39e7fc00d3fc2070d565620b5b74ed to your computer and use it in GitHub Desktop.
evaluator for untyped lambda calculus
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"))
)
)
);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment