在過(guò)去的近十年的時(shí)間里，面向?qū)ο缶幊檀笮衅涞?。以至于在大學(xué)的教育里，老師也只會(huì)教給我們兩種編程模型，面向過(guò)程和面向?qū)ο蟆?/p>

孰不知，在面向?qū)ο螽a(chǎn)生之前，在面向?qū)ο笏枷氘a(chǎn)生之前，函數(shù)式編程已經(jīng)有了數(shù)十年的歷史。

那么，接下來(lái)，就讓我們回顧這個(gè)古老又現(xiàn)代的編程模型，讓我們看看究竟是什么魔力將這個(gè)概念，將這個(gè)古老的概念，在21世紀(jì)的今天再次拉入了我們的視野。

1. 什么是函數(shù)式編程

在維基百科中，已經(jīng)對(duì)函數(shù)式編程有了很詳細(xì)的介紹。

那我們就來(lái)摘取一下Wiki上對(duì)Functional Programming的定義：

In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data.

簡(jiǎn)單地翻譯一下，也就是說(shuō)函數(shù)式編程是一種編程模型，他將計(jì)算機(jī)運(yùn)算看做是數(shù)學(xué)中函數(shù)的計(jì)算，并且避免了狀態(tài)以及變量的概念。

接下來(lái)，我們就來(lái)剖析下函數(shù)式編程的一些特征。

2. 從并發(fā)說(shuō)開(kāi)來(lái)

說(shuō)來(lái)慚愧，我第一個(gè)真正接觸到函數(shù)式編程，要追溯到兩年以前的《Erlang程序設(shè)計(jì)》，我們知道Erlang是一個(gè)支持高并發(fā)，有著強(qiáng)大容錯(cuò)性的函數(shù)式編程語(yǔ)言。

因?yàn)闀r(shí)間太久了，而且一直沒(méi)有過(guò)真正地應(yīng)用，所以對(duì)Erlang也只是停留在一些感性認(rèn)識(shí)上。在我眼里，Erlang對(duì)高并發(fā)的支持體現(xiàn)在兩方面，第一，Erlang對(duì)輕量級(jí)進(jìn)程的支持(請(qǐng)注意此處進(jìn)程并不等于操作系統(tǒng)的進(jìn)程，而只是Erlang內(nèi)部的一個(gè)單位單元)，第二，就是變量的不變性。

3. 變量的不變性

在《Erlang程序設(shè)計(jì)》一書(shū)中，對(duì)變量的不變性是這樣說(shuō)的，Erlang是目前唯一變量不變性的語(yǔ)言。具體的話我記不清了，我不知道是老爺子就是這么寫的，還是譯者的問(wèn)題。我在給這本書(shū)寫書(shū)評(píng)的時(shí)候吹毛求疵地說(shuō)：

我對(duì)這句話有異議，切不說(shuō)曾經(jīng)的Lisp，再到如今的F#都對(duì)賦值操作另眼相看，低人一等。單說(shuō)如今的Java和C#，提供的final和readonly一樣可以支持變量的不變性，而這個(gè)唯一未免顯得有點(diǎn)太孤傲了些。

讓我們先來(lái)看兩段程序，首先是我們常見(jiàn)的一種包含賦值的程序：

class Account:   
    def __init__(self,balance):   
        self.balance = balance   
    def desposit(self,amount):   
        selfself.balance = self.balance + amount   
        return self.balance   
    def despositTwice(self):   
        selfself.balance = self.balance * 2   
        return self.balance  
if __name__ == '__main__':   
    account = Account(100)   
    print(account.desposit(10))   
    print(account.despositTwice())  
  

這段程序本身是沒(méi)有問(wèn)題的，但是我們考慮這樣一種情況，現(xiàn)在有多個(gè)進(jìn)程在同時(shí)跑這一個(gè)程序，那么程序就會(huì)被先desposit 還是先 despositTwice所影響。

但是如果我們采用這樣的方式：

def makeAccount(balance):   
    global desposit   
    global despositTwice   
    def desposit(amount):   
        result = balance + amount   
        return result   
    def despositTwice():   
        result = balance * 2   
        return result   
    def dispatch(method):   
        return eval(method)   
    return dispatch  
if __name__ == '__main__':   
    handler = makeAccount(100)   
    print(handler('desposit')(10))   
    print(handler('despositTwice')())  
  

這時(shí)我們就會(huì)發(fā)現(xiàn)，無(wú)論多少個(gè)進(jìn)程在跑，因?yàn)槲覀儽旧頉](méi)有賦值操作，所以都不會(huì)影響到我們的最終結(jié)果。

但是這樣也像大家看到的一樣，采用這樣的方式?jīng)]有辦法保持狀態(tài)。

這也就是我們?cè)谥案拍钪锌吹降臒o(wú)狀態(tài)性。

4. 再看函數(shù)式編程的崛起

既然已經(jīng)看完了函數(shù)式編程的基本特征，那就讓我們來(lái)想想數(shù)十年后函數(shù)式編程再次崛起的幕后原因。

一直以來(lái)，作為函數(shù)式編程代表的Lisp，還是Haskell，更多地都是在大學(xué)中，在實(shí)驗(yàn)室中應(yīng)用，而很少真的應(yīng)用到真實(shí)的生產(chǎn)環(huán)境。

先讓我們?cè)賮?lái)回顧一下偉大的摩爾定律：

1、集成電路芯片上所集成的電路的數(shù)目，每隔18個(gè)月就翻一番。

2、微處理器的性能每隔18個(gè)月提高一倍，而價(jià)格下降一半。

3、用一個(gè)美元所能買到的電腦性能，每隔18個(gè)月翻兩番。

一如摩爾的預(yù)測(cè)，整個(gè)信息產(chǎn)業(yè)就這樣飛速地向前發(fā)展著，但是在近年，我們卻可以發(fā)現(xiàn)摩爾定律逐漸地失效了，芯片上元件的尺寸是不可能無(wú)限地縮小的，這就意味著芯片上所能集成的電子元件的數(shù)量一定會(huì)在某個(gè)時(shí)刻達(dá)到一個(gè)極限。那么當(dāng)技術(shù)達(dá)到這個(gè)極限時(shí)，我們又該如何適應(yīng)日益增長(zhǎng)的計(jì)算需求，電子元件廠商給出了答案，就是多核。

多核并行程序設(shè)計(jì)就這樣被推到了前線，而命令式編程天生的缺陷卻使并行編程模型變得非常復(fù)雜，無(wú)論是信號(hào)量，還是鎖的概念，都使程序員不堪其重。

就這樣，函數(shù)式編程終于在數(shù)十年后，終于走出實(shí)驗(yàn)室，來(lái)到了真實(shí)的生產(chǎn)環(huán)境中，無(wú)論是冷門的Haskell，Erlang，還是Scala，F(xiàn)#，都是函數(shù)式編程成功的典型。

5. 函數(shù)式編程的第一型

我們知道，對(duì)象是面向?qū)ο蟮牡谝恍?，那么函?shù)式編程也是一樣，函數(shù)是函數(shù)式編程的第一型。

我們?cè)诤瘮?shù)式編程中努力用函數(shù)來(lái)表達(dá)所有的概念，完成所有的操作。

在面向?qū)ο缶幊讨校覀儼褜?duì)象傳來(lái)傳去，那在函數(shù)式編程中，我們要做的是把函數(shù)傳來(lái)傳去，而這個(gè)，說(shuō)成術(shù)語(yǔ)，我們把他叫做高階函數(shù)。

那我們就來(lái)看一個(gè)高階函數(shù)的應(yīng)用，熟悉js的同學(xué)應(yīng)該對(duì)下面的代碼很熟悉，讓我們來(lái)寫一個(gè)在電子電路中常用的濾波器的示例代碼。

def Filt(arr,func):   
    result = []   
    for item in arr:   
        result.append(func(item))   
    return result  
def MyFilter(ele):   
    if ele < 0 :   
        return 0   
    return ele  
if __name__ == '__main__':   
    arr = [-5,3,5,11,-45,32]   
    print('%s' % (Filt(arr,MyFilter)))  
  

哦，之前忘記了說(shuō)，什么叫做高階函數(shù)，我們給出定義：

在數(shù)學(xué)和計(jì)算機(jī)科學(xué)中，高階函數(shù)是至少滿足下列一個(gè)條件的函數(shù):

接受一個(gè)或多個(gè)函數(shù)作為輸入

輸出一個(gè)函數(shù)

那么，毫無(wú)疑問(wèn)上面的濾波器，就是高階函數(shù)的一種應(yīng)用。

在函數(shù)式編程中，函數(shù)是基本單位，是第一型，他幾乎被用作一切，包括最簡(jiǎn)單的計(jì)算，甚至連變量都被計(jì)算所取代。在函數(shù)式編程中，變量只是一個(gè)名稱，而不是一個(gè)存儲(chǔ)單元，這是函數(shù)式編程與傳統(tǒng)的命令式編程最典型的不同之處。

讓我們看看，變量只是一個(gè)名稱，在上面的代碼中，我們可以這樣重寫主函數(shù)：

if __name__ == '__main__':   
    arr = [-5,3,5,11,-45,32]   
    func = MyFilter   
    print('%s' % (Filt(arr,func))) 

當(dāng)然，我們還可以把程序更精簡(jiǎn)一些，利用函數(shù)式編程中的利器，map,filter和reduce :

if __name__ == '__main__':   
    arr = [-5,3,5,11,-45,32]   
    print('%s' % (map(lambda x : 0 if x<0 else x ,arr))) 

這樣看上去是不是更賞心悅目呢?

這樣我們就看到了，函數(shù)是我們編程的基本單位。

6. 函數(shù)式編程的數(shù)學(xué)本質(zhì)

忘了是誰(shuí)說(shuō)過(guò)：一切問(wèn)題，歸根結(jié)底到最后都是數(shù)學(xué)問(wèn)題。

編程從來(lái)都不是難事兒，無(wú)非是細(xì)心，加上一些函數(shù)類庫(kù)的熟悉程度，加上經(jīng)驗(yàn)的堆積，而真正困難的，是如何把一個(gè)實(shí)際問(wèn)題，轉(zhuǎn)換成一個(gè)數(shù)學(xué)模型。這也是為什么微軟，Google之類的公司重視算法，這也是為什么數(shù)學(xué)建模大賽在大學(xué)計(jì)算機(jī)系如此被看重的原因。

先假設(shè)我們已經(jīng)憑借我們良好的數(shù)學(xué)思維和邏輯思維建立好了數(shù)學(xué)模型，那么接下來(lái)要做的是如何把數(shù)學(xué)語(yǔ)言來(lái)表達(dá)成計(jì)算機(jī)能看懂的程序語(yǔ)言。

這里我們?cè)倏丛诘谒墓?jié)中，我們提到的賦值模型，同一個(gè)函數(shù)，同一個(gè)參數(shù)，卻會(huì)在不同的場(chǎng)景下計(jì)算出不同的結(jié)果，這是在數(shù)學(xué)函數(shù)中完全不可能出現(xiàn)的情況，f(x) = y ，那么這個(gè)函數(shù)無(wú)論在什么場(chǎng)景下，都會(huì)得到同樣的結(jié)果，這個(gè)我們稱之為函數(shù)的確定性。

這也是賦值模型與數(shù)學(xué)模型的不兼容之處。而函數(shù)式編程取消了賦值模型，則使數(shù)學(xué)模型與編程模型完美地達(dá)成了統(tǒng)一。

7. 函數(shù)式編程的抽象本質(zhì)

相信每個(gè)程序員都對(duì)抽象這個(gè)概念不陌生。

