Introduce let-expressions

3 files changed, 95 insertions, 14 deletions

diff --git a/rust/src/ast.rs b/rust/src/ast.rs
index 8729fa2..2221856 100644
--- a/rust/src/ast.rs
+++ b/rust/src/ast.rs
@@ -8,6 +8,7 @@ pub enum Value {
     App(Box<Value>, Box<Value>),
     Lam(String, Box<Value>),
     Def(String, Box<Value>),
+    Let(String, Box<Value>, Box<Value>),
 }
 
 impl Display for Value {
@@ -19,6 +20,7 @@ impl Display for Value {
             Value::App(l, r) => write!(f, "({} {})", l, r),
             Value::Lam(var, body) => write!(f, "(lam {} {})", var, body),
             Value::Def(var, value) => write!(f, "(def {} {})", var, value),
+            Value::Let(var, value, body) => write!(f, "(let ({} {}) {})", var, value, body),
         }
     }
 }
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));
     }
 }
diff --git a/rust/src/parser.rs b/rust/src/parser.rs
index d733008..b065ec3 100644
--- a/rust/src/parser.rs
+++ b/rust/src/parser.rs
@@ -7,6 +7,7 @@ enum Token {
     Lambda,
     Word(String),
     Define,
+    Let,
 }
 
 #[derive(Debug)]
@@ -84,6 +85,7 @@ fn parse_definition(parser: &mut Parser) -> Result<Value, String> {
 
 fn parse_expression(parser: &mut Parser) -> Result<Value, String> {
     parse_abstraction(parser)
+        .or_else(|_| parse_let(parser))
         .or_else(|_| parse_application(parser))
         .or_else(|_| parse_value(parser))
 }
@@ -105,6 +107,21 @@ fn parse_variable(parser: &mut Parser) -> Result<String, String> {
     Ok(var)
 }
 
+fn parse_let(parser: &mut Parser) -> Result<Value, String> {
+    parser.expect(Token::LParen)?;
+    parser.expect(Token::Let).map_err(|e| {
+        parser.backtrack();
+        e.to_string()
+    })?;
+    parser.expect(Token::LParen)?;
+    let var = parse_variable(parser)?;
+    let body = parse_expression(parser)?;
+    parser.expect(Token::RParen)?;
+    let expr = parse_expression(parser)?;
+    parser.expect(Token::RParen)?;
+    Ok(Value::Let(var, Box::new(body), Box::new(expr)))
+}
+
 fn parse_application(parser: &mut Parser) -> Result<Value, String> {
     parser.expect(Token::LParen)?;
     let left = parse_expression(parser)?;
@@ -151,6 +168,8 @@ fn terminate(result: &mut Vec<Token>, word: &mut String) {
             result.push(Token::Lambda);
         } else if w == "def" {
             result.push(Token::Define);
+        } else if w == "let" {
+            result.push(Token::Let);
         } else {
             result.push(Token::Word(w));
         }
@@ -284,6 +303,18 @@ mod tests {
         assert_eq!(vec![Sym("foo".to_string()), Num(42)], parse("foo 42"));
     }
 
+    #[test]
+    fn parse_let_expressions() {
+        assert_eq!(
+            vec![Value::Let(
+                "x".to_string(),
+                Box::new(Num(12)),
+                Box::new(Sym("x".to_string()))
+            )],
+            parse("(let (x 12) x)")
+        );
+    }
+
     impl Arbitrary for Value {
         type Parameters = ();
         type Strategy = BoxedStrategy<Self>;
@@ -300,6 +331,9 @@ mod tests {
                 prop_oneof![
                     (inner.clone(), inner.clone()).prop_map(|(l, r)| App(Box::new(l), Box::new(r))),
                     (identifier, inner.clone()).prop_map(|(var, body)| Lam(var, Box::new(body))),
+                    (identifier, inner.clone(), inner.clone()).prop_map(|(var, body, expr)| {
+                        Value::Let(var, Box::new(body), Box::new(expr))
+                    }),
                 ]
             });
             prop_oneof![