brainfuck

不动点组合子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"
    }