理解Y组合子

Published on 2009年09月19日 in 笔记. 9 Comments Tags: , , .

众所周知，lambda演算通过递归就可以图灵完备。好，用纯lambda演算写个递归吧。

等等，要递归必须得有名字，而lambda演算里赋予名字的唯一方式就是传递参数。像lisp那样define可不行啊。只能这样绕个圈子：

(\f.\x.
    (if  (= x 1)
        1
        (* x (f f  (- x 1)))))

这里把函数本身作为第一个参数传递给自己，从而实现的递归。要调用这个递归函数，还得套一个let（当然，换成lambda形式）:

((\fac. (fac fac 5))
        (\f.\x.
              (if (= x 1)
                    1
                    (* x (f f (- x 1))))))

真难看！每次递归都得把自己当作参数传递一遍，很机械！机械的活不应由人类做！想下，如果将递归函数里的(f f (- x 1))换成(f (- x 1))，或许还可以接受…好，Y组合子应运而生，现在你可以这样自然地递归了：

Y (\f.\x
     (if (= x 1)
          1
          (* x (f (- x 1))))) 5

数学家在追求美感上可是不遗余力啊。不过Y是如何做到的？

想想，Y组合子又叫不动点函数。什么是不动点？x=f(x)=f(f(x))…，这个x就是不动点：不管套多少层函数调用，在不动点上的值总是相等。Y f = f (Y f)=f (f (Y f))，这个Y f就是个不动点，高阶函数的不动点。什么是组合子？很简单，可以柯里化、没有自由变量的函数就是组合子 :)

便于理解，我们给(\f.\x (if (= x 1) 1 (* x (f (- x 1)))))这个lambda一个名字fac，看看一步步的递归是怎么来的：

Y fac 3
> fac (Y fac) 3         	//transform, Y!
> 3 * ((Y fac) 2)        	//3 !=1 so recurse
> 3 * (fac (Y fac) 2)    	//Y transform again
> 3 * (2 * ((Y fac) 1))       //2 !=1 so recurse
> 3 * (2 * (fac (Y fac) 1))   	//Y transform again
> 3 * (2 * 1)             	//1=1, so recursion ends.
> 6

就是这样了。里面有柯里化，也有惰性求值（缺一不可！）。一环套一环，然后就递归了。

Y组合子的定义：Y = \y. (\x.y (x x)) (\x.y (x x))，天知道大神（大神的名字叫做Haskell Curry! -v-）是怎么想出来的 =v=

不妨自己在纸上推倒一下(也只能在纸上推倒，这东西在实际的编程中貌似是没有应用的 :D)

9 Responses to “理解Y组合子”

Feed for this Entry Trackback Address
  • xpycc
    2009年09月19日 at 7:32 下午

    这玩意儿从初中到现在，一直都没时间看 = =…

    回复回复
  • ssword
    2009年09月19日 at 8:23 下午

    @xpycc 我也就是粗略看了下，感觉不是很难理解（如果没理解错的话），呵呵

    回复回复
  • xpycc
    2009年09月19日 at 8:56 下午

    难道是被 pongba 搞复杂了？

    回复回复
  • TheKingOfDoubleCat
    2009年09月19日 at 9:43 下午

    牛B得都没样子了。。。。。。哎

    回复回复
  • ssword
    2009年09月19日 at 9:58 下午

    @TheKingOfDoubleCat 操…您就没回复过别的

    回复回复
  • FTS
    2009年09月20日 at 1:01 下午

    很“数学”的东西?

    回复回复
  • ssword
    2009年09月20日 at 4:04 下午

    @FTS
    也不是很数学吧..不过倒确实是数学家发明的。那时候貌似还没有高级语言，所以说不管lambda演算还是Y组合子都不过是一种形式上的“记法”。像现在高级语言里的递归就不用绕这弯子了：

    int fac(int n){
    if (n==1)
       return 1;
    else
       return n*fac(n-1);
}
    回复回复
  • PeterGhostWolf
    2009年09月22日 at 11:02 下午

    我记得发明Y Combinator的人叫作Haskell……..
    说来我在Scheme里N久前实现的Y组合子就没有成功运行过…无论是Lazy还是应用序…有空去调一下好了…
    实际上这不止是绕弯,而是另外一种思想的表示.

    回复回复
  • ssword
    2009年09月26日 at 4:24 下午

    @PeterGhostWolf
    只知道haskell是组合子逻辑的发明人，刚刚查了下Y组合子果然是haskell发明的，呵呵。

    感觉“绕弯”，是觉得这并不是数学里的递归。至于Y组合子在组合子逻辑中的地位就不大了解了，以后再看看。

    低估了Y组合子实现的难度。在haskell里想当然地写了一个
    y = \y -> (\x -> y (x x)) (\x -> y (x x))
    结果haskell提示不可以有循环类型声明，在网上搜了下，觉得haskell的实现不大好看，要绕点弯子才能实现。就用ruby写了一个极为猥琐的实现，orz

    class Proc
    def -(x)
        self.call(x)
    end
    def _
        self.call
    end
end
 
 
y=lambda{|f|
    (lambda{|z| f-(lambda{z-z}) }.call(
    lambda{|x| f-(lambda{x-x}) }))
}
 
fac_=lambda{|f| lambda{|n|
    if (n._==0)
        lambda{ 1 }
    else
        lambda{n._*(f._-lambda{n._-1})._}
    end}}
 
#puts(((y-fac_)-lambda{1})._)
#puts((fac_-lambda{|x|lambda{2}}-lambda{1})._)
test_f=y-fac_
1.upto(1000) {|i|
    puts (test_f-(lambda{i}))._
    sleep 0.2
}
    回复回复

Leave a Reply