Rust实现Church Numeral遇栈溢出问题求助

我用Rust实现了丘奇数，但运行测试时出现栈溢出问题，尤其是处理大数值的转换时。

原始实现代码 #

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
}

测试代码 #

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));
    // }
}

错误信息 #

运行engineering_isnt_just_mathematics测试时触发栈溢出：

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. 

尝试的优化 #

我认为问题出在大数值转换时的栈溢出，尝试改写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))
    }
}

修改后能通过N=77777的测试，但仍无法处理777777777777777这类超大数值。

需求 #

求解决栈溢出问题的方案，以及能支持超大数值转换的进一步优化思路。

内容的提问来源于stack exchange，提问作者wuhu lalala