Fix bug in reduce Application case

5 files changed, 191 insertions, 118 deletions

diff --git a/samples/sample1.code b/samples/sample1.code
index 6ac6847..a675849 100644
--- a/samples/sample1.code
+++ b/samples/sample1.code
@@ -1,11 +1,18 @@
-# f a b = int.eq? a b;
-# f 1 2
-#     "true"
-#     "false";
+# result =
+#     bool.to-string
+#         (int.eq? 2 2);
 
-compare? a b fn = fn b a;
-compare? 2 2 int.eq?
-    "true"
-    "false";
+# string.eq? result "true";
 
-int.eq? "foobar";
\ No newline at end of file
+# string.eq?
+#     (bool.to-string
+#         (int.eq? 2 2))
+#     "true";
+
+# string.eq?
+#     (bool.to-string
+#         (int.eq? 2 2));
+
+string.eq?
+    (bool.to-string
+        true);
diff --git a/src/builtins.rs b/src/builtins.rs
index 20ed23b..3063d10 100644
--- a/src/builtins.rs
+++ b/src/builtins.rs
@@ -1,5 +1,6 @@
 use super::ast;
 use super::runtime::{advance_v, Term, Value};
+use super::*;
 use std::fmt;
 use std::rc::Rc;
 
@@ -42,7 +43,7 @@ impl fmt::Display for Builtin {
     }
 }
 
