Rust 编程 | 基于Y组合子实现闭包递归

MikeLoveRust

发布于 2020-03-10 15:42:07

1.6K0

发布于 2020-03-10 15:42:07

文章被收录于专栏：Rust语言学习交流

关注上方蓝字关注我们

理清头脑混沌，觉醒心智天地

本文灵感来自于《Rust 编程之道》读者群里读者朋友们的一些问题和讨论。

现在想实现这样一个Y函数，用于计算自然数列阶乘的值。

// 输出 3628800
fn main() {
    let fact = &|f: &dyn Fn(i32) -> i32, i| if i > 0 { i * f(i - 1) } else { 1 };
    println!("{}", Y(fact, 10))
}

该函数的第一个参数是一个闭包，用于指定阶乘（factorial）的计算方法。第二个参数是一个值，指定了要计算10以内的阶乘。

一般函数式语言中，匿名函数递归是用 Y 组合子来实现递归。Rust 是混合式范式语言，自然也支持函数式语言特性，所以我们来试试用 Rust 如何实现 Y 组合子。

故事得从 lambda 演算讲起

（对这方面知识了解的朋友可跳过这一小节）

在具体实现代码之前，先来了解下什么是 Y 组合子。想要了解 Y 组合子，又必须得知道什么是 Lambda 演算。暂时先不用考虑它们都是干什么的，只需要先了解它们是什么。（不要被这些符号吓懵，都是纸老虎）

先来看一下lambda表达式的基本语法(BNF)：

<expr> ::= <identifier>   // 恒等函数， λx.x
<expr> ::= *lambda* <identifier-list>. <expr> // 返回恒等函数的函数， λy. (λx.x)
<expr> ::= (<expr> <expr>)

使用lambda表达式的基本语法规则，我们就可以使用前两条语法来定义lambda 函数了，如：

// lambda x y. x + y
λx y. (+ x y) // ----> λx. (λ y. + x y), 利用currying技术，支持多个参数，闭包的鼻祖

其中，x 和 y 分别都是 identifier。而 x + y就是一个表达式（expr）。为了表示方便，可以用 λ 这个符号来表示 lambda ：

λx y. (+ x y)

注意，这里定义的函数是一个匿名的加法函数，如果给它命名为 add 的话，相当于是：

let add = λ x y. (x + y)
// 等价于
add(x, y)

函数定义好以后，如何计算具体的值呢，比如想计算 add(2, 3)，怎么办？那就可以用上面的第三条规则：

( (λx y. (+ x y)) 2  3 )

其中，匿名函数是一个expr，2和3具体的值也是一个字面量expr。（不知道大家有没有发现，这个语法看上去像不像 Lisp 呢？）

那么接下来如何具体求值呢？就需要用到两条求值规则了。

Alpha 等价变换（equivalence or conversion）
Beta 规约（reduction）

Alpha 等价变换

Alpha是一个重命名操作。就是说，变量的名称是不重要的：给定Lambda演算中的任意表达式，我们可以修改函数参数的名称，只要我们同时修改函数体内所有对它的自由引用。

所以，对于上面的求值表达式：

λx y. (+ x y)
// 经过 Alpha 变换以后，不会影响函数的含义
λy x. (+ y x)

Beta 规约

这才是真正让函数可以求值的规则。这条规则使得Lambda演算能够执行任何可以由机器来完成的计算。

如果你有一个函数应用，你可以对这个函数体中和对应函数标识符相关的部分做替换，替换方法是把标识符用参数值替换。也就是说：

// 对该函数进行求值计算
( (λx y. (+ x y)) 2  3 )
// Beta 规约以后得到
(λx y. (+ 2 3))

就是用 2 和 3，分别替换了 x 和 y。看了半天，是不是发现，这条规则你从初中学函数的时候就开始用了？

再看一个复杂的例子：

// 有两个参数的函数
( (λ x y. x y) (λ z . z * z) 3 )

