浅谈Y组合子

这篇文章希望能够通俗地讲清楚Y组合子,如果对lambda演算感兴趣的同学可以看看最后的相关资料

在lambda中,如果我们想要递归,以斐波那契数列为例,可以这样:

let power = lambda n. IF_Else n==0 1 n*power(n-1)

然而,在“纯”lambda演算中,是没有let关键字的,但我们可以暂时忘记这件事。我们需要换个方法进行递归,如果直接的递归不可行,那么我们可以尝试间接的。很容易能想到通过参数把自己传给自己:

let P = lambda self n. If_Else n==0 1 n*self(self, n-1)
P(P, 3)

如果每次递归都要这么写,就显得很不优雅。我们要想一个办法,能够通用的把自己传给自己。就像上面一样。我们试着构造一下,把斐波那契数列的逻辑替换为任意函数:

let gen = lambda self. AnyFunction(self(self))
gen(gen)

尝试写出斐波那契数列的AnyFunction实现:

let AnyFunction = lambda self n. If_Else n==0 1 n*self(n-1)

经过展开之后,发现任何函数只要在AnyFunction那个位置,经过上面的代码之后,都能够实现递归。

其中gen(gen)展开如下:

gen(gen) => AnyFunction(gen(gen))

可能你会疑问,gen(gen)为什么能够表达自己呢?因为gen(gen)展开为AnyFunction(gen(gen)),它能够返回AnyFunction自身,这就得到自己了。并且这时会把这个gen(gen)再传给AnyFunction。而gen(gen)不求值时是不展开的,因此gen(gen)没有被调用时,没有任何作用,但是一旦AnyFunction内部调用了传进来的gen(gen),那么就进行求值再次得到“自己”。通俗来讲,与其说gen(gen)是自身,还不如说这是一个把能够得到自己,并且把gen(gen)再次传入的函数。

在理解这个机制之后,通用的递归函数已经到手。封装一下就轻而易举了,这就是传说中的Y组合子:

let Y = lambda f. 
	let gen = lambda self. f(self(self))
	gen(gen)

再把let去掉可得到Y的定义:

lambda f. (lambda x. (f(x x)) lambda x. (f(x x)))

接下来可以试着使用一下:

( ( lambda f. (lambda x. (f(x x)) lambda x. (f(x x))) )
  ( lambda f. lambda n. n==0 ? 1 : n*(f n-1) )
) 4

看,完美!证明了lambda只需要alpha/beta/eta三条规则而不需要命名。


相关资料,从易到难排序

其他相关资料




转载标明原文链接:jjyy.guru/y-combinator


你可能还喜欢: