?一 Y-Combinator
Y組合子是Lambda演算的一部分，也是函數(shù)式編程的理論基礎(chǔ)。它是一種方法/技巧，在沒有賦值語句的前提下定義遞歸的匿名函數(shù)。即僅僅通過Lambda表達(dá)式這個最基本的“原子”實(shí)現(xiàn)循環(huán)/迭代，頗有道生一、一生二、二生三、三生萬物的感覺。
1 從遞歸的階乘函數(shù)開始
先不考慮效率等其他因素，寫一個最簡單的遞歸階乘函數(shù)。此處采用Scheme，你可以選擇自己熟悉的編程語言跟著我一步一步實(shí)現(xiàn)Y-Combinator版的階乘函數(shù)。
(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 綁定函數(shù)名
想要遞歸地調(diào)用一個函數(shù)，就必須給這個函數(shù)取一個名字。匿名函數(shù)想要實(shí)現(xiàn)遞歸，就得取一個臨時的名字。所謂臨時，指這個名字只在此函數(shù)體內(nèi)有效，函數(shù)執(zhí)行完成后，這個名字就伴隨函數(shù)一起消失。為解決這個問題，第一篇文章中[1]強(qiáng)制規(guī)定匿名函數(shù)有一個隱藏的名字this指向自己，這導(dǎo)致this這個變量名被強(qiáng)行占用，并不優(yōu)雅，因此第二篇文章[2]借鑒Clojure的方法，允許自定義一個名字。
但在Lambda演算中，只有最普通的Lambda，沒有賦值語句，如何綁定一個名字呢?答案是使用Lambda的參數(shù)列表!
(lambda (factorial)
(lambda (n)
(if (zero? n)
1
(* n (factorial (- n 1))))))
3 生成階乘函數(shù)的函數(shù)
雖然通過參數(shù)列表，即使用閉包技術(shù)給匿名函數(shù)取了一個名字，但此函數(shù)并不是我們想要的階乘函數(shù)，而是階乘函數(shù)的元函數(shù)(meta-factorial)，即生成階乘函數(shù)的函數(shù)。因此需要執(zhí)行這個元函數(shù)，獲得想要的階乘函數(shù)：
((lambda (factorial)
(lambda (n)
(if (zero? n)
1
(* n (factorial (- n 1))))))
xxx)
此時又出現(xiàn)另一個問題：實(shí)參xxx，即形參factorial該取什么值?從定義來看，factorial就是函數(shù)自身，既然是“自身”，首先想到的就是復(fù)制一份一模一樣的代碼：
((lambda (factorial)
(lambda (n)
(if (zero? n)
1
(* n (factorial (- n 1))))))
(lambda (factorial)
(lambda (n)
(if (zero? n)
1
(* n (factorial (- n 1)))))))
看起來已經(jīng)把自己傳遞給了自己，但馬上發(fā)現(xiàn) (factorial (- n 1)) 會失敗，因?yàn)榇藭r的 factorial 不是一個階乘函數(shù)，而是一個包含階乘函數(shù)的函數(shù)，即要獲取包含在內(nèi)部的函數(shù)，因此調(diào)用方式要改成 ((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就能清晰地看出它是階乘的元函數(shù)，而不是階乘函數(shù)本身。
4 去除重復(fù)
以上代碼已經(jīng)實(shí)現(xiàn)了lambda的自我調(diào)用，但其中包含重復(fù)的代碼，meta-factorial即做函數(shù)又做參數(shù)，即 (meta meta) ：
((lambda (meta)
(meta meta))
(lambda (meta-factorial)
(lambda (n)
(if (zero? n)
1
(* n ((meta-factorial meta-factorial) (- n 1)))))))
5 提取階乘函數(shù)
因?yàn)槲覀兿胍氖请A乘函數(shù)，所以用factorial取代 (meta-factorial meta-factorial) ，方法同樣是使用參數(shù)列表命名：
((lambda (meta)
(meta meta))
(lambda (meta-factorial)
((lambda (factorial)
(lambda (n)
(if (zero? n)
1
(* n (factorial (- n 1))))))
(meta-factorial meta-factorial))))
這段代碼還不能正常運(yùn)行，因?yàn)镾cheme以及其他主流的編程語言實(shí)現(xiàn)都采用“應(yīng)用序”，即執(zhí)行函數(shù)時先計(jì)算參數(shù)的值，因此 (meta-factorial meta-factorial) 原來是在求階乘的過程中才被執(zhí)行，現(xiàn)在提取出來后執(zhí)行的時間被提前，于是陷入無限循環(huán)。解決方法是把它包裝在Lambda中(你學(xué)到了Lambda的另一個用處：延遲執(zhí)行)。
((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行正是最初定義的匿名遞歸階乘函數(shù)，我們終于得到了階乘函數(shù)本身!
6 形成模式
如果把其中的階乘函數(shù)作為一個整體提取出來，那就是得到一種“模式”，即能生成任意匿名遞歸函數(shù)的模式：
((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組合子，我們就能定義任意的匿名遞歸函數(shù)。前文中定義的是遞歸求階乘，再定義一個遞歸求斐波那契數(shù)：
(y-combinator
(lambda (fib)
(lambda (n)
(if (< n 3)
1
(+ (fib (- n 1))
(fib (- n 2)))))))
二 10種實(shí)現(xiàn)
下面用10種不同的編程語言實(shí)現(xiàn)Y組合子，以及Y版的遞歸階乘函數(shù)。實(shí)際開發(fā)中可能不會用上這樣的技巧，但這些代碼分別展示了這10種語言的諸多語法特性，能幫助你了解如何在這些語言中實(shí)現(xiàn)以下功能：
如何定義匿名函數(shù);
如何就地調(diào)用一個匿名函數(shù);
如何將函數(shù)作為參數(shù)傳遞給其他函數(shù);
如何定義參數(shù)數(shù)目不定的函數(shù);
如何把函數(shù)作為值返回;
如何將數(shù)組里的元素平坦開來傳遞給函數(shù);
三元表達(dá)式的使用方法。
這10種編程語言，有Python、PHP、Perl、Ruby等大家耳熟能詳?shù)哪_本語言，估計(jì)最讓大家驚訝的應(yīng)該是其中有Java!
1 Scheme
我始終覺得Scheme版是這么多種實(shí)現(xiàn)中最優(yōu)雅的!它沒有“刻意”的簡潔，讀起來很自然。
(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
其實(shí)Clojure不需要借助Y-Combinator就能實(shí)現(xiàn)匿名遞歸函數(shù)，它的lambda——fn——支持傳遞一個函數(shù)名，為這個臨時函數(shù)命名。也許Clojure的fn不應(yīng)該叫匿名函數(shù)，應(yīng)該叫臨時函數(shù)更貼切。
同樣是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版其實(shí)差不多，只不過Common Lisp屬于Lisp-2，即函數(shù)命名空間與變量命名空間不同，因此調(diào)用匿名函數(shù)時需要額外的funcall。我個人不喜歡這個額外的調(diào)用，覺得它是冗余信息，位置信息已經(jīng)包含了角色信息，就像命令行的第一個參數(shù)永遠(yuǎn)是命令。
(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那兒借鑒了許多，包括它的缺點(diǎn)。和Common Lisp一樣，Ruby中執(zhí)行一個匿名函數(shù)也需要額外的“.call”，或者使用中括號“[]”而不是和普通函數(shù)一樣的小括號“()”，總之在Ruby中匿名函數(shù)與普通函數(shù)不一樣!還有繁雜的符號也影響我在Ruby中使用匿名函數(shù)的心情，因此我會把Ruby看作語法更靈活、更簡潔的Java，而不會考慮寫函數(shù)式風(fēng)格的代碼。
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中匿名函數(shù)的使用方式與普通函數(shù)一樣，就這段代碼而言，Python之于Ruby就像Scheme之于Common Lisp。但Python對Lambda的支持簡直弱爆了，函數(shù)體只允許有一條語句!我決定我的工具箱中用Python取代C語言，雖然Python對匿名函數(shù)的支持只比C語言好一點(diǎn)點(diǎn)。
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函數(shù)不能聲明參數(shù)的抱怨更甚于繁雜的符號!
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);假設(shè)Perl能像其他語言一樣聲明參數(shù)列表，代碼會更簡潔直觀：
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等關(guān)鍵字總是刺痛我的神經(jīng)：
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有相同的毛病，最讓我意外的是它沒有三元運(yùn)算符!不過沒有使用花括號讓代碼看起來清爽不少~
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還多。
<?php
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表達(dá)式，而是匿名類!匿名函數(shù)的意義是把代碼塊作為參數(shù)傳遞，這正是匿名類所做得事情。
package me.zzp.fn;
public class YCombinator {
public interface Lambda<E> {
E call(Object... args);
}
public static Lambda<Lambda> yCombinator(final Lambda<Lambda> f) {
return new Lambda<Lambda>() {
@Override
public Lambda call(Object... args) {
final Lambda<Lambda> u = (Lambda<Lambda>) args[0];
return u.call(u);
}
}.call(new Lambda<Lambda>() {
@Override
public Lambda call(Object... args) {
final Lambda<Lambda> x = (Lambda<Lambda>) args[0];
return f.call(new Lambda<Object>() {
@Override
public Object call(Object... args) {
return x.call(x).call(args);
}
});
}
});
}
public static void main(String[] args) {
Lambda<Lambda> y = yCombinator(new Lambda<Lambda>() {
@Override
public Lambda call(Object... args) {
final Lambda<Integer> factorial = (Lambda<Integer>) args[0];
return new Lambda<Integer>() {
@Override
public Integer call(Object... args) {
Integer n = Integer.parseInt(args[0].toString());
if (n < 2) {
return Integer.valueOf(1);
} else {
return n * factorial.call(n - 1);
}
}
};
}
});
System.out.println(y.call(10));
}
}
相關(guān)鏈接
[1]http://zzp.me/2011-08-05/recursive-lambda/
[2]http://zzp.me/2012-08-04/clojure-style-lambda-in-common-lisp/
