匿名递归函数

递归可以说是所有程序设计语言中必不可少的一部分了,是一种在数学、计算机科学中都很常见的工具。对于程序员来说嘛,不理解递归函数的程序员不是一个合格的程序员,递归在很大程度上可以提高程序员的效率(虽然不一定提升程序效率)。

那如果所有的函数都没有名字,那该如何递归呢?

没错,我是在说 lambda 演算系统中的概念, lambda 演算系统中的 lambda 表达式是没有名字的,因此直接通过函数名进行递归的想法在这里是行不通的。但是可以通过特殊方法实现递归,下面来介绍一下。

本文不打算讲多少 lambda 演算的东西,毕竟自己也是初学,只是想用编程语言使用纯匿名函数实现递归,就是手痒想写一下然后记录了一下。我打算使用 JS 实现,是因为 JS 简单。

Lambda演算中的递归

首先我们从一点点理论开始,慢慢道来。

我们都知道,或者至少听说过 lambda 演算系统是图灵完备的,或者说,和图灵机是等价的。换个朴素一点,更贴近生活的说法就是, lambda 演算做到所有我们现在电脑能做到的事情,甚至有过之而无不及。

但是这个没有数字、没有条件分支、没有循环,没有这些我们熟悉概念的一套理论,如何做到我们现在的机器能做到的一切工作呢?这里不去管前两个问题,在假设前两个问题都已经被解决的情况下,我们来解决循环的问题。

在允许递归的语言里,循环都可以转化为递归,只要确定了终止条件就可以。但是在一个无法递归的语言里,该怎么实现循环呢?

你想,这还不简单,把函数作为另一个的参数传入,那这个函数作为另一个函数的绑定变量,也就有一个名字了。这真是个好主意,也是要介绍的第一种方法,\omega组合子。

\omega 组合子的定义为 \lambda x.x\ x ,换成常见的编程语言的写法就是function (x) { return x(x); }。这个怎么用呢?按照惯例,这里举一个阶乘函数 (factorial)的例子。

W = x => x(x)
fact = W(f => n => n ? n * f(f)(n - 1) : 1)

应该注意到了,这里 f(f) 就是这个递归函数本身,在下一层递归中,又用到了上一层传入的 f,那最上层的 f 是什么呢?是 W 传入的自己,所以每一层递归中,都把自己和参数传给下一层函数,以便下一层可以继续传自己和参数。

本来到这里,故事可以完美结束了。但是数学家们总觉得这个方法缺乏一些灵性,每次都需要手动把自己往下传,实在是太丑陋了,于是 Haskell Brooks Curry 发现了另一种更优雅的方式。

不动点组合子

什么是不动点?一句话解释就是,对于一个函数 f ,使得 f(x)=xx 就是它的一个不动点。

那么不动点组合子呢?这里有它的定义 \lambda f.(\lambda x.f\ (x\ x))(\lambda x.f\ (x\ x)) ,我们一般用 Y 来表示它,所以也会叫它 Y 组合子。还是用人能看出来的语言写一遍:

function Y(f) {
  return function(x) {
    return f(x(x))
  }(function(x) {
    return f(x(x))
  })
}
// Or use arrow function
Y = f => (x => f(x(x)))(x => f(x(x)))

这么复杂?我们先不急着用 JS 跑这段代码,因为这段代码是有问题的,至于有什么问题、为什么有问题,后面也会解释,我们先来解释为什么这个叫不动点组合子。

不动点组合子接受一个函数,如果我们对其进行 \beta规约 运算,简单理解就是把参数替换掉。

\begin{aligned}Y\ g&=(\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x)))\ g\\&=(\lambda x.g\ (x\ x))(\lambda x.g\ (x\ x))\\&=g\ ((\lambda x.g\ (x\ x))\ (\lambda x.g\ (x\ x)))\\&=g\ (Y\ g)\\\end{aligned}

总之,最后变成了 Y\ g=g\ (Y\ g) 的形式,或者用更熟悉的表示是 Y(g)=g(Y(g)) 。于是, Y(g) 就是函数 g 的不动点。

好了,但是这又有什么用呢? 来个例子,继续用阶乘的例子解释一下

Y = f => (x => f(x(x)))(x => f(x(x)))
fact = Y(f => n => n ? n * f(n - 1) : 1)

因为 Y(g) = g(Y(g)) ,把 Y(g) 代入回 f 中有 Y(g) = n => n ? n * Y(g)(n - 1) : 1 ,于是这就有个递归的模样了。

完善JS中的实现

上面说到缺陷是直接执行会递归过深,知道存在这个现象了,可是为什么?

