easy_lambda_calculus/
main.rs

1use std::collections::HashMap;
2use std::fmt;
3
4//macro for new lambda
5#[macro_export]
6macro_rules! lambda {
7    ($x:expr) => (
8        Lambda::new($x, vec![])
9    );
10    ($x:expr, $($y:expr), +) => (
11        Lambda::new($x, vec![$($y), +])
12    );
13
14}
15
16//Lambda data type
17#[derive(Debug, PartialEq, Clone)]
18pub enum Lambda {
19    Func((Box<Lambda>, Box<Lambda>)),
20    Variable(String),
21    Reducible((Box<Lambda>, Box<Lambda>)),
22    AlphaMark(Box<Lambda>),
23    //tokens
24    StVec(Vec<String>),
25    Brack(Vec<Lambda>),
26    TFunc(Vec<String>),
27    Container(Box<Lambda>),
28    AttPl(()),
29}
30
31impl Lambda {
32    //Alphabet for variable naming
33    const ALPH: &str = "xyzwabcdefghijklmnopqrstuv";
34    //new lambda from formatted string
35    pub fn new(s: &str, f: Vec<Lambda>) -> Lambda {
36        let chars = s
37            .chars()
38            .collect::<Vec<char>>()
39            .iter()
40            .map(|x| x.to_string())
41            .collect::<Vec<String>>();
42        let bracks = Self::find_bracks(chars, false);
43        let tokens = Self::parse_bracks(bracks, &f, 0).0;
44        Self::parse_tokens(tokens)
45    }
46    //order characters by brackets
47    fn find_bracks(chars: Vec<String>, alph: bool) -> Lambda {
48        //find brackets
49        let mut starts: Vec<usize> = Vec::new();
50        let mut ends: Vec<usize> = Vec::new();
51        let mut alphas: Vec<usize> = Vec::new();
52        let mut count = 0;
53        for (i, char) in chars.iter().enumerate() {
54            match (char.as_str(), count) {
55                (")", 1) => {
56                    ends.push(i);
57                    count -= 1;
58                }
59                (")", 0) => panic!("Unclosed bracket"),
60                (")", _) => count -= 1,
61                ("(", 0) => {
62                    if i != 0 && chars[i - 1] == "&" {
63                        alphas.push(i)
64                    }
65                    starts.push(i);
66                    count += 1;
67                }
68                ("(", _) => count += 1,
69                _ => {}
70            }
71        }
72        if starts.len() != ends.len() {
73            panic!("Unclosed bracket");
74        }
75        //split the string into bracket tokens and mark them for alpha reduction if needed
76        if starts.is_empty() && alph {
77            return Self::AlphaMark(Box::new(Self::Brack(vec![Self::StVec(chars)])));
78        } else if starts.is_empty() {
79            return Self::Brack(vec![Self::StVec(chars)]);
80        }
81        let mut bracks: Vec<Lambda> = Vec::new();
82        if !chars[..starts[0]].to_vec().is_empty() {
83            bracks.push(Self::StVec(chars[..starts[0]].to_vec()));
84        }
85        for i in 0..starts.len() {
86            if alphas.contains(&starts[i]) {
87                bracks.push(Self::find_bracks(
88                    chars[starts[i] + 1..ends[i]].to_vec(),
89                    true,
90                ));
91            } else {
92                bracks.push(Self::find_bracks(
93                    chars[starts[i] + 1..ends[i]].to_vec(),
94                    false,
95                ));
96            }
97            if i + 1 != starts.len() {
98                bracks.push(Self::StVec(chars[ends[i] + 1..starts[i + 1]].to_vec()));
99            } else if !chars[ends[i] + 1..].to_vec().is_empty() {
100                bracks.push(Self::StVec(chars[ends[i] + 1..].to_vec()));
101            }
102        }
103        if alph {
104            return Self::AlphaMark(Box::new(Self::Brack(bracks)));
105        }
106        Self::Brack(bracks)
107    }
108    //parse the brackets and characters into brackets and tokens
109    fn parse_bracks(brs: Lambda, vec: &Vec<Lambda>, mut vec_num: usize) -> (Lambda, usize) {
110        if let Self::Brack(br) = brs {
111            let mut parse_vec: Vec<Lambda> = Vec::new();
112            for b in br {
113                match &b {
114                    Self::Brack(_) => {
115                        let t: Lambda;
116                        (t, vec_num) = Self::parse_bracks(b, vec, vec_num);
117                        if let Self::Brack(v) = &t
118                            && v.len() == 1
119                        {
120                            parse_vec.push(v[0].clone());
121                        } else {
122                            parse_vec.push(t);
123                        }
124                    }
125                    Self::StVec(v) => {
126                        let t: Vec<Lambda>;
127                        (t, vec_num) = Self::parse_stvec(v.clone(), vec, vec_num);
128                        parse_vec.extend_from_slice(&t[..]);
129                    }
130                    Self::AlphaMark(l) => {
131                        let temp: Lambda;
132                        (temp, vec_num) = Self::parse_bracks(*l.clone(), vec, vec_num);
133                        parse_vec.push(Self::AlphaMark(Box::new(temp)));
134                    }
135                    _ => panic!("Syntax error"),
136                }
137            }
138            return (Self::Brack(parse_vec), vec_num);
139        }
140        panic!("Syntax error")
141    }
142    //turn the characters into tokens
143    fn parse_stvec(strs: Vec<String>, vec: &[Lambda], mut vec_num: usize) -> (Vec<Lambda>, usize) {
144        let mut token_vec: Vec<Lambda> = Vec::new();
145        let mut pass_num = 0;
146        for i in 0..strs.len() {
147            if pass_num > 0 {
148                pass_num -= 1;
149            } else if strs[i] == "%" {
150                (token_vec, pass_num) = Self::parse_func_char(strs.clone(), token_vec, i);
151            } else if strs[i] == "{" && strs[i + 1] == "}" {
152                token_vec.push(Self::Container(Box::new(vec[vec_num].clone())));
153                vec_num += 1;
154                pass_num += 1;
155            } else {
156                for j in i..strs.len() {
157                    match strs[j].as_str() {
158                        " " => {
159                            token_vec.push(Self::AttPl(()));
160                        }
161                        "&" => {}
162                        "{" => {}
163                        "}" => {}
164                        _ => {
165                            (token_vec, pass_num) = Self::find_vars(&strs, token_vec, j);
166                        }
167                    }
168                }
169                pass_num += 1;
170            }
171        }
172        (token_vec, vec_num)
173    }
174    //find variable tokens
175    fn find_vars(strs: &[String], mut token_vec: Vec<Lambda>, i: usize) -> (Vec<Lambda>, i32) {
176        let mut pass_num = 0;
177        if !Self::ALPH.contains(&strs[i]) {
178            panic!("Syntax error");
179        }
180        let mut var: String = "".to_string();
181        for k in i..strs.len() {
182            if !Self::ALPH.contains(&strs[k]) {
183                token_vec.push(Self::Variable(var));
184                pass_num += 1;
185                break;
186            }
187            var.push_str(&strs[k]);
188            if k == strs.len() - 1 {
189                token_vec.push(Self::Variable(var));
190                pass_num += 1;
191                break;
192            }
193            pass_num += 1;
194        }
195        (token_vec, pass_num)
196    }
197    //parse the function syntax
198    fn parse_func_char(
199        strs: Vec<String>,
200        mut token_vec: Vec<Lambda>,
201        i: usize,
202    ) -> (Vec<Lambda>, i32) {
203        let mut pass_num: i32 = 0;
204        let mut val_vec: Vec<String> = Vec::new();
205        let mut var: String = "".to_string();
206        for st in strs[i + 1..].iter() {
207            match st.as_str() {
208                "." => {
209                    val_vec.push(var);
210                    token_vec.push(Self::TFunc(val_vec));
211                    pass_num += 1;
212                    break;
213                }
214                "|" => {
215                    val_vec.push(var);
216                    var = "".to_string();
217                }
218                _ => {
219                    if Self::ALPH.contains(st) {
220                        var.push_str(st);
221                    } else {
222                        panic!("Syntax error");
223                    }
224                }
225            }
226            pass_num += 1;
227        }
228        (token_vec, pass_num)
229    }
230    //turn brackets and tokens into a lambda
231    fn parse_tokens(token: Lambda) -> Lambda {
232        match token {
233            Self::Brack(v) => Self::parse_token_vec(v),
234            Self::Variable(_) => token,
235            Self::AlphaMark(l) => Self::AlphaMark(Box::new(Self::parse_tokens(*l))),
236            Self::Reducible((a, b)) => Self::parse_tokens(*a).attach(Self::parse_tokens(*b)),
237            Self::Func((a, b)) => Self::Func((a, Box::new(Self::parse_tokens(*b)))),
238            Self::Container(l) => *l,
239            _ => panic!("syntax error"),
240        }
241    }
242    //turn a vec of tokens into a lambda
243    fn parse_token_vec(mut vec: Vec<Lambda>) -> Lambda {
244        let temp_vec = vec.clone();
245        for (i, l) in temp_vec.iter().enumerate() {
246            if let Self::AttPl(_) = *l {
247                vec = [
248                    &vec[..i - 1],
249                    &vec![
250                        Self::parse_tokens(vec[i - 1].clone())
251                            .attach(Self::parse_tokens(vec[i + 1].clone())),
252                    ][..],
253                    &vec[i + 2..],
254                ]
255                .concat();
256            }
257        }
258        match vec[0].clone() {
259            Self::TFunc(v) => Self::parse_func_token(v, vec),
260            Self::Brack(_) => Self::parse_tokens(vec[0].clone()),
261            Self::Reducible(_) => Self::parse_tokens(vec[0].clone()),
262            Self::Variable(_) => vec[0].clone(),
263            _ => panic!("Syntax error"),
264        }
265    }
266    //turn the shorthand function token into lambda functions
267    fn parse_func_token(vec: Vec<String>, tokens: Vec<Lambda>) -> Lambda {
268        if !vec.is_empty() {
269            return Self::func(
270                vec[0].as_str(),
271                Self::parse_func_token(vec[1..vec.len()].to_vec(), tokens),
272            );
273        }
274        if tokens.is_empty() {
275            panic!("Syntax error");
276        }
277        Self::parse_token_vec(tokens[1..tokens.len()].to_vec())
278    }
279    //make new function variant with a string and a Lambda
280    pub fn func(a: &str, b: Lambda) -> Lambda {
281        Self::Func((Box::new(Self::var(a)), Box::new(b)))
282    }
283    //make new variable variant with a string
284    pub fn var(inp: &str) -> Lambda {
285        Self::Variable(inp.to_string())
286    }
287    //make new reductible variant by attaching an input Lambda to a Lambda
288    pub fn attach(self, a: Lambda) -> Lambda {
289        Self::Reducible((Box::new(self), Box::new(a)))
290    }
291    //mark a lambda for alpha reduction
292    pub fn alpha(self) -> Lambda {
293        Self::AlphaMark(Box::new(self))
294    }
295    //beta reduce a reducible
296    pub fn reduce(self) -> Lambda {
297        if let Self::Reducible((a, b)) = self.clone() {
298            //if reducible has a function reduce the function, else if it has a reducible, reduce the inside reducible
299            if let Self::Func((c, d)) = &*a {
300                return Self::recursive_reduce(*d.clone(), *c.clone(), *b);
301            } else if let Self::Reducible(_) = &*a {
302                return a.reduce().attach(*b);
303            }
304            panic!("Cannot reduce");
305        }
306        panic!("Cannot reduce");
307    }
308    //alpha reduce a lambda
309    pub fn alpha_reduce(self) -> Lambda {
310        let (m, _, _) = Self::set_map(self.clone(), vec![HashMap::new()], 0, 0, 0);
311        let (out, _) = Self::recursive_alpha(self, m, 0, 0);
312        out
313    }
314    //recursive function to substitute every instance of the given variable
315    fn recursive_reduce(b: Lambda, a: Lambda, sub: Lambda) -> Lambda {
316        match b {
317            //if it is a function variant, check for the variable being substituted or reduce an inside function
318            Self::Func((c, d)) => {
319                if a != *d {
320                    return Self::Func((c, Box::new(Self::recursive_reduce(*d, a, sub))));
321                }
322                Self::Func((c, Box::new(sub)))
323            }
324            //if it is a reducible, reduce both the function and the input expression
325            Self::Reducible((c, d)) => Self::recursive_reduce(*c, a.clone(), sub.clone())
326                .attach(Self::recursive_reduce(*d, a, sub)),
327            //if it is just a variable, substitute if it is the variable being substituted
328            Self::Variable(_) => {
329                if a == b {
330                    return sub;
331                }
332                b
333            }
334            Self::AlphaMark(_) => b,
335            _ => panic!("Cannot reduce {:?}", b),
336        }
337    }
338    //function to evaluate lambda
339    pub fn evaluate(self) -> Lambda {
340        self.alpha_reduce().recursive_evaluate().alpha_reduce()
341    }
342    //function to recursively reduce every reducible
343    fn recursive_evaluate(self) -> Lambda {
344        if let Self::Reducible(_) = self {
345            return self.reduce().recursive_evaluate();
346        }
347        self
348    }
349    //function to assign a vector of hashmaps to a lambda
350    fn set_map(
351        l: Lambda,
352        mut m: Vec<HashMap<String, usize>>,
353        mut i: usize,
354        al: usize,
355        mut al_in: usize,
356    ) -> (Vec<HashMap<String, usize>>, usize, usize) {
357        match l {
358            Self::Variable(a) => {
359                if !m[al].contains_key(a.as_str()) {
360                    m[al].insert(a, i);
361                    (m, i + 1, al_in)
362                } else {
363                    (m, i, al_in)
364                }
365            }
366            Self::Func((a, b)) => {
367                if let Self::Variable(c) = *a
368                    && !m[al].contains_key(c.as_str())
369                {
370                    m[al].insert(c, i);
371                }
372                Self::set_map(*b, m, i + 1, al, al_in)
373            }
374            Self::Reducible((a, b)) => {
375                (m, i, al_in) = Self::set_map(*a, m, i, al, al_in);
376                Self::set_map(*b, m, i, al, al_in)
377            }
378            Self::AlphaMark(a) => {
379                al_in += 1;
380                m.push(HashMap::new());
381                Self::set_map(*a, m, i, al_in, al_in)
382            }
383            _ => panic!("Cannot map lambda"),
384        }
385    }
386    //function to get a lambda variable name from an integer
387    fn get_name(mut n: usize) -> String {
388        let mut out = "".to_string();
389        let chars = Self::ALPH.chars();
390        let num = chars.clone().count();
391        n += 1;
392        while n != 0 {
393            let mut temp = chars.clone().nth((n - 1) % num).unwrap().to_string();
394            temp.push_str(&out);
395            out = temp;
396            n = ((n - 1) - ((n - 1) % num)) / num;
397        }
398        out
399    }
400    //recursive function to remove any colliding variable names
401    fn recursive_alpha(
402        l: Lambda,
403        m: Vec<HashMap<String, usize>>,
404        al: usize,
405        mut al_in: usize,
406    ) -> (Lambda, usize) {
407        match l {
408            Self::Variable(a) => match m[al].get(&a) {
409                Some(b) => (Self::Variable(Self::get_name(*b)), al_in),
410                _ => panic!("Cannot alpha reduce"),
411            },
412            Self::Func((a, b)) => {
413                let c: Lambda;
414                let d: Lambda;
415                (c, al_in) = Self::recursive_alpha(*a, m.clone(), al, al_in);
416                (d, al_in) = Self::recursive_alpha(*b, m, al, al_in);
417                (Self::Func((Box::new(c), Box::new(d))), al_in)
418            }
419            Self::Reducible((a, b)) => {
420                let c: Lambda;
421                let d: Lambda;
422                (c, al_in) = Self::recursive_alpha(*a, m.clone(), al, al_in);
423                (d, al_in) = Self::recursive_alpha(*b, m, al, al_in);
424                (c.attach(d), al_in)
425            }
426            Self::AlphaMark(a) => {
427                al_in += 1;
428                Self::recursive_alpha(*a, m, al_in, al_in)
429            }
430            _ => panic!("Cannot alpha reduce"),
431        }
432    }
433    //function to calculate a string to represent the lambda
434    fn display(l: Lambda) -> String {
435        match l {
436            Self::Variable(a) => a,
437            Self::Func((a, mut b)) => {
438                let d = b.clone();
439                let mut s1 = Self::display(*a);
440                let mut s2 = "".to_string();
441                while let Self::Func((ref a, ref c)) = *b {
442                    s1.push('|');
443                    s1.push_str(&Self::display(*a.clone()));
444                    if let Self::Func(_) = **c {
445                    } else {
446                        s2 = Self::display(*c.clone());
447                    }
448                    b = c.clone();
449                }
450                if s2.is_empty() {
451                    s2 = Self::display(*d)
452                }
453                format!("(λ{}.{})", &s1, &s2)
454            }
455            Self::Reducible((a, b)) => {
456                let s1 = Self::display(*a);
457                let s2 = Self::display(*b);
458                format!("({} {})", &s1, &s2)
459            }
460            Self::AlphaMark(a) => {
461                let s1 = Self::display(*a);
462                format!("&{}", &s1)
463            }
464            _ => panic!("Cannot display"),
465        }
466    }
467}
468
469//implement display for the lambda data type
470impl fmt::Display for Lambda {
471    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
472        write!(f, "{}", Lambda::display(self.clone()))
473    }
474}
475
476//code to evaluate a(t, t)
477pub fn main() {
478    let t = lambda!("%x|y.x"); //true
479    let f = lambda!("%x|y.y"); //false
480    let a = lambda!("%x|y.(x y) &{}", f); //and
481    let res = lambda!("({} &{}) &{}", a, t.clone(), t); //and(true, true)
482    println!("{}", res.evaluate());
483}
484//outputs (%x|y.x) which is equivalent to true
easy_lambda_calculus/main.rs

easy_lambda_calculus/
main.rs
