Lambda算子5a:Why oh why Y?
先看一个非lambda算子的简单递归函数。嗯,猜对了,就是求阶乘,n!。没办法,标准例子嘛:factorial(n) = 1 if n = 0
factorial(n) = n * factorial(n-1) if n > 0
而最后是我们的递减函数。我们用Pred x 来计算x – 1。
嗯,现在我们可以来搞定阶乘函数了。递归部分暂时空白:lambda n . IsZero n 1 (Mult n (
something (Pred n)))
注意哈。我们不得不用something 暂时替代一下,因为我们没有任何函数名可用。不像上面的factorial(n) = n * factorial(n-1) if n > 0,要递归的时候调用同一个函数名,传入不同的参数就行了。所有现在问题就是:我们怎么才能让这个something 递归起来?
这个问题的答案就是所谓的组合子了。组合子是特殊的高阶函数(高阶函数的参数是函数,返回值也是函数)。定义这个函数时除了应用函数,不需要引用其它任何东西。Y组合子好像有种魔力,能让递归变得可能。它的定义如下:
let Y = lambda y . (lambda x . y (x x)) (lambda x . y (x x))
仔细观察一下这个定义,可以发现我们称这个函数为Y的原因在于它的形状。我们把上面的公式写成解析树的形式。把你的显示器倒过来,就可以看到一个接一个地Y了。^_^
Y组合子特别的地方在于把Y应用到Y身上后返回的是对这个应用自身的应用。也就是说,(Y Y) = Y (Y Y)
. 我们来推导一下 (Y Y)
Y Y
- 展开第一个 Y:
(lambda y . (lambda x . y (x x)) (lambda x . y (x x))) Y
- 来一把beta:
(lambda x . Y (x x)) (lambda x. Y (x x))
- 第二个lambda式子里有x, 和第一个式子里的x冲突了,所以来个Alpha[x/z] :把第二个lmabda式子里的x换成z:
(lambda x . Y (x x)) (lambda z. Y (z z))
- 再来Beta:
Y ((lambda z. Y (z z)) (lambda z. Y (z z)))
- 把Y展开,然后对y和x做alpha变换:alpha[y/a][x/b]:
(lambda a . (lambda b . a (b b)) (lambda b . a (b b))) ((lambda z. Y (z z)) (lambda z. Y (z z)))
- 再Beta,不要嫌长哈:
(lambda b . ((lambda z. Y (z z)) (lambda z. Y (z z))) (b b)) (lambda b . ((lambda z. Y (z z)) (lambda z. Y (z z))) (b b))
Y Y = Y (Y Y)
。
这也是Y的魔力:通过把自身应用到自身,它再造了自己:(Y Y) = Y (Y Y) = Y (Y (Y Y))
, 子子孙孙,无穷无尽。Y最重要的特性便是Y F = F (Y F)。Y一附身,就有定点了。神奇得紧啊。let fact = lambda n . IsZero n 1 (Mult n (fact (Pred n)))
现在的问题是,”fact”并不是一个在fact内定义好的标识符。我们怎么才能让lambda式子内的”fact”指向”fact”的函数定义?思考ing….嗯,我们可以再做一个lmabda函数,以便我们把”fact”函数当成参数传进去,然后如果我们可以想法写出一个能把自己当成参数传给自己的”fact”, 就大功告成了。我们把这种自己玩儿自己的函数叫做metafact:
let metafact = lambda fact . (lambda n . IsZero n 1 (Mult n (fact (Pred n))))
注意哈,(metafact fact) n = fact n。也就是说,fact是metafact这个函数的一个定点。定点的定义其实很简单:F(X) = X的话,X就是函数F的一个定点。当年高一时好像就学了这个概念。想不到的是这个看似简单的概念竟然在许多计算机科学理论和应用里扮演重要角色。比如程序分析,比如格点理论,比如模型检验,比如µ-算子,比如拓扑。
fact n = (metafact metafact) n
.
这里揭示了一个非常重要的技巧:我们实现函数自我引用(self-reference)的基本方法就是把一个函数应用到他自身。而通过自我引用完成递归就是Y起作用的地方。它让我们构建一个怪异的结构。在这种结构里,上面式子里的函数可以被复制到我们需要递归的地方。如下式子可以实现我们的构想: metafact (Y metafact)
。把它展开:(lambda fact . (lambda n . IsZero n 1 (Mult n (fact (Pred n))))) (Y (lambda fact . (lambda n . IsZero n 1 (Mult n (fact (Pred n))))))
(Y metafact)
就是lambda函数metafact参数fact的值。当我们对该函数应用β转换时,如果n为0, 函数返回1。如果n不为0,我们则调用Mult n (fact (Pred n))。对Fact应用beta转换, 我们得到Y metafact (就是我们传进去的参数哈)。结合Y的疯狂魔术,我们得到 metafact (Y metafact) (Pred n)。
如果你对Y有兴趣,我们强烈推荐The Little Schemer这本书。该书非常精彩,写得象一本儿童读物。书里要么每一页正面是一个问题,背面就是答案,要么一页分成两栏,一栏问题一栏答案。书的风格轻松幽默,不仅教你Scheme编程,更教人怎么思考。
(lambda x y . x * y) 3 ((lambda z. z * z) 4)
我们可以采用不同的顺序来计算:先对(lambda x y . x * y
)做beta变换,得到3 * ((lambda z . z * z) 4)
或者,我们可以对((lambda z . z * z) 4)
做beta变换先:(lambda x y . x * y) 3 (4 * 4)
这个例子里,两种不同的方法得出同样的结果。但对有些表达式却不然。第一种顺序叫做lazy evaluation:只有在需要一个函数时我们才计算它。第二种顺序叫做eager evaluation:我们总是计算出一个参数的值再把该参数传给一个函数。编程语言里面,Lisp, Scheme, 和ML这三种基于lambda算子的语言采用eager evaluation。Haskell和Mrianda这两种基于lambda算子的语言采用lazy evaluation。这篇帖子里的Y组合子是对lazy evaluation的Y。如果我们采用eager evaluation,前述的Y组合子就失效了――它会不停地拷贝Y,形成死循环。