很简单,Y组合子中存在一个 (\lambda x.f\ (x \ x))(\lambda x.f\ (x\ x)) ,这里显然会导致递归,而且没有终结。那么,解决方法是?

我们再套一层函数,让求值不立刻进行,需要的时候才手动调用,所谓惰性求值:

Y = f => (x => f(() => x(x)))(x => f(() => x(x)))

这样,通过类似的推导可以得出 Y(g) = g(() => Y(g)) 。另一边,带入的函数需要稍作修改,要改成

fact = Y(f => n => n ? n * f()(n - 1) : 1)

才能正常使用。同理,因为 Y(g) = g(() => Y(g)) ,将原式带入可得 Y(g) = n => n ? n * (() => Y(g))()(n - 1) : 1 ,这里显然 (() => Y(g))() 就是 Y(g) ,所以理论结果和上面的没有区别,但是因为不会在函数中直接展开调用,所以不会有爆栈的问题了。

这样至少代码可以运行了,但是不对呀,怎么又多出了一个函数调用呢?宝宝不喜欢,我们能不能把它去掉?

这当然也是可以的,如下定义组合子即可: \lambda f.(\lambda x.f\ (\lambda y.x \ x\ y))\ (\lambda x.f\ (\lambda y.x \ x\ y))\ g

这又是什么意思呢?如果能理解一点 \lambda 表达式的 \beta 规约 计算,可以从下面的推导过程看出一点端倪:

\begin{aligned}Y\ g=&\lambda f.(\lambda x.f\ (\lambda y.x \ x\ y))\ (\lambda x.f\ (\lambda y.x \ x\ y))\ g\\=&(\lambda x.g\ (\lambda y.x\ x\ y))\ (\lambda x.g\ (\lambda y.x\ x\ y))\\=&g\ (\lambda y.(\lambda x.g\ (\lambda y.x\ x\ y))\ (\lambda x.g\ (\lambda y.x\ x\ y))\ y)\\=&g\ (\lambda y.Y\ g\ y)\\\end{aligned}

这个式子的含义是 Y(g) = g((y) => Y(g)(y)) ,这里同样有了惰性求值的特性,所以不会有之前递归过深的问题,而且,还传了一个参数,并对其进行求值了,我们来看看发生了什么。

Y = f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y)))
fact = Y(f => n => n ? n * f(n - 1) : 1)

因为 Y(g) = g((y) => Y(g)(y)) ,带入得到 Y(g) = n => n ? n * ((y) => Y(g)(y))(n - 1) : 1 ,显然, ((y) => Y(g)(y))(n - 1) 就是 Y(g)(n - 1) ,递归达成。

这里看起来已经完美了,对于 fact 也可以正常执行,但是有一个小问题——这个表达式不支持多参函数。之前的都支持多参函数,唯独这里出了点小问题,原因是这个y只能接受一个值,需要多参,我们可以用JS的参数扩展语句实现,不是大问题。

Y = f => (x => f((...y) => x(x)(...y)))(x => f((...y) => x(x)(...y)))

这里,在我看起来就已经完美了,如果嫌后面两个相同的一串太麻烦,还可以应用上之前的 \omega 组合子来缩减一下代码。

Y = f => (g => g(g))(x => f((...y) => x(x)(...y)))

后记

关于这个不动点组合子,我在很早以前就在某篇文章里看到过,一直没理解是什么意思,也纠结了很久。这几周看了一下 \lambda 演算,的确是一个极致简洁,但又无比强大的工具。在各个地方搜集资料简单学习了无类型 lambda 演算之后,终于搞清楚了这个不动点组合子的含义,然后就手痒想写一个出来。

为什么不使用C++?C++当然可以写,不过废了我很长的时间去调试模板,结果是实在是丑得一逼。感觉到静态类型注定要死在类型推断上之后,决定用动态类型的语言实现。感觉常用的 Python 的 lambda 废得一逼(虽然写这个还是绰绰有余)主要是丑得一逼,我最后还是换了 JS 。

后来,在完成这篇文章后,我又去别的地方找了一下相关资料,不小心发现有个网站上面有很多语言实现的Y组合子,而我本人的 JS 的实现早就被别人发现过(这个网站上 C++ 的两个实现都有问题,不能接受多个参数的 lambda 表达式),瞬间失去了热情。不过虽然自己做了重复的工作,不过毕竟造了一遍(没用的)轮子,还是和直接看别人的答案不一样的吧,稍稍自我安慰一下。

发表评论

电子邮件地址不会被公开。 必填项已用*标注