Recursion working oh yes

5 files changed, 164 insertions, 39 deletions

diff --git a/Cargo.toml b/Cargo.toml
index 0866d42..9ad0a2b 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.1.0"
 edition = "2021"
 
 [features]
-reduce_debug = []
+debug = []
 
 # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
 
diff --git a/samples/sample1.code b/samples/sample1.code
index a675849..168421b 100644
--- a/samples/sample1.code
+++ b/samples/sample1.code
@@ -1,18 +1,14 @@
-# result =
-#     bool.to-string
-#         (int.eq? 2 2);
+triangle n = int.eq? n 1
+        1
+        (int.add
+            n
+            (triangle (int.sub n 1)));
 
-# string.eq? result "true";
+triangle 500;
 
-# string.eq?
-#     (bool.to-string
-#         (int.eq? 2 2))
-#     "true";
+# factorial n =
+#     int.eq? n 0
+#         1
+#         (int.mul n (factorial (int.sub n 1)));
 
-# string.eq?
-#     (bool.to-string
-#         (int.eq? 2 2));
-
-string.eq?
-    (bool.to-string
-        true);
+# factorial 20;
\ No newline at end of file
diff --git a/src/builtins.rs b/src/builtins.rs
index d0f5788..390a213 100644
--- a/src/builtins.rs
+++ b/src/builtins.rs
@@ -84,8 +84,11 @@ pub fn make_identity_function() -> Term {
 }
 
 pub const B_INTEGER_EQ: &str = "int.eq?";
-pub const B_INTEGER_INCREMENT: &str = "int.increment";
+pub const B_INTEGER_INCREMENT: &str = "int.inc";
 pub const B_INTEGER_ADD: &str = "int.add";
+pub const B_INTEGER_SUBTRACT: &str = "int.sub";
+pub const B_INTEGER_MULTIPLY: &str = "int.mul";
+pub const B_INTEGER_DIVIDE: &str = "int.div";
 pub const B_STRING_EQ: &str = "string.eq?";
 pub const B_BOOL_TO_STRING: &str = "bool.to-string";
 
