简介： Y组合子是Lambda演算的一部分，也是函数式编程的实践根底。它是一种办法/技巧，在没有赋值语句的前提下定义递归的匿名函数，即仅仅通过Lambda表达式这个最根本的“原子”实现循环/迭代。本文将用10种不同的编程语言实现Y组合子，以及Y版的递归阶乘函数。
作者 | 技师
起源 | 阿里技术公众号
一 Y-Combinator
Y组合子是Lambda演算的一部分，也是函数式编程的实践根底。它是一种办法/技巧，在没有赋值语句的前提下定义递归的匿名函数。即仅仅通过Lambda表达式这个最根本的“原子”实现循环/迭代，颇有道生一、毕生二、二生三、三生万物的感觉。
1 从递归的阶乘函数开始
先不思考效率等其余因素，写一个最简略的递归阶乘函数。此处采纳Scheme，你能够抉择本人相熟的编程语言跟着我一步一步实现Y-Combinator版的阶乘函数。
(define (factorial n)
(if (zero? n)
1 (* n (factorial (- n 1)))))
Scheme中 (define (fn-name)) 是 (define fn-name (lambda)) 的简写，就像JS中，function foo() {} 等价于 var foo = function() {}。把下面的定义开展成Lambda的定义：
(define factorial
(lambda (n)
(if (zero? n) 1 (* n (factorial (- n 1))))))
2 绑定函数名
想要递归地调用一个函数，就必须给这个函数取一个名字。匿名函数想要实现递归，就得取一个长期的名字。所谓长期，指这个名字只在此函数体内无效，函数执行实现后，这个名字就随同函数一起隐没。为解决这个问题，第一篇文章中[1]强制规定匿名函数有一个暗藏的名字this指向本人，这导致this这个变量名被强行占用，并不优雅，因而第二篇文章[2]借鉴Clojure的办法，容许自定义一个名字。
但在Lambda演算中，只有最一般的Lambda，没有赋值语句，如何绑定一个名字呢？答案是应用Lambda的参数列表！
(lambda (factorial)
(lambda (n)
(if (zero? n) 1 (* n (factorial (- n 1))))))
3 生成阶乘函数的函数
尽管通过参数列表，即应用闭包技术给匿名函数取了一个名字，但此函数并不是咱们想要的阶乘函数，而是阶乘函数的元函数（meta-factorial），即生成阶乘函数的函数。因而须要执行这个元函数，取得想要的阶乘函数：
((lambda (factorial)
(lambda (n)
(if (zero? n) 1 (* n (factorial (- n 1))))))
xxx)
此时又呈现另一个问题：实参xxx，即形参factorial该取什么值？从定义来看，factorial就是函数本身，既然是“本身”，首先想到的就是复制一份截然不同的代码：
((lambda (factorial)
(lambda (n)
(if (zero? n) 1 (* n (factorial (- n 1))))))
(lambda (factorial)
(lambda (n)
(if (zero? n) 1 (* n (factorial (- n 1)))))))
看起来曾经把本人传递给了本人，但马上发现 (factorial (- n 1)) 会失败，因为此时的 factorial 不是一个阶乘函数，而是一个蕴含阶乘函数的函数，即要获取蕴含在外部的函数，因而调用形式要改成 ((meta-factorial meta-factorial) (- n 1)) ：
((lambda (meta-factorial)
(lambda (n)
(if (zero? n) 1 (* n ((meta-factorial meta-factorial) (- n 1))))))
(lambda (meta-factorial)
(lambda (n)
(if (zero? n) 1 (* n ((meta-factorial meta-factorial) (- n 1)))))))
把名字改成meta-factorial就能清晰地看出它是阶乘的元函数，而不是阶乘函数自身。
4 去除反复
以上代码曾经实现了lambda的自我调用，但其中蕴含反复的代码，meta-factorial即做函数又做参数，即 (meta meta) ：
((lambda (meta)
(meta meta))
(lambda (meta-factorial)
(lambda (n)
(if (zero? n) 1 (* n ((meta-factorial meta-factorial) (- n 1)))))))
5 提取阶乘函数
因为咱们想要的是阶乘函数，所以用factorial取代 (meta-factorial meta-factorial) ，办法同样是应用参数列表命名：
((lambda (meta)
(meta meta))
(lambda (meta-factorial)
((lambda (factorial)
(lambda (n)
(if (zero? n)
1
(* n (factorial (- n 1))))))
(meta-factorial meta-factorial))))
这段代码还不能失常运行，因为Scheme以及其余支流的编程语言实现都采纳“利用序”，即执行函数时先计算参数的值，因而 (meta-factorial meta-factorial) 原来是在求阶乘的过程中才被执行，当初提取进去后执行的工夫被提前，于是陷入有限循环。解决办法是把它包装在Lambda中（你学到了Lambda的另一个用途：提早执行）。
((lambda (meta)
(meta meta))
(lambda (meta-factorial)
((lambda (factorial)
(lambda (n)
(if (zero? n)
1
(* n (factorial (- n 1))))))
(lambda args
(apply (meta-factorial meta-factorial) args)))))
此时，代码中第4行到第8行正是最后定义的匿名递归阶乘函数，咱们终于失去了阶乘函数自身！
6 造成模式
如果把其中的阶乘函数作为一个整体提取进去，那就是失去一种“模式”，即能生成任意匿名递归函数的模式：
((lambda (fn)
((lambda (meta)
(meta meta))
(lambda (meta-fn)
(fn
(lambda args
(apply (meta-fn meta-fn) args))))))
(lambda (factorial)
(lambda (n)
(if (zero? n) 1 (* n (factorial (- n 1)))))))
Lambda演算中称这个模式为Y组合子（Y-Combinator），即：
(define (y-combinator fn)
((lambda (meta)
(meta meta))
(lambda (meta-fn)
(fn
(lambda args
(apply (meta-fn meta-fn) args))))))
有了Y组合子，咱们就能定义任意的匿名递归函数。前文中定义的是递归求阶乘，再定义一个递归求斐波那契数：
(y-combinator
(lambda (fib)
(lambda (n)
(if (< n 3)
1
(+ (fib (- n 1))
(fib (- n 2)))))))
二 10种实现
上面用10种不同的编程语言实现Y组合子，以及Y版的递归阶乘函数。理论开发中可能不会用上这样的技巧，但这些代码别离展现了这10种语言的诸多语法个性，能帮忙你理解如何在这些语言中实现以下性能：
如何定义匿名函数；
如何就地调用一个匿名函数；
如何将函数作为参数传递给其余函数；
如何定义参数数目不定的函数；
如何把函数作为值返回；
如何将数组里的元素平坦开来传递给函数；
三元表达式的应用办法。
这10种编程语言，有Python、PHP、Perl、Ruby等大家耳熟能详的脚本语言，预计最让大家诧异的应该是其中有Java！
1 Scheme
我始终感觉Scheme版是这么多种实现中最优雅的！它没有“刻意”的简洁，读起来很天然。
(define (y-combinator f)
((lambda (u)
(u u))
(lambda (x)
(f (lambda args
(apply (x x) args))))))
((y-combinator
(lambda (factorial)
(lambda (n)
(if (zero? n)
1
(* n (factorial (- n 1)))))))
10) ; => 3628800
2 Clojure
其实Clojure不须要借助Y-Combinator就能实现匿名递归函数，它的lambda——fn——反对传递一个函数名，为这个长期函数命名。兴许Clojure的fn不应该叫匿名函数，应该叫长期函数更贴切。
同样是Lisp，Clojure版本比Scheme版本更简短，却让我感觉是一种刻意的简洁。我喜爱用fn取代lambda，但用稀奇古怪的符号来缩减代码量会让代码的可读性变差（我最近如同变得不太喜爱用符号，哈哈）。
(defn y-combinator [f]
(#(% %) (fn [x] (f #(apply (x x) %&)))))
((y-combinator
(fn [factorial]
#(if (zero? %) 1 (* % (factorial (dec %))))))
10)
3 Common Lisp
Common Lisp版和Scheme版其实差不多，只不过Common Lisp属于Lisp-2，即函数命名空间与变量命名空间不同，因而调用匿名函数时须要额定的funcall。我集体不喜爱这个额定的调用，感觉它是冗余信息，地位信息曾经蕴含了角色信息，就像命令行的第一个参数永远是命令。
(defun y-combinator (f)
((lambda (u)
(funcall u u))
(lambda (x)
(funcall f (lambda (&rest args)
(apply (funcall x x) args))))))
(funcall (y-combinator
(lambda (factorial)
(lambda (n)
(if (zerop n)
1
(* n (funcall factorial (1- n)))))))
10)
4 Ruby
Ruby从Lisp那儿借鉴了许多，包含它的毛病。和Common Lisp一样，Ruby中执行一个匿名函数也须要额定的“.call”，或者应用中括号“[]”而不是和一般函数一样的小括号“()”，总之在Ruby中匿名函数与一般函数不一样！还有繁冗的符号也影响我在Ruby中应用匿名函数的情绪，因而我会把Ruby看作语法更灵便、更简洁的Java，而不会思考写函数式格调的代码。
def y_combinator(&f)
lambda {|&u| u[&u]}.call do |&x|
f[&lambda {|*a| x[&x][*a]}]
end
end
y_combinator do |&factorial|
lambda {|n| n.zero? ? 1: n*factorial[n-1]}
end[10]
5 Python
Python中匿名函数的应用形式与一般函数一样，就这段代码而言，Python之于Ruby就像Scheme之于Common Lisp。但Python对Lambda的反对几乎弱爆了，函数体只容许有一条语句！我决定我的工具箱中用Python取代C语言，尽管Python对匿名函数的反对只比C语言好一点点。
def y_combinator(f):
return (lambda u: u(u))(lambda x: f(lambda *args: x(x)(*args)))
y_combinator(lambda factorial: lambda n: 1 if n < 2 else n * factorial(n-1))(10)
6 Perl
我集体对Perl函数不能申明参数的埋怨更甚于繁冗的符号！
sub y_combinator {
my $f = shift;
sub { $_[0]->($_[0]); }->(sub {
my $x = shift;
$f->(sub { $x->($x)->(@_); });
});
}
print y_combinator(sub {
my $factorial = shift;
sub { $_[0] < 2? 1: $_[0] * $factorial->($_[0] - 1); };
})->(10);
假如Perl能像其余语言一样申明参数列表，代码会更简洁直观：
sub y_combinator($f) {
sub($u) { $u->($u); }->(sub($x) {
$f->(sub { $x->($x)->(@_); });
});
}
print y_combinator(sub($factorial) {
sub($n) { $n < 2? 1: $n * $factorial->($n – 1); };
})->(10);
7 JavaScript
JavaScript无疑是脚本语言中最风行的！但简短的function、return等关键字总是刺痛我的神经：
var y_combinator = function(fn) {
return (function(u) {
return u(u);
})(function(x) {
return fn(function() {
return x(x).apply(null, arguments);
});
});
};
y_combinator(function(factorial) {
return function(n) {
return n <= 1? 1: n * factorial(n - 1);
};
})(10);
ES6提供了 => 语法，能够更加简洁：
const y_combinator = fn => (u => u(u))(x => fn((…args) => x(x)(…args)));
y_combinator(factorial => n => n <= 1? 1: n * factorial(n – 1))(10);
8 Lua
Lua和JavaScript有雷同的故障，最让我意外的是它没有三元运算符！不过没有应用花括号让代码看起来清新不少~
function y_combinator(f)
return (function(u)
return u(u)
end)(function(x)
return f(function(...)
return x(x)(...)
end)
end)
end
print(y_combinator(function(factorial)
return function(n)
return n < 2 and 1 or n * factorial(n-1)
end
end)(10))
留神：Lua版本为5.2。5.1的语法不同，需将 x(x)(…) 换成 x(x)(unpack(arg))。
9 PHP
PHP也是JavaScript的难兄难弟，function、return……
此外，PHP版本是脚本语言中符号（$、_、()、{}）用的最多的！是的，比Perl还多。
function y_combinator($f) {
return call_user_func(function($u) {
return $u($u);
}, function($x) use ($f) {
return $f(function() use ($x) {
return call_user_func_array($x($x), func_get_args());
});
});
}
echo call_user_func(y_combinator(function($factorial) {
return function($n) use ($factorial) {
return ($n < 2)? 1: ($n * $factorial($n-1));
};
}), 10);
10 Java
最初，Java退场。我说的不是Java 8，即不是用Lambda表达式，而是匿名类！匿名函数的意义是把代码块作为参数传递，这正是匿名类所做得事件。
原文链接
本文为阿里云原创内容，未经容许不得转载。
转载请注明原文链接：关于java:10种编程语言实现Y组合子
