lalrpop-lambda 0.6.1

A λ-calculus grammar writting with LALRPOP.
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

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

/// Church encoded natural numbers
///
/// ```
/// # #![feature(box_syntax)]
/// # #[macro_use]
/// # extern crate lalrpop_lambda;
/// use lalrpop_lambda::Expression;
///
/// # fn main() {
/// assert_eq!(λ!{f.λ!{x.x}}, Expression::from(0));
/// assert_eq!(λ!{f.λ!{x.γ!(f,x)}}, Expression::from(1));
/// assert_eq!(λ!{f.λ!{x.γ!(f,γ!(f,γ!(f,x)))}}, Expression::from(3));
/// # }
/// ```
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(&Strategy::Applicative(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(&Strategy::Applicative(true)) {
            Expression::Var(id) => {
                if id == variable!(f) { 1 } else { 0 }
            },
            Expression::Abs(Abstraction(Variable(_id, _ty), box body)) => {
                u64::from(body)
            },
            Expression::App(Application(box e1, box e2)) => {
                u64::from(e1) + u64::from(e2)
            },
        }
    }
}

/// ```
/// # #![feature(box_syntax)]
/// # #[macro_use]
/// # extern crate lalrpop_lambda;
/// # fn main() {
/// let one = λ!{f.λ!{x.γ!(f,x)}};
/// let two = one.clone() + one.clone();
/// assert_eq!(2, u64::from(two.clone()));
/// assert_eq!(4, u64::from(two.clone() + two.clone()));
/// # }
/// ```
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(&Strategy::Applicative(false))
    }
}

/// ```
/// # #![feature(box_syntax)]
/// # #[macro_use]
/// # extern crate lalrpop_lambda;
/// # fn main() {
/// let one = λ!{f.λ!{x.γ!(f,x)}};
/// let two = one.clone() + one.clone();
/// assert_eq!(1, u64::from(one.clone() * one.clone()));
/// assert_eq!(4, u64::from(two.clone() * two.clone()));
/// # }
/// ```
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(&Strategy::Applicative(false))
    }
}


#[cfg(test)]
mod tests {
    use pretty_assertions::assert_eq;
    use crate::parse::ExpressionParser;
    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 zero() {
        // TODO: Should this be correct? What to do about smaller terms?
        assert_eq!(0, u64::from(λ!{x.x}));
    }


    #[test]
    fn one() {
        let ω = ExpressionParser::new().parse("λx.x x").unwrap();

        // TODO: Should this be correct? What to do about smaller terms?
        assert_eq!(1, u64::from(ω(Expression::from(1))));
    }

    #[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));
    }

    // app!(n, (\f.\x.(f (f x)))) -> 2^n
}