@@ -97,6 +100,9 @@ pub fn try_ast_symbol_to_builtin_term(symbol: &ast::Symbol) -> Option<Term> {
         B_INTEGER_EQ => Builtin::new(B_INTEGER_EQ, 2),
         B_INTEGER_INCREMENT => Builtin::new(B_INTEGER_INCREMENT, 1),
         B_INTEGER_ADD => Builtin::new(B_INTEGER_ADD, 2),
+        B_INTEGER_SUBTRACT => Builtin::new(B_INTEGER_SUBTRACT, 2),
+        B_INTEGER_MULTIPLY => Builtin::new(B_INTEGER_MULTIPLY, 2),
+        B_INTEGER_DIVIDE => Builtin::new(B_INTEGER_DIVIDE, 2),
         B_STRING_EQ => Builtin::new(B_STRING_EQ, 2),
         B_BOOL_TO_STRING => Builtin::new(B_BOOL_TO_STRING, 1),
         _ => return None,
@@ -130,7 +136,46 @@ pub fn evaluate_builtin(builtin: &Builtin, rhs: Rc<Term>) -> Result<(Rc<Term>, u
                 2 => Term::Builtin(builtin.bind_arg(primitive)),
                 1 => {
                     let other_value = extract_enum_value!(&builtin.arguments[0], Value::Integer(other_value) => other_value);
-                    Term::Primitive(Value::Integer(value + other_value))
+                    Term::Primitive(Value::Integer(other_value + value))
+                }
+                _ => return argument_n_error(builtin.identifier, builtin.n_arguments),
+            },
+            Term::Primitive(_) => return argument_type_error(builtin.identifier, &*rhs),
+            _ => return Ok((Rc::new(Term::Builtin(builtin.clone())), 0)),
+        },
+        B_INTEGER_SUBTRACT => match &*rhs {
+            Term::Primitive(primitive @ Value::Integer(value)) => match builtin.n_arguments {
+                2 => Term::Builtin(builtin.bind_arg(primitive)),
+                1 => {
+                    let other_value = extract_enum_value!(&builtin.arguments[0], Value::Integer(other_value) => other_value);
+                    Term::Primitive(Value::Integer(other_value - value))
+                }
+                _ => return argument_n_error(builtin.identifier, builtin.n_arguments),
+            },
+            Term::Primitive(_) => return argument_type_error(builtin.identifier, &*rhs),
+            _ => return Ok((Rc::new(Term::Builtin(builtin.clone())), 0)),
+        },
+        B_INTEGER_MULTIPLY => match &*rhs {
+            Term::Primitive(primitive @ Value::Integer(value)) => match builtin.n_arguments {
+                2 => Term::Builtin(builtin.bind_arg(primitive)),
+                1 => {
+                    let other_value = extract_enum_value!(&builtin.arguments[0], Value::Integer(other_value) => other_value);
+                    Term::Primitive(Value::Integer(other_value * value))
+                }
+                _ => return argument_n_error(builtin.identifier, builtin.n_arguments),
+            },
+            Term::Primitive(_) => return argument_type_error(builtin.identifier, &*rhs),
+            _ => return Ok((Rc::new(Term::Builtin(builtin.clone())), 0)),
+        },
+        B_INTEGER_DIVIDE => match &*rhs {
+            Term::Primitive(primitive @ Value::Integer(value)) => match builtin.n_arguments {
+                2 => Term::Builtin(builtin.bind_arg(primitive)),
+                1 => {
+                    if *value == 0 {
+                        return Err("[runtime] divide by zero".to_owned());
+                    }
+                    let other_value = extract_enum_value!(&builtin.arguments[0], Value::Integer(other_value) => other_value);
+                    Term::Primitive(Value::Integer(other_value / value))
                 }
                 _ => return argument_n_error(builtin.identifier, builtin.n_arguments),
             },
diff --git a/src/runtime.rs b/src/runtime.rs
index 9e903cd..6eff337 100644
--- a/src/runtime.rs
+++ b/src/runtime.rs
@@ -183,34 +183,67 @@ pub fn reduce_term(
             }
         }
         Term::Builtin(_) => Ok((Rc::clone(&term_rc), 0)),
-        _ => todo!("reduce_term cases"),
+        Term::Lazy(symbol) => {
+            if resolve_lazy {
+                let table_lookup_value = symbol_table
+                    .get(symbol)
+                    .ok_or(format!("[runtime] symbol not defined: {}", symbol))?;
+
+                // println!("Expanded {} into\n{}\n", symbol, *table_lookup_value);
+                Ok((Rc::clone(table_lookup_value), 1))
+            } else {
+                Ok((term_rc, 0))
+            }
+        }
     }?;
 
     Ok((result_term, result_n))
 }
 
