Rust闭包实现递归

发表于 |

在不动点组合子Y-Combinator中介绍了如何借助 Y-Combinator 和 Z-Combinator 实现在闭包中引用自己。

基于 Y-Combinator 的方案

回忆一下 Y-Combinator 的定义

1
Y = λf.(λx.f (x x)) (λx.f (x x))

Fn

这里的X是为了实现 Y-Combinator 中的 x x 这样的结构。从不动点组合子Y-Combinator中可以知道 x 实际上是个递归类型。

容易看出，这里很多东西都是一样的，例如Rc<dyn Fn(A) -> O>和impl Fn(A) -> O都表示的是F：

  1. 返回值可以用 impl 做静态分发，当然写成 Box<dyn Fn(A) -> O> 返回也是没问题的
  2. impl 本身也不能作为 closure 的参数
    impl Trait only allowed in function and inherent method return types, not in closure param
    但是可以在普通函数中用 
    1
    2
    3
    4
    5
    6
    // Error
    let fi = |i:i32| -> i32 { i + 1 };
    let f1 = |f: impl Fn(i32) -> i32| -> i32 { f(1) };
    // OK
    fn fi(i:i32) -> i32 { i + 1 }
    fn f1(f: impl Fn(i32) -> i32) -> i32 { f(1) }

整个实现如下所示，简单介绍下：

  1. (|x: X<F>| x.call(x.clone()))(x)
    实际上就是 x x，这里用 eta-conversion 来避免了立即求值。
  2. 那么 inner1 就应该是 (λx.f (x x))了
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
fn y<A, O, F>(f: Rc<dyn Fn(Rc<dyn Fn(A) -> O>) -> F>) -> impl Fn(A) -> O
    where
        F: Fn(A) -> O,
        F: 'static,
        A: 'static,
        O: 'static,
{
    struct X<F>(Rc<dyn Fn(X<F>) -> F>);

    impl<F> Clone for X<F> {
        fn clone(&self) -> Self {
            Self(Rc::clone(&self.0))
        }
    }

    impl<F> X<F> {
        fn call(&self, x: Self) -> F {
            (self.0)(x)
        }
    }

    let inner = Rc::new(move |x: X<F>| f(
            Rc::new(move |a| (x.call(x.clone())) (a))
        ));
    let x = X(inner);
    (|x: X<F>| x.call(x.clone()))(x)
}

FnMut

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
fn y_mut<A, O, F>(f: Rc<RefCell<dyn FnMut(Rc<RefCell<dyn FnMut(A) -> O>>) -> F>>) -> impl FnMut(A) -> O
    where
        F: FnMut(A) -> O,
        F: 'static,
        A: 'static,
        O: 'static,
{
    struct X<F>(Rc<RefCell<dyn FnMut(X<F>) -> F>>);

    impl<F> Clone for X<F> {
        fn clone(&self) -> Self {
            Self(Rc::clone(&self.0))
        }
    }

    impl<F> X<F> {
        fn call(&self, x: Self) -> F {
            ((*self.0).borrow_mut())(x)
        }
    }

    let ff = Rc::new(RefCell::new(move |x: X<F>| {
        let mut ff_borrowd = (*f).borrow_mut();
        ff_borrowd(Rc::new(RefCell::new(move |a| (x.call(x.clone()))(a))))
    }));
    let x = X(ff);
    (|x: X<F>| x.call(x.clone()))(x)
}

fn main() {
    let a = Rc::new(RefCell::new(vec![0; 5]));
    let n: usize = (*a).borrow_mut().len();

    y_mut(Rc::new(RefCell::new({
        let a = Rc::clone(&a);
        move |f: Rc<RefCell<dyn FnMut(usize)>>| {
            let a = Rc::clone(&a);
            move |i| {
                if i < n {
                    (*a).borrow_mut()[i] = i;
                    ((*f).borrow_mut())(i + 1);
                }
            }
        }
    })))(0);
    println!("a is {:?}", a.borrow());
}

其他方案

  1. struct 包 closure
  2. 在 fn 定义 fn
    但不能捕获任何变量了
  3. 一个神奇的办法
    这个做法很有趣，它实际上是先顶一个 placeholder 的 fact 函数即 weak_holder，在真正的 fact 函数被定义时，调用 myself。在 fact 函数定义结束后，再把 fact 函数赋给 placeholder 的 weak_holder。 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    use std::{
        cell::RefCell,
        rc::{Rc, Weak},
    };

    fn main() {
        let weak_holder: Rc<RefCell<Weak<dyn Fn(u32) -> u32>>> =
            Rc::new(RefCell::new(Weak::<fn(u32) -> u32>::new()));
        let weak_holder2 = weak_holder.clone();
        let fact: Rc<dyn Fn(u32) -> u32> = Rc::new(move |x| {
            let myself = weak_holder2.borrow().upgrade().unwrap();
            if x == 0 {
                1
            } else {
                x * myself(x - 1)
            }
        });
        weak_holder.replace(Rc::downgrade(&fact));

        println!("{}", fact(5)); // prints "120"
        println!("{}", fact(6)); // prints "720"
    }