the Y Combinator

December 20, 2007 – 7:33 pm

今天看到 A Use of the Y Combinator in Ruby 这篇文章,却被他的代码搞晕了,半天看不明白,于是只好另辟蹊径,不看他的代码,却自己来写一下,如果我写出来的代码和他一样,那自然就明白了,如果不一样,也好对比一番,相信也更容易理解了。

这里要解决的问题大致就是“匿名递归函数”的问题。递归函数大家都知道了,例如经典的阶乘函数:

1
2
3
4
5
6
7
def fact(n)
  if n == 0
    1
  else
    n*fact(n-1)
  end
end

匿名函数也没啥,在许多语言里,函数就和普通的值没有什么区别,不一定非要有一个名字,例如 lambda 就可以创建一个匿名函数:

func = lambda { puts "hello" }

那“匿名递归函数”又是什么呢?首先它是匿名的,哦,那么用 lambda 好了,其次它是递归的,这也好办,自己调用自己嘛。问题就出在这“自己”上!看那个阶乘函数代码的第五行 n*fact(n-1) ,原来函数有 fact 这个名字,可以直接调用,现在匿名了,如何调用这个“自己”呢? thisself ?可惜都不是!必须要有一个变量来引用到这个“自己”才行,如果没有一个全局(或在某个作用域里)的名字,那么至少要作为一个参数。用 Y combinator 正好可以解决这个问题,于是程序可以这样写了:

1
2
3
4
5
6
7
8
9
fact = y_comb do |me|
  lambda { |x|
    if x == 0
      1
    else
      x*me.call(x-1)
    end
  }
end

这里“自己”(也就是第二行的那个 lambda 产生的匿名函数)被作为参数 me 传递进来。这个 y_comb 究竟是如何做的呢?你可以自己尝试实现一下,如果实在迫不及待或者一时想不出来,就跟我一起来探索神奇的 Y combinator 吧!

y_comb 初看一般都会有些绕,我尝试用三种不同的方法来实现它,希望你能找到一种自己觉得容易理解的:


lambda 演算

Y combinator 是由 Haskell B. Curry (这个人的名字很牛是吧? :D ) 所发现的一个在 untyped lambda calculas 中的一个 Fixed point combinator (或 Fixed point operator) 。Fixed point 应该很熟悉了,一个函数 f 的 Fixed point x 应当满足 f(x) == x 。而一个 Fixed point combinator g 能干什么呢?它能够生成 f 的 Fixed point ,换句话说, g(f) 就是 f 的一个 Fixed point ,亦即:f(g(f)) == g(f)

在 lambda 演算中 Y combinator 就长这个样子:

y.png

这里直接引用了 lambda 演算的语法,不要晕,语法其实很简单。首先

lambda.png

表示一个函数,参数是 y ,而函数体是 body (这样只能表示一个参数,多个参数怎么办?用 Curry !)。其次:

call.png

表示以参数 x 去调用函数 f (难道 Haskell 的那种函数调用的语法就是从这里来的? ;) ) 。表达式里的括号仅仅是起到修改优先级的作用,与 Lisp 里的括号没有什么关系。

lambda 演算有几条规则,诸如 “beta 归约”、“alpha 变换”等等,在数学上自然是要严格定义的,但是从另一个角度来看却也都是很 trivial 的东西(还记得我在这篇日志中提到的 Joel 修的 Dynamic Logic 的第一堂课证明的 f := not f 吗? :p ),就不列举出来了,我们直接来看演算过程,一看就明白!这是将 Y combinator 应用于函数 g 的过程:

calculus.png

最后推导得到 g (Y g) (也就是说 Y(g) == g(Y(g)) 了)。求得一个函数的不动点对于构造匿名递归函数有什么帮助呢?再来看看下面的演算,不妨定义一个函数 F

f.png

这和我们前面用 y_comb 做的那个类似,如果有一个表示“自己”的东西作为参数 f 传递进来,就可以被调用以实现递归了。究竟如何传递这个“自己”进来,还要看下面的演算:

fact.png

注意其中的 (Y F) ,这个就是我们要的 fact 函数,如果用 fact 这个名字替换进去,结果就明了了:

result.png

嗯,理论准备完毕,就要开始写代码了,直接翻译成 Ruby 代码:

1
2
3
4
5
6
7
def y_comb(f)
  lambda { |x|
      f.call(x.call(x))
  }.call(lambda { |x|
             f.call(x.call(x))
         })
end