-const MAX_REDUCTION_ITERATIONS: usize = 1000;
+const MAX_REDUCTION_ITERATIONS: usize = 10000;
 
 pub fn repeatedly_reduce_term(
     symbol_table: &HashMap<String, Rc<Term>>,
     term_rc: Rc<Term>,
     bound_variable_opt: &Option<(usize, Rc<Term>)>,
-    resolve_lazy: bool,
-) -> ReductionResult {
+) -> Result<Rc<Term>, String> {
     let mut term = term_rc;
     let mut i: usize = 0;
     loop {
+        loop {
+            // println!("Reduce iteration #{}", i);
+            i += 1;
+            if i >= MAX_REDUCTION_ITERATIONS {
+                return Err("MAX_REDUCTION_ITERATIONS reached".to_owned());
+            }
+
+            let (result_term, substitution_n) =
+                reduce_term(&symbol_table, term.clone(), bound_variable_opt, false)?;
+
+            if cfg!(feature = "debug") {
+                println!("i = {}:\n{}\n", i, result_term);
+            }
+
+            if substitution_n > 0 {
+                term = result_term;
+            } else {
+                break;
+            }
+        }
+
+        // Once resolve_lazy = false has stabilized, do one round of resolve_lazy = true
+        // println!("Reduce iteration #{}", i);
         i += 1;
         if i >= MAX_REDUCTION_ITERATIONS {
             return Err("MAX_REDUCTION_ITERATIONS reached".to_owned());
         }
 
-        let (result_term, substitution_n) = reduce_term(
-            &symbol_table,
-            term.clone(),
-            bound_variable_opt,
-            resolve_lazy,
-        )?;
+        let (result_term, substitution_n) =
+            reduce_term(&symbol_table, term.clone(), bound_variable_opt, true)?;
+
+        if cfg!(feature = "debug") {
+            println!("i = {}:\n{}\n", i, result_term);
+        }
 
         if substitution_n > 0 {
             term = result_term;
@@ -218,7 +251,7 @@ pub fn repeatedly_reduce_term(
             break;
         }
     }
-    Ok((term, 0))
+    Ok(term)
 }
 
 fn process_expr_inner_unary(
@@ -349,7 +382,7 @@ pub fn process(
             }
             ast::Statement::Expression(expression) => {
                 let term = process_expr(&symbol_table, expression, &vec![]);
-                let (result_term, _) = repeatedly_reduce_term(&symbol_table, term, &None, false)?;
+                let result_term = repeatedly_reduce_term(&symbol_table, term, &None)?;
 
                 println!("[{}]: {}", index, result_term);
                 output_terms.push(result_term);
diff --git a/src/test.rs b/src/test.rs
index 728e2e5..3ec0ac3 100644
--- a/src/test.rs
+++ b/src/test.rs
@@ -140,7 +140,7 @@ fn reduce_parameterized_func() -> Result<(), String> {
     assert_eq!(terms.len(), 1);
     let term = &terms[0];
 
-    let (result_term, _) = repeatedly_reduce_term(&symbol_table, Rc::clone(term), &None, false)?;
+    let result_term = repeatedly_reduce_term(&symbol_table, Rc::clone(term), &None)?;
 
     let expected = Term::Primitive(Value::Integer(10));
     assert_eq!(*result_term, expected);
@@ -164,7 +164,7 @@ fn reduce_builtin_int_add() -> Result<(), String> {
     let term3 = &terms[2];
 
     // First expression
-    let (result_term1, _) = repeatedly_reduce_term(&symbol_table, Rc::clone(term1), &None, false)?;
+    let result_term1 = repeatedly_reduce_term(&symbol_table, Rc::clone(term1), &None)?;
     let expected1_identifier = builtins::B_INTEGER_ADD;
     let result_builtin1 = match &*result_term1 {
         Term::Builtin(b) => b,
@@ -174,7 +174,7 @@ fn reduce_builtin_int_add() -> Result<(), String> {
     assert_eq!(result_builtin1.identifier, expected1_identifier);
 
     // Second expression
-    let (result_term2, _) = repeatedly_reduce_term(&symbol_table, Rc::clone(term2), &None, false)?;
+    let result_term2 = repeatedly_reduce_term(&symbol_table, Rc::clone(term2), &None)?;
     let expected2_identifier = builtins::B_INTEGER_ADD;
     let result_builtin2 = match &*result_term2 {
         Term::Builtin(b) => b,
@@ -184,7 +184,7 @@ fn reduce_builtin_int_add() -> Result<(), String> {
     assert_eq!(result_builtin2.identifier, expected2_identifier);
 
     // Third expression
-    let (result_term3, _) = repeatedly_reduce_term(&symbol_table, Rc::clone(term3), &None, false)?;
+    let result_term3 = repeatedly_reduce_term(&symbol_table, Rc::clone(term3), &None)?;
     let expected3 = Value::Integer(30);
     let result_builtin3 = match &*result_term3 {
         Term::Primitive(p) => p,
@@ -215,7 +215,7 @@ fn reduce_builtin_int_eq() -> Result<(), String> {
     let term2 = &terms[1];
 
     // First expression
-    let (result_term1, _) = repeatedly_reduce_term(&symbol_table, Rc::clone(term1), &None, false)?;
+    let result_term1 = repeatedly_reduce_term(&symbol_table, Rc::clone(term1), &None)?;
     let expected1_string = Value::String("false".to_owned());
     let result_builtin1 = match &*result_term1 {
         Term::Primitive(p) => p,
@@ -225,7 +225,7 @@ fn reduce_builtin_int_eq() -> Result<(), String> {
     assert_eq!(*result_builtin1, expected1_string);
 
     // Second expression
-    let (result_term2, _) = repeatedly_reduce_term(&symbol_table, Rc::clone(term2), &None, false)?;
+    let result_term2 = repeatedly_reduce_term(&symbol_table, Rc::clone(term2), &None)?;
     let expected2_string = Value::String("true".to_owned());
     let result_builtin2 = match &*result_term2 {
         Term::Primitive(p) => p,
@@ -256,7 +256,7 @@ fn reduce_builtin_str_eq() -> Result<(), String> {
     let term2 = &terms[1];
 
     // First expression
-    let (result_term1, _) = repeatedly_reduce_term(&symbol_table, Rc::clone(term1), &None, false)?;
+    let result_term1 = repeatedly_reduce_term(&symbol_table, Rc::clone(term1), &None)?;
     let expected1_string = Value::String("false".to_owned());
     let result_builtin1 = match &*result_term1 {
         Term::Primitive(p) => p,
@@ -266,7 +266,7 @@ fn reduce_builtin_str_eq() -> Result<(), String> {
     assert_eq!(*result_builtin1, expected1_string);
 
     // Second expression
-    let (result_term2, _) = repeatedly_reduce_term(&symbol_table, Rc::clone(term2), &None, false)?;
+    let result_term2 = repeatedly_reduce_term(&symbol_table, Rc::clone(term2), &None)?;
     let expected2_string = Value::String("true".to_owned());
     let result_builtin2 = match &*result_term2 {
         Term::Primitive(p) => p,
@@ -314,8 +314,59 @@ fn reduce_nontrivial_terminates2() -> Result<(), String> {
     assert_eq!(terms.len(), 1);
     let term1 = &terms[0];
 
-    let (_, _) = repeatedly_reduce_term(&symbol_table, Rc::clone(term1), &None, false)?;
+    let _ = repeatedly_reduce_term(&symbol_table, Rc::clone(term1), &None)?;
 
     // Terminates
     Ok(())
 }
+
+#[test]
+#[serial]
+fn problem_factorial() -> Result<(), String> {
+    initialize_before_test();
+    let source = "
+    factorial n =
+        int.eq? n 0
+            1
+            (int.mul n (factorial (int.sub n 1)));
+
+    factorial 20;
+    ";
+
+    let (terms, symbol_table) = evaluate_from_source(source.to_owned(), None)?;
+    assert_eq!(terms.len(), 1);
+    let term1 = &terms[0];
+
+    let result_rc = repeatedly_reduce_term(&symbol_table, Rc::clone(term1), &None)?;
+    let expected = Term::Primitive(Value::Integer(2432902008176640000));
+
+    assert_eq!(*result_rc, expected);
+
+    Ok(())
+}
+
+#[test]
+#[serial]
+fn problem_triangle_numbers() -> Result<(), String> {
+    initialize_before_test();
+    let source = "
+    triangle n = int.eq? n 1
+        1
+        (int.add
+            n
+            (triangle (int.sub n 1)));
+
+    triangle 500;
+    ";
+
+    let (terms, symbol_table) = evaluate_from_source(source.to_owned(), None)?;
+    assert_eq!(terms.len(), 1);
+    let term1 = &terms[0];
+
+    let result_rc = repeatedly_reduce_term(&symbol_table, Rc::clone(term1), &None)?;
+    let expected = Term::Primitive(Value::Integer(125250));
+
+    assert_eq!(*result_rc, expected);
+
+    Ok(())
+}