-fn argument_type_error(builtin_id: &'static str, arg: &Value) -> Result<(Rc<Term>, usize), String> {
+fn argument_type_error(builtin_id: &'static str, arg: &Term) -> Result<(Rc<Term>, usize), String> {
     Err(format!(
         "[runtime] cannot apply builtin {} to argument {}",
         builtin_id, arg
@@ -56,9 +57,14 @@ fn argument_n_error(builtin_id: &'static str, n: usize) -> Result<(Rc<Term>, usi
     ))
 }
 
-pub const B_INTEGER_EQ: &str = "int.eq?";
-pub const B_INTEGER_INCREMENT: &str = "int.increment";
-pub const B_INTEGER_ADD: &str = "int.add";
+macro_rules! boolean_function {
+    ($value:expr) => {
+        match $value {
+            true => make_boolean_true_function(),
+            false => make_boolean_false_function(),
+        }
+    };
+}
 
 pub fn make_boolean_true_function() -> Term {
     let x = advance_v();
@@ -77,6 +83,12 @@ pub fn make_identity_function() -> Term {
     Term::Abstraction(v, Rc::new(Term::Variable(v)))
 }
 
+pub const B_INTEGER_EQ: &str = "int.eq?";
+pub const B_INTEGER_INCREMENT: &str = "int.increment";
+pub const B_INTEGER_ADD: &str = "int.add";
+pub const B_STRING_EQ: &str = "string.eq?";
+pub const B_BOOL_TO_STRING: &str = "bool.to-string";
+
 pub fn try_ast_symbol_to_builtin_term(symbol: &ast::Symbol) -> Option<Term> {
     let builtin = match symbol.as_str() {
         "true" => return Some(make_boolean_true_function()),
@@ -85,6 +97,8 @@ 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_STRING_EQ => Builtin::new(B_STRING_EQ, 2),
+        B_BOOL_TO_STRING => Builtin::new(B_BOOL_TO_STRING, 1),
         _ => return None,
     };
 
@@ -94,54 +108,54 @@ pub fn try_ast_symbol_to_builtin_term(symbol: &ast::Symbol) -> Option<Term> {
 pub fn evaluate_builtin(builtin: &Builtin, rhs: Rc<Term>) -> Result<(Rc<Term>, usize), String> {
     let result_term = match builtin.identifier {
         B_INTEGER_EQ => match &*rhs {
-            Term::Primitive(primitive) => match primitive {
-                Value::Integer(value) => match builtin.n_arguments {
-                    2 => Term::Builtin(builtin.bind_arg(primitive)),
-                    1 => {
-                        let other = &builtin.arguments[0];
-                        match other {
-                            Value::Integer(other_value) => {
-                                if value == other_value {
-                                    make_boolean_true_function()
-                                } else {
-                                    make_boolean_false_function()
-                                }
-                            }
-                            other => return argument_type_error(builtin.identifier, other),
-                        }
-                    }
-                    _ => return argument_n_error(builtin.identifier, builtin.n_arguments),
-                },
-                other => return argument_type_error(builtin.identifier, other),
+            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);
+
+                    boolean_function!(value == other_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_INCREMENT => match &*rhs {
-            Term::Primitive(primitive) => match primitive {
-                Value::Integer(value) => Term::Primitive(Value::Integer(value + 1)),
-                other => return argument_type_error(builtin.identifier, other),
-            },
+            Term::Primitive(Value::Integer(value)) => Term::Primitive(Value::Integer(value + 1)),
+            Term::Primitive(_) => return argument_type_error(builtin.identifier, &*rhs),
             _ => return Ok((Rc::new(Term::Builtin(builtin.clone())), 0)),
         },
         B_INTEGER_ADD => match &*rhs {
-            Term::Primitive(primitive) => match primitive {
-                Value::Integer(value) => match builtin.n_arguments {
-                    2 => Term::Builtin(builtin.bind_arg(primitive)),
-                    1 => {
-                        let other = &builtin.arguments[0];
-                        match other {
-                            Value::Integer(other_value) => {
-                                Term::Primitive(Value::Integer(value + other_value))
-                            }
-                            other => return argument_type_error(builtin.identifier, other),
-                        }
-                    }
-                    _ => return argument_n_error(builtin.identifier, builtin.n_arguments),
-                },
-                other => return argument_type_error(builtin.identifier, other),
+            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(value + other_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_STRING_EQ => match &*rhs {
+            Term::Primitive(primitive @ Value::String(value)) => match builtin.n_arguments {
+                2 => Term::Builtin(builtin.bind_arg(primitive)),
+                1 => {
+                    let other_value = extract_enum_value!(&builtin.arguments[0], Value::String(other_value) => other_value);
+
+                    boolean_function!(value == other_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_BOOL_TO_STRING => {
+            let true_str_rc = Rc::new(Term::Primitive(Value::String(String::from("true"))));
+            let false_str_rc = Rc::new(Term::Primitive(Value::String(String::from("false"))));
+            let inner = Rc::new(Term::Application(rhs, true_str_rc));
+            Term::Application(inner, false_str_rc)
+        }
         _ => {
             return Err(format!(
                 "[runtime] invalid builtin evaluated: {}",
diff --git a/src/main.rs b/src/main.rs
index cc37974..8ff5efc 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -11,6 +11,16 @@ mod runtime;
 #[cfg(test)]
 mod test;
 
+#[macro_export]
+macro_rules! extract_enum_value {
+    ($value:expr, $pattern:pat => $extracted_value:expr) => {
+        match $value {
+            $pattern => $extracted_value,
+            _ => panic!("extract_enum_value: Pattern doesn't match!"),
+        }
+    };
+}
+
 fn main() {
     use ast::Program;
     use pest::Parser;
diff --git a/src/runtime.rs b/src/runtime.rs
index 789d31a..0dc4789 100644
--- a/src/runtime.rs
+++ b/src/runtime.rs
@@ -15,7 +15,7 @@ impl fmt::Display for Value {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         match self {
             Value::Integer(value) => write!(f, "Integer({})", value),
-            Value::String(value) => write!(f, "String({})", value),
+            Value::String(value) => write!(f, "String(\"{}\")", value),
         }
     }
 }
@@ -36,10 +36,7 @@ impl Term {
         match self {
             Term::Lazy(symbol) => format!("{}Lazy({})", indent_str, symbol),
             Term::Variable(v) => format!("{}Variable({})", indent_str, v),
-            Term::Primitive(value) => match value {
-                Value::Integer(int_val) => format!("{}Integer({})", indent_str, int_val),
-                Value::String(str_val) => format!("{}String({})", indent_str, str_val),
-            },
+            Term::Primitive(value) => format!("{}{}", indent_str, value),
             Term::Builtin(builtin) => format!("{}{}", indent_str, builtin),
             Term::Abstraction(v, body) => format!(
                 "{}Abstraction({})\n{}",
@@ -136,24 +133,15 @@ pub fn reduce_term(
                 }
                 Term::Builtin(builtin) => {
                     let (builtin_evaled_terms, builtin_n) =
-                        builtins::evaluate_builtin(builtin, subst_rhs_rc)?;
+                        builtins::evaluate_builtin(builtin, Rc::clone(&subst_rhs_rc))?;
 
                     // TODO: think this through
                     if builtin_n > 0 {
-                        if cfg!(feature = "reduce_debug") {
-                            println!(":: builtin_n: {} > 0", builtin_n);
-                            println!(
-                                ":: returning builtin_evaled_terms:\n{}\n",
-                                builtin_evaled_terms
-                            );
-                        }
                         Ok((builtin_evaled_terms, rhs_n + builtin_n))
                     } else {
-                        if cfg!(feature = "reduce_debug") {
-                            println!(":: builtin_n: {} < 0", builtin_n);
-                            println!(":: returning application as is:\n{}\n", term);
-                        }
-                        Ok((Rc::clone(&term_rc), rhs_n))
+                        let new_app =
+                            Term::Application(Rc::clone(lhs_rc), Rc::clone(&subst_rhs_rc));
+                        Ok((Rc::new(new_app), rhs_n))
                     }
                 }
                 _ => {
@@ -163,10 +151,16 @@ pub fn reduce_term(
                         bound_variable_opt,
                         resolve_lazy,
                     )?;
-                    Ok((
-                        Rc::new(Term::Application(subst_lhs_rc, subst_rhs_rc)),
-                        rhs_n + lhs_n,
-                    ))
+
+                    let subst_n = rhs_n + lhs_n;
+                    if subst_n > 0 {
+                        let new_app = Term::Application(subst_lhs_rc, subst_rhs_rc);
+                        Ok((Rc::new(new_app), subst_n))
+                    } else {
+                        let new_app =
+                            Term::Application(Rc::clone(lhs_rc), Rc::clone(&subst_rhs_rc));
+                        Ok((Rc::new(new_app), 0))
+                    }
                 }
             }?;
 
@@ -179,51 +173,19 @@ pub fn reduce_term(
                 bound_variable_opt,
                 resolve_lazy,
             )?;
-            Ok((Rc::new(Term::Abstraction(*abs_v, subst_body)), subst_n))
-        }
-        Term::Builtin(_) => Ok((Rc::clone(&term_rc), 0)),
-        // Term::Lazy(symbol) => {
-        //     if resolve_lazy {
-        //         let table_lookup_value = symbol_table.get(symbol);
-        //         if table_lookup_value.is_some() {
-        //             let lookup_rc = table_lookup_value.unwrap();
-        //             return reduce_term(
-        //                 symbol_table,
-        //                 lookup_rc.clone(),
-        //                 bound_variable_opt,
-        //                 resolve_lazy,
-        //             );
-        //         }
 
-        //         let builtin_value = builtins::try_builtin_symbol_to_term(symbol);
-        //         if builtin_value.is_some() {
-        //             let builtin_rc = Rc::new(builtin_value.unwrap());
-        //             return reduce_term(
-        //                 symbol_table,
-        //                 builtin_rc.clone(),
-        //                 bound_variable_opt,
-        //                 resolve_lazy,
-        //             );
-        //         }
+            if subst_n > 0 {
+                let new_abs = Term::Abstraction(*abs_v, subst_body);
 
-        //         panic!("[runtime] symbol {} not defined", symbol);
-        //     } else {
-        //         term_rc
-        //     }
-        // }
+                Ok((Rc::new(new_abs), subst_n))
+            } else {
+                Ok((Rc::clone(&term_rc), 0))
+            }
+        }
+        Term::Builtin(_) => Ok((Rc::clone(&term_rc), 0)),
         _ => todo!("reduce_term cases"),
     }?;
 
-    if cfg!(feature = "reduce_debug") {
-        println!(
-            "reduce_term with:\nterm_rc:\n{}\nbound_variable_opt:\n{}\nresolve_lazy:\n{}\n",
-            Rc::clone(&term_rc),
-            _bound_variable_opt_to_string(bound_variable_opt),
-            resolve_lazy
-        );
-        println!("result_term:\n{}\nresult_n: {}\n", result_term, result_n);
-        println!("\n=========\n");
-    }
     Ok((result_term, result_n))
 }
 
@@ -242,14 +204,14 @@ pub fn repeatedly_reduce_term(
         if i >= MAX_REDUCTION_ITERATIONS {
             return Err(String::from("MAX_REDUCTION_ITERATIONS reached"));
         }
-        // println!("Term:\n{}", term);
+
         let (result_term, substitution_n) = reduce_term(
             &symbol_table,
             term.clone(),
             bound_variable_opt,
             resolve_lazy,
         )?;
-        // println!("Reduction OK:\n{},\nN: {}\n", result_term, substitution_n);
+
         if substitution_n > 0 {
             term = result_term;
         } else {
@@ -372,7 +334,6 @@ pub fn process(
                 parameters,
                 expression,
             } => {
-                // println!("[runtime] defining symbol: {:#?}", symbol);
                 let bound_params: Vec<(ast::Symbol, usize)> = parameters
                     .iter()
                     .map(|param| (param.clone(), advance_v()))
@@ -384,11 +345,9 @@ pub fn process(
                     term = Rc::new(Term::Abstraction(*v, Rc::clone(&term)));
                 });
 
-                // println!("Term:\n{}", term);
                 symbol_table.insert(symbol.clone(), term);
             }
             ast::Statement::Expression(expression) => {
-                // println!("[runtime] evaluating free-standing expression");
                 let term = process_expr(&symbol_table, expression, &vec![]);
                 let (result_term, _) = repeatedly_reduce_term(&symbol_table, term, &None, false)?;
 
diff --git a/src/test.rs b/src/test.rs
index a2dea85..0600798 100644
--- a/src/test.rs
+++ b/src/test.rs
@@ -236,3 +236,86 @@ fn reduce_builtin_int_eq() -> Result<(), String> {
 
     Ok(())
 }
+
+#[test]
+#[serial]
+fn reduce_builtin_str_eq() -> Result<(), String> {
+    initialize_before_test();
+    let source = "
+    string.eq? \"foo\" \"bar\"
+        \"true\"
+        \"false\";
+    string.eq? \"baz\" \"baz\"
+        \"true\"
+        \"false\";
+    ";
+
+    let (terms, symbol_table) = evaluate_from_source(String::from(source), None)?;
+    assert_eq!(terms.len(), 2);
+    let term1 = &terms[0];
+    let term2 = &terms[1];
+
+    // First expression
+    let (result_term1, _) = repeatedly_reduce_term(&symbol_table, Rc::clone(term1), &None, false)?;
+    let expected1_string = Value::String(String::from("false"));
+    let result_builtin1 = match &*result_term1 {
+        Term::Primitive(p) => p,
+        _ => return Err(format!("{} is not a primitive", result_term1)),
+    };
+
+    assert_eq!(*result_builtin1, expected1_string);
+
+    // Second expression
+    let (result_term2, _) = repeatedly_reduce_term(&symbol_table, Rc::clone(term2), &None, false)?;
+    let expected2_string = Value::String(String::from("true"));
+    let result_builtin2 = match &*result_term2 {
+        Term::Primitive(p) => p,
+        _ => return Err(format!("{} is not a primitive", result_term2)),
+    };
+
+    assert_eq!(*result_builtin2, expected2_string);
+
+    Ok(())
+}
+
+#[test]
+#[serial]
+fn reduce_nontrivial_terminates1() -> Result<(), String> {
+    initialize_before_test();
+    let source = "
+    string.eq?
+        (bool.to-string
+            true);
+    ";
+
+    let (terms, symbol_table) = evaluate_from_source(String::from(source), None)?;
+    assert_eq!(terms.len(), 1);
+    let term1 = &terms[0];
+
+    let (_, _) = reduce_term(&symbol_table, Rc::clone(term1), &None, false)?;
+
+    // Terminates
+    Ok(())
+}
+
+#[test]
+#[serial]
+fn reduce_nontrivial_terminates2() -> Result<(), String> {
+    initialize_before_test();
+    let source = "
+    result =
+        bool.to-string
+            (int.eq? 2 2);
+
+    string.eq? result \"true\";
+    ";
+
+    let (terms, symbol_table) = evaluate_from_source(String::from(source), None)?;
+    assert_eq!(terms.len(), 1);
+    let term1 = &terms[0];
+
+    let (_, _) = repeatedly_reduce_term(&symbol_table, Rc::clone(term1), &None, false)?;
+
+    // Terminates
+    Ok(())
+}