easy_lambda_calculus 1.0.5

//! Simple and easy to write lambda calculus
//! # Example:
//! ```rust
//! use easy_lambda_calculus::*;
//!
//! //code to evaluate and(true, true)
//!fn main() {
//!   let t = lambda!("%x|y.x"); //true
//!   let f = lambda!("%x|y.y"); //false
//!   let a = lambda!("%x|y.(x y) &{}", f); //and
//!   let res = lambda!("({} &{}) &{}", a, t.clone(), t); //and(true, true)
//!   println!("{}", res.evaluate());
//!}
//! //outputs (%x|y.x) which is equivalent to true

use std::collections::HashMap;
use std::fmt;

///Makes a new lambda from a string
///
///```rust
///use easy_lambda_calculus::*;
///
///let l = lambda!("%x|y.y")
///println!("{}", lambda!("%x|y.(x y) &{}", l));
/// //outputs λx|y.(x y) &(λx|y.y)
///```
///
///#### Syntax:
///
///%x.x to define function with input variable x and output defined after the dot.
///
///%x|y.y to define a function with multiple inputs (equivalent to %x.(%y.y) ), variables separated by a pipe | character.
///
///Variables can be multiple characters.
///eg: %var.var or %true|false.true are also valid.
///
///(x y) to apply y into function x.
///(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.
///
///&(x) is used to mark section x for alpha reduction, so you can reuse variable names without any unintended interactions.
///
///{} is used to input a lambda variable into the lambda, uses the same syntax as the `format!()` macro, &{} is shorthand for &({}).
#[macro_export]
macro_rules! lambda {
    ($x:expr) => (
        Lambda::new($x, vec![])
    );
    ($x:expr, $($y:expr), +) => (
        Lambda::new($x, vec![$($y), +])
    );

}

///Lambda data type
#[derive(Debug, PartialEq, Clone)]
pub enum Lambda {
    ///Function
    Func((Box<Lambda>, Box<Lambda>)),
    ///Variable
    Variable(String),
    ///Marks a lambda being applied into a function
    Reducible((Box<Lambda>, Box<Lambda>)),
    ///Marks a lambda for alpha reduction
    AlphaMark(Box<Lambda>),

    ///Vector of strings to be converted into a lambda
    StVec(Vec<String>),
    ///Token for brackets
    Brack(Vec<Lambda>),
    ///Token for shorthand functions
    TFunc(Vec<String>),
    ///Token to contain a lambda inputted through formatting
    Container(Box<Lambda>),
    ///Token to mark where to put reducibles
    AttPl(()),
}

