From 8463dd24f815fe2b8f25fe9763e0a43023bfbb20 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Fri, 23 Dec 2022 00:36:31 +0800 Subject: renaming core to chain and some other changes Some changes: - The core crate is renamed to "chain". - The crate "viz" is added, which will provide layered graph drawing algorithms. - A function is added to convert from a grammar to the regular language of its left-linear closures. - A function is added to convert from a nondeterministic finite automaton to its "null" closure. A null closure is the same automaton with edges added, as if some edges are "null". Whether an edge is null is determined by a function. Combined with the previous change, we can convert a grammar to the regular language of the null closure of its left-linear closures. --- Now it remains to test more grammars and add an Atom trait, before finishing the part about compilations. --- benches/bench_receme.rs | 293 ------------------------------------------------ 1 file changed, 293 deletions(-) delete mode 100644 benches/bench_receme.rs (limited to 'benches/bench_receme.rs') diff --git a/benches/bench_receme.rs b/benches/bench_receme.rs deleted file mode 100644 index c9583a9..0000000 --- a/benches/bench_receme.rs +++ /dev/null @@ -1,293 +0,0 @@ -use criterion::{black_box, criterion_group, criterion_main, Criterion}; - -use receme::{ - catana::{Ana, Cata}, - functor::Functor, - hylo::Hylo, - tree::{DFTree, TEStrategy, Tree, TreeIndex}, -}; - -#[derive(Debug, Clone)] -enum Expr { - Add(T, T), - Lit(isize), -} - -impl Functor for Expr { - type Target = Expr; - - fn fmap(self, mut f: impl FnMut(T) -> S) -> Self::Target { - match self { - Expr::Add(a, b) => Expr::Add(f(a), f(b)), - Expr::Lit(value) => Expr::Lit(value), - } - } -} - -#[derive(Debug, Clone)] -enum ExBox { - Add(Box, Box), - Lit(isize), -} - -impl ExBox { - fn lit(value: isize) -> Self { - Self::Lit(value) - } - - fn add(a: ExBox, b: ExBox) -> Self { - Self::Add(Box::new(a), Box::new(b)) - } -} - -pub fn bench(c: &mut Criterion) { - fn construct_tree() -> Tree> { - let strategy: TEStrategy = TEStrategy::UnsafeArena; - - let elements: Vec> = vec![ - Expr::Add(1, 2).fmap(TreeIndex::new), - Expr::Lit(1), - Expr::Add(3, 4).fmap(TreeIndex::new), - Expr::Lit(3), - Expr::Add(5, 6).fmap(TreeIndex::new), - Expr::Lit(10), - Expr::Lit(-14), - ]; - - Tree::new(elements, strategy) - } - - fn construct_box_tree() -> Box { - Box::new(ExBox::add( - ExBox::lit(1), - ExBox::add(ExBox::lit(3), ExBox::add(ExBox::lit(10), ExBox::lit(-14))), - )) - } - - let tree = construct_tree(); - - let safe_tree = { - let mut tree = tree.clone(); - tree.set_strategy(Default::default()); - tree - }; - - let depth_first_tree = { - let mut tree = tree.clone(); - tree.set_strategy(TEStrategy::DepthFirst); - tree - }; - - let boxtree = construct_box_tree(); - - c.bench_function("bench cata", |b| { - b.iter(|| { - let result = tree.clone().cata(|expr: Expr| match expr { - Expr::Add(a, b) => a + b, - Expr::Lit(v) => v, - }); - - black_box(result); - }) - }); - - c.bench_function("bench cata safe", |b| { - b.iter(|| { - let result = safe_tree.clone().cata(|expr: Expr| match expr { - Expr::Add(a, b) => a + b, - Expr::Lit(v) => v, - }); - - black_box(result); - }) - }); - - c.bench_function("bench cata depth first", |b| { - b.iter(|| { - let result = depth_first_tree - .clone() - .cata(|expr: Expr| match expr { - Expr::Add(a, b) => a + b, - Expr::Lit(v) => v, - }); - - black_box(result); - }) - }); - - c.bench_function("bench cata loop", |b| { - b.iter(|| { - let tree = tree.clone(); - - let mut stack: Vec> = vec![Ok(0)]; - let mut result_stack: Vec = vec![]; - - while let Some(top) = stack.pop() { - let top_is_ok_p = top.is_ok(); - - let top = match top { - Ok(top) => top, - Err(top) => top, - }; - - let top_node = tree.nth(top).unwrap(); - - match top_node { - Expr::Add(a, b) => { - if top_is_ok_p { - stack.push(Err(top)); - stack.push(Ok(**b)); - stack.push(Ok(**a)); - } else { - let a = result_stack.pop().unwrap(); - let b = result_stack.pop().unwrap(); - - result_stack.push(a + b); - } - } - Expr::Lit(v) => result_stack.push(*v), - } - } - - let result = result_stack.pop().unwrap(); - - black_box(result); - }) - }); - - c.bench_function("bench ana box loop", |b| { - b.iter(|| { - let boxtree = boxtree.clone(); - - let mut elements = vec![]; - - let mut stack = vec![boxtree]; - - while let Some(bt) = stack.pop() { - match *bt { - ExBox::Add(a, b) => { - let len = elements.len(); - - elements.push(Expr::Add(TreeIndex::new(len + 1), TreeIndex::new(len + 2))); - - stack.push(b); - stack.push(a); - } - ExBox::Lit(v) => elements.push(Expr::Lit(v)), - } - } - - let tree: Tree> = Tree::new(elements, Default::default()); - - black_box(tree); - }) - }); - - c.bench_function("bench ana boxed", |b| { - b.iter(|| { - let boxtree = boxtree.clone(); - - let tree = Tree::ana(boxtree, |bt: Box| match *bt { - ExBox::Add(a, b) => Expr::Add(a, b), - ExBox::Lit(v) => Expr::Lit(v), - }); - - black_box(tree); - }) - }); - - c.bench_function("bench ana depth first boxed", |b| { - b.iter(|| { - let boxtree = boxtree.clone(); - - let tree = DFTree::ana(boxtree, |bt: Box| match *bt { - ExBox::Add(a, b) => Expr::Add(a, b), - ExBox::Lit(v) => Expr::Lit(v), - }); - - black_box(tree); - }) - }); - - c.bench_function("bench hylo", |b| { - b.iter(|| { - let boxtree = boxtree.clone(); - - black_box(Tree::hylo( - boxtree, - |expr| match expr { - Expr::Add(a, b) => a + b, - Expr::Lit(v) => v, - }, - |bt: Box| match *bt { - ExBox::Add(a, b) => Expr::Add(a, b), - ExBox::Lit(v) => Expr::Lit(v), - }, - )) - }) - }); - - c.bench_function("bench hylo loop", |b| { - b.iter(|| { - let boxtree = boxtree.clone(); - - let mut elements = vec![]; - - let mut stack = vec![boxtree]; - - while let Some(bt) = stack.pop() { - match *bt { - ExBox::Add(a, b) => { - let len = elements.len(); - - elements.push(Expr::Add(TreeIndex::new(len + 1), TreeIndex::new(len + 2))); - - stack.push(b); - stack.push(a); - } - ExBox::Lit(v) => elements.push(Expr::Lit(v)), - } - } - - let tree: Tree> = Tree::new(elements, Default::default()); - - let mut stack: Vec> = vec![Ok(0)]; - let mut result_stack: Vec = vec![]; - - while let Some(top) = stack.pop() { - let top_is_ok_p = top.is_ok(); - let top = match top { - Ok(top) => top, - Err(top) => top, - }; - - let top_node = tree.nth(top).unwrap(); - - match top_node { - Expr::Add(a, b) => { - if top_is_ok_p { - stack.push(Err(top)); - stack.push(Ok(**b)); - stack.push(Ok(**a)); - } else { - let a = result_stack.pop().unwrap(); - let b = result_stack.pop().unwrap(); - - result_stack.push(a + b); - } - } - Expr::Lit(v) => result_stack.push(*v), - } - } - - let result = result_stack.pop().unwrap(); - - assert_eq!(result, 0); - - black_box(result); - }) - }); -} - -criterion_group!(benches, bench); -criterion_main!(benches); -- cgit v1.2.3-18-g5258