对照着上面的演算来看,这里的 f 参数对应到上面对应的 Ffact(n) 就正好等价于 (Y(F))(n)(y_comb(f))(n) 了,这样我们前面的那段定义匿名递归的 fact代码就可以跑起来了!

赶快去试试!是不是 stack overflow 了? :p 问题出在我们的 Y combinator 的实现上。可是我们完全是按照 lambda 演算的式子照搬过来的啊?怎么会出错呢?错就正好错在照搬了!仔细看看 y_comb 的实现,会发现那根本是一个无休止的递归调用,当然会 stack overflow 了!

可是为什么在 lambda 演算的时候却推导出正确的结果了?那是因为演算是在一个 call by name 的求值策略下进行的。这属于 non-strict evaluation 的一种,而 Ruby 却属于 strict evaluation ,刚好相反。出现无穷递归的地方其实就是(y_comb代码)的第三行和第五行,我们希望能将它的执行拖延一下:

lazy(f.call(x.call(x)))

可惜 Ruby 并没有内置 lazy 的支持,不过这也好办,我们可以轻松用 lambda 模拟出一个 lazy 来:

class Object
  alias lazy lambda
end
class Proc
  alias force call
end

于是 y_comb 就写成这样:

1
2
3
4
5
6
7
def y_comb(f)
  lambda { |x|
      lazy{f.call(x.call(x))}
  }.call(lambda { |x|
             lazy{f.call(x.call(x))}
         })
end

只是这样却有一点不爽,因为 lazy 是手工模拟出来的,不支持自动按需求值,所以要用的时候还需要手工调用 force ,如下所示 :

1
2
3
4
5
6
7
8
9
fact = Kernel.gen_recursive do |me|
  lambda { |x|
    if x == 0
      1
    else
      x*me.force.call(x-1)
    end
  }
end

这也好办!反正 lazy 也只是一个函数嘛,我们干脆一不做二不休,让它直接伪装成被“lazy 掉”的那个函数!换句话说,让它把所有的参数转发给内部的那个函数,让调用它与调用内部的那个函数从外部看不出任何区别来:

1
2
3
4
5
6
7
8
9
10
11
def y_comb(f)
  lambda { |x|
    lambda { |*args|
      f.call(x.call(x)).call(*args)
    }
  }.call(lambda { |x|
           lambda { |*args|
             f.call(x.call(x)).call(*args)
           }
         })
end

这样我们就可以使用原来的代码来定义 fact 而不必手动 force 了。

自己的代码写好了,再去和 Charles Duan 的代码对比,大同小异! :)


用 Y 来实现 Y

前面的实现多少有些没有意思,虽然 lambda 演算证明了 Y combinator 的正确性,但是结论却是直接给出来的,没有讲如何得到这个有趣的东西的。既然 lambda 演算也看过了,下面我们就抛开 Haskell B. Curry 给的 Y combinator 的那个实现,自己在 Ruby 里从头开始推导试试。

结论仍然是一样的,我们希望实现 Y(g) = g(Y(g)) 。这虽然是结论,但是其实也可以算是定义啊:

1
2
3
def y_comb(f)
  f.call(y_comb(f))
end

按照前面讨论的,再加上 lazy 求值:

1
2
3
def y_comb(f)
  lambda { |*args| f.call(y_comb(f)).call(*args) }
end

一切万事大吉了!没想到这么简单,前面竟然费了那么多功夫!可惜这里我们犯了一个“禁忌”:y_comb 的函数体里(通过全局名字 y_comb )递归调用了它自己。虽然在 Ruby 里能顺利通过,但弱是在本身没有这样命名递归函数支持的语言里,要通过 Y combinator 来做的话,这样的代码就不能存在了。

这样我们陷入了一个死循环:要实现递归,我们需要一个 Y combinator ;要实现 Y combinator ,我们又需要递归支持。为了让死循环停下来,我们干脆假设在实现 y_comb 的时候有一个预先实现好了的神奇的 Y combinator Y 可以用,先用 Yy_comb 做出来,再来处理 Y 。看似有些不可靠,其实不然:y_comb 是通用的,而 Y 则只需要针对 y_comb 有效就可以了,特殊情况总是会变得容易一些!

如果有 Y 的话,y_comb 就很容易了:

1
2
3
4
5
6
y_comb = Y(lambda do |me|
                    lambda do |f|
                      lambda { |*args| f.call(me.call(f)).call(*args) }
                    end
                  end)
define_method :y_comb, &y_comb