impl Lambda {
    //Alphabet for variable naming
    const ALPH: &str = "xyzwabcdefghijklmnopqrstuv";
    //new lambda from formatted string
    #[doc(hidden)]
    pub fn new(s: &str, f: Vec<Lambda>) -> Lambda {
        let chars = s
            .chars()
            .collect::<Vec<char>>()
            .iter()
            .map(|x| {
                let mut a = x.to_string();
                if a == "{" {
                    a = "({".to_string();
                } else if a == "}" {
                    a = "})".to_string();
                }
                a.clone()
            })
            .collect::<String>()
            .chars()
            .collect::<Vec<char>>()
            .iter()
            .map(|x| x.to_string())
            .collect::<Vec<String>>();
        let bracks = Self::find_bracks(chars, false);
        let tokens = Self::parse_bracks(bracks, &f, 0).0;
        Self::parse_tokens(tokens)
    }
    //order characters by brackets
    fn find_bracks(chars: Vec<String>, alph: bool) -> Lambda {
        //find brackets
        let mut starts: Vec<usize> = Vec::new();
        let mut ends: Vec<usize> = Vec::new();
        let mut alphas: Vec<usize> = Vec::new();
        let mut count = 0;
        for (i, char) in chars.iter().enumerate() {
            match (char.as_str(), count) {
                (")", 1) => {
                    ends.push(i);
                    count -= 1;
                }
                (")", 0) => panic!("Unclosed bracket"),
                (")", _) => count -= 1,
                ("(", 0) => {
                    if i != 0 && chars[i - 1] == "&" {
                        alphas.push(i);
                    }
                    starts.push(i);
                    count += 1;
                }
                ("(", _) => count += 1,
                _ => {}
            }
        }
        if starts.len() != ends.len() {
            panic!("Unclosed bracket");
        }
        //split the string into bracket tokens and mark them for alpha reduction if needed
        if starts.is_empty() && alph {
            return Self::AlphaMark(Box::new(Self::Brack(vec![Self::StVec(chars)])));
        } else if starts.is_empty() {
            return Self::Brack(vec![Self::StVec(chars)]);
        }
        let mut bracks: Vec<Lambda> = Vec::new();
        if !chars[..starts[0]].to_vec().is_empty() {
            bracks.push(Self::StVec(chars[..starts[0]].to_vec()));
        }
        for i in 0..starts.len() {
            if alphas.contains(&starts[i]) {
                bracks.push(Self::find_bracks(
                    chars[starts[i] + 1..ends[i]].to_vec(),
                    true,
                ));
            } else {
                bracks.push(Self::find_bracks(
                    chars[starts[i] + 1..ends[i]].to_vec(),
                    false,
                ));
            }
            if i + 1 != starts.len() {
                bracks.push(Self::StVec(chars[ends[i] + 1..starts[i + 1]].to_vec()));
            } else if !chars[ends[i] + 1..].to_vec().is_empty() {
                bracks.push(Self::StVec(chars[ends[i] + 1..].to_vec()));
            }
        }
        if alph {
            return Self::AlphaMark(Box::new(Self::Brack(bracks)));
        }
        Self::Brack(bracks)
    }
    //parse the brackets and characters into brackets and tokens
    fn parse_bracks(brs: Lambda, vec: &Vec<Lambda>, mut vec_num: usize) -> (Lambda, usize) {
        if let Self::Brack(br) = brs {
            let mut parse_vec: Vec<Lambda> = Vec::new();
            for b in br {
                match &b {
                    Self::Brack(_) => {
                        let t: Lambda;
                        (t, vec_num) = Self::parse_bracks(b, vec, vec_num);
                        if let Self::Brack(v) = &t
                            && v.len() == 1
                        {
                            parse_vec.push(v[0].clone());
                        } else {
                            parse_vec.push(t);
                        }
                    }
                    Self::StVec(v) => {
                        let t: Vec<Lambda>;
                        (t, vec_num) = Self::parse_stvec(v.clone(), vec, vec_num);
                        parse_vec.extend_from_slice(&t[..]);
                    }
                    Self::AlphaMark(l) => {
                        let temp: Lambda;
                        (temp, vec_num) = Self::parse_bracks(*l.clone(), vec, vec_num);
                        parse_vec.push(Self::AlphaMark(Box::new(temp)));
                    }
                    _ => panic!("Syntax error"),
                }
            }
            return (Self::Brack(parse_vec), vec_num);
        }
        panic!("Syntax error")
    }
    //turn the characters into tokens
    fn parse_stvec(strs: Vec<String>, vec: &[Lambda], mut vec_num: usize) -> (Vec<Lambda>, usize) {
        let mut token_vec: Vec<Lambda> = Vec::new();
        let mut pass_num = 0;
        for i in 0..strs.len() {
            if pass_num > 0 {
                pass_num -= 1;
            } else if strs[i] == "%" {
                (token_vec, pass_num) = Self::parse_func_char(strs.clone(), token_vec, i);
            } else if strs[i] == "{" && strs[i + 1] == "}" {
                token_vec.push(Self::Container(Box::new(vec[vec_num].clone())));
                vec_num += 1;
                pass_num += 1;
            } else {
                for j in i..strs.len() {
                    match strs[j].as_str() {
                        " " => {
                            token_vec.push(Self::AttPl(()));
                        }
                        "&" => {}
                        "{" => {}
                        "}" => {}
                        _ => {
                            (token_vec, pass_num) = Self::find_vars(&strs, token_vec, j);
                        }
                    }
                }
                pass_num += 1;
            }
        }
        (token_vec, vec_num)
    }
    //find variable tokens
    fn find_vars(strs: &[String], mut token_vec: Vec<Lambda>, i: usize) -> (Vec<Lambda>, i32) {
        let mut pass_num = 0;
        if !Self::ALPH.contains(&strs[i]) {
            panic!("Syntax error {}", &strs[i]);
        }
        let mut var: String = "".to_string();
        for k in i..strs.len() {
            if !Self::ALPH.contains(&strs[k]) {
                token_vec.push(Self::Variable(var));
                pass_num += 1;
                break;
            }
            var.push_str(&strs[k]);
            if k == strs.len() - 1 {
                token_vec.push(Self::Variable(var));
                pass_num += 1;
                break;
            }
            pass_num += 1;
        }
        (token_vec, pass_num)
    }
    //parse the function syntax
    fn parse_func_char(
        strs: Vec<String>,
        mut token_vec: Vec<Lambda>,
        i: usize,
    ) -> (Vec<Lambda>, i32) {
        let mut pass_num: i32 = 0;
        let mut val_vec: Vec<String> = Vec::new();
        let mut var: String = "".to_string();
        for st in strs[i + 1..].iter() {
            match st.as_str() {
                "." => {
                    val_vec.push(var);
                    token_vec.push(Self::TFunc(val_vec));
                    pass_num += 1;
                    break;
                }
                "|" => {
                    val_vec.push(var);
                    var = "".to_string();
                }
                _ => {
                    if Self::ALPH.contains(st) {
                        var.push_str(st);
                    } else {
                        panic!("Syntax error");
                    }
                }
            }
            pass_num += 1;
        }
        (token_vec, pass_num)
    }
    //turn brackets and tokens into a lambda
    fn parse_tokens(token: Lambda) -> Lambda {
        match token {
            Self::Brack(v) => Self::parse_token_vec(v),
            Self::Variable(_) => token,
            Self::AlphaMark(l) => Self::AlphaMark(Box::new(Self::parse_tokens(*l))),
            Self::Reducible((a, b)) => Self::parse_tokens(*a).attach(Self::parse_tokens(*b)),
            Self::Func((a, b)) => Self::Func((a, Box::new(Self::parse_tokens(*b)))),
            Self::Container(l) => *l,
            _ => panic!("syntax error"),
        }
    }
    //turn a vec of tokens into a lambda
    fn parse_token_vec(mut vec: Vec<Lambda>) -> Lambda {
        let temp_vec = vec.clone();
        for (i, l) in temp_vec.iter().enumerate() {
            if let Self::AttPl(_) = *l {
                vec = [
                    &vec[..i - 1],
                    &vec![
                        Self::parse_tokens(vec[i - 1].clone())
                            .attach(Self::parse_tokens(vec[i + 1].clone())),
                    ][..],
                    &vec[i + 2..],
                ]
                .concat();
            }
        }
        match vec[0].clone() {
            Self::TFunc(v) => Self::parse_func_token(v, vec),
            Self::Brack(_) => Self::parse_tokens(vec[0].clone()),
            Self::Reducible(_) => Self::parse_tokens(vec[0].clone()),
            Self::Variable(_) => vec[0].clone(),
            Self::Container(_) => vec[0].clone(),
            Self::AlphaMark(a) => Self::AlphaMark(Box::new(Self::parse_tokens(*a))),
            _ => panic!("Syntax error"),
        }
    }
    //turn the shorthand function token into lambda functions
    fn parse_func_token(vec: Vec<String>, tokens: Vec<Lambda>) -> Lambda {
        if !vec.is_empty() {
            return Self::func(
                vec[0].as_str(),
                Self::parse_func_token(vec[1..vec.len()].to_vec(), tokens),
            );
        }
        if tokens.is_empty() {
            panic!("Syntax error");
        }
        Self::parse_token_vec(tokens[1..tokens.len()].to_vec())
    }
    //make new function variant with a string and a Lambda
    fn func(a: &str, b: Lambda) -> Lambda {
        Self::Func((Box::new(Self::var(a)), Box::new(b)))
    }
    //make new variable variant with a string
    fn var(inp: &str) -> Lambda {
        Self::Variable(inp.to_string())
    }
    //make new reductible variant by attaching an input Lambda to a Lambda
    fn attach(self, a: Lambda) -> Lambda {
        Self::Reducible((Box::new(self), Box::new(a)))
    }

