在過去的近十年的時間里，面向對象編程大行其道。以至于在大學的教育里，老師也只會教給我們兩種編程模型，面向過程和面向對象。

孰不知，在面向對象產(chǎn)生之前，在面向對象思想產(chǎn)生之前，函數(shù)式編程已經(jīng)有了數(shù)十年的歷史。

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

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

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

那我們就來摘取一下Wiki上對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.

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

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

2. 從并發(fā)說開來

說來慚愧，我第一個真正接觸到函數(shù)式編程，要追溯到兩年以前的《Erlang程序設計》，我們知道Erlang是一個支持高并發(fā)，有著強大容錯性的函數(shù)式編程語言。

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

3. 變量的不變性

在《Erlang程序設計》一書中，對變量的不變性是這樣說的，Erlang是目前唯一變量不變性的語言。具體的話我記不清了，我不知道是老爺子就是這么寫的，還是譯者的問題。我在給這本書寫書評的時候吹毛求疵地說：

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

讓我們先來看兩段程序，首先是我們常見的一種包含賦值的程序：

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())  
  

這段程序本身是沒有問題的，但是我們考慮這樣一種情況，現(xiàn)在有多個進程在同時跑這一個程序，那么程序就會被先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')())  
  

這時我們就會發(fā)現(xiàn)，無論多少個進程在跑，因為我們本身沒有賦值操作，所以都不會影響到我們的最終結果。

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

這也就是我們在之前概念中看到的無狀態(tài)性。

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

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

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

先讓我們再來回顧一下偉大的摩爾定律：

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

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

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

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

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

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

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

我們知道，對象是面向對象的第一型，那么函數(shù)式編程也是一樣，函數(shù)是函數(shù)式編程的第一型。

我們在函數(shù)式編程中努力用函數(shù)來表達所有的概念，完成所有的操作。

在面向對象編程中，我們把對象傳來傳去，那在函數(shù)式編程中，我們要做的是把函數(shù)傳來傳去，而這個，說成術語，我們把他叫做高階函數(shù)。

那我們就來看一個高階函數(shù)的應用，熟悉js的同學應該對下面的代碼很熟悉，讓我們來寫一個在電子電路中常用的濾波器的示例代碼。

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)))  
  

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

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

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

輸出一個函數(shù)

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

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

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

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

當然，我們還可以把程序更精簡一些，利用函數(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ù)學本質

忘了是誰說過：一切問題，歸根結底到最后都是數(shù)學問題。

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

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

這里我們再看在第四節(jié)中，我們提到的賦值模型，同一個函數(shù)，同一個參數(shù)，卻會在不同的場景下計算出不同的結果，這是在數(shù)學函數(shù)中完全不可能出現(xiàn)的情況，f(x) = y ，那么這個函數(shù)無論在什么場景下，都會得到同樣的結果，這個我們稱之為函數(shù)的確定性。

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

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

相信每個程序員都對抽象這個概念不陌生。

在面向對象編程中，我們說，類是現(xiàn)實事物的一種抽象表示。那么抽象的最大作用在我看來就在于抽象事物的重用性，一個事物越具體，那么他的可重用性就越低，因此，我們再打造可重用性代碼，類，類庫時，其實在做的本質工作就在于提高代碼的抽象性。而再往大了說開來，程序員做的工作，就是把一系列過程抽象開來，反映成一個通用過程，然后用代碼表示出來。

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

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

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

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

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

我們來看個例子，我們在這里舉一個求x的n次方的例子，我們用傳統(tǒng)的命令式編程來寫一下：

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)) 

這里，我們一直在對result變量賦值，但是我們知道，在函數(shù)式編程中的變量是具有不變性的，那么我們?yōu)榱吮３謗esult的狀態(tài)，就需要將result作為函數(shù)參數(shù)來傳遞以保持狀態(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ù)式編程的一個重要的概念，循環(huán)可以沒有，但是遞歸對于函數(shù)式編程卻是不可或缺的。

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

遞歸其實就是將大問題無限地分解，直到問題足夠小。

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

循環(huán)是在描述我們該如何地去解決問題。

遞歸是在描述這個問題的定義。

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

先說我們最常見的遞歸模型，這里，我不采用動態(tài)規(guī)劃來做臨時狀態(tài)的緩存，只是說這種思路：

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

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

那接下來，我們看下循環(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 

這里則是在描述我們該如何求解斐波那契數(shù)列，應該先怎么樣再怎么樣。

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

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

10. 尾遞歸，偽遞歸

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

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

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

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

那么我們來看下斐波那契尾遞歸的寫法：

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

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

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

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

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

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

每一次都要做一個那樣的計算是吧，我用臨時變量交換一下。temp=b ; b=a+b;a=temp。

那么按照這個思路一步步轉換下去，是不是就是我們在上面寫的那段循環(huán)代碼呢?

那么這個尾遞歸，其實本質上就是個“偽遞歸”，您說呢?

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

11. 惰性求值與并行

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

在Haskell里，有個repeat關鍵字，他的作用是返回一個無限長的List，那么我們來看下：

take 10 (repeat 1)

就是這句代碼，如果沒有了惰性求值，我想這個進程一定會死在那里，可是結果卻是很正常，返回了長度為10的List，List里的值都是1。這就是惰性求值的典型案例。

我們看這樣一段簡單的代碼：

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

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

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

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

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

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

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

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

我們看完了函數(shù)式編程的特點，我們想想函數(shù)式編程的應用場合。

1. 數(shù)學推理

2. 并行程序

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

就像如果要用Scala完全取代今天的Java的工作，我想恐怕效果會很糟糕。而讓Scala來負責底層服務的編寫，恐怕再合適不過了。

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

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

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