Rewrite value system

4 files changed, 163 insertions, 184 deletions

diff --git a/samples/sample1.code b/samples/sample1.code
index 821941f..b72d496 100644
--- a/samples/sample1.code
+++ b/samples/sample1.code
@@ -3,3 +3,7 @@
 #     int.multiply n (factorial (int.decrement n));
 
 # factorial 10;
+
+true
+    (id 1)
+    (id 2);
diff --git a/src/builtins.rs b/src/builtins.rs
index 351a652..46b6ec5 100644
--- a/src/builtins.rs
+++ b/src/builtins.rs
@@ -1,107 +1,31 @@
 use super::ast;
-use super::runtime;
-use super::runtime::Value;
+use super::runtime::{advance_v, Term};
 use std::rc::Rc;
 
 pub const B_INTEGER_INCREMENT: &str = "int.increment";
-pub const B_INTEGER_DECREMENT: &str = "int.decrement";
-pub const B_INTEGER_ADD: &str = "int.add";
-pub const B_INTEGER_MULTIPLY: &str = "int.multiply";
-pub const B_INTEGER_EQ: &str = "int.eq?";
 
-#[derive(Debug, Clone)]
-pub enum BuiltinFunction {
-    IntegerIncrement,
-    IntegerDecrement,
-    IntegerAdd,
-    IntegerAdd1(i64),
-    IntegerMultiply,
-    IntegerMultiply1(i64),
-    IntegerEq,
-    IntegerEq1(i64),
+pub fn make_boolean_true_function() -> Term {
+    let x = advance_v();
+    let y = advance_v();
+    Term::Abstraction(x, Rc::new(Term::Abstraction(y, Rc::new(Term::Variable(x)))))
 }
 
-pub fn try_builtin_symbol_to_value(symbol: &ast::Symbol) -> Option<Value> {
-    match symbol.as_str() {
-        "true" => Some(runtime::make_boolean_true_function()),
-        "false" => Some(runtime::make_boolean_false_function()),
-        "id" => Some(runtime::make_identity_function()),
-        B_INTEGER_INCREMENT => Some(Value::BuiltinFunction(BuiltinFunction::IntegerIncrement)),
-        B_INTEGER_DECREMENT => Some(Value::BuiltinFunction(BuiltinFunction::IntegerDecrement)),
-        B_INTEGER_ADD => Some(Value::BuiltinFunction(BuiltinFunction::IntegerAdd)),
-        B_INTEGER_MULTIPLY => Some(Value::BuiltinFunction(BuiltinFunction::IntegerMultiply)),
-        B_INTEGER_EQ => Some(Value::BuiltinFunction(BuiltinFunction::IntegerEq)),
-        _ => None,
-    }
+pub fn make_boolean_false_function() -> Term {
+    let x = advance_v();
+    let y = advance_v();
+    Term::Abstraction(x, Rc::new(Term::Abstraction(y, Rc::new(Term::Variable(y)))))
 }
 
-pub fn apply_builtin(builtin: &BuiltinFunction, arg: &Value) -> Rc<Value> {
-    match builtin {
-        BuiltinFunction::IntegerIncrement => match arg {
-            Value::Integer(value) => Rc::new(Value::Integer(value + 1)),
-            _ => panic!(
-                "[runtime] tried to apply non-integer value to {}",
-                B_INTEGER_INCREMENT
-            ),
-        },
-        BuiltinFunction::IntegerDecrement => match arg {
-            Value::Integer(value) => Rc::new(Value::Integer(value - 1)),
-            _ => panic!(
-                "[runtime] tried to apply non-integer value to {}",
-                B_INTEGER_DECREMENT
-            ),
-        },
-        BuiltinFunction::IntegerAdd => match arg {
-            Value::Integer(value) => {
-                Rc::new(Value::BuiltinFunction(BuiltinFunction::IntegerAdd1(*value)))
-            }
-            _ => panic!(
-                "[runtime] tried to apply non-integer value to {}",
-                B_INTEGER_ADD
-            ),
-        },
-        BuiltinFunction::IntegerAdd1(other) => match arg {
-            Value::Integer(value) => Rc::new(Value::Integer(other + value)),
-            _ => panic!(
-                "[runtime] tried to apply non-integer value to {}",
-                B_INTEGER_ADD
-            ),
-        },
-        BuiltinFunction::IntegerMultiply => match arg {
-            Value::Integer(value) => Rc::new(Value::BuiltinFunction(
-                BuiltinFunction::IntegerMultiply1(*value),
-            )),
-            _ => panic!(
-                "[runtime] tried to apply non-integer value to {}",
-                B_INTEGER_MULTIPLY
-            ),
-        },
-        BuiltinFunction::IntegerMultiply1(other) => match arg {
-            Value::Integer(value) => Rc::new(Value::Integer(other * value)),
-            _ => panic!(
-                "[runtime] tried to apply non-integer value to {}",
-                B_INTEGER_MULTIPLY
-            ),
-        },
-        BuiltinFunction::IntegerEq => match arg {
-            Value::Integer(value) => {
-                Rc::new(Value::BuiltinFunction(BuiltinFunction::IntegerEq1(*value)))
-            }
-            _ => panic!(
-                "[runtime] tried to apply non-integer value to {}",
-                B_INTEGER_EQ
-            ),
-        },
-        BuiltinFunction::IntegerEq1(other) => match arg {
-            Value::Integer(value) => Rc::new(if other == value {
-                runtime::make_boolean_true_function()
-            } else {
-                runtime::make_boolean_false_function()
-            }),
-            _ => panic!(
-                "[runtime] tried to apply non-integer value to {}",
-                B_INTEGER_EQ
-            ),
-        },
+pub fn make_identity_function() -> Term {
+    let v = advance_v();
+    Term::Abstraction(v, Rc::new(Term::Variable(v)))
+}
+
+pub fn try_builtin_symbol_to_value(symbol: &ast::Symbol) -> Option<Term> {
+    match symbol.as_str() {
+        "true" => Some(make_boolean_true_function()),
+        "false" => Some(make_boolean_false_function()),
+        "id" => Some(make_identity_function()),
+        _ => None,
     }
 }
diff --git a/src/main.rs b/src/main.rs
index 59e91df..c8b499d 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -30,5 +30,5 @@ fn main() {
     let syntax_tree: Program = ast::from_parse_tree(&mut parse_tree);
     // println!("syntax tree = {:#?}", syntax_tree);
 
-    runtime::evaluate(&syntax_tree);
+    runtime::process(&syntax_tree);
 }
diff --git a/src/runtime.rs b/src/runtime.rs
index 9a5b4b4..ca4457e 100644
--- a/src/runtime.rs
+++ b/src/runtime.rs
@@ -1,6 +1,5 @@
 use super::ast;
 use super::builtins;
-use super::builtins::BuiltinFunction;
 use std::collections::HashMap;
 use std::fmt;
 use std::rc::Rc;
@@ -10,9 +9,6 @@ use std::sync::atomic::{AtomicUsize, Ordering};
 pub enum Value {
     Integer(i64),
     String(String),
-    Var(usize),
-    Function(usize, Rc<Value>),
-    BuiltinFunction(BuiltinFunction),
 }
 
 impl fmt::Display for Value {
@@ -20,78 +16,108 @@ impl fmt::Display for Value {
         match self {
             Value::Integer(value) => write!(f, "{} :: Integer", value),
             Value::String(value) => write!(f, "{} :: String", value),
-            Value::Var(v) => write!(f, "{} :: Unbound variable", v),
-            Value::Function(_, _) => {
-                write!(f, "Function :: Function")
-            }
-            Value::BuiltinFunction(_) => write!(f, "Built-in function :: Function"),
         }
     }
 }
 
-static VAR_ID_INC: AtomicUsize = AtomicUsize::new(0);
-
-fn advance_v() -> usize {
-    let v = VAR_ID_INC.load(Ordering::Relaxed);
-    VAR_ID_INC.store(v + 1, Ordering::Relaxed);
-    v
+#[derive(Debug, Clone)]
+pub enum Term {
+    Variable(usize),
+    Abstraction(usize, Rc<Term>),
+    Application(Rc<Term>, Rc<Term>),
+    Primitive(Value),
+    Lazy(String),
 }
 
-pub fn make_boolean_true_function() -> Value {
-    let x = advance_v();
-    let y = advance_v();
-    Value::Function(x, Rc::new(Value::Function(y, Rc::new(Value::Var(x)))))
+impl Term {
+    fn fmt_with_indent(&self, indent: usize) -> String {
+        let indent_str = std::iter::repeat("|  ").take(indent).collect::<String>();
+        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::Abstraction(v, body) => format!(
+                "{}Abstraction({})\n{}",
+                indent_str,
+                v,
+                body.fmt_with_indent(indent + 1)
+            ),
+            Term::Application(lhs, rhs) => format!(
+                "{}Application\n{}\n{}",
+                indent_str,
+                lhs.fmt_with_indent(indent + 1),
+                rhs.fmt_with_indent(indent + 1),
+            ),
+        }
+    }
 }
 
-pub fn make_boolean_false_function() -> Value {
-    let x = advance_v();
-    let y = advance_v();
-    Value::Function(x, Rc::new(Value::Function(y, Rc::new(Value::Var(y)))))
+impl fmt::Display for Term {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "{}", self.fmt_with_indent(0))
+    }
 }
 
-pub fn make_identity_function() -> Value {
-    let v = advance_v();
-    Value::Function(v, Rc::new(Value::Var(v)))
-}
+static VAR_ID_INC: AtomicUsize = AtomicUsize::new(0);
 
-fn try_apply_function(func_rc: Rc<Value>, arg_rc: Rc<Value>, bound_v: Option<usize>) -> Rc<Value> {
-    let func = &*func_rc;
-    let arg = &*arg_rc;
-    match func {
-        Value::Function(func_v, body_rc) => {
-            let v1 = bound_v.unwrap_or(*func_v);
-            let body = &**body_rc;
-            match body {
-                Value::Var(v2) => {
-                    if v1 == *v2 {
-                        arg_rc
-                    } else {
-                        Rc::clone(body_rc)
-                    }
-                }
-                Value::Function(body_v, _) => {
-                    let new_body = try_apply_function(Rc::clone(body_rc), arg_rc, Some(v1));
-                    Rc::new(Value::Function(*body_v, new_body))
-                }
-                _ => Rc::clone(body_rc),
-            }
-        }
-        Value::BuiltinFunction(builtin) => builtins::apply_builtin(builtin, arg),
-        _ => func_rc,
-    }
+pub fn advance_v() -> usize {
+    let v = VAR_ID_INC.load(Ordering::Relaxed);
+    VAR_ID_INC.store(v + 1, Ordering::Relaxed);
+    v
 }
 
-fn evaluate_expr_inner_unary(
-    symbol_table: &HashMap<String, Rc<Value>>,
+// fn try_apply_function(lhs_rc: Rc<Value>, rhs_rc: Rc<Value>, bound_v: Option<usize>) -> Rc<Value> {
+//     let lhs = &*lhs_rc;
+//     // println!(
+//     //     "[debug] try_apply_function({:#?}, {:#?}, {:#?})",
+//     //     func_rc, arg_rc, bound_v
+//     // );
+
+//     match lhs {
+//         Value::Function(func_v, body_rc, builtin_name_opt) => {
+//             let v1 = bound_v.unwrap_or(*func_v);
+//             let body = &**body_rc;
+//             match body {
+//                 Value::Var(v2) => {
+//                     if v1 == *v2 {
+//                         rhs_rc
+//                     } else {
+//                         Rc::clone(body_rc)
+//                     }
+//                 }
+//                 Value::Function(body_v, _, body_builtin_name_opt) => {
+//                     let new_body = try_apply_function(Rc::clone(body_rc), rhs_rc, Some(v1));
+//                     // TODO builtin handling
+//                     Rc::new(Value::Function(*body_v, new_body, None))
+//                 }
+//                 _ => Rc::clone(body_rc),
+//             }
+//         }
+//         _ => lhs_rc,
+//     }
+// }
+
+fn process_expr_inner_unary(
+    symbol_table: &HashMap<String, Rc<Term>>,
     inner: &ast::ExpressionInner,
-) -> Rc<Value> {
+    bound_symbols: &Vec<(ast::Symbol, usize)>,
+) -> Rc<Term> {
     match inner {
-        ast::ExpressionInner::IntegerLiteral(value) => Rc::new(Value::Integer(*value)),
-        ast::ExpressionInner::StringLiteral(value) => Rc::new(Value::String(value.clone())),
+        ast::ExpressionInner::IntegerLiteral(value) => {
+            Rc::new(Term::Primitive(Value::Integer(*value)))
+        }
+        ast::ExpressionInner::StringLiteral(value) => {
+            Rc::new(Term::Primitive(Value::String(value.clone())))
+        }
         ast::ExpressionInner::Symbol(value) => {
-            let builtin_value = builtins::try_builtin_symbol_to_value(value);
-            if builtin_value.is_some() {
-                return Rc::new(builtin_value.unwrap());
+            let bound_symbol_opt = bound_symbols
+                .iter()
+                .find(|(bound_symbol, _)| bound_symbol == value);
+            if bound_symbol_opt.is_some() {
+                return Rc::new(Term::Variable(bound_symbol_opt.unwrap().1));
             }
 
             let table_lookup_value = symbol_table.get(value);
@@ -100,41 +126,52 @@ fn evaluate_expr_inner_unary(
                 return Rc::clone(lookup_rc);
             }
 
-            panic!("[runtime] symbol not defined: {:#?}", value);
+            let builtin_value = builtins::try_builtin_symbol_to_value(value);
+            if builtin_value.is_some() {
+                return Rc::new(builtin_value.unwrap());
+            }
+
+            Rc::new(Term::Lazy(value.clone()))
         }
         ast::ExpressionInner::Expression(value_rc) => {
             let sub_expr = &**value_rc;
-            evaluate_expr(symbol_table, sub_expr)
+            process_expr(symbol_table, sub_expr, bound_symbols)
         }
     }
 }
 
-fn evaluate_expr_inner_binary(
-    symbol_table: &HashMap<String, Rc<Value>>,
+fn process_expr_inner_binary(
+    symbol_table: &HashMap<String, Rc<Term>>,
     lhs: &ast::ExpressionInner,
     rhs: &ast::ExpressionInner,
-) -> Rc<Value> {
+    bound_symbols: &Vec<(ast::Symbol, usize)>,
+) -> Rc<Term> {
     match lhs {
         ast::ExpressionInner::Expression(value_rc) => {
             let sub_expr = &**value_rc;
 
-            let evaled_lhs = evaluate_expr(symbol_table, sub_expr);
-            let evaled_rhs = evaluate_expr_inner_unary(symbol_table, rhs);
-            try_apply_function(evaled_lhs, evaled_rhs, None)
+            let lhs_term = process_expr(symbol_table, sub_expr, bound_symbols);
+            let rhs_term = process_expr_inner_unary(symbol_table, rhs, bound_symbols);
+            Rc::new(Term::Application(lhs_term, rhs_term))
         }
         ast::ExpressionInner::Symbol(value) => {
-            let lhs_value_rc: Rc<Value>;
+            let lhs_term: Rc<Term>;
+            let bound_symbol_opt = bound_symbols
+                .iter()
+                .find(|(bound_symbol, _)| bound_symbol == value);
 
-            if let Some(builtin) = builtins::try_builtin_symbol_to_value(value) {
-                lhs_value_rc = Rc::new(builtin);
+            if let Some(bound_symbol) = bound_symbol_opt {
+                lhs_term = Rc::new(Term::Variable(bound_symbol.1));
             } else if let Some(lookup) = symbol_table.get(value) {
-                lhs_value_rc = Rc::clone(lookup);
+                lhs_term = Rc::clone(lookup);
+            } else if let Some(builtin) = builtins::try_builtin_symbol_to_value(value) {
+                lhs_term = Rc::new(builtin);
             } else {
-                panic!("[runtime] symbol not defined: {:#?}", value);
+                lhs_term = Rc::new(Term::Lazy(value.clone()));
             }
 
-            let evaled_rhs = evaluate_expr_inner_unary(symbol_table, rhs);
-            try_apply_function(lhs_value_rc, evaled_rhs, None)
+            let rhs_term = process_expr_inner_unary(symbol_table, rhs, bound_symbols);
+            Rc::new(Term::Application(lhs_term, rhs_term))
         }
         other => unreachable!(
             "[runtime] this should not be on the left side of a binary expression: {:#?}",
@@ -143,22 +180,25 @@ fn evaluate_expr_inner_binary(
     }
 }
 
-fn evaluate_expr(
-    symbol_table: &HashMap<String, Rc<Value>>,
+fn process_expr(
+    symbol_table: &HashMap<String, Rc<Term>>,
     expression: &ast::Expression,
-) -> Rc<Value> {
+    bound_symbols: &Vec<(ast::Symbol, usize)>,
+) -> Rc<Term> {
     match expression {
-        ast::Expression::Unary(inner) => evaluate_expr_inner_unary(symbol_table, inner),
+        ast::Expression::Unary(inner) => {
+            process_expr_inner_unary(symbol_table, inner, bound_symbols)
+        }
         ast::Expression::Binary(inner1, inner2) => {
-            evaluate_expr_inner_binary(symbol_table, inner1, inner2)
+            process_expr_inner_binary(symbol_table, inner1, inner2, bound_symbols)
         }
     }
 }
 
-pub fn evaluate(program: &ast::Program) {
-    let mut symbol_table: HashMap<String, Rc<Value>> = HashMap::new();
+pub fn process(program: &ast::Program) {
+    let mut symbol_table: HashMap<String, Rc<Term>> = HashMap::new();
 
-    for statement in program {
+    for (index, statement) in program.iter().enumerate() {
         match statement {
             ast::Statement::Definition {
                 symbol,
@@ -166,13 +206,24 @@ pub fn evaluate(program: &ast::Program) {
                 expression,
             } => {
                 println!("[runtime] defining symbol: {:#?}", symbol);
-                let value = evaluate_expr(&symbol_table, expression);
-                symbol_table.insert(symbol.clone(), value);
+                let bound_params: Vec<(ast::Symbol, usize)> = parameters
+                    .iter()
+                    .map(|param| (param.clone(), advance_v()))
+                    .collect();
+
+                let evaled_expr = process_expr(&symbol_table, expression, &bound_params);
+                let mut abstracted_expr: Rc<Term> = evaled_expr;
+
+                // bound_params.iter().rev().for_each(|(_, v)| {
+                //     abstracted_expr = Rc::new(Value::Function(*v, Rc::clone(&abstracted_expr)));
+                // });
+
+                symbol_table.insert(symbol.clone(), abstracted_expr);
             }
             ast::Statement::Expression(expression) => {
                 println!("[runtime] evaluating free-standing expression");
-                let value = evaluate_expr(&symbol_table, expression);
-                println!("Result: {}", value);
+                let term = process_expr(&symbol_table, expression, &vec![]);
+                println!("Result:\n{}", term);
             }
         }
     }