lcalc/src/main.rs

#![feature(box_patterns, box_syntax)]

use std::fmt::{self, Write};
use std::sync::atomic::{AtomicUsize, Ordering};

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Name(pub String);

impl fmt::Display for Name {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.0)
    }
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Function(pub Name, pub Expr);

impl fmt::Display for Function {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        if let Expr::Function(box Function(..)) = self.1 {
            // handling multiple-argument functions
            let mut args = format!("{}", self.0);
            let mut expr = &self.1;
            while let Expr::Function(box Function(n, e)) = expr {
                write!(args, "{}", n)?;
                expr = e;
            }
            write!(f, "λ{}.{}", args, expr)
        }
        else {
            write!(f, "λ{}.{}", self.0, self.1)
        }
    }
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Expr {
    Name(Name),
    Function(Box<Function>),
    Application(Box<Expr>, Box<Expr>)
}

impl fmt::Display for Expr {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Expr::Name(n) => n.fmt(f),
            Expr::Function(n) => n.fmt(f),
            Expr::Application(box e1, box e2) => {
                if let Expr::Function(box Function(_, Expr::Name(_))) = e1 {
                    write!(f, "({}){}", e1, e2)
                }
                else {
                    write!(f, "[{}{}]", e1, e2)
                }
            }
        }
    }
}

static VARIABLE_COUNTER: AtomicUsize = AtomicUsize::new(0);

pub fn new_var() -> Name {
    let cnt = VARIABLE_COUNTER.fetch_add(1, Ordering::SeqCst);
    Name(format!("a{}", cnt))
}

pub fn expr_contains_name(expr: &Expr, name: &Name) -> bool {
    match expr {
        Expr::Name(n) if n == name => true,
        Expr::Function(box Function(n, e)) =>
            n == name || expr_contains_name(e, name),
        Expr::Application(box left, box right) =>
            expr_contains_name(left, name) || expr_contains_name(right, name),
        _ => false
    }
}

// https://open.spotify.com/track/6S0JlNqvdDJ6Oq5dSOjuE2?si=xNioxjqVTVCD7HCf67p0pw
pub fn he_walk(old_name: Name, new_expr: Expr, ast: Expr) -> Expr {
    //println!("let {} = {} in {}", old_name, new_expr, ast);
    match ast {
        Expr::Name(n) if n == old_name => new_expr.clone(),
        x @ Expr::Name(..) => x,
        Expr::Application(box left, box right) => {
            Expr::Application(
                box he_walk(old_name.clone(), new_expr.clone(), left),
                box he_walk(old_name.clone(), new_expr.clone(), right))
        },
        Expr::Function(box Function(name, expr)) => {
            let Function(name_new, expr_new) = if name == old_name || expr_contains_name(&expr, &name) {
                //println!("swizzle time");
                let new_name = new_var();
                Function(new_name.clone(), he_walk(name, Expr::Name(new_name), expr))
            }
            else {
                Function(name, expr)
            };
            Expr::Function(box Function(
                    name_new,
                    he_walk(old_name, new_expr, expr_new)))
        }
    }
}

pub fn apply(e1: Expr, e2: Expr) -> Expr {
    Expr::Application(box e1, box e2)
}
pub fn var<T: Into<String>>(name: T) -> Expr {
    Expr::Name(Name(name.into()))
}
pub fn lambda<T: Into<String>>(name: T, e: Expr) -> Expr {
    Expr::Function(box Function(Name(name.into()), e))
}
pub fn id() -> Expr {
    lambda("x", var("x"))
}
pub fn zero() -> Expr {
    lambda("s", lambda("z", var("z")))
}
pub fn succ() -> Expr {
    lambda("w", lambda("y", lambda("x", apply(var("y"), apply(apply(var("w"), var("y")), var("x"))))))
}
pub fn asucc(e: Expr) -> Expr {
    apply(succ(), e)
}
pub fn apply_function_to_expr(fun: Function, e: Expr) -> Expr {
    //println!("funcall: {} = {} in {}", fun.0, e, fun.1);
    he_walk(fun.0, e, fun.1)
}
pub fn encode_num(num: usize) -> Expr {
    let mut ret = zero();
    for _ in 0..num {
        ret = asucc(ret).eval()
    }
    ret
}
pub fn decode_num(e: Expr) -> Option<usize> {
    if let Expr::Function(box Function(s, Expr::Function(box Function(z, mut expr)))) = e {
        let mut ret = 0;
        while let Expr::Application(box Expr::Name(n), box new_exp) = expr {
            if n == s {
                ret += 1;
            }
            else {
                return None;
            }
            expr = new_exp;
        }
        if expr == Expr::Name(z) {
            Some(ret)
        }
        else {
            None
        }
    }
    else {
        None
    }
}

impl Expr {
    pub fn eval(self) -> Self {
        let mut this = self;
        loop {
            //println!("eval {}:", this);
            let ret = match this.clone() {
                Expr::Application(box left, box right) => {
                    let mut expr = left;
                    loop {
                        match expr {
                            x @ Expr::Application(..) => {
                                expr = x.eval();
                            },
                            Expr::Function(box func) => {
                                break apply_function_to_expr(func, right);
                            },
                            x @ Expr::Name(..) => {
                                break Expr::Application(box x, box right.eval());
                            }
                        }
                    }
                },
                Expr::Function(box Function(name, expr)) =>
                    Expr::Function(box Function(name, expr.eval())),
                x => x
            };
            //println!("eval {} => {}", this, ret);
            if this == ret {
                break ret;
            }
            this = ret;
        }
    }
}

fn main() {
    let ii = apply(id(), id());
    let test2 = apply(lambda("x", lambda("y", apply(var("x"), var("y")))), var("y"));
    // (λx.(λy.(x(λx.xy))))y
    let test3 = apply(lambda("x", lambda("y", apply(var("x"), lambda("x", apply(var("x"), var("y")))))), var("y"));
    // (λx.xx)(λx.xx)
    let test4 = apply(lambda("x", apply(var("x"), var("x"))), lambda("x", apply(var("x"), var("x"))));
    println!("*** {}", lambda("x", lambda("y", lambda("z", var("k")))));
    println!("*** {} => {}", ii, ii.clone().eval());
    println!("*** {} => {}", test2, test2.clone().eval());
    println!("*** {} => {}", test3, test3.clone().eval());
    println!("*** {} => {}", test4, test4.clone().eval());
    println!("zero is {}, succ is {}", zero(), succ());
    println!("one is {}", asucc(zero()).eval());
    println!("two is {}", asucc(asucc(zero())).eval());
    println!("three is {}", asucc(asucc(asucc(zero()))).eval());
    for x in 0..5 {
        println!("{} is {} => {:?}", x, encode_num(x), decode_num(encode_num(x)));
    }
}

#[cfg(test)]
mod test {
    use crate::*;
    #[test]
    fn id_id() {
        assert_eq!(
            apply(id(), id()).eval(),
            id()
        );
    }
}