在面向?qū)ο缶幊讨?，我們說(shuō)，類是現(xiàn)實(shí)事物的一種抽象表示。那么抽象的最大作用在我看來(lái)就在于抽象事物的重用性，一個(gè)事物越具體，那么他的可重用性就越低，因此，我們?cè)俅蛟炜芍赜眯源a，類，類庫(kù)時(shí)，其實(shí)在做的本質(zhì)工作就在于提高代碼的抽象性。而再往大了說(shuō)開(kāi)來(lái)，程序員做的工作，就是把一系列過(guò)程抽象開(kāi)來(lái)，反映成一個(gè)通用過(guò)程，然后用代碼表示出來(lái)。

在面向?qū)ο笾?，我們把事物抽象。而在函?shù)式編程中，我們則是在將函數(shù)方法抽象，第六節(jié)的濾波器已經(jīng)讓我們知道，函數(shù)一樣是可重用，可置換的抽象單位。

那么我們說(shuō)函數(shù)式編程的抽象本質(zhì)則是將函數(shù)也作為一個(gè)抽象單位，而反映成代碼形式，則是高階函數(shù)。

8.狀態(tài)到底怎么辦

我們說(shuō)了一大堆函數(shù)式編程的特點(diǎn)，但是我們忽略了，這些都是在理想的層面，我們回頭想想第四節(jié)的變量不變性，確實(shí)，我們說(shuō)，函數(shù)式編程是無(wú)狀態(tài)的，可是在我們現(xiàn)實(shí)情況中，狀態(tài)不可能一直保持不變，而狀態(tài)必然需要改變，傳遞，那么我們?cè)诤瘮?shù)式編程中的則是將其保存在函數(shù)的參數(shù)中，作為函數(shù)的附屬品來(lái)傳遞。

ps：在Erlang中，進(jìn)程之間的交互傳遞變量是靠“信箱”的收發(fā)信件來(lái)實(shí)現(xiàn)，其實(shí)我們想一想，從本質(zhì)而言，也是將變量作為一個(gè)附屬品來(lái)傳遞么!

我們來(lái)看個(gè)例子，我們?cè)谶@里舉一個(gè)求x的n次方的例子，我們用傳統(tǒng)的命令式編程來(lái)寫一下：

def expr(x,n):   
    result = 1   
    for i in range(1,n+1):   
        resultresult = result * x   
    return result  
if __name__ == '__main__':   
    print(expr(2,5)) 

這里，我們一直在對(duì)result變量賦值，但是我們知道，在函數(shù)式編程中的變量是具有不變性的，那么我們?yōu)榱吮３謗esult的狀態(tài)，就需要將result作為函數(shù)參數(shù)來(lái)傳遞以保持狀態(tài)：

def expr(num,n):   
    if n==0:   
        return 1   
    return num*expr(num,n-1)  
if __name__ == '__main__':   
    print(expr(2,5)) 

呦，這不是遞歸么!

#p#

9. 函數(shù)式編程和遞歸

遞歸是函數(shù)式編程的一個(gè)重要的概念，循環(huán)可以沒(méi)有，但是遞歸對(duì)于函數(shù)式編程卻是不可或缺的。

在這里，我得承認(rèn)，我確實(shí)不知道我該怎么解釋遞歸為什么對(duì)函數(shù)式編程那么重要。我能想到的只是遞歸充分地發(fā)揮了函數(shù)的威力，也解決了函數(shù)式編程無(wú)狀態(tài)的問(wèn)題。(如果大家有其他的意見(jiàn)，請(qǐng)賜教)

遞歸其實(shí)就是將大問(wèn)題無(wú)限地分解，直到問(wèn)題足夠小。

而遞歸與循環(huán)在編程模型和思維模型上最大的區(qū)別則在于：

循環(huán)是在描述我們?cè)撊绾蔚厝ソ鉀Q問(wèn)題。

遞歸是在描述這個(gè)問(wèn)題的定義。

那么就讓我們以斐波那契數(shù)列為例來(lái)看下這兩種編程模型。

