Introduce let-expressions

1 files changed, 59 insertions, 14 deletions

diff --git a/rust/src/lambda.rs b/rust/src/lambda.rs
index 41c0c26..9d810f9 100644
--- a/rust/src/lambda.rs
+++ b/rust/src/lambda.rs
@@ -7,27 +7,56 @@ use ast::*;
 mod parser;
 use parser::*;
 
+struct Environment {
+    bindings: std::collections::HashMap<String, Value>,
+}
+
+impl Environment {
+    fn new() -> Self {
+        Environment {
+            bindings: std::collections::HashMap::new(),
+        }
+    }
+
+    fn bind(&mut self, var: &str, value: &Value) {
+        self.bindings.insert(var.to_string(), value.clone());
+    }
+}
+
 pub fn eval_file(file_name: &str) -> String {
     let content = read_to_string(file_name).unwrap();
     let values = parse(&content.to_string());
-    values
+    eval_all(&values)
         .iter()
-        .map(eval)
         .map(|v| v.to_string())
         .collect::<Vec<String>>()
         .join(" ")
 }
 
-fn eval(arg: &Value) -> Value {
+fn eval_all(values: &[Value]) -> Vec<Value> {
+    let mut env = Environment::new();
+    values.iter().map(|v| eval(v, &mut env)).collect()
+}
+
+fn eval(arg: &Value, env: &mut Environment) -> Value {
     match arg {
+        Value::Def(var, value) => {
+            env.bind(var, value);
+            Value::Bool(true)
+        }
+        Value::Let(var, value, expr) => {
+            env.bind(var, value);
+            eval(expr, env)
+        }
         Value::App(l, r) => {
-            let result = apply(&eval(l), r);
+            let result = apply(&eval(l, env), r);
             if is_reducible(&result) {
-                eval(&result)
+                eval(&result, env)
             } else {
                 result
             }
         }
+        Value::Sym(var) => env.bindings.get(var).unwrap_or(arg).clone(),
         other => other.clone(),
     }
 }
@@ -74,28 +103,32 @@ fn gensym() -> String {
 
 #[cfg(test)]
 mod lambda_test {
-    use crate::{eval, parse, Value};
+    use crate::{eval, eval_all, parse, Environment, Value};
 
     fn parse1(string: &str) -> Value {
         parse(string).pop().unwrap()
     }
 
+    fn eval1(value: &Value) -> Value {
+        eval(value, &mut Environment::new())
+    }
+
     #[test]
     fn evaluating_a_non_reducible_value_yields_itself() {
         let value = parse1("(foo 12)");
-        assert_eq!(value, eval(&value));
+        assert_eq!(value, eval1(&value));
     }
 
     #[test]
     fn evaluating_application_on_an_abstraction_reduces_it() {
         let value = parse1("((lam x x) 12)");
-        assert_eq!(Value::Num(12), eval(&value));
+        assert_eq!(Value::Num(12), eval1(&value));
     }
 
     #[test]
     fn substitution_occurs_within_abstraction_body() {
         let value = parse1("(((lam x (lam y x)) 13) 12)");
-        assert_eq!(Value::Num(13), eval(&value));
+        assert_eq!(Value::Num(13), eval1(&value));
     }
 
     #[test]
@@ -103,32 +136,44 @@ mod lambda_test {
         let value = parse1("(((lam x (lam y (y x))) 13) 12)");
         assert_eq!(
             Value::App(Box::new(Value::Num(12)), Box::new(Value::Num(13))),
-            eval(&value)
+            eval1(&value)
         );
     }
 
     #[test]
     fn substitution_does_not_capture_free_variables() {
         let value = parse1("(((lam x (lam x x)) 13) 12)");
-        assert_eq!(Value::Num(12), eval(&value));
+        assert_eq!(Value::Num(12), eval1(&value));
     }
 
     #[test]
     fn interpretation_applies_to_both_sides_of_application() {
         let value = parse1("((lam x x) ((lam x x) 12))");
-        assert_eq!(Value::Num(12), eval(&value));
+        assert_eq!(Value::Num(12), eval1(&value));
     }
 
     #[test]
     fn reduction_is_applied_until_normal_form_is_reached() {
         let value = parse1("((((lam y (lam x (lam y (x y)))) 13) (lam x x)) 11)");
-        assert_eq!(Value::Num(11), eval(&value));
+        assert_eq!(Value::Num(11), eval1(&value));
     }
 
     #[test]
     fn reduction_always_select_leftmost_outermost_redex() {
         // this should not terminate if we evaluate the rightmost redex first
         let value = parse1("((lam x 1) ((lam x (x x)) (lam x (x x))))");
-        assert_eq!(Value::Num(1), eval(&value));
+        assert_eq!(Value::Num(1), eval1(&value));
+    }
+
+    #[test]
+    fn defined_symbols_are_evaluated_to_their_definition() {
+        let values = parse("(def foo 12)  foo");
+        assert_eq!(vec![Value::Bool(true), Value::Num(12)], eval_all(&values));
+    }
+
+    #[test]
+    fn let_expressions_bind_symbol_to_expression_in_environment() {
+        let values = parse("(let (foo (lam x x))  (foo 12))");
+        assert_eq!(vec![Value::Num(12)], eval_all(&values));
     }
 }