1 
//! # Gen_reduce
2 
//!
3 
//! **A generic reduction engine for recursive data types.**
4 
//!
5 
//! This library provides methods which, given a tree and a set of node-to-node transformation rules,
6 
//! repeatedly rewrites parts of the tree until no more rules can be applied.
7 
//!
8 
//! ## A Simple Example
9 
//!
10 
//! ***Adapted from (Mitchell and Runciman 2007)***
11 
//!
12 
//! Below is an example using a "calculator" language. The engine allows us to reduce the expression to a simplified form.
13 
//!
14 
//# TODO (Felix): choose a more concise example
15 
//!
16 
//! ```rust
17 
//! use tree_morph::*;
18 
//! use uniplate::derive::Uniplate;
19 
//!
20 
//! #[derive(Debug, Clone, PartialEq, Eq, Uniplate)]
21 
//! enum Expr {
22 
//!     Add(Box<Expr>, Box<Expr>),
23 
//!     Mul(Box<Expr>, Box<Expr>),
24 
//!     Neg(Box<Expr>),
25 
//!     Val(i32),
26 
//!     Var(String),
27 
//! }
28 
//!
29 
//! enum ReductionRule {
30 
//!     Eval,       // Evaluate constant expressions
31 
//!
32 
//!     AddZero,   // a + 0 ~> a
33 
//!     AddSame,   // a + a ~> 2 * a
34 
//!     MulOne,    // a * 1 ~> a
35 
//!     MulZero,   // a * 0 ~> 0
36 
//!     DoubleNeg, // -(-a) ~> a
37 
//!
38 
//!     Associativity, // Define a consistent form: a */+ (b */+ c) ~> (a */+ b) */+ c
39 
//!                    // This rule also mixes things up for (a, b) to be tested by other rules
40 
//! }
41 
//!
42 
//! impl Rule<Expr, ()> for ReductionRule {
43
153 
//!     fn apply(&self, cmd: &mut Commands<Expr, ()>, expr: &Expr, _: &()) -> Option<Expr> {
44 
//!         use ReductionRule::*;
45 
//!         use Expr::*;
46 
//!
47
153 
//!         match self {
48
12 
//!             AddZero => match expr {
49
12 
//!                 Add(a, b) if matches!(a.as_ref(), Val(0)) => Some(*b.clone()),
50
12 
//!                 Add(a, b) if matches!(b.as_ref(), Val(0)) => Some(*a.clone()),
51
23 
//!                 _ => None,
52 
//!             },
53
11 
//!             AddSame => match expr {
54
11 
//!                 Add(a, b) if a == b => Some(Mul(bx(Val(2)), a.clone())),
55
21 
//!                 _ => None,
56 
//!             },
57
6 
//!             MulOne => match expr {
58
6 
//!                 Mul(a, b) if matches!(a.as_ref(), Val(1)) => Some(*b.clone()),
59
6 
//!                 Mul(a, b) if matches!(b.as_ref(), Val(1)) => Some(*a.clone()),
60
20 
//!                 _ => None,
61 
//!             },
62
5 
//!             MulZero => match expr {
63
5 
//!                 Mul(a, b) if matches!(a.as_ref(), Val(0)) ||
64
5 
//!                     matches!(b.as_ref(), Val(0)) => Some(Val(0)),
65
20 
//!                 _ => None,
66 
//!             },
67
20 
//!             DoubleNeg => match expr {
68
1 
//!                 Neg(a) => match a.as_ref() {
69
1 
//!                     Neg(b) => Some(*b.clone()),
70 
//!                     _ => None,
71 
//!                 },
72
19 
//!                 _ => None,
73 
//!             },
74
26 
//!             Eval => match expr {
75
13 
//!                 Add(a, b) => match (a.as_ref(), b.as_ref()) {
76
1 
//!                     (Val(x), Val(y)) => Some(Val(x + y)),
77
12 
//!                     _ => None,
78 
//!                 },
79
7 
//!                 Mul(a, b) => match (a.as_ref(), b.as_ref()) {
80
1 
//!                     (Val(x), Val(y)) => Some(Val(x * y)),
81
6 
//!                     _ => None,
82 
//!                 },
83
1 
//!                 Neg(a) => match a.as_ref() {
84 
//!                     Val(x) => Some(Val(-x)),
85
1 
//!                     _ => None,
86 
//!                 },
87
5 
//!                 _ => None,
88 
//!             },
89
19 
//!            Associativity => match expr {
90
9 
//!                 Add(a, b) => match (a.as_ref(), b.as_ref()) {
91
1 
//!                     (x, Add(y, z)) => Some(Add(bx(Add(a.clone(), y.clone())), z.clone())),
92
8 
//!                     _ => None,
93 
//!                 },
94
5 
//!                 Mul(a, b) => match (a.as_ref(), b.as_ref()) {
95
1 
//!                     (x, Mul(y, z)) => Some(Mul(bx(Mul(a.clone(), y.clone())), z.clone())),
96
4 
//!                     _ => None,
97 
//!                 },
98
5 
//!                 _ => None,
99 
//!             },
100 
//!         }
101
153 
//!     }
102 
//! }
103 
//!
104 
//! // (-(-x) + ((x * 1) + 0)) + ((1 + 1) * x)   ~>   4 * x
105
1 
//! fn main() {
106 
//!     use Expr::*;
107 
//!     use ReductionRule::*;
108 
//!
109
1 
//!     let expr = Add(
110
1 
//!         bx(Add(
111
1 
//!             bx(Neg(
112
1 
//!                 bx(Neg(
113
1 
//!                     bx(Var("x".to_string())),
114
1 
//!                 )),
115
1 
//!             )),
116
1 
//!             bx(Add(
117
1 
//!                 bx(Mul(
118
1 
//!                     bx(Var("x".to_string())),
119
1 
//!                     bx(Val(1)),
120
1 
//!                 )),
121
1 
//!                 bx(Val(0)),
122
1 
//!             )),
123
1 
//!         )),
124
1 
//!         bx(Mul(
125
1 
//!             bx(Add(
126
1 
//!                 bx(Val(1)),
127
1 
//!                 bx(Val(1))
128
1 
//!             )),
129
1 
//!             bx(Var("x".to_string())),
130
1 
//!         )),
131
1 
//!     );
132
1 
//!
133
1 
//!     // Ordering is important here: we evaluate first (1), then reduce (2..6), then change form (7)
134
1 
//!     let rules = [Eval, AddZero, AddSame, MulOne, MulZero, DoubleNeg, Associativity];
135
1 
//!
136
1 
//!     let (expr, _) = reduce_with_rules(&rules, helpers::select_first, expr, ());
137
1 
//!     assert_eq!(expr, Mul(bx(Val(4)), bx(Var("x".to_string()))));
138
1 
//! }
139 
//!
140
20 
//! fn bx(expr: Expr) -> Box<Expr> {
141
20 
//!     Box::new(expr)
142
20 
//! }
143 
//! ```
144 
//!
145 
//! ## Recommendations
146 
//!
147 
//! Defining rules as an enum can quickly lead to massive match statements.
148 
//! To avoid this, consider instead using a struct containing a function pointer.
149 
//! These functions can then be defined elsewhere for better organization.
150 
//!
151 

            

        

            

                152
            

            

                
            

            

                
mod commands;

            

        

            

                153
            

            

                
            

            

                
pub mod helpers;

            

        

            

                154
            

            

                
            

            

                
mod reduce;

            

        

            

                155
            

            

                
            

            

                
mod reduction;

            

        

            

                156
            

            

                
            

            

                
mod rule;

            

        

            

                157
            

            

                
            

            

                

            

        

            

                158
            

            

                
            

            

                
pub use commands::Commands;

            

        

            

                159
            

            

                
            

            

                
pub use reduce::{reduce, reduce_with_rules};

            

        

            

                160
            

            

                
            

            

                
pub use reduction::Reduction;

            

        

            

                161
            

            

                
            

            

                
pub use rule::Rule;