4 files changed, 22 insertions, 1 deletions
diff --git a/rust/Cargo.lock b/rust/Cargo.lock
index 66cad99..46be018 100644
--- a/rust/Cargo.lock
+++ b/rust/Cargo.lock
@@ -217,6 +217,7 @@ name = "rust"
 version = "0.1.0"
 dependencies = [
  "proptest",
+ "rand",
 ]
 
 [[package]]
diff --git a/rust/Cargo.toml b/rust/Cargo.toml
index 7aa1a6f..bb52045 100644
--- a/rust/Cargo.toml
+++ b/rust/Cargo.toml
@@ -4,6 +4,7 @@ version = "0.1.0"
 edition = "2021"
 
 [dependencies]
+rand = "0.8.5"
 
 [dev-dependencies]
 proptest = "1.0.0"
diff --git a/rust/sample/test_full.txt b/rust/sample/test_full.txt
index 253c752..ece76b8 100644
--- a/rust/sample/test_full.txt
+++ b/rust/sample/test_full.txt
@@ -1 +1 @@
-((lam x x) true)
+(((lam x (lam x x)) 13) true)
diff --git a/rust/src/lambda.rs b/rust/src/lambda.rs
index d767003..0080f63 100644
--- a/rust/src/lambda.rs
+++ b/rust/src/lambda.rs
@@ -1,3 +1,4 @@
+use rand::Rng;
 use std::fs::read_to_string;
 
 mod ast;
@@ -32,12 +33,24 @@ fn apply(l: &Value, r: &Value) -> Value {
 fn subst(var: &str, body: &Value, e: &Value) -> Value {
     match body {
         Value::Sym(x) if x == var => e.clone(),
+        Value::Lam(x, b) if x == var => {
+            let y = gensym();
+            let bd = subst(x, b, &Value::Sym(y.clone()));
+            Value::Lam(y, Box::new(bd))
+        }
         Value::Lam(x, b) => Value::Lam(x.to_string(), Box::new(subst(var, b, e))),
         Value::App(l, r) => Value::App(Box::new(subst(var, l, e)), Box::new(subst(var, r, e))),
         other => other.clone(),
     }
 }
 
+fn gensym() -> String {
+    let mut rng = rand::thread_rng();
+
+    let n1: u8 = rng.gen();
+    format!("x_{}", n1)
+}
+
 #[cfg(test)]
 mod lambda_test {
     use crate::{interpret, parse, Value};
@@ -68,4 +81,10 @@ mod lambda_test {
             interpret(&value)
         );
     }
+
+    #[test]
+    fn substitution_does_not_capture_free_variables() {
+        let value = parse("(((lam x (lam x x)) 13) 12)");
+        assert_eq!(Value::Num(12), interpret(&value));
+    }
 }