church number in rust

Question

This is a church number implementation under rust, but there are some problems ，there is my code

use std::cell::RefCell;
use std::rc::Rc;
pub type Church<T> = Rc<dyn Fn(Rc<dyn Fn(T) -> T>) -> Rc<dyn Fn(T) -> T>>;

pub fn one<T: 'static>() -> Church<T> {
    Rc::new(move |f| Rc::new(move |x| f(x)))
}

pub fn two<T: 'static>() -> Church<T> {
    Rc::new(move |f| Rc::new(move |x| f(f(x))))
}

pub fn zero<T: 'static>() -> Church<T> {
    Rc::new(|_| Rc::new(|x| x))
}


pub fn succ<T: 'static>(n: Church<T>) -> Church<T> {
    Rc::new(move |f| {
        let f_n = n(Rc::clone(&f));
        Rc::new(move |x| f(f_n(x)))
    })
}

pub fn add<T: 'static>(n: Church<T>, m: Church<T>) -> Church<T> {
    Rc::new(move |f| {
        let f_n = n(Rc::clone(&f));
        let f_m = m(Rc::clone(&f));
        Rc::new(move |x| f_m(f_n(x)))
    })
    
}


pub fn mult<T: 'static>(n: Church<T>, m: Church<T>) -> Church<T> {
    Rc::new(move |f| {
        let f_n = n(Rc::clone(&f));
        let f_m_n = m(Rc::clone(&f_n));
        Rc::new(move |x| f_m_n(x))
    })
}


pub fn exp<T: 'static>(n: usize, m: usize) -> Church<T> {
    let church_n: Rc<dyn Fn(Rc<dyn Fn(T) -> T>) -> Rc<dyn Fn(T) -> T>> = from_usize(n);
    let church_m: Rc<dyn Fn(Rc<dyn Fn(T) -> T>) -> Rc<dyn Fn(T) -> T>> = from_usize(m);
    Rc::new(move |f| {
        let f_m = Rc::clone(&church_m);
        let f_n = Rc::clone(&church_n);
        let mut result = f.clone();
        for _ in 0..m {
            result = f_n(result.clone());
        }
        result
    })
}

/// Implement a function to convert a Church numeral to a usize type.
pub fn to_usize<T: 'static + Default>(n: Church<T>) -> usize {
    let count = Rc::new(RefCell::new(0));

    let c = Rc::clone(&count);
    let default_function: Rc<dyn Fn(T) -> T> = Rc::new(
        move |x| {
            let mut count_mut = c.borrow_mut();
            *count_mut += 1;
            x
        }
    );

    let result_function = n(default_function);

    let _ = result_function(Default::default());

    let result = *count.borrow();
    result
}

/// Implement a function to convert a usize type to a Church numeral.
pub fn from_usize<T: 'static>(n: usize) -> Church<T> {
    
    let mut result = zero();
    for _ in 0..n {
        result = succ(result);
    }
    result
}

this is the test code

mod test {
    fn id(n: usize) -> usize {
        to_usize(from_usize::<()>(n))
    }

    fn c_id(n: Church<usize>) -> Church<usize> {
        from_usize(to_usize(n))
    }

    #[test]
    fn engineering_isnt_just_mathematics() {
        const N: usize = 77777;
        assert_eq!(N, id(N));
    }

    /// This test case is an optional challenge.
    /// While it's not necessary to pass this test,
    /// successfully doing so could provide a sense of satisfaction and achievement.
    // #[test]
    // fn i_said_engineering_isnt_just_mathematics() {
    //     const N: usize = 777777777777777;
    //     assert_eq!(N, id(N));
    // }

   
}

my question is i can't pass the test

#[test]
    fn engineering_isnt_just_mathematics() {
        const N: usize = 77777;
        assert_eq!(N, id(N));
    }

the error output is

running 1 test

thread 'assignments::assignment08
::church_grade::test::engineering_isnt_just_mathematics' has overflowed its stack
fatal runtime error: stack overflow
error: test failed, to rerun pass `-p cs220 --lib`

Caused by:
  process didn't exit successfully: `/home/liscopye/cs220/target/debug/deps/cs220-444ce00a2079485d 
'assignments::assignment08::church_grade::test::engineering_isnt_just_mathematics' --exact --nocapture` (signal: 6, SIGABRT: process abort signal)

 *  The terminal process "cargo 'test', '--package', 'cs220', '--lib', '--', 'assignments::assignment08::church_grade::test::engineering_isnt_just_mathematics', '--exact', '--nocapture'" terminated with exit code: 101. 
 *  Terminal will be reused by tasks, press any key to close it. 

i think the reason is when church nunber is too large, when convert it to natural number, stack overflow will happen.it means maybe there is some problem with my to_size() function.

i try to use tail recursion, every time call the f, i just increase the count。When there are multiple levels of f nesting, it is only expanded once each time. but i don't known if it's a possible method to solve it and i don't know how to achieve it

I rewrite the from_usize:

pub fn from_usize<T: 'static>(n: usize) -> Church<T> {
    if n == 0 {
        zero()
    } else if n == 1 {
        one()
    } else if n == 2 {
        two()
    } else if n % 2 == 0 {
        add(from_usize(n / 2), from_usize(n / 2))
    } else {
        succ(from_usize(n - 1))
    }
}

It can pass 77777, but still can't pass 777777777777777, I will try to do more optimization

Answer 1

I think your problem is:

for _ in 0..n {
    result = succ(result);
}

This causes a recursion depth of 77777 when evaluating it later, which is most certainly too deep for a normal stack.

So I'd say your solution is not fixing a single line or something similar; it's rather an algorithmical rethinking.

You might have to divide and conquer. Currently, you are representing an 8 as:

f8(x) = f(f7(x))
f7(x) = f(f6(x))
f6(x) = f(f5(x))
f5(x) = f(f4(x))
f4(x) = f(f3(x))
f3(x) = f(f2(x))
f2(x) = f(f(x))

This is what breaks your stack, as it has O(n) recursion depth.

Now if you were to instead represent it as:

f8(x) = f4(f4(x))
f4(x) = f2(f2(x))
f2(x) = f(f(x))

You can already see how much easier an evaluation of that function would be, because you now only go O(log n) recursions deep. Further, because you can reuse f4 multiple times (as it is an Rc in your code), you should be able to represent much bigger numbers like this.

Of course there's still the challenge of representing numbers that are not a multiple of 2, but I'm sure you will figure something out, based on the binary representation of a number or similar :) like, 12 is 8 + 4 + 2 (binary 0b1110). Based on that, you should be able to achieve the same O(log n) stack depth for arbitrary numbers.