转载

浅谈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)再次传入的函数。

在理解这个机制之后,通用的递归函数已经到手。封装一下就轻而易举了,这就是传说中的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三条规则而不需要命名。

相关资料,从易到难排序

  • g9的lambda calculus系列 有很多lambda的入门讲解,幽默风趣
  • The Little Schemer 手把手学lambda
  • The Seasoned Schemer 手把手2
  • SICP 不用多说,看书评
  • MIT讲SICP MIT的课,值得一看
正文到此结束
Loading...