现在问题落在了 Y 上,我们不能用同样的方法,否则就停不下来了。那怎么办呢?暴力解决,手工展开!实用 Y 就是希望能传递一个 me 进去:

1
2
3
4
5
lambda { |me|
  lambda do |f|
    lambda { |*args| f.call(me.call(f)).call(*args) }
  end
}.call(??)

这里的 ?? 就是要传递的 me ,也就是第二行的那个 lambda 函数体。再手抄一份好了:

1
2
3
4
5
6
7
lambda { |me|
  lambda do |f|
    lambda { |*args| f.call(me.call(f)).call(*args) }
  end
}.call(lambda do |f|
         lambda { |*args| f.call(me.call(f)).call(*args) }
       end)

唉,可惜事情还是没有那么简单,这次在第六行的时候用到了 me ,但是这里却是没有 me 存在的。如果能像第一行那样把 me 传递进来就好了:

1
2
3
4
5
6
7
8
9
lambda { |me|
  lambda do |f|
    lambda { |*args| f.call(me.call(f)).call(*args) }
  end
}.call(lambda { |me|
         lambda do |f|
           lambda { |*args| f.call(me.call(f)).call(*args) }
         end
       })

但是此时传递进来的 me 并不是第二行的那个 lambda 函数,而是第一行那个。有什么区别呢?这个 me 需要调用两次才能得到最终的返回值 lambda { |*args| ... } ,于是修改 me.call(f)me.call(me).call(f)

1
2
3
4
5
6
7
8
9
10
y_comb = lambda { |me|
  lambda do |f|
    lambda { |*args| f.call(me.call(me).call(f)).call(*args) }
  end
}.call(lambda { |me|
         lambda do |f|
           lambda { |*args| f.call(me.call(me).call(f)).call(*args) }
         end
       })
define_method :y_comb, &y_comb

信不信由你,这一堆乱七八糟的 lambdacall 就是一个 Y combinator 。稍微整理一下,交换一下 mef 的层次,就能得到和前面一样的代码:

1
2
3
4
5
6
7
def y_comb(f)
  lambda { |me|
    lambda { |*args| f.call(me.call(me)).call(*args) }
  }.call(lambda { |me|
           lambda { |*args| f.call(me.call(me)).call(*args) }
         })
end


从特殊到一般

前面一个推导过程推导出了一个复杂的结果,还需要化简一下才能得到满意的答案,这里我们再来看看从一个特殊的例子归纳出一般情况的过程。还是计算阶乘的例子吧,一开始,我们需要递归调用 fact 但是却没有这个名字可以引用,于是我们将他作为参数 me 传递进来:

1
2
3
lambda { |me, n|
  n.zero? and 1 or n*me.call(me, n-1)
}

于是计算 5 的阶乘可以这样来:

1
2
3
4
fact = lambda { |me, n|
  n.zero? and 1 or n*me.call(me, n-1)
}
fact.call(fact, 5)

me 和原来的参数混淆在一起了,不舒服, Currying 一下:

1
2
3
4
fact = lambda { |me|
  lambda { |n| n.zero? and 1 or n*me.call(me).call(n-1) }
}
fact.call(fact).call(5)

但是在实现 fact 的代码中有一个 me.call(me) ,这会让人感到莫名奇妙,因为我们最终是要抽象出一个通用的 Y combinator 来,所有把那部分提取出来(作为 inner_fact ):

1
2
3
4
5
6
7
8
9
10
fact = lambda { |me|
  lambda { |n|
    inner_fact = lambda { |f|
      lambda { |n| n.zero? and 1 or n*f.call(n-1) }
    }
    inner_me = me.call(me)
    inner_fact.call(inner_me).call(n)
  }
}
fact.call(fact).call(5)

经过我们的努力,inner_fact 现在不以来于环境中的任何变量了,于是我们把它单独提取出来:

1
2
3
4
5
6
7
8
9
10
inner_fact = lambda { |f|
  lambda { |n| n.zero? and 1 or n*f.call(n-1) }
}
fact = lambda { |me|
  lambda { |n|
    inner_me = me.call(me)
    inner_fact.call(inner_me).call(n)
  }
}
fact.call(fact).call(5)

再看看构造 fact 的那段代码,已经与阶乘没有任何关系了,仅仅需要一个整体的 inner_fact 就可以构造出来,因此它已经可以作为通用的 Y combinator 被包装起来了:

1
2
3
4
5
6
7
8
9
def y_comb(inner_fact)
  fact = lambda { |me|
    lambda { |n|
      inner_me = me.call(me)
      inner_fact.call(inner_me).call(n)
    }
  }
  fact.call(fact).call(5)
