lamcalc/
builder.rs

1//! Conveniently build Lambda expressions.
2use crate::exp::{Exp, Ident};
3
4impl<T: Clone + Eq> Exp<T> {
5    /// 标识符与 var 相同的 unbounded 变量绑定为 var
6    ///
7    /// de_bruijn_index 的初值为 0
8    fn bind(&mut self, id: &T, de_bruijn_index: u32) -> &mut Self {
9        match self {
10            Exp::Var(var) => {
11                if var.0 == *id {
12                    var.1 = de_bruijn_index
13                }
14            }
15            Exp::Abs(var, exp) => {
16                if var.0 != *id {
17                    exp.bind(id, de_bruijn_index + 1);
18                }
19            }
20            Exp::App(l, exp) => {
21                l.bind(id, de_bruijn_index);
22                exp.bind(id, de_bruijn_index);
23            }
24        };
25        self
26    }
27}
28
29#[doc(hidden)]
30pub fn app<T>(exps: Vec<Exp<T>>) -> Exp<T>
31where
32    T: Clone + Eq,
33{
34    let mut res = None;
35    for exp in exps {
36        res = match res {
37            Some(l) => Some(Exp::App(Box::new(l), Box::new(exp))),
38            None => Some(exp),
39        }
40    }
41    res.unwrap()
42}
43
44#[doc(hidden)]
45pub fn abs<T>(v: T, exp: Exp<T>) -> Exp<T>
46where
47    T: Clone + Eq,
48{
49    let mut exp = exp;
50    exp.bind(&v, 1); // 下面有 abstraction 故初值为 1
51    Exp::Abs(Ident(v, 0), Box::new(exp))
52}
53
54#[doc(hidden)]
55pub fn unbounded_var<T>(v: T) -> Exp<T>
56where
57    T: Clone + Eq,
58{
59    Exp::Var(Ident(v, 0))
60}
61
62/// Build lambda expression with [`String`] identifier conveniently.
63/// Generally:
64///
65/// 1. Dot `.` can be used to define abstraction.
66/// 2. Parentheses can be used to denote subexpression.
67/// 3. Application is left associated by default.
68/// 
69/// If you find an expression not parsed, try adding parentheses to subexpressions.
70///
71/// For examples please checkout the home page.
72#[macro_export]
73macro_rules! lambda {
74    // 消掉外层括号
75    [($( $t:tt )+)] => {
76        lambda![$( $t )+]
77    };
78    // variable expression
79    [{$v:expr}] => {
80        $v.clone()
81    };
82    // variable
83    // The keyword metavariable $crate can be used to refer to the current crate;
84    [$v:ident] => {
85        $crate::builder::unbounded_var::<String>(String::from(stringify!($v)))
86    };
87    // abstraction
88    [$v:ident.$( $t:tt )+] => {
89        $crate::builder::abs(String::from(stringify!($v)), lambda![$( $t )+])
90    };
91    // application
92    [$l:tt $( $t:tt )+] => {
93        $crate::builder::app(vec![lambda![$l], $( lambda![$t] ),+])
94    };
95}
96
97#[cfg(test)]
98mod tests {
99    use crate::builder::{abs, app, unbounded_var};
100
101    #[test]
102    fn test_builder() {
103        let and = lambda!(x. (y. x y x));
104        assert_eq!(
105            and,
106            abs(
107                String::from("x"),
108                abs(
109                    String::from("y"),
110                    app(vec![
111                        unbounded_var(String::from("x")),
112                        unbounded_var(String::from("y")),
113                        unbounded_var(String::from("x")),
114                    ])
115                )
116            )
117        );
118    }
119}
lamcalc/builder.rs

lamcalc/
builder.rs
