< 返回版块

lithbitren 发表于 2023-09-04 03:08

Tags:闭包,递归

最近在看wasm的文档,其中有一个章节讲request_animation_frame的。

要知道JavaScript的这个API传统上都是无限递归调用的(因为没有返回值,所以一般来说不会因为无限递归而爆栈)。

但没想到在rust_wasm的范例里竟然强行用闭包实现了递归,不同于其他rust的闭包递归那样构造不动点结构体,而是用Rc<RefCell<Option<_>>>来构造循环引用以实现闭包递归。 我把wasm的Closure结构体替换成了Box<dyn Fn(..) -> ..>,于是发现居然能通过这种奇技淫巧来实现闭包递归。

传统不动点结构体法:(来自知乎 酱紫君 的回答

fn main() {
    struct Y<'yy> {
        fix: &'yy dyn Fn(&Y, u32) -> u32,
    }
    let fibonacci = {
        let yc = Y { fix: &|y, n| if n <= 1 { n } else { (y.fix)(y, n - 1) + (y.fix)(y, n - 2) } };
        move |i| (yc.fix)(&yc, i)
    };
    let factorial = {
        let yc = Y { fix: &|y, n| if n == 0 { 1 } else { n * (y.fix)(y, n - 1) } };
        move |i| (yc.fix)(&yc, i)
    };
    assert_eq!(fibonacci(7), 13);
    assert_eq!(factorial(7), 5040);
}

Rc/RefCell循环引用法:

use std::cell::RefCell;
use std::rc::Rc;

fn main() {
    let f = Rc::new(RefCell::new(None));
    let g: Rc<RefCell<Option<Box<dyn Fn(u32) -> u32>>>> = f.clone();
    *g.borrow_mut() = Some(Box::new(move |i|
        if i <= 1 { 1 } else { i * f.borrow().as_ref().unwrap()(i - 1) }
    ));
    assert_eq!(g.borrow().as_ref().unwrap()(5), 120);
}

循环引用法把rust最常见的几个甲Rc<RefCell<Option<Box<dyn...全都叠上了,讲不好和不动点法哪个更繁琐,不过wasm那个范例里循环引用还可以从外部捕获变量进行无参数递归,感觉更神奇了。

(注:都不推荐使用,递归还是建议用最基础外部fn函数来定义最好)


Ext Link: https://play.rust-lang.org/?version=stable&mode=release&edition=2018&gist=6fcd8064e9b4f875826ce1c6448fd3f7

评论区

写评论
Wybxc 2023-09-04 22:19

OCaml 里经常使用这种方法来形成递归,叫做“tying the recursive knot”:

let fact0 =
  ref (fun x -> x)

let fact n =  (* note: no [rec] *)
  if n = 0 then 1 else n * (!fact0) (n-1)

let () = fact0 := fact

let x = fact 5 (* ==> 120 *)
1 共 1 条评论, 1 页