aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Cargo.lock133
-rw-r--r--Cargo.toml3
-rw-r--r--src/main.rs9
-rw-r--r--src/runtime.rs134
-rw-r--r--src/test.rs148
5 files changed, 351 insertions, 76 deletions
diff --git a/Cargo.lock b/Cargo.lock
index f0663a8..26278f2 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -3,6 +3,12 @@
version = 3
[[package]]
+name = "bitflags"
+version = "1.3.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "bef38d45163c2f1dde094a7dfd33ccf595c92905c8f8f4fdc18d06fb1037718a"
+
+[[package]]
name = "block-buffer"
version = "0.7.3"
source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -36,6 +42,12 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "14c189c53d098945499cdfa7ecc63567cf3886b3332b312a5b4585d8d3a6a610"
[[package]]
+name = "cfg-if"
+version = "1.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd"
+
+[[package]]
name = "digest"
version = "0.8.1"
source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -60,6 +72,36 @@ dependencies = [
]
[[package]]
+name = "instant"
+version = "0.1.12"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7a5bbe824c507c5da5956355e86a746d82e0e1464f65d862cc5e71da70e94b2c"
+dependencies = [
+ "cfg-if",
+]
+
+[[package]]
+name = "lazy_static"
+version = "1.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e2abad23fbc42b3700f2f279844dc832adb2b2eb069b2df918f455c4e18cc646"
+
+[[package]]
+name = "libc"
+version = "0.2.108"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "8521a1b57e76b1ec69af7599e75e38e7b7fad6610f037db8c79b127201b5d119"
+
+[[package]]
+name = "lock_api"
+version = "0.4.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "712a4d093c9976e24e7dbca41db895dabcbac38eb5f4045393d17a95bdfb1109"
+dependencies = [
+ "scopeguard",
+]
+
+[[package]]
name = "maplit"
version = "1.0.2"
source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -72,6 +114,31 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "2839e79665f131bdb5782e51f2c6c9599c133c6098982a54c794358bf432529c"
[[package]]
+name = "parking_lot"
+version = "0.11.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7d17b78036a60663b797adeaee46f5c9dfebb86948d1255007a1d6be0271ff99"
+dependencies = [
+ "instant",
+ "lock_api",
+ "parking_lot_core",
+]
+
+[[package]]
+name = "parking_lot_core"
+version = "0.8.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d76e8e1493bcac0d2766c42737f34458f1c8c50c0d23bcb24ea953affb273216"
+dependencies = [
+ "cfg-if",
+ "instant",
+ "libc",
+ "redox_syscall",
+ "smallvec",
+ "winapi",
+]
+
+[[package]]
name = "pest"
version = "2.1.3"
source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -129,6 +196,7 @@ version = "0.1.0"
dependencies = [
"pest",
"pest_derive",
+ "serial_test",
]
[[package]]
@@ -141,6 +209,43 @@ dependencies = [
]
[[package]]
+name = "redox_syscall"
+version = "0.2.10"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "8383f39639269cde97d255a32bdb68c047337295414940c68bdd30c2e13203ff"
+dependencies = [
+ "bitflags",
+]
+
+[[package]]
+name = "scopeguard"
+version = "1.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d29ab0c6d3fc0ee92fe66e2d99f700eab17a8d57d1c1d3b748380fb20baa78cd"
+
+[[package]]
+name = "serial_test"
+version = "0.5.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e0bccbcf40c8938196944a3da0e133e031a33f4d6b72db3bda3cc556e361905d"
+dependencies = [
+ "lazy_static",
+ "parking_lot",
+ "serial_test_derive",
+]
+
+[[package]]
+name = "serial_test_derive"
+version = "0.5.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "b2acd6defeddb41eb60bb468f8825d0cfd0c2a76bc03bfd235b6a1dc4f6a1ad5"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "syn",
+]
+
+[[package]]
name = "sha-1"
version = "0.8.2"
source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -153,6 +258,12 @@ dependencies = [
]
[[package]]
+name = "smallvec"
+version = "1.7.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1ecab6c735a6bb4139c0caafd0cc3635748bbb3acf4550e8138122099251f309"
+
+[[package]]
name = "syn"
version = "1.0.81"
source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -180,3 +291,25 @@ name = "unicode-xid"
version = "0.2.2"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "8ccb82d61f80a663efe1f787a51b16b5a51e3314d6ac365b08639f52387b33f3"
+
+[[package]]
+name = "winapi"
+version = "0.3.9"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5c839a674fcd7a98952e593242ea400abe93992746761e38641405d28b00f419"
+dependencies = [
+ "winapi-i686-pc-windows-gnu",
+ "winapi-x86_64-pc-windows-gnu",
+]
+
+[[package]]
+name = "winapi-i686-pc-windows-gnu"
+version = "0.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6"
+
+[[package]]
+name = "winapi-x86_64-pc-windows-gnu"
+version = "0.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f"
diff --git a/Cargo.toml b/Cargo.toml
index 63dc455..b5a9ba0 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -8,3 +8,6 @@ edition = "2021"
[dependencies]
pest = "2.0"
pest_derive = "2.0"
+
+[dev-dependencies]
+serial_test = "0.5.1"
diff --git a/src/main.rs b/src/main.rs
index c8b499d..cc37974 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -8,6 +8,9 @@ mod builtins;
mod lparser;
mod runtime;
+#[cfg(test)]
+mod test;
+
fn main() {
use ast::Program;
use pest::Parser;
@@ -30,5 +33,9 @@ fn main() {
let syntax_tree: Program = ast::from_parse_tree(&mut parse_tree);
// println!("syntax tree = {:#?}", syntax_tree);
- runtime::process(&syntax_tree);
+ let process_result = runtime::process(&syntax_tree, None);
+ if process_result.is_err() {
+ println!("{}", process_result.unwrap_err());
+ return;
+ }
}
diff --git a/src/runtime.rs b/src/runtime.rs
index 8e71eb3..f059709 100644
--- a/src/runtime.rs
+++ b/src/runtime.rs
@@ -5,7 +5,7 @@ use std::fmt;
use std::rc::Rc;
use std::sync::atomic::{AtomicUsize, Ordering};
-#[derive(Debug, Clone)]
+#[derive(Debug, Clone, PartialEq)]
pub enum Value {
Integer(i64),
String(String),
@@ -20,7 +20,7 @@ impl fmt::Display for Value {
}
}
-#[derive(Debug, Clone)]
+#[derive(Debug, Clone, PartialEq)]
pub enum Term {
Variable(usize),
Abstraction(usize, Rc<Term>),
@@ -61,7 +61,7 @@ impl fmt::Display for Term {
}
}
-static VAR_ID_INC: AtomicUsize = AtomicUsize::new(0);
+pub static VAR_ID_INC: AtomicUsize = AtomicUsize::new(0);
pub fn advance_v() -> usize {
let v = VAR_ID_INC.load(Ordering::Relaxed);
@@ -69,38 +69,7 @@ pub fn advance_v() -> usize {
v
}
-// 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 bound_variable_opt_to_string(bound_variable_opt: &Option<(usize, Rc<Term>)>) -> String {
+fn _bound_variable_opt_to_string(bound_variable_opt: &Option<(usize, Rc<Term>)>) -> String {
match bound_variable_opt {
Some((v, term_rc)) => format!("({}, {})", v, term_rc),
None => String::from("None"),
@@ -130,21 +99,17 @@ fn substitute_var(
}
}
-type ReductionResult = Result<(Rc<Term>, usize), String>;
+pub type ReductionResult = Result<(Rc<Term>, usize), String>;
-fn reduce_term(
+pub fn reduce_term(
symbol_table: &HashMap<String, Rc<Term>>,
term_rc: Rc<Term>,
bound_variable_opt: &Option<(usize, Rc<Term>)>,
resolve_lazy: bool,
) -> ReductionResult {
let term = &*term_rc;
- println!(
- "[debug] reduce_term with term_rc:\n{}\nbound_variable_opt:\n{}\n",
- term_rc,
- bound_variable_opt_to_string(bound_variable_opt)
- );
- let result = match term {
+
+ match term {
Term::Primitive(_) => Ok((term_rc, 0)),
Term::Variable(_) => substitute_var(term_rc, bound_variable_opt),
Term::Application(lhs_rc, rhs_rc) => {
@@ -217,9 +182,39 @@ fn reduce_term(
// }
// }
_ => todo!("reduce_term cases"),
- };
- // println!("[debug] returning {}\n", result);
- result
+ }
+}
+
+const MAX_REDUCTION_ITERATIONS: usize = 1000;
+
+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 {
+ let mut term = term_rc;
+ let mut i: usize = 0;
+ loop {
+ i += 1;
+ 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 {
+ break;
+ }
+ }
+ Ok((term, 0))
}
fn process_expr_inner_unary(
@@ -317,8 +312,16 @@ fn process_expr(
}
}
-pub fn process(program: &ast::Program) {
- let mut symbol_table: HashMap<String, Rc<Term>> = HashMap::new();
+pub type ProcessResult = Result<(Vec<Rc<Term>>, HashMap<String, Rc<Term>>), String>;
+
+pub fn process(
+ program: &ast::Program,
+ initial_symbol_table: Option<HashMap<String, Rc<Term>>>,
+) -> ProcessResult {
+ let mut symbol_table: HashMap<String, Rc<Term>> =
+ initial_symbol_table.unwrap_or(HashMap::new());
+
+ let mut output_terms: Vec<Rc<Term>> = vec![];
for (_index, statement) in program.iter().enumerate() {
match statement {
@@ -327,7 +330,7 @@ pub fn process(program: &ast::Program) {
parameters,
expression,
} => {
- println!("[runtime] defining symbol: {:#?}", symbol);
+ // println!("[runtime] defining symbol: {:#?}", symbol);
let bound_params: Vec<(ast::Symbol, usize)> = parameters
.iter()
.map(|param| (param.clone(), advance_v()))
@@ -339,38 +342,19 @@ pub fn process(program: &ast::Program) {
term = Rc::new(Term::Abstraction(*v, Rc::clone(&term)));
});
- println!("Term:\n{}", term);
+ // println!("Term:\n{}", term);
symbol_table.insert(symbol.clone(), term);
}
ast::Statement::Expression(expression) => {
- println!("[runtime] evaluating free-standing expression");
- let mut term: Rc<Term> = process_expr(&symbol_table, expression, &vec![]);
- let mut reduction_result: ReductionResult;
- loop {
- // println!("Term:\n{}", term);
- reduction_result = reduce_term(&symbol_table, term.clone(), &None, false);
- match reduction_result {
- Ok((result_term, substitution_n)) => {
- println!("Reduction OK:\n{},\nN: {}\n", result_term, substitution_n);
- if substitution_n > 0 {
- term = result_term;
- } else {
- break;
- }
- }
- Err(err_string) => {
- println!("Reduction ERR:\n{}\n", err_string)
- }
- }
- }
+ // 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)?;
- println!("Reduction terminated, result:\n{}", term);
+ // println!("Reduction terminated, result:\n{}", term);
+ output_terms.push(result_term);
}
}
}
- // println!(
- // "[runtime] evaluation done, symbol_table state dump: {:#?}",
- // symbol_table
- // );
+ Ok((output_terms, symbol_table))
}
diff --git a/src/test.rs b/src/test.rs
new file mode 100644
index 0000000..58f9e84
--- /dev/null
+++ b/src/test.rs
@@ -0,0 +1,148 @@
+use super::*;
+use runtime::*;
+use serial_test::serial;
+use std::collections::HashMap;
+use std::rc::Rc;
+use std::sync::atomic::Ordering;
+
+fn evaluate_from_source(
+ content: String,
+ initial_symbol_table: Option<HashMap<String, Rc<Term>>>,
+) -> ProcessResult {
+ use ast::Program;
+ use pest::Parser;
+
+ let parse_tree_result = lparser::LParser::parse(lparser::Rule::program, &content);
+
+ if parse_tree_result.is_err() {
+ return Err(format!("{}", parse_tree_result.unwrap_err()));
+ }
+
+ let mut parse_tree = parse_tree_result.unwrap();
+
+ let syntax_tree: Program = ast::from_parse_tree(&mut parse_tree);
+
+ runtime::process(&syntax_tree, initial_symbol_table)
+}
+
+fn initialize_before_test() {
+ VAR_ID_INC.store(0, Ordering::Relaxed);
+}
+
+#[test]
+#[serial]
+fn test_reduce_integer_primitive() -> Result<(), String> {
+ initialize_before_test();
+ let term = Term::Primitive(Value::Integer(123));
+ let (result_term, _) = reduce_term(&HashMap::new(), Rc::new(term.clone()), &None, false)?;
+ assert_eq!(*result_term, term);
+ Ok(())
+}
+
+#[test]
+#[serial]
+fn test_reduce_string_primitive() -> Result<(), String> {
+ initialize_before_test();
+ let term = Term::Primitive(Value::String(String::from("foobar")));
+ let (result_term, _) = reduce_term(&HashMap::new(), Rc::new(term.clone()), &None, false)?;
+ assert_eq!(*result_term, term);
+ Ok(())
+}
+
+#[test]
+#[serial]
+fn test_reduce_id_call() -> Result<(), String> {
+ initialize_before_test();
+ let source = "
+ id 1;
+ ";
+ let (terms, symbol_table) = evaluate_from_source(String::from(source), None)?;
+ assert_eq!(terms.len(), 1);
+
+ let term = &terms[0];
+ let (result_term, _) = reduce_term(&symbol_table, Rc::clone(term), &None, false)?;
+
+ let expected = Term::Primitive(Value::Integer(1));
+ assert_eq!(*result_term, expected);
+ Ok(())
+}
+
+#[test]
+#[serial]
+fn test_reduce_id_call_negative() -> Result<(), String> {
+ initialize_before_test();
+ let source = "
+ id 1;
+ ";
+ let (terms, symbol_table) = evaluate_from_source(String::from(source), None)?;
+ assert_eq!(terms.len(), 1);
+
+ let term = &terms[0];
+ let (result_term, _) = reduce_term(&symbol_table, Rc::clone(term), &None, false)?;
+
+ let expected = Term::Primitive(Value::Integer(2));
+ assert_ne!(*result_term, expected);
+ Ok(())
+}
+
+#[test]
+#[serial]
+fn test_define_parameterized_func() -> Result<(), String> {
+ initialize_before_test();
+ let source = "
+ f a b = b a;
+ ";
+ let (terms, symbol_table) = evaluate_from_source(String::from(source), None)?;
+ assert_eq!(terms.len(), 0);
+
+ let term = symbol_table.get("f").ok_or("f not in symbol table")?;
+
+ let (result_term, _) = reduce_term(&symbol_table, Rc::clone(term), &None, false)?;
+
+ let expected = Term::Abstraction(
+ 0,
+ Rc::new(Term::Abstraction(
+ 1,
+ Rc::new(Term::Application(
+ Rc::new(Term::Variable(1)),
+ Rc::new(Term::Variable(0)),
+ )),
+ )),
+ );
+ assert_eq!(*result_term, expected);
+ Ok(())
+}
+
+#[test]
+#[serial]
+fn test_reduce_parameterized_func() -> Result<(), String> {
+ initialize_before_test();
+ let source = "
+ f 10 id;
+ ";
+
+ let predefined_f = Rc::new(Term::Abstraction(
+ 0,
+ Rc::new(Term::Abstraction(
+ 1,
+ Rc::new(Term::Application(
+ Rc::new(Term::Variable(1)),
+ Rc::new(Term::Variable(0)),
+ )),
+ )),
+ ));
+
+ let mut initial_symbol_table: HashMap<String, Rc<Term>> = HashMap::new();
+ initial_symbol_table.insert(String::from("f"), Rc::clone(&predefined_f));
+
+ let (terms, symbol_table) =
+ evaluate_from_source(String::from(source), Some(initial_symbol_table))?;
+ assert_eq!(terms.len(), 1);
+ let term = &terms[0];
+
+ let (result_term, _) = repeatedly_reduce_term(&symbol_table, Rc::clone(term), &None, false)?;
+
+ let expected = Term::Primitive(Value::Integer(10));
+ assert_eq!(*result_term, expected);
+ Ok(())
+}

Want to contribute? Host your changes somewhere and send me the link: jan (at) sydanviita.fi. Also, check out my website.


forge.jan.systems — powered by cgit