作者 | 技師
來源 | 阿裡技術公衆号
一 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表達式，而是匿名類！匿名函數的意義是把代碼塊作為參數傳遞，這正是匿名類所做得事情。
相關連結
[1] http://zzp.me/2011-08-05/recursive-lambda/ [2] http://zzp.me/2012-08-04/clojure-style-lambda-in-common-lisp/
免費領取電子書
《高德技術2020年刊合輯》
高德技術重磅釋出《高德技術2020年刊合輯》電子書，覆寫了大前端、算法、架構、汽車工程、品質等多個領域，以及數篇高德入選頂會論文的解讀，分享高德在智慧出行上的最佳技術實踐和總結。
掃碼加阿裡妹好友，回複“高德”擷取吧~(若掃碼無效，可直接添加alimei4、alimei5、alimei6、alimei7)