先說(shuō)我們最常見(jiàn)的遞歸模型，這里，我不采用動(dòng)態(tài)規(guī)劃來(lái)做臨時(shí)狀態(tài)的緩存，只是說(shuō)這種思路：

def Fib(a):   
    if a==0 or a==1:   
        return 1   
    else:   
        return Fib(a-2)+Fib(a-1) 

遞歸是在描述什么是斐波那契數(shù)列，這個(gè)數(shù)列的定義就是一個(gè)數(shù)等于他的前兩項(xiàng)的和，并且已知Fib(0)和Fib(1)等于1。而程序則是用計(jì)算機(jī)語(yǔ)言來(lái)把這個(gè)定義重新描述了一次。

那接下來(lái)，我們看下循環(huán)模型：

def Fib(n):   
    a=1   
    b=1   
    nn = n - 1   
    while n>0:   
        temp=a   
        aa=a+b   
        b=temp   
        nn = n-1   
    return b 

這里則是在描述我們?cè)撊绾吻蠼忪巢瞧鯏?shù)列，應(yīng)該先怎么樣再怎么樣。

而我們明顯可以看到，遞歸相比于循環(huán)，具有著更加良好的可讀性。

但是，我們也不能忽略，遞歸而產(chǎn)生的StackOverflow，而賦值模型呢?我們懂的，函數(shù)式編程不能賦值，那么怎么辦?

10. 尾遞歸，偽遞歸

我們之前說(shuō)到了遞歸和循環(huán)各自的問(wèn)題，那怎么來(lái)解決這個(gè)問(wèn)題，函數(shù)式編程為我們拋出了答案，尾遞歸。

什么是尾遞歸，用最通俗的話說(shuō)：就是在最后一部單純地去調(diào)用遞歸函數(shù)，這里我們要注意“單純”這個(gè)字眼。

那么我們說(shuō)下尾遞歸的原理，其實(shí)尾遞歸就是不要保持當(dāng)前遞歸函數(shù)的狀態(tài)，而把需要保持的東西全部用參數(shù)給傳到下一個(gè)函數(shù)里，這樣就可以自動(dòng)清空本次調(diào)用的?？臻g。這樣的話，占用的?？臻g就是常數(shù)階的了。

在看尾遞歸代碼之前，我們還是先來(lái)明確一下遞歸的分類，我們將遞歸分成“樹(shù)形遞歸”和“尾遞歸”，什么是樹(shù)形遞歸，就是把計(jì)算過(guò)程逐一展開(kāi)，最后形成的是一棵樹(shù)狀的結(jié)構(gòu)，比如之前的斐波那契數(shù)列的遞歸解法。

那么我們來(lái)看下斐波那契尾遞歸的寫法：

def Fib(a,b,n):   
    if n==0:   
        return b   
    else:   
        return Fib(b,a+b,n-1) 

這里看上去有些難以理解，我們來(lái)解釋一下：傳入的a和b分別是前兩個(gè)數(shù)，那么每次我都推進(jìn)一位，那么b就變成了第一個(gè)數(shù)，而a+b就變成的第二個(gè)數(shù)。

這就是尾遞歸。其實(shí)我們想一想，這不是在描述問(wèn)題，而是在尋找一種問(wèn)題的解決方案，和上面的循環(huán)有什么區(qū)別呢?我們來(lái)做一個(gè)從尾遞歸到循環(huán)的轉(zhuǎn)換把!

最后返回b是把，那我就先聲明了，b=0

要傳入a是把，我也聲明了，a=1

要計(jì)算到n==0是把，還是循環(huán)while n!=0

每一次都要做一個(gè)那樣的計(jì)算是吧，我用臨時(shí)變量交換一下。temp=b ; b=a+b;a=temp。

那么按照這個(gè)思路一步步轉(zhuǎn)換下去，是不是就是我們?cè)谏厦鎸懙哪嵌窝h(huán)代碼呢?