    ///A single step of beta reduction
    ///
    ///```rust
    ///use easy_lambda_calculus::*;
    ///
    ///println!("{}", lambda!("(%x.(x x)) (%y|z.z)").reduce());
    /// //outputs (λy|z.z) (λy|z.z)
    ///```
    ///
    ///#### Reduction order:
    ///
    ///Outer brackets are beta reduced first.
    ///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))
    ///
    ///If the left side is an application into a function rather then a function, it will be beta reduced first.
    ///eg: (((λx.x) (λy.(y y))) (λz.z)) will reduce to ((λy.(y y)) (λz.z))
    ///
    ///For reduction with functions marked for alpha reduction, see Lambda.alpha_reduce().
    pub fn reduce(self) -> Lambda {
        if let Self::Reducible((a, b)) = self.clone() {
            //if reducible has a function reduce the function, else if it has a reducible, reduce the inside reducible
            if let Self::Func((c, d)) = &*a {
                return Self::recursive_reduce(*d.clone(), *c.clone(), *b);
            } else if let Self::Reducible(_) = &*a {
                return a.reduce().attach(*b);
            } else if let Self::Reducible(_) = *b {
                return a.attach(b.reduce());
            } else if let Self::Variable(_) = &*a {
                return a.attach(*b);
            }
            panic!("Cannot reduce");
        }
        if let Self::Func((a, b)) = self.clone() {
            return Self::Func((a, Box::new(b.reduce())));
        }
        self
        //panic!("Cannot reduce");
    }

