Rust smart pointer issue

Question

I'm trying to implement Church numerals

//! representation of natural numbers using lambda calculus, named after  
//! Alonzo Church. Each Church numeral corresponds to a natural number `n`  
//! and is represented as a higher-order function that applies a given function `f` `n` times.  
//! ex) f(f(f(x))) is equal to number 3
use std::rc::Rc;

/// Church numerals are represented as higher-order functions that take a function `f`
pub type Church<T> = Rc<dyn Fn(Rc<dyn Fn(T) -> T>) -> Rc<dyn Fn(T) -> T>>;


/// Implement a function to convert a Church numeral to a usize type.
pub fn to_usize<T: 'static + Default>(n: Church<T>) -> usize {
    use std::cell::RefCell;

    let counter = Rc::new(RefCell::new(0));
    let counter_clone = Rc::clone(&counter);

    let result_func = n(Rc::new(move |x| {
        *counter_clone.borrow_mut() += 1;
        x
    }));

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

    // Extract the value from the reference-counted cell
    let result = *counter.borrow();

    result
}

I'm trying to implement to_usize function, which convert given Church to it's corresponding value.
However, counter value doesn't update and still remain zero. I think counter and counter_clone have same reference...

Answer 1

I don't see a problem with the behaviour of the code: with the correct input (a Church numeral), it produces the expected number.

println!("0: {}", to_usize(Rc::new(|f: Rc<dyn Fn(usize) -> usize>| Rc::new(move |x| x))));
println!("1: {}", to_usize(Rc::new(|f: Rc<dyn Fn(usize) -> usize>| Rc::new(move |x| f(x)))));
println!("2: {}", to_usize(Rc::new(|f: Rc<dyn Fn(usize) -> usize>| Rc::new(move |x| f(f(x)))))));
println!("3: {}", to_usize(Rc::new(|f: Rc<dyn Fn(usize) -> usize>| Rc::new(move |x| f(f(f(x)))))));

Outputs 0 through 3 as expected. Maybe the functions you were passing as input were not correct?

On a separate note, the type parameter of to_usize does not accurately capture what you would want from Church numeral, which is that it receives a function that is polymorphic in its input. Instead, the type parameter is constrained by to_usize and chosen at the call site, even though the call site does not make use of it. As a consequence, the way you are tracking "how many calls occurred" is using RefCell (which, as @Chayim pointed out in the comments, could be a Cell), which is suprising.

Ideally, to_usize could choose to instantiate the Church numeral with a usize type parameter, but this would require rank 2 polymorphism that Rust does not offer (for <T> Rc<dyn Fn(T) -> T>).

As a compromise, with an extra trait constraint:

pub fn to_usize<
    T: 'static + Default + std::ops::Add<usize, Output = T>
>(n: Church<T>) -> T {
    n(Rc::new(|x| x + 1))(Default::default())
}