end

变量名需要改一改了,再把硬编码的 call(5) 去掉就可以得到我们想要的递归函数:

1
2
3
4
5
6
7
8
9
def y_comb(f)
  g = lambda { |me|
    lambda { |n|
      inner_me = me.call(me)
      f.call(inner_me).call(n)
    }
  }
  g.call(g)
end

把局部变量的形式变得更加 functional ,再把单参数的 n 换成任意参数的 *args

1
2
3
4
5
6
7
8
9
def y_comb(f)
  lambda { |g|
    g.call(g)
  }.call(lambda { |me|
           lambda { |*args|
             f.call(me.call(me)).call(*args)
           }
         })
end

这就是一个通用的 Y combinator 啦!我想这种方法应该更容易理解一些,虽然最后都转换成了 lambda 调用的形式,但是中间推导使用了局部变量的形式,通常看起来更熟悉一点。 :)

好了,三种方法都说完了,可是却又不禁要问: Y combinator 在实际编程中有应用的地方吗?对于匿名递归函数来说,用处还是有的,比如实现 Charles Duan 提到的 autovivifying hash ,然而如果把条件放宽松一些:只要不在全局(或当前)名字空间中创建函数名就算匿名的话,可以很容易地用 closure 来实现:

1
2
3
4
5
6
7
8
9
fact = lambda {
  recursive = lambda { |n|
    if n == 0
      1
    else
      n*recursive.call(n-1)
    end
  }
}.call

即使对于 autovivifying hash ,也有一个更简洁明了的实现:

1
2
3
4
5
class AVHash < Hash
    def initialize
        super { |h,k| h[k] = AVHash.new }
    end
end

Reginald Braithwaite 甚至还有一篇文章提到 Y combinator (在 Ruby 或其他类似的语言中)没有什么实用价值。不过在 Ruby 中没有应用的地方是因为 Ruby 并不是一门纯粹的函数式编程语言,并不代表在其他地方没有实用价值。Fixed point combinator 在理论中自然是处于非常总要的地位,而且除了 Y combinator 之外还有许多其他的 Fixed point combinator ,感兴趣的话可以参加 Wikipedia 上的相关条目(我在文中都做了链接了)。

而且 Reginald Braithwaite 的那篇文章虽然说没有看到 Y combinator 的用处,但是主旨却是鼓励去了解的:

New ideas—by which I mean, new to you—are an important way to sharpen your saw. If for no other reason than this: the brain needs regular exercise to perform at or near its potential. Learning new things keeps you sharp, even if you don’t directly use the things you learned.

Do not dismiss impractical or weird problems. While you may not have an immediate application for the code you write to solve such problems, you are maximizing your learning when you venture outside of your usual problem space.

最后,附上本文相关的源代码。其中的 Ruby 的测试代码需要用 RSpec 来运行。

  1. 11 Responses to “the Y Combinator”

  2. ycombinator.com 是一个很有名的startup网站,那些人都是lisper :)

    By Jack on Dec 21, 2007

  3. Paul Graham ;)

    By goncha on Dec 21, 2007

  4. 嗯,那个我知道,Paul Graham 是 《On Lisp》 的作者,据说 Lisp 在近代重新复活是他的努力?好像 reddit 最初就是他用 Lisp 做的?

    By pluskid on Dec 21, 2007

  5. Paul Graham … 不喜欢那个家伙, 以为别人都是傻瓜. 这个世界不是少了lisp就不转了.

    By galilette on Dec 22, 2007

  6. 哈哈! :D

    By pluskid on Dec 22, 2007

  7. TO: galilette,

    难道只有那样才能学习Lisp么@?@
    Pluskid你要加油阿

    By Jack on Dec 23, 2007

  8. 嘿嘿, kid你可要把持住自己阿..

    不过研究标明lisp是一个地域性很强的语言, 人口密度以Boston为中心向四周呈指数衰减, 所以最重要的估计是混到Boston去, 比如MIT啥的

    By galilette on Dec 23, 2007

  9. @_@ 看不懂你们在说什么耶~~

    By pluskid on Dec 23, 2007

  10. TO: galilette

    偏执才能成精啊,Smalltalk的一些元老也是这样的

    By Goncha on Dec 25, 2007

  11. 能这么推Y的,可想脑子多乱

    By 9527 on Apr 5, 2008

  1. 1 Trackback(s)

  2. Sep 11, 2011: Path to Void » Blog Archive » 递归引发的血案

Post a Comment