    ///Alpha reduce any sections marked for alpha reduction
    ///
    ///```rust
    ///use easy_lambda_calculus::*;
    ///
    ///println!("{}", lambda!("(%z.(z z)) &(%z.z)").alpha_reduce());
    /// //outputs ((λx.(x x)) (λy.y))
    ///```
    ///
    ///#### Alpha reduction properties:
    ///
    ///Alpha reduction will rename every variable based on when they show up in the lambda.
    ///They are renamed with the naming scheme: x, y, z, w, a, b ... u, v, xx, xy...
    ///
    ///The renamed variables in any section marked for alpha reduction will be different from any other one.
    ///
    ///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.
    ///
    ///The sections marked for alpha reduction cannot be reduced, however can be reduced into other functions
    ///Note that reducing them into other functions does not remove that they are marked for alpha reduction, and can cause unwanted effects.
    ///For example if multiple variables are substituted with the section marked for alpha reduction, when alpha reduced, every copy will have different variable names.
    pub fn alpha_reduce(self) -> Lambda {
        let (m, _, _) = Self::set_map(self.clone(), vec![HashMap::new()], 0, 0, 0);
        let (out, _) = Self::recursive_alpha(self, m, 0, 0);
        out
    }
    //recursive function to substitute every instance of the given variable
    fn recursive_reduce(b: Lambda, a: Lambda, sub: Lambda) -> Lambda {
        match b {
            //if it is a function variant, check for the variable being substituted or reduce an inside function
            Self::Func((c, d)) => {
                if a != *d {
                    return Self::Func((c, Box::new(Self::recursive_reduce(*d, a, sub))));
                }
                Self::Func((c, Box::new(sub)))
            }
            //if it is a reducible, reduce both the function and the input expression
            Self::Reducible((c, d)) => Self::recursive_reduce(*c, a.clone(), sub.clone())
                .attach(Self::recursive_reduce(*d, a, sub)),
            //if it is just a variable, substitute if it is the variable being substituted
            Self::Variable(_) => {
                if a == b {
                    return sub;
                }
                b
            }
            Self::AlphaMark(_) => b,
            _ => panic!("Cannot reduce {:?}", b),
        }
    }
    ///Evaluate a lambda
    ///
    ///
    ///```rust
    ///use easy_lambda_calculus::*;
    ///
    ///println!("{}", lambda!("(%x.&(%x.&(%x.x))) &(%x.x)").evaluate());
    /// //outputs (λx|y.y)
    ///```
    ///
    ///#### Evaluation method:
    ///
    ///Evaluation will first alpha reduce the lambda.
    ///It will then automatically beta reduce the lambda until it cannot be reduced anymore.
    ///Lastly it will alpha reduce the lambda again, to output it with predictable names.
    pub fn evaluate(self) -> Lambda {
        self.alpha_reduce().recursive_evaluate().alpha_reduce()
    }
    //function to recursively reduce every reducible
    fn recursive_evaluate(self) -> Lambda {
        let mut l = self.clone();
        loop {
            let ll = l.clone();
            if let Self::Reducible(_) = &self {
                l = l.reduce()
            } else if let Self::Func(_) = &self {
                l = l.reduce();
            }
            if l == ll {
                break;
            }
        }
        l
    }
    //function to assign a vector of hashmaps to a lambda
    fn set_map(
        l: Lambda,
        mut m: Vec<HashMap<String, usize>>,
        mut i: usize,
        al: usize,
        mut al_in: usize,
    ) -> (Vec<HashMap<String, usize>>, usize, usize) {
        match l {
            Self::Variable(a) => {
                if !m[al].contains_key(a.as_str()) {
                    m[al].insert(a, i);
                    (m, i + 1, al_in)
                } else {
                    (m, i, al_in)
                }
            }
            Self::Func((a, b)) => {
                if let Self::Variable(c) = *a
                    && !m[al].contains_key(c.as_str())
                {
                    m[al].insert(c, i);
                }
                Self::set_map(*b, m, i + 1, al, al_in)
            }
            Self::Reducible((a, b)) => {
                (m, i, al_in) = Self::set_map(*a, m, i, al, al_in);
                Self::set_map(*b, m, i, al, al_in)
            }
            Self::AlphaMark(a) => {
                al_in += 1;
                m.push(HashMap::new());
                Self::set_map(*a, m, i, al_in, al_in)
            }
            _ => panic!("Cannot map lambda"),
        }
    }
    //function to get a lambda variable name from an integer
    fn get_name(mut n: usize) -> String {
        let mut out = "".to_string();
        let chars = Self::ALPH.chars();
        let num = chars.clone().count();
        n += 1;
        while n != 0 {
            let mut temp = chars.clone().nth((n - 1) % num).unwrap().to_string();
            temp.push_str(&out);
            out = temp;
            n = ((n - 1) - ((n - 1) % num)) / num;
        }
        out
    }
    //recursive function to remove any colliding variable names
    fn recursive_alpha(
        l: Lambda,
        m: Vec<HashMap<String, usize>>,
        al: usize,
        mut al_in: usize,
    ) -> (Lambda, usize) {
        match l {
            Self::Variable(a) => match m[al].get(&a) {
                Some(b) => (Self::Variable(Self::get_name(*b)), al_in),
                _ => panic!("Cannot alpha reduce"),
            },
            Self::Func((a, b)) => {
                let c: Lambda;
                let d: Lambda;
                (c, al_in) = Self::recursive_alpha(*a, m.clone(), al, al_in);
                (d, al_in) = Self::recursive_alpha(*b, m, al, al_in);
                (Self::Func((Box::new(c), Box::new(d))), al_in)
            }
            Self::Reducible((a, b)) => {
                let c: Lambda;
                let d: Lambda;
                (c, al_in) = Self::recursive_alpha(*a, m.clone(), al, al_in);
                (d, al_in) = Self::recursive_alpha(*b, m, al, al_in);
                (c.attach(d), al_in)
            }
            Self::AlphaMark(a) => {
                al_in += 1;
                Self::recursive_alpha(*a, m, al_in, al_in)
            }
            _ => panic!("Cannot alpha reduce"),
        }
    }
    //function to calculate a string to represent the lambda
    fn display(l: Lambda) -> String {
        match l {
            Self::Variable(a) => a,
            Self::Func((a, mut b)) => {
                let d = b.clone();
                let mut s1 = Self::display(*a);
                let mut s2 = "".to_string();
                while let Self::Func((ref a, ref c)) = *b {
                    s1.push('|');
                    s1.push_str(&Self::display(*a.clone()));
                    if let Self::Func(_) = **c {
                    } else {
                        s2 = Self::display(*c.clone());
                    }
                    b = c.clone();
                }
                if s2.is_empty() {
                    s2 = Self::display(*d)
                }
                format!("(%{}.{})", &s1, &s2)
            }
            Self::Reducible((a, b)) => {
                let s1 = Self::display(*a);
                let s2 = Self::display(*b);
                format!("({} {})", &s1, &s2)
            }
            Self::AlphaMark(a) => {
                let s1 = Self::display(*a);
                format!("&{}", &s1)
            }
            _ => panic!("Cannot display"),
        }
    }
    ///Lambda from u16 with church encoding
    pub fn from_u16(n: u16) -> Lambda {
        let mut l = Self::var("x");
        if n != 0 {
            l = l.attach(Self::var("y"));
        }
        for _ in 0..n - 1 {
            l = Self::var("x").attach(l);
        }
        Self::func("x", Self::func("y", l))
    }
    ///Add numbers together with church encoding
    pub fn add() -> Lambda {
        lambda!("%x|y|z|w.(y z) ((x z) w)").alpha_reduce()
    }
    ///Add one to numbers with church encoding
    pub fn succ() -> Lambda {
        lambda!("%a|f|x.(a f) (f x)").alpha_reduce()
    }
}

//implement display for the lambda data type
impl fmt::Display for Lambda {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}", Lambda::display(self.clone()))
    }
}