簡介： 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) ; => 36288002 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運算式，而是匿名類！匿名函式的意義是把代碼塊作為引數傳遞，這正是匿名類所做得事情，
原文鏈接
本文為阿里云原創內容，未經允許不得轉載，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/280306.html
標籤：AI