Wednesday, 22 April 2009
 Understanding the Y Combinator

理解Y组合子

原文链接：http://www.fatvat.co.uk/2009/04/understanding-y-combinator.html

 

Like monads, understanding the Y Combinator is a rite of passage for the aspiring functional programmer. So here's my take on it, using Clojure.
A fixed point combinator is a function g which produces such a fixed point p for any function f.
像单子一样，理解Y组合子是任何有雄心的函数式程序员的必经之路。在此我们将使用Clojure呈现它。
不动点组合子是对任意函数f生成一个不动点P的函数g

 g(f)=p
 f(p)=p



Why is this important or interesting for a programming language? It's important because it allows you to describe recursion in terms of rewrites, rather than computation steps. This allows for anonymous recursive functions.
为何这对于一门编程语言来说如此重要或有趣？之所以重要，是因为它允许使用重写代替计算步骤来描述递归。这将允许匿名递归函数。

So how do we write the Y combinator in Clojure? Taking the lambda-calculus definition and switching the word lambda for fn, gives us this incomprehensible mess!
如何使用Clojure语言编写Y组合子？首先用Lambda算子给出定义，然后将关键字lambda换为fn，我们得到了下面这坨乱七八糟的东西：

(defn Y [r]
 ((fn [f] (f f))
 (fn [f]
 (r (fn [x] ((f f) x))))))


But what does it actually mean? Probably the best way to understand is with a real example and to do that, we need a recursive function. Given that everyone else uses factorial, we'll use a simpler recursive function that sums up a sequence.
它的实际意义是什么呢？可能理解它的最佳途径是接触一个实际的例子，我们需要一个递归函数。有人用阶乘描述它，而我们将使用更简单的递归函数--对一个列表求和。

(defn sum-seq [x]
 (if (empty? x)
 0
 (+ (first x) (sum-seq (rest x)))))
 


In the definition above, we've written the function with explicit recursion. We'll use the Y combinator to get rid of that!
在上面的定义中，我们编写了一个显式的递归程序。我们将使用Y组合子清除它。



The first step is to rethink the function in terms of a series of functions. Our goal is to create a way of expressing this computation as a series of function calls. We want to write a function that given a function to compute the sum of a sequence, gives us the next function to compute the sum of a sequence.
首先，将这个函数想象成一系列函数中的一个。我们的目标是找到一个方法，将这个计算展开为一系列函数调用。我们要编写一个返回另一个函数的函数，用返回的函数计算对序列求和。


(defn sum-seq-fn-gen [func]
 (fn [s]
 (if (empty? s)
 0
 (+ (first s) (func (rest s))))))



So now we have such a function. We can already use it:
我们现在已经得到了这个函数。可以使用它了。

 user> ((sum-seq-fn-gen nil) [])
 0

 user> ((sum-seq-fn-gen (sum-seq-fn-generator nil)) [9])
 9

 user> ((sum-seq-fn-gen (sum-seq-fn-gen (sum-seq-fn-gen nil))) [1 9])
 10


It's not that useful, as at the moment we'd have to type in an awful lot of characters to sum a large list. What we really want is some way of calculating the fixed point of such a function. Thankfully we already have that, thanks to the Y combinator.
并不是很实用，此刻在对一个大点的列表求和时我们必须输入一串长得恶心的字符。我们真正需要的是通过某种途径计算这个函数的不动点。谢天谢地，我们已经找到了它，感谢Y组合子。

 user> ((Y sum-seq-fn-gen) [1 2 3 4 5])
 15

 user> ((Y sum-seq-fn-gen) (range 0 1000))
 499500


So the Y Combinator has given us what we need. Given a function and an input, find the fixed point. Note that there is no explicit recursion going on. sum-seq-fn-gen could be an anonymous function.
这样，Y组合子给了我们所需要的。提供了一个函数和一个输入，找到不动点。并且已经不再使用显示的递归了。

sum-seq-fn-gen 可以替换为一个匿名函数。

 user> ((Y 
 (fn [func]
 (fn [s] 
 (if (empty? s)
 0
 (+ (first s) (func (rest s))))))) [1 2 3 4 5])
 15



The best way to understand the Y combinator is to see how it's used and then run through the fun exercise of expanding it and seeing what happens. I found the links below useful:
理解Y组合子的最好的途径是了解它的用途以及展开以上练习中的函数，观察发生了什么。下面的链接很有用帮助：


Sketchy Lisp - derivation of Y Combinator

Clojure April 1.0

Y Combinator in Arc and Java

【本文翻译仅为外语学习及阅读目的，原文作者个人观点与译者及译言网无关】