Simplify eval() to match WHNF definition

1 files changed, 10 insertions, 38 deletions

diff --git a/rust/src/lambda.rs b/rust/src/lambda.rs
index 2586de6..f69fb5b 100644
--- a/rust/src/lambda.rs
+++ b/rust/src/lambda.rs
@@ -34,14 +34,6 @@ impl<'a> Environment<'a> {
             None => None,
         })
     }
-
-    fn binds(&self, s: &str) -> bool {
-        self.bindings.contains_key(s)
-            || match *self.parent {
-                Some(parent) => parent.binds(s),
-                None => false,
-            }
-    }
 }
 
 impl<'a> Default for Environment<'a> {
@@ -66,40 +58,19 @@ pub fn eval(arg: &Value, env: &mut Environment) -> Value {
             newenv.bind(var, value);
             eval(expr, &mut newenv)
         }
-        Value::App(l, r) => {
-            let result = apply(&eval(l, env), r);
-            if is_reducible(&result, env) {
-                eval(&result, env)
-            } else {
-                result
-            }
-        }
+        Value::App(l, r) => match eval(l, env) {
+            Value::Lam(v, body) => eval(&subst(&v, &body, r), env),
+            Value::Sym(var) => match env.lookup(&var) {
+                Some(val) => eval(&Value::App(Box::new(val.clone()), r.clone()), env),
+                None => arg.clone(),
+            },
+            other => Value::App(Box::new(other), r.clone()),
+        },
         Value::Sym(var) => env.lookup(var).unwrap_or(arg).clone(),
         other => other.clone(),
     }
 }
 
-fn is_reducible(result: &Value, env: &Environment) -> bool {
-    match result {
-        Value::App(l, r) => match **l {
-            Value::Lam(_, _) => true,
-            _ => is_reducible(l, env) || is_reducible(r, env),
-        },
-        Value::Let(_, _, _) => true,
-        Value::Sym(s) => env.binds(s),
-        Value::Lam(_, _) => false,
-        _ => false,
-    }
-}
-
-fn apply(l: &Value, r: &Value) -> Value {
-    if let Value::Lam(v, body) = l {
-        subst(v, body, r)
-    } else {
-        Value::App(Box::new(l.clone()), Box::new(r.clone()))
-    }
-}
-
 fn subst(var: &str, body: &Value, e: &Value) -> Value {
     match body {
         Value::Sym(x) if x == var => e.clone(),
@@ -182,7 +153,8 @@ mod lambda_test {
 
     #[test]
     fn reduction_always_select_leftmost_outermost_redex() {
-        // this should not terminate if we evaluate the rightmost redex first
+        // this should not terminate if we evaluate the rightmost redex first, eg.
+        // applicative order reduction
         let value = parse1("((lam x 1) ((lam x (x x)) (lam x (x x))))");
         assert_eq!(Value::Num(1), eval1(&value));
     }