专栏首页Rust语言学习交流Rust 编程 | 基于Y组合子实现闭包递归

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

关注上方蓝字关注我们

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

本文灵感来自于《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)
// 就这样一直递归调用下去

后记

希望本文能给读者朋友们带来一些收获,如有错漏,欢迎指教。关于 Y 组合子和函数式编程,还有更多内容值得去学习和探索。

武汉加油,中国加油,大家加油

点击「阅读原文」可查看完整代码

本文分享自微信公众号 - Rust语言学习交流(rust-china)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 19:救援

    19:救援 总时间限制: 1000ms 内存限制: 65536kB描述 救生船从大本营出发,营救若干屋顶上的人回到大本营,屋顶数目以及每个屋顶的坐标  和人数...

    attack
  • 用FME进行数据分析之数据透视表

    数据透视表是计算、汇总和分析数据的强大工具,可助你了解数据中的对比情况、模式和趋势。

    数据处理与分析
  • 手把手教你搭建一个 Elasticsearch 集群

    凡事都要讲究个为什么。在搭建集群之前,我们首先先问一句,为什么我们需要搭建集群?它有什么优势呢?

    崔庆才
  • 能跟你聊DOTA的神经对话模型:Meena&DialoGPT

    提到对话机器人或者聊天机器人,国内的朋友可能先想到的是微软小冰或者苹果Siri。这两个机器人由于需要完成一些功能性的任务,都采用了模块化设计,虽然神经网络在其中...

    朴素人工智能
  • 手把手教你用Prophet快速进行时间序列预测(附Prophet和R代码)

    对于任何业务而言,基于时间进行分析都是至关重要的。库存量应该保持在多少?你希望商店的客流量是多少?多少人会乘坐飞机旅游?类似这样待解决的问题都是重要的时间序列问...

    数据派THU
  • sql基础知识:分页+排序

    Oracle的分页还真是挺恶心地,不像mysql直接Limit就搞定 select name from student limit 0,20; Oracle需要...

    用户1154259
  • Web前端学习 第7章 Vue基础教程8 提交表单

    v-model指令可以实现数据的双向绑定,也就是说如果input标签添加v-model指令后,在页面上修改input内的文本,会直接改变v-model绑定的变量...

    学习猿地

扫码关注云+社区

领取腾讯云代金券