[wip] generate nested terms through pairing function

3 files changed, 46 insertions, 4 deletions

diff --git a/rust/src/ast.rs b/rust/src/ast.rs
index 29d548f..cfc0e40 100644
--- a/rust/src/ast.rs
+++ b/rust/src/ast.rs
@@ -88,10 +88,6 @@ mod ast_tests {
     use proptest::collection::vec;
     use proptest::prelude::*;
 
-    fn any_sym() -> impl Strategy<Value = Value> {
-        identifier().prop_map(Sym)
-    }
-
     proptest! {
 
        #[test]
diff --git a/rust/src/lambda.rs b/rust/src/lambda.rs
index ee5cb1f..3a8372b 100644
--- a/rust/src/lambda.rs
+++ b/rust/src/lambda.rs
@@ -117,6 +117,11 @@ pub fn generate_expr(size: u32, runner: &mut TestRunner) -> Value {
         6 => simple_lambda().new_tree(runner).unwrap().current(),
         7 => app_to_lambda().new_tree(runner).unwrap().current(),
         8 => multi_app().new_tree(runner).unwrap().current(),
+        9 => any::<u16>()
+            .prop_flat_map(gen_terms)
+            .new_tree(runner)
+            .unwrap()
+            .current(),
         _ => todo!(),
     }
 }
@@ -157,6 +162,34 @@ fn app_to_lambda() -> impl Strategy<Value = Value> {
     (lam, arg).prop_map(|(l, a)| Value::App(Box::new(l), Box::new(a)))
 }
 
+fn pairing(k: u16) -> (u16, u16) {
+    let a = ((((8 * (k as u32) + 1) as f32).sqrt() - 1.0) / 2.0).floor();
+    let b = (a * (a + 1.0)) / 2.0;
+    let n = (k as f32) - b;
+    (n as u16, (a - n) as u16)
+}
+
+fn gen_terms(u: u16) -> impl Strategy<Value = Value> {
+    if u % 2 != 0 {
+        let j = (u - 1) / 2;
+        if j % 2 == 0 {
+            let k = j / 2;
+            let (n, m) = pairing(k);
+            let r = (gen_terms(n), gen_terms(m))
+                .prop_map(move |(l, r)| Value::App(Box::new(l), Box::new(r)));
+            r.boxed()
+        } else {
+            let k = (j - 1) / 2;
+            let (n, m) = pairing(k);
+            let r = gen_terms(m).prop_map(move |v| Value::Lam(format!("x_{}", n), Box::new(v)));
+            r.boxed()
+        }
+    } else {
+        let j = u / 2;
+        Just(Value::Sym(format!("x_{}", j))).boxed()
+    }
+}
+
 #[cfg(test)]
 mod lambda_test {
     use crate::parser::parse;
diff --git a/rust/src/web.rs b/rust/src/web.rs
index 8fa9452..f676b3c 100644
--- a/rust/src/web.rs
+++ b/rust/src/web.rs
@@ -489,6 +489,19 @@ mod app_tests {
     }
 
     #[test]
+    async fn client_generates_more_complex_terms_at_level_9() {
+        let mut client = client();
+        client.grade = 9;
+
+        let (input, _) = client.generate_expr();
+
+        let parsed = parse(&input);
+        match &parsed[..] {
+            _ => panic!("Expected term, got {:?}", parsed),
+        }
+    }
+
+    #[test]
     async fn client_increases_grade_on_successful_test() {
         let mut client = client();
         let expected = "1".to_string();