那么這個(gè)尾遞歸，其實(shí)本質(zhì)上就是個(gè)“偽遞歸”，您說(shuō)呢?

既然我們可以優(yōu)化，對(duì)于大多數(shù)的函數(shù)式編程語(yǔ)言的編譯器來(lái)說(shuō)，他們對(duì)尾遞歸同樣提供了優(yōu)化，使尾遞歸可以優(yōu)化成循環(huán)迭代的形式，使其不會(huì)造成堆棧溢出的情況。

11. 惰性求值與并行

第一次接觸到惰性求值這個(gè)概念應(yīng)該是在Haskell語(yǔ)言中，看一個(gè)最簡(jiǎn)單的惰性求值，我覺(jué)得也是最經(jīng)典的例子：

在Haskell里，有個(gè)repeat關(guān)鍵字，他的作用是返回一個(gè)無(wú)限長(zhǎng)的List，那么我們來(lái)看下：

take 10 (repeat 1)

就是這句代碼，如果沒(méi)有了惰性求值，我想這個(gè)進(jìn)程一定會(huì)死在那里，可是結(jié)果卻是很正常，返回了長(zhǎng)度為10的List，List里的值都是1。這就是惰性求值的典型案例。

我們看這樣一段簡(jiǎn)單的代碼：

def getResult():   
    a = getA()   //Take a long time   
    b = getB()   //Take a long time   
    c = a + b 

這段代碼本身很簡(jiǎn)單，在命令式程序設(shè)計(jì)中，編譯器(或解釋器)會(huì)做的就是逐一解釋代碼，按順序求出a和b的值，然后再求出c。

可是我們從并行的角度考慮，求a的值是不是可以和求b的值并行呢?也就是說(shuō)，直到執(zhí)行到a+b的時(shí)候我們編譯器才意識(shí)到a和b直到現(xiàn)在才需要，那么我們雙核處理器就自然去發(fā)揮去最大的功效去計(jì)算了呢!

這才是惰性求值的最大威力。

當(dāng)然，惰性求值有著這樣的優(yōu)點(diǎn)也必然有著缺點(diǎn)，我記得我看過(guò)一個(gè)例子是最經(jīng)典的：

def Test():   
    print('Please enter a number:')   
    a = raw_input() 

可是這段代碼如果惰性求值的話，第一句話就不見(jiàn)得會(huì)在第二句話之前執(zhí)行了。

12. 函數(shù)式編程總覽

我們看完了函數(shù)式編程的特點(diǎn)，我們想想函數(shù)式編程的應(yīng)用場(chǎng)合。

1. 數(shù)學(xué)推理

2. 并行程序

那么我們總體地說(shuō)，其實(shí)函數(shù)式編程最適合地還是解決局部性的數(shù)學(xué)小問(wèn)題，要讓函數(shù)式編程來(lái)做CRUD，來(lái)做我們傳統(tǒng)的邏輯性很強(qiáng)的Web編程，就有些免為其難了。

就像如果要用Scala完全取代今天的Java的工作，我想恐怕效果會(huì)很糟糕。而讓Scala來(lái)負(fù)責(zé)底層服務(wù)的編寫，恐怕再合適不過(guò)了。

而在一種語(yǔ)言中融入多種語(yǔ)言范式，最典型的C#。在C# 3.0中引入Lambda表達(dá)式，在C# 4.0中引入聲明式編程，我們某些人在嘲笑C#越來(lái)越臃腫的同時(shí)，卻忽略了，這樣的語(yǔ)法糖，帶給我們的不僅僅是代碼書(shū)寫上的遍歷，更重要的是編程思維的一種進(jìn)步。

好吧，那就讓我們忘記那些C#中Lambda背后的實(shí)現(xiàn)機(jī)制，在C#中，還是在那些更純粹地支持函數(shù)式編程的語(yǔ)言中，盡情地去體驗(yàn)函數(shù)式編程帶給我們的快樂(lè)把!
 

原文鏈接：http://www.cnblogs.com/kym/archive/2011/03/07/1976519.html