1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106

use std::ops::{Add, Mul};
use crate::{Expression, Abstraction, Application, Variable};

/// Church encoded natural numbers
///
/// ```
/// # #![feature(box_syntax)]
/// # #[macro_use]
/// # extern crate lalrpop_lambda;
/// # fn main() {
/// assert_eq!(0, u64::from(λ!{f.λ!{x.x}}));
/// assert_eq!(1, u64::from(λ!{f.λ!{x.γ!(f,x)}}));
/// assert_eq!(3, u64::from(λ!{f.λ!{x.γ!(f,γ!(f,γ!(f,x)))}}));
/// # }
/// ```
impl From<u64> for Expression {
    fn from(n: u64) -> Self {
        let succ = λ!{n.λ!{f.λ!{x.γ!(f, γ!(γ!(n, f), x))}}};
        let mut e = λ!{f.λ!{x.x}};
        for _ in 0..n {
            e = app!({&succ}, {&e}).normalize(false);
        }
        e
    }
}

/// Convert λ term back to native Rust type
///
/// ```
/// # #![feature(box_syntax)]
/// # #[macro_use]
/// # extern crate lalrpop_lambda;
/// # fn main() {
/// assert_eq!(0, u64::from(λ!{f.λ!{x.x}}));
/// assert_eq!(1, u64::from(λ!{f.λ!{x.γ!(f,x)}}));
/// assert_eq!(3, u64::from(λ!{f.λ!{x.γ!(f,γ!(f,γ!(f,x)))}}));
/// # }
/// ```
impl From<Expression> for u64 {
    fn from(e: Expression) -> u64 {
        // TODO: It would be ideal to use the Fn conversion and a way to "bind" `f` to u64::add.
        //
        // XXX: In fact more than ideal, this really should only be able to return an `Option<u64>`
        // since there are lambda terms which can evaluate to something which is not a chruch
        // encoded function.
        match e.normalize(true) {
            Expression::Var(id) => {
                if id == variable!(f) { 1 } else { 0 }
            },
            Expression::Abs(Abstraction(Variable(_id), box body)) => {
                u64::from(body)
            },
            Expression::App(Application(box e1, box e2)) => {
                u64::from(e1) + u64::from(e2)
            },
        }
    }
}

impl Add for Expression {
    type Output = Self;

    fn add(self, other: Self) -> Self {
        let add = λ!{m.λ!{n.λ!{f.λ!{x.γ!(γ!(m,f),γ!(γ!(n,f),x))}}}};
        γ!(γ!({add},{self}),{other}).normalize(false)
    }
}

impl Mul for Expression {
    type Output = Self;

    fn mul(self, other: Self) -> Self {
        let mul = λ!{m.λ!{n.λ!{f.λ!{x.γ!(γ!(m,γ!(n,f)),x)}}}};
        γ!(γ!({mul},{self}),{other}).normalize(false)
    }
}


#[cfg(test)]
mod tests {
    use super::*;

    // // TODO: Move these to tests as we finalize.
    // dbg!(u64::from(var!(x)));
    // dbg!(u64::from(var!(f)));
    // dbg!(u64::from(app!(f,app!(f,x))));
    // dbg!(u64::from(abs!{f.app!(f,app!(f,x))}));
    // dbg!(u64::from(abs!{f.abs!{x.app!(f,app!(f,x))}}));

    #[test]
    fn u64() {
        assert_eq!(0u64, Expression::from(0).into());
        assert_eq!(5u64, Expression::from(5).into());
    }

    #[test]
    fn add() {
        assert_eq!(Expression::from(5), Expression::from(2) +
                                        Expression::from(3));
    }

    #[test]
    fn multiply() {
        assert_eq!(Expression::from(6), Expression::from(2) * Expression::from(3));
    }
}