easy_lambda_calculus/
lib.rs

1//! Simple and easy to write lambda calculus
2//! # Example:
3//! ```rust
4//! use easy_lambda_calculus::*;
5//!
6//! //code to evaluate and(true, true)
7//!fn main() {
8//!   let t = lambda!("%x|y.x"); //true
9//!   let f = lambda!("%x|y.y"); //false
10//!   let a = lambda!("%x|y.(x y) &{}", f); //and
11//!   let res = lambda!("({} &{}) &{}", a, t.clone(), t); //and(true, true)
12//!   println!("{}", res.evaluate());
13//!}
14//! //outputs (%x|y.x) which is equivalent to true
15
16use std::collections::HashMap;
17use std::fmt;
18
19///Makes a new lambda from a string
20///
21///```rust
22///use easy_lambda_calculus::*;
23///
24///let l = lambda!("%x|y.y")
25///println!("{}", lambda!("%x|y.(x y) &{}", l));
26/// //outputs λx|y.(x y) &(λx|y.y)
27///```
28///
29///#### Syntax:
30///
31///%x.x to define function with input variable x and output defined after the dot.
32///
33///%x|y.y to define a function with multiple inputs (equivalent to %x.(%y.y) ), variables separated by a pipe | character.
34///
35///Variables can be multiple characters.
36///eg: %var.var or %true|false.true are also valid.
37///
38///(x y) to apply y into function x.
39///(x y z) is not valid as the reduction order is ambiguous, define it with ((x y) z) or (x (y z)), see Lambda.reduce() for reduction order.
40///
41///&(x) is used to mark section x for alpha reduction, so you can reuse variable names without any unintended interactions.
42///
43///{} is used to input a lambda variable into the lambda, uses the same syntax as the `format!()` macro, &{} is shorthand for &({}).
44#[macro_export]
45macro_rules! lambda {
46    ($x:expr) => (
47        Lambda::new($x, vec![])
48    );
49    ($x:expr, $($y:expr), +) => (
50        Lambda::new($x, vec![$($y), +])
51    );
52
53}
54
55///Lambda data type
56#[derive(Debug, PartialEq, Clone)]
57pub enum Lambda {
58    ///Function
59    Func((Box<Lambda>, Box<Lambda>)),
60    ///Variable
61    Variable(String),
62    ///Marks a lambda being applied into a function
63    Reducible((Box<Lambda>, Box<Lambda>)),
64    ///Marks a lambda for alpha reduction
65    AlphaMark(Box<Lambda>),
66
67    ///Vector of strings to be converted into a lambda
68    StVec(Vec<String>),
69    ///Token for brackets
70    Brack(Vec<Lambda>),
71    ///Token for shorthand functions
72    TFunc(Vec<String>),
73    ///Token to contain a lambda inputted through formatting
74    Container(Box<Lambda>),
75    ///Token to mark where to put reducibles
76    AttPl(()),
77}
78
79impl Lambda {
80    //Alphabet for variable naming
81    const ALPH: &str = "xyzwabcdefghijklmnopqrstuv";
82    //new lambda from formatted string
83    #[doc(hidden)]
84    pub fn new(s: &str, f: Vec<Lambda>) -> Lambda {
85        let chars = s
86            .chars()
87            .collect::<Vec<char>>()
88            .iter()
89            .map(|x| {
90                let mut a = x.to_string();
91                if a == "{" {
92                    a = "({".to_string();
93                } else if a == "}" {
94                    a = "})".to_string();
95                }
96                a.clone()
97            })
98            .collect::<String>()
99            .chars()
100            .collect::<Vec<char>>()
101            .iter()
102            .map(|x| x.to_string())
103            .collect::<Vec<String>>();
104        let bracks = Self::find_bracks(chars, false);
105        let tokens = Self::parse_bracks(bracks, &f, 0).0;
106        Self::parse_tokens(tokens)
107    }
108    //order characters by brackets
109    fn find_bracks(chars: Vec<String>, alph: bool) -> Lambda {
110        //find brackets
111        let mut starts: Vec<usize> = Vec::new();
112        let mut ends: Vec<usize> = Vec::new();
113        let mut alphas: Vec<usize> = Vec::new();
114        let mut count = 0;
115        for (i, char) in chars.iter().enumerate() {
116            match (char.as_str(), count) {
117                (")", 1) => {
118                    ends.push(i);
119                    count -= 1;
120                }
121                (")", 0) => panic!("Unclosed bracket"),
122                (")", _) => count -= 1,
123                ("(", 0) => {
124                    if i != 0 && chars[i - 1] == "&" {
125                        alphas.push(i);
126                    }
127                    starts.push(i);
128                    count += 1;
129                }
130                ("(", _) => count += 1,
131                _ => {}
132            }
133        }
134        if starts.len() != ends.len() {
135            panic!("Unclosed bracket");
136        }
137        //split the string into bracket tokens and mark them for alpha reduction if needed
138        if starts.is_empty() && alph {
139            return Self::AlphaMark(Box::new(Self::Brack(vec![Self::StVec(chars)])));
140        } else if starts.is_empty() {
141            return Self::Brack(vec![Self::StVec(chars)]);
142        }
143        let mut bracks: Vec<Lambda> = Vec::new();
144        if !chars[..starts[0]].to_vec().is_empty() {
145            bracks.push(Self::StVec(chars[..starts[0]].to_vec()));
146        }
147        for i in 0..starts.len() {
148            if alphas.contains(&starts[i]) {
149                bracks.push(Self::find_bracks(
150                    chars[starts[i] + 1..ends[i]].to_vec(),
151                    true,
152                ));
153            } else {
154                bracks.push(Self::find_bracks(
155                    chars[starts[i] + 1..ends[i]].to_vec(),
156                    false,
157                ));
158            }
159            if i + 1 != starts.len() {
160                bracks.push(Self::StVec(chars[ends[i] + 1..starts[i + 1]].to_vec()));
161            } else if !chars[ends[i] + 1..].to_vec().is_empty() {
162                bracks.push(Self::StVec(chars[ends[i] + 1..].to_vec()));
163            }
164        }
165        if alph {
166            return Self::AlphaMark(Box::new(Self::Brack(bracks)));
167        }
168        Self::Brack(bracks)
169    }
170    //parse the brackets and characters into brackets and tokens
171    fn parse_bracks(brs: Lambda, vec: &Vec<Lambda>, mut vec_num: usize) -> (Lambda, usize) {
172        if let Self::Brack(br) = brs {
173            let mut parse_vec: Vec<Lambda> = Vec::new();
174            for b in br {
175                match &b {
176                    Self::Brack(_) => {
177                        let t: Lambda;
178                        (t, vec_num) = Self::parse_bracks(b, vec, vec_num);
179                        if let Self::Brack(v) = &t
180                            && v.len() == 1
181                        {
182                            parse_vec.push(v[0].clone());
183                        } else {
184                            parse_vec.push(t);
185                        }
186                    }
187                    Self::StVec(v) => {
188                        let t: Vec<Lambda>;
189                        (t, vec_num) = Self::parse_stvec(v.clone(), vec, vec_num);
190                        parse_vec.extend_from_slice(&t[..]);
191                    }
192                    Self::AlphaMark(l) => {
193                        let temp: Lambda;
194                        (temp, vec_num) = Self::parse_bracks(*l.clone(), vec, vec_num);
195                        parse_vec.push(Self::AlphaMark(Box::new(temp)));
196                    }
197                    _ => panic!("Syntax error"),
198                }
199            }
200            return (Self::Brack(parse_vec), vec_num);
201        }
202        panic!("Syntax error")
203    }
204    //turn the characters into tokens
205    fn parse_stvec(strs: Vec<String>, vec: &[Lambda], mut vec_num: usize) -> (Vec<Lambda>, usize) {
206        let mut token_vec: Vec<Lambda> = Vec::new();
207        let mut pass_num = 0;
208        for i in 0..strs.len() {
209            if pass_num > 0 {
210                pass_num -= 1;
211            } else if strs[i] == "%" {
212                (token_vec, pass_num) = Self::parse_func_char(strs.clone(), token_vec, i);
213            } else if strs[i] == "{" && strs[i + 1] == "}" {
214                token_vec.push(Self::Container(Box::new(vec[vec_num].clone())));
215                vec_num += 1;
216                pass_num += 1;
217            } else {
218                for j in i..strs.len() {
219                    match strs[j].as_str() {
220                        " " => {
221                            token_vec.push(Self::AttPl(()));
222                        }
223                        "&" => {}
224                        "{" => {}
225                        "}" => {}
226                        _ => {
227                            (token_vec, pass_num) = Self::find_vars(&strs, token_vec, j);
228                        }
229                    }
230                }
231                pass_num += 1;
232            }
233        }
234        (token_vec, vec_num)
235    }
236    //find variable tokens
237    fn find_vars(strs: &[String], mut token_vec: Vec<Lambda>, i: usize) -> (Vec<Lambda>, i32) {
238        let mut pass_num = 0;
239        if !Self::ALPH.contains(&strs[i]) {
240            panic!("Syntax error {}", &strs[i]);
241        }
242        let mut var: String = "".to_string();
243        for k in i..strs.len() {
244            if !Self::ALPH.contains(&strs[k]) {
245                token_vec.push(Self::Variable(var));
246                pass_num += 1;
247                break;
248            }
249            var.push_str(&strs[k]);
250            if k == strs.len() - 1 {
251                token_vec.push(Self::Variable(var));
252                pass_num += 1;
253                break;
254            }
255            pass_num += 1;
256        }
257        (token_vec, pass_num)
258    }
259    //parse the function syntax
260    fn parse_func_char(
261        strs: Vec<String>,
262        mut token_vec: Vec<Lambda>,
263        i: usize,
264    ) -> (Vec<Lambda>, i32) {
265        let mut pass_num: i32 = 0;
266        let mut val_vec: Vec<String> = Vec::new();
267        let mut var: String = "".to_string();
268        for st in strs[i + 1..].iter() {
269            match st.as_str() {
270                "." => {
271                    val_vec.push(var);
272                    token_vec.push(Self::TFunc(val_vec));
273                    pass_num += 1;
274                    break;
275                }
276                "|" => {
277                    val_vec.push(var);
278                    var = "".to_string();
279                }
280                _ => {
281                    if Self::ALPH.contains(st) {
282                        var.push_str(st);
283                    } else {
284                        panic!("Syntax error");
285                    }
286                }
287            }
288            pass_num += 1;
289        }
290        (token_vec, pass_num)
291    }
292    //turn brackets and tokens into a lambda
293    fn parse_tokens(token: Lambda) -> Lambda {
294        match token {
295            Self::Brack(v) => Self::parse_token_vec(v),
296            Self::Variable(_) => token,
297            Self::AlphaMark(l) => Self::AlphaMark(Box::new(Self::parse_tokens(*l))),
298            Self::Reducible((a, b)) => Self::parse_tokens(*a).attach(Self::parse_tokens(*b)),
299            Self::Func((a, b)) => Self::Func((a, Box::new(Self::parse_tokens(*b)))),
300            Self::Container(l) => *l,
301            _ => panic!("syntax error"),
302        }
303    }
304    //turn a vec of tokens into a lambda
305    fn parse_token_vec(mut vec: Vec<Lambda>) -> Lambda {
306        let temp_vec = vec.clone();
307        for (i, l) in temp_vec.iter().enumerate() {
308            if let Self::AttPl(_) = *l {
309                vec = [
310                    &vec[..i - 1],
311                    &vec![
312                        Self::parse_tokens(vec[i - 1].clone())
313                            .attach(Self::parse_tokens(vec[i + 1].clone())),
314                    ][..],
315                    &vec[i + 2..],
316                ]
317                .concat();
318            }
319        }
320        match vec[0].clone() {
321            Self::TFunc(v) => Self::parse_func_token(v, vec),
322            Self::Brack(_) => Self::parse_tokens(vec[0].clone()),
323            Self::Reducible(_) => Self::parse_tokens(vec[0].clone()),
324            Self::Variable(_) => vec[0].clone(),
325            Self::Container(_) => vec[0].clone(),
326            Self::AlphaMark(a) => Self::AlphaMark(Box::new(Self::parse_tokens(*a))),
327            _ => panic!("Syntax error"),
328        }
329    }
330    //turn the shorthand function token into lambda functions
331    fn parse_func_token(vec: Vec<String>, tokens: Vec<Lambda>) -> Lambda {
332        if !vec.is_empty() {
333            return Self::func(
334                vec[0].as_str(),
335                Self::parse_func_token(vec[1..vec.len()].to_vec(), tokens),
336            );
337        }
338        if tokens.is_empty() {
339            panic!("Syntax error");
340        }
341        Self::parse_token_vec(tokens[1..tokens.len()].to_vec())
342    }
343    //make new function variant with a string and a Lambda
344    fn func(a: &str, b: Lambda) -> Lambda {
345        Self::Func((Box::new(Self::var(a)), Box::new(b)))
346    }
347    //make new variable variant with a string
348    fn var(inp: &str) -> Lambda {
349        Self::Variable(inp.to_string())
350    }
351    //make new reductible variant by attaching an input Lambda to a Lambda
352    fn attach(self, a: Lambda) -> Lambda {
353        Self::Reducible((Box::new(self), Box::new(a)))
354    }
355
356    ///A single step of beta reduction
357    ///
358    ///```rust
359    ///use easy_lambda_calculus::*;
360    ///
361    ///println!("{}", lambda!("(%x.(x x)) (%y|z.z)").reduce());
362    /// //outputs (λy|z.z) (λy|z.z)
363    ///```
364    ///
365    ///#### Reduction order:
366    ///
367    ///Outer brackets are beta reduced first.
368    ///eg: ((λx.(x x)) ((λy.(y y)) (λz.z))) will reduce to (((λy.(y y)) (λz.z)) ((λy.(y y)) (λz.z))) and not (λx.(x x)) ((λz.z) (λz.z))
369    ///
370    ///If the left side is an application into a function rather then a function, it will be beta reduced first.
371    ///eg: (((λx.x) (λy.(y y))) (λz.z)) will reduce to ((λy.(y y)) (λz.z))
372    ///
373    ///For reduction with functions marked for alpha reduction, see Lambda.alpha_reduce().
374    pub fn reduce(self) -> Lambda {
375        if let Self::Reducible((a, b)) = self.clone() {
376            //if reducible has a function reduce the function, else if it has a reducible, reduce the inside reducible
377            if let Self::Func((c, d)) = &*a {
378                return Self::recursive_reduce(*d.clone(), *c.clone(), *b);
379            } else if let Self::Reducible(_) = &*a {
380                return a.reduce().attach(*b);
381            } else if let Self::Func((c, d)) = &*b {
382                return Self::Func((c.clone(), Box::new(d.clone().reduce())));
383            } else if let Self::Reducible(_) = *b {
384                return a.attach(b.reduce());
385            } else if let Self::Variable(_) = &*a {
386                return a.attach(*b);
387            }
388            panic!("Cannot reduce");
389        }
390        if let Self::Func((a, b)) = self.clone() {
391            return Self::Func((a, Box::new(b.reduce())));
392        }
393        self
394        //panic!("Cannot reduce");
395    }
396
397    ///Alpha reduce any sections marked for alpha reduction
398    ///
399    ///```rust
400    ///use easy_lambda_calculus::*;
401    ///
402    ///println!("{}", lambda!("(%z.(z z)) &(%z.z)").alpha_reduce());
403    /// //outputs ((λx.(x x)) (λy.y))
404    ///```
405    ///
406    ///#### Alpha reduction properties:
407    ///
408    ///Alpha reduction will rename every variable based on when they show up in the lambda.
409    ///They are renamed with the naming scheme: x, y, z, w, a, b ... u, v, xx, xy...
410    ///
411    ///The renamed variables in any section marked for alpha reduction will be different from any other one.
412    ///
413    ///The alpha reduction function can also be used when there are no sections marked for alpha reduction, to rename the variables in the lambda based on the naming scheme.
414    ///
415    ///The sections marked for alpha reduction cannot be reduced, however can be reduced into other functions
416    ///Note that reducing them into other functions does not remove that they are marked for alpha reduction, and can cause unwanted effects.
417    ///For example if multiple variables are substituted with the section marked for alpha reduction, when alpha reduced, every copy will have different variable names.
418    pub fn alpha_reduce(self) -> Lambda {
419        let (m, _, _) = Self::set_map(self.clone(), vec![HashMap::new()], 0, 0, 0);
420        let (out, _) = Self::recursive_alpha(self, m, 0, 0);
421        out
422    }
423    //recursive function to substitute every instance of the given variable
424    fn recursive_reduce(b: Lambda, a: Lambda, sub: Lambda) -> Lambda {
425        match b {
426            //if it is a function variant, check for the variable being substituted or reduce an inside function
427            Self::Func((c, d)) => {
428                if a != *d {
429                    return Self::Func((c, Box::new(Self::recursive_reduce(*d, a, sub))));
430                }
431                Self::Func((c, Box::new(sub)))
432            }
433            //if it is a reducible, reduce both the function and the input expression
434            Self::Reducible((c, d)) => Self::recursive_reduce(*c, a.clone(), sub.clone())
435                .attach(Self::recursive_reduce(*d, a, sub)),
436            //if it is just a variable, substitute if it is the variable being substituted
437            Self::Variable(_) => {
438                if a == b {
439                    return sub;
440                }
441                b
442            }
443            Self::AlphaMark(_) => b,
444            _ => panic!("Cannot reduce {:?}", b),
445        }
446    }
447    ///Evaluate a lambda
448    ///
449    ///
450    ///```rust
451    ///use easy_lambda_calculus::*;
452    ///
453    ///println!("{}", lambda!("(%x.&(%x.&(%x.x))) &(%x.x)").evaluate());
454    /// //outputs (λx|y.y)
455    ///```
456    ///
457    ///#### Evaluation method:
458    ///
459    ///Evaluation will first alpha reduce the lambda.
460    ///It will then automatically beta reduce the lambda until it cannot be reduced anymore.
461    ///Lastly it will alpha reduce the lambda again, to output it with predictable names.
462    pub fn evaluate(self) -> Lambda {
463        self.alpha_reduce().recursive_evaluate().alpha_reduce()
464    }
465    //function to recursively reduce every reducible
466    fn recursive_evaluate(self) -> Lambda {
467        let mut l = self.clone();
468        loop {
469            let ll = l.clone();
470            if let Self::Reducible(_) = &self {
471                l = l.reduce()
472            } else if let Self::Func(_) = &self {
473                l = l.reduce();
474            }
475            if l == ll {
476                break;
477            }
478        }
479        l
480    }
481    //function to assign a vector of hashmaps to a lambda
482    fn set_map(
483        l: Lambda,
484        mut m: Vec<HashMap<String, usize>>,
485        mut i: usize,
486        al: usize,
487        mut al_in: usize,
488    ) -> (Vec<HashMap<String, usize>>, usize, usize) {
489        match l {
490            Self::Variable(a) => {
491                if !m[al].contains_key(a.as_str()) {
492                    m[al].insert(a, i);
493                    (m, i + 1, al_in)
494                } else {
495                    (m, i, al_in)
496                }
497            }
498            Self::Func((a, b)) => {
499                if let Self::Variable(c) = *a
500                    && !m[al].contains_key(c.as_str())
501                {
502                    m[al].insert(c, i);
503                }
504                Self::set_map(*b, m, i + 1, al, al_in)
505            }
506            Self::Reducible((a, b)) => {
507                (m, i, al_in) = Self::set_map(*a, m, i, al, al_in);
508                Self::set_map(*b, m, i, al, al_in)
509            }
510            Self::AlphaMark(a) => {
511                al_in += 1;
512                m.push(HashMap::new());
513                Self::set_map(*a, m, i, al_in, al_in)
514            }
515            _ => panic!("Cannot map lambda"),
516        }
517    }
518    //function to get a lambda variable name from an integer
519    fn get_name(mut n: usize) -> String {
520        let mut out = "".to_string();
521        let chars = Self::ALPH.chars();
522        let num = chars.clone().count();
523        n += 1;
524        while n != 0 {
525            let mut temp = chars.clone().nth((n - 1) % num).unwrap().to_string();
526            temp.push_str(&out);
527            out = temp;
528            n = ((n - 1) - ((n - 1) % num)) / num;
529        }
530        out
531    }
532    //recursive function to remove any colliding variable names
533    fn recursive_alpha(
534        l: Lambda,
535        m: Vec<HashMap<String, usize>>,
536        al: usize,
537        mut al_in: usize,
538    ) -> (Lambda, usize) {
539        match l {
540            Self::Variable(a) => match m[al].get(&a) {
541                Some(b) => (Self::Variable(Self::get_name(*b)), al_in),
542                _ => panic!("Cannot alpha reduce"),
543            },
544            Self::Func((a, b)) => {
545                let c: Lambda;
546                let d: Lambda;
547                (c, al_in) = Self::recursive_alpha(*a, m.clone(), al, al_in);
548                (d, al_in) = Self::recursive_alpha(*b, m, al, al_in);
549                (Self::Func((Box::new(c), Box::new(d))), al_in)
550            }
551            Self::Reducible((a, b)) => {
552                let c: Lambda;
553                let d: Lambda;
554                (c, al_in) = Self::recursive_alpha(*a, m.clone(), al, al_in);
555                (d, al_in) = Self::recursive_alpha(*b, m, al, al_in);
556                (c.attach(d), al_in)
557            }
558            Self::AlphaMark(a) => {
559                al_in += 1;
560                Self::recursive_alpha(*a, m, al_in, al_in)
561            }
562            _ => panic!("Cannot alpha reduce"),
563        }
564    }
565    //function to calculate a string to represent the lambda
566    fn display(l: Lambda) -> String {
567        match l {
568            Self::Variable(a) => a,
569            Self::Func((a, mut b)) => {
570                let d = b.clone();
571                let mut s1 = Self::display(*a);
572                let mut s2 = "".to_string();
573                while let Self::Func((ref a, ref c)) = *b {
574                    s1.push('|');
575                    s1.push_str(&Self::display(*a.clone()));
576                    if let Self::Func(_) = **c {
577                    } else {
578                        s2 = Self::display(*c.clone());
579                    }
580                    b = c.clone();
581                }
582                if s2.is_empty() {
583                    s2 = Self::display(*d)
584                }
585                format!("(%{}.{})", &s1, &s2)
586            }
587            Self::Reducible((a, b)) => {
588                let s1 = Self::display(*a);
589                let s2 = Self::display(*b);
590                format!("({} {})", &s1, &s2)
591            }
592            Self::AlphaMark(a) => {
593                let s1 = Self::display(*a);
594                format!("&{}", &s1)
595            }
596            _ => panic!("Cannot display"),
597        }
598    }
599    ///Lambda from u16 with church encoding
600    pub fn from_u16(n: u16) -> Lambda {
601        let mut l = Self::var("x");
602        if n != 0 {
603            l = l.attach(Self::var("y"));
604            for _ in 0..n - 1 {
605                l = Self::var("x").attach(l);
606            }
607        }
608        Self::func("x", Self::func("y", l))
609    }
610    ///u16 from Lambda with church encoding
611    pub fn as_u16(self: Lambda) -> Option<u16> {
612        let mut l = self;
613        if let Lambda::Func((a, b)) = l {
614            if let Lambda::Func((c, d)) = *b {
615                l = *d;
616                let mut n = 0;
617                loop {
618                    if let Lambda::Reducible((e, f)) = l {
619                        if e != a {
620                            return None;
621                        }
622                        n += 1;
623                        if f == c {
624                            return Some(n);
625                        }
626                        l = *f;
627                    } else {
628                        return None;
629                    }
630                }
631            } else {
632                return None;
633            }
634        }
635        None
636    }
637    ///Add one to numbers with church encoding
638    pub fn succ() -> Lambda {
639        lambda!("%a|f|x.(a f) (f x)").alpha_reduce()
640    }
641    ///Add numbers together with church encoding
642    pub fn add() -> Lambda {
643        lambda!("%x|y|z|w.(y z) ((x z) w)").alpha_reduce()
644    }
645}
646
647//implement display for the lambda data type
648impl fmt::Display for Lambda {
649    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
650        write!(f, "{}", Lambda::display(self.clone()))
651    }
652}
easy_lambda_calculus/lib.rs

easy_lambda_calculus/
lib.rs
