From 778881eda5b0955fb4c845fb29097f048491f007 Mon Sep 17 00:00:00 2001
From: Arnaud Bailly <arnaud.bailly@iohk.io>
Date: Wed, 25 Sep 2024 14:11:41 +0200
Subject: Let creates a new environment

---
 rust/src/lambda.rs | 56 +++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 45 insertions(+), 11 deletions(-)

(limited to 'rust/src/lambda.rs')

diff --git a/rust/src/lambda.rs b/rust/src/lambda.rs
index 9d810f9..97b6f08 100644
--- a/rust/src/lambda.rs
+++ b/rust/src/lambda.rs
@@ -1,5 +1,5 @@
 use rand::Rng;
-use std::fs::read_to_string;
+use std::{collections::HashMap, fs::read_to_string};
 
 mod ast;
 use ast::*;
@@ -7,20 +7,45 @@ use ast::*;
 mod parser;
 use parser::*;
 
-struct Environment {
-    bindings: std::collections::HashMap<String, Value>,
+#[derive(Debug, PartialEq)]
+struct Environment<'a> {
+    parent: Box<Option<&'a Environment<'a>>>,
+    bindings: HashMap<String, Value>,
 }
 
-impl Environment {
+impl<'a> Environment<'a> {
     fn new() -> Self {
         Environment {
-            bindings: std::collections::HashMap::new(),
+            parent: Box::new(None),
+            bindings: HashMap::new(),
         }
     }
 
     fn bind(&mut self, var: &str, value: &Value) {
         self.bindings.insert(var.to_string(), value.clone());
     }
+
+    fn extends(&'a self) -> Self {
+        Environment {
+            parent: Box::new(Some(self)),
+            bindings: HashMap::new(),
+        }
+    }
+
+    fn lookup(&self, var: &str) -> Option<&Value> {
+        self.bindings.get(var).or_else(|| match *self.parent {
+            Some(parent) => parent.lookup(var),
+            None => None,
+        })
+    }
+
+    fn binds(&self, s: &str) -> bool {
+        self.bindings.contains_key(s)
+            || match *self.parent {
+                Some(parent) => parent.binds(s),
+                None => false,
+            }
+    }
 }
 
 pub fn eval_file(file_name: &str) -> String {
@@ -45,28 +70,31 @@ fn eval(arg: &Value, env: &mut Environment) -> Value {
             Value::Bool(true)
         }
         Value::Let(var, value, expr) => {
-            env.bind(var, value);
-            eval(expr, env)
+            let mut newenv = env.extends();
+            newenv.bind(var, value);
+            eval(expr, &mut newenv)
         }
         Value::App(l, r) => {
             let result = apply(&eval(l, env), r);
-            if is_reducible(&result) {
+            if is_reducible(&result, env) {
                 eval(&result, env)
             } else {
                 result
             }
         }
-        Value::Sym(var) => env.bindings.get(var).unwrap_or(arg).clone(),
+        Value::Sym(var) => env.lookup(var).unwrap_or(arg).clone(),
         other => other.clone(),
     }
 }
 
-fn is_reducible(result: &Value) -> bool {
+fn is_reducible(result: &Value, env: &Environment) -> bool {
     match result {
         Value::App(l, r) => match **l {
             Value::Lam(_, _) => true,
-            _ => is_reducible(l) || is_reducible(r),
+            _ => is_reducible(l, env) || is_reducible(r, env),
         },
+        Value::Let(_, _, _) => true,
+        Value::Sym(s) => env.binds(s),
         Value::Lam(_, _) => false,
         _ => false,
     }
@@ -176,4 +204,10 @@ mod lambda_test {
         let values = parse("(let (foo (lam x x))  (foo 12))");
         assert_eq!(vec![Value::Num(12)], eval_all(&values));
     }
+
+    #[test]
+    fn let_expressions_introduce_new_scope_for_bindings() {
+        let values = parse("(let (foo (lam x x)) ((let (foo foo) foo) 13))");
+        assert_eq!(vec![Value::Num(13)], eval_all(&values));
+    }
 }
-- 
cgit v1.2.3