diff options
Diffstat (limited to 'rust/src/lambda.rs')
| -rw-r--r-- | rust/src/lambda.rs | 23 |
1 files changed, 14 insertions, 9 deletions
diff --git a/rust/src/lambda.rs b/rust/src/lambda.rs index f69fb5b..6f394d8 100644 --- a/rust/src/lambda.rs +++ b/rust/src/lambda.rs @@ -44,24 +44,29 @@ impl<'a> Default for Environment<'a> { pub fn eval_all(values: &[Value]) -> Vec<Value> { let mut env = Environment::new(); - values.iter().map(|v| eval(v, &mut env)).collect() + values.iter().map(|v| eval_whnf(v, &mut env)).collect() } -pub fn eval(arg: &Value, env: &mut Environment) -> Value { +/// Reduce the given value to weak head normal form using call-by-name +/// evaluation strategy. +/// +/// call-by-name reduces the leftmost outermost redex first, which is +/// not under a lambda abstraction. +pub fn eval_whnf(arg: &Value, env: &mut Environment) -> Value { match arg { Value::Def(var, value) => { env.bind(var, value); - Value::Bool(true) + Value::Bool(true) // TODO: return a more meaningful value? } Value::Let(var, value, expr) => { let mut newenv = env.extends(); newenv.bind(var, value); - eval(expr, &mut newenv) + eval_whnf(expr, &mut newenv) } - Value::App(l, r) => match eval(l, env) { - Value::Lam(v, body) => eval(&subst(&v, &body, r), env), + Value::App(l, r) => match eval_whnf(l, env) { + Value::Lam(v, body) => eval_whnf(&subst(&v, &body, r), env), Value::Sym(var) => match env.lookup(&var) { - Some(val) => eval(&Value::App(Box::new(val.clone()), r.clone()), env), + Some(val) => eval_whnf(&Value::App(Box::new(val.clone()), r.clone()), env), None => arg.clone(), }, other => Value::App(Box::new(other), r.clone()), @@ -96,14 +101,14 @@ fn gensym() -> String { mod lambda_test { use crate::parser::parse; - use super::{eval, eval_all, Environment, Value}; + use super::{eval_all, eval_whnf, Environment, Value}; fn parse1(string: &str) -> Value { parse(string).pop().unwrap() } fn eval1(value: &Value) -> Value { - eval(value, &mut Environment::new()) + eval_whnf(value, &mut Environment::new()) } #[test] |