// 开始使用Beta规约进行运算
// step 1:   使用 (λ z . z * z) 替换 x， 使用 3 替换 y
( (λ x y. (λ z . z * z)  3)

// step 2: 使用 3 替换 z
(  λ x y. (λ z . 3 * 3) ）

Lambda演算的规则简单来说差不多就是这些。

Y 不动点

因为 Lambda演算是没有名字的，那么如果想实现递归该怎么办？（想想我们本文初始提出的问题，如果用Rust 闭包来实现递归，连类型如何表示都无法做到）

所以，我们需要采用一些非常的手段，使用 Y 不动点组合子。

先来看一下阶乘函数用简单函数的表示：

// factorial
fact(n) = 1 if n = 0
fact(n) = n * fact(n-1) if n > 0

那么如果改成 lambda 演算呢？

λn. IsZero ( n  1  (Mut n Rec(n-1) ) )

IsZero 代表判断是不是 0，如果是0 ，则返回 1，如果不是0，则返回 n 和 Rec(n - 1 )的乘积。其中，Rec(n-1)代表了递归的求值。那么，如何递归呢？

答案就是使用 Y 不动点组合子，它的样子如下：

let Y = λy . (λx . y (x x)) (λx . y (x x))

Y组合子的特别之处在于它应用自身来创造本身，也就是说可以这样：

 (Y Y) = Y (Y Y)

我们使用上面的规约规则来看看它如何工作：

// 展开第一个 Y：
(λy . (λ x . y (x x)) (λ x . y (x x))) Y

// Beat规约：
(λ x . Y (x x)) (λ x . Y (x x))

// Alpha[x/z]变换第二个lambda：
(λ x . Y (x x)) (λ z . Y (z z))

// 继续beta规约：
Y ((λ z . Y (z z) (λ z . Y (z z))

// 展开前面的 Y，并进行alpha[y/a][x/b]变换
// (λy . (λ x . y (x x)) (λ x . y (x x))) ((λ z . Y (z z) (λ z . Y (z z))
 (λa . (λ b . a (b b)) (λ b . a (b b)))  ((λ z . Y (z z) (λ z . Y (z z))

// beta 规约：((λ z . Y (z z) (λ z . Y (z z)) 替换 a
( λ b . ( (λ z. Y (z z)) (λ z. Y (z z))) (b b) )   (λ b . ((λ z. Y (z z)) (λ z. Y (z z))) (b b) )


// 现在观察，是不是
// ( λ b .  Y Y (b b) )   (λ b . Y Y (b b) )
// ( λ x .  Y Y (x x) )   (λ x . Y Y (x x) )
// ( λ x .  Y (x x) )  (λ x . Y (x x) ) ( Y )
// 注意：Y Y == (λ x . Y (x x)) (λ x . Y (x x)) 即 :
Y (Y Y)

有点绕脑子是不是？回到最初的函数：

// factorial
fact(n) = 1 if n = 0
fact(n) = n * fact(n-1) if n > 0

// 写成
fact n = if n==0  1  n*fact(n-1)

// 也就是
fact = λn. if n==0 1  n*(fact n-1)

// 将fact拿出来
fact = λf. λn.( if n==0 1 n*(f n-1) )  fact

// 将 λf. λn.( if n==0 1 n*(f n-1)) 写作 F 的话，则有：
fact = F fact

这不就是不动点吗？fac 是 F 的不动点。

fact = F fact // fact 是 F 的不动点
fact = YF // 再把 Y 组合子和不动点关联起来
// 就可以用于递归验证了：
fact 3
= YF 3
= F YF 3 // F 在 n不是0的时候返回 n*(f n-1) ，现在 n 是 3
= 3*(YF 2)
= 3*(F YF 2) // 不断展开
= 3*(2*(YF 1))
= 3*(2*(F YF 1)) // 不断展开
= 3*(2*(1*(YF 0)))
= 3*(2*(1*1))
= 6

Rust 中实现 Y 组合子来递归闭包

那么在 Rust 里该如何实现呢？Rust 里支持闭包，而闭包可以用作是一个匿名函数。

经过前面的学习，我们想想，该如何用Rust 构造 Y组合子呢？先假如只传入一个闭包参数：

// 定义一个 trait，这个trait必须要求是对象安全的
// 这个 trait 里定义了 一个回调方法
trait Mut<R> {
    fn recu(&self, o: & dyn Mut<R>) -> R;
}

// 为闭包实现递归调用
impl<R, F> Mut<R> for F
where
    F: Fn(&dyn Mut<R>) -> R,
{
    
    fn recu(&self, o: & dyn Mut<R>) -> R {
        self(o)
    }
}

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

fn Y<T, F: Fn(T) -> T>(f: &F) -> T {
    (&|x: &Mut<T>| x.recu(x)) (&|x: &Mut<T>| f( x.recu(x) ) )
}

// 把 x的类型去掉再看看：
(&|x| x.recu(x)) (&|x| f( x.recu(x) ) ) //  （ g(x) ）（ f(g(x) ）

但是，这是「call-by-name」的求值方式。要使得它真正工作，我们还必须传入一个值，因为Rust是「call-by-value」的方式来求值的，只有函数式语言是「call-by-name」，这个和lambda演算的求值顺序有关（具体可以自行搜索相关资料），「call-by-name」属于惰性求值，只有在需要计算的时候给具体的值就可以了。

所以，我们需要给Y函数还传递另外一个值，用于「call-by-value」式递归计算。

trait Mut<T, R> {
    fn recu(&self, o: & dyn Mut<T, R>, t: T) -> R;
}

impl<T, R, F> Mut<T, R> for F
where
    F: Fn(&dyn Mut<T, R>, T) -> R,
{
    
    fn recu(&self, o: & dyn Mut<T, R>, t: T) -> R {
        self(o, t)
    }
}

// 定义Y组合子：Y = λf. (λx.x x) (λx. f(x x))
fn Y<T, R, F>(f: &F, t: T) -> R
where
    F: Fn(&dyn Fn(T) -> R, T) -> R,
{
    (&|x: &dyn Mut<T, R>, t| x.recu(x, t))(&|x: & dyn Mut<T, R>, t| f(&|t| x.recu(x, t), t), t)
}

fn main() {
    let fact = &|f: &dyn Fn(i32) -> i32, i| if i > 0 { i * f(i - 1) } else { 1 };
    println!("{}", Y(fact, 10)) // 3628800
}

playground (阅读原文)

其中实现 Y 组合子这行代码如何理解呢？

(&|x: &dyn Mut<T, R>, t| x.recu(x, t))(&|x: & dyn Mut<T, R>, t| f(&|t| x.recu(x, t), t), t)
 
// 整个闭包可看作  （ g(x, t) ）（ f(g(x, t) , t）

执行过程大概是：

Y(fact, 10)
==
 (&|x: &dyn Mut<T, R>, t| x.recu(x, t))(&|x: & dyn Mut<T, R>, t| fact(&|t| x.recu(x, t), t), t)

// 整个闭包可看作 f(...)(x,t),
// 最开始执行右侧括号内的 (&|x: & dyn Mut<T, R>, t| f(&|t| x.recu(x, t), t), t)
// 所以，就是  fact(fact.recu(fact, 10 ), 10)
// 就这样一直递归调用下去