函數式程式設計

1. 概論

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

孰不知，在面向對象産生之前，在面向對象思想産生之前，函數式程式設計已經有了數十年的曆史。

那麼，接下來，就讓我們回顧這個古老又現代的程式設計模型，讓我們看看究竟是什麼魔力将這個概念，将這個古老的概念，在21世紀的今天再次拉入了我們的視野。

2. 什麼是函數式程式設計

在維基百科中，已經對函數式程式設計有了很詳細的介紹。

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

簡單地翻譯一下，也就是說函數式程式設計是一種程式設計模型，他将計算機運算看做是數學中函數的計算，并且避免了狀态以及變量的概念。

接下來，我們就來剖析下函數式程式設計的一些特征。

3. 從并發說開來

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

因為時間太久了，而且一直沒有過真正地應用，是以對Erlang也隻是停留在一些感性認識上。在我眼裡，Erlang對高并發的支援展現在兩方面，第一，Erlang對輕量級程序的支援（請注意此處程序并不等于作業系統的程序，而隻是Erlang内部的一個機關單元），第二，就是變量的不變性。

4. 變量的不變性

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

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

讓我們先來看兩段程式，首先是我們常見的一種包含指派的程式：

class Account:

    def __init__(self,balance):

        self.balance = balance

    def desposit(self,amount):

        self.balance = self.balance + amount

        return self.balance

    def despositTwice(self):

        self.balance = self.balance * 2

if __name__ == '__main__':

    account = Account(100)

    print(account.desposit(10))

    print(account.despositTwice())

這段程式本身是沒有問題的，但是我們考慮這樣一種情況，現在有多個程序在同時跑這一個程式，那麼程式就會被先desposit 還是先 despositTwice所影響。

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

def makeAccount(balance):

    global desposit

    global despositTwice

    def desposit(amount):

        result = balance + amount

        return result

    def despositTwice():

        result = balance * 2

    def dispatch(method):

        return eval(method)

    return dispatch

    handler = makeAccount(100)

    print(handler('desposit')(10))

    print(handler('despositTwice')())

這時我們就會發現，無論多少個程序在跑，因為我們本身沒有指派操作，是以都不會影響到我們的最終結果。

但是這樣也像大家看到的一樣，采用這樣的方式沒有辦法保持狀态。

這也就是我們在之前概念中看到的無狀态性。

5. 再看函數式程式設計的崛起

既然已經看完了函數式程式設計的基本特征，那就讓我們來想想數十年後函數式程式設計再次崛起的幕後原因。

一直以來，作為函數式程式設計代表的Lisp，還是Haskell，更多地都是在大學中，在實驗室中應用，而很少真的應用到真實的生産環境。

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

1、內建電路晶片上所內建的電路的數目，每隔18個月就翻一番。 2、微處理器的性能每隔18個月提高一倍，而價格下降一半。 3、用一個美元所能買到的電腦性能，每隔18個月翻兩番。

一如摩爾的預測，整個資訊産業就這樣飛速地向前發展着，但是在近年，我們卻可以發現摩爾定律逐漸地失效了，晶片上元件的尺寸是不可能無限地縮小的，這就意味着晶片上所能內建的電子元件的數量一定會在某個時刻達到一個極限。那麼當技術達到這個極限時，我們又該如何适應日益增長的計算需求，電子元件廠商給出了答案，就是多核。

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

就這樣，函數式程式設計終于在數十年後，終于走出實驗室，來到了真實的生産環境中，無論是冷門的Haskell，Erlang，還是Scala，F#，都是函數式程式設計成功的典型。

6. 函數式程式設計的第一型

我們知道，對象是面向對象的第一型，那麼函數式程式設計也是一樣，函數是函數式程式設計的第一型。

我們在函數式程式設計中努力用函數來表達所有的概念，完成所有的操作。

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

那我們就來看一個高階函數的應用，熟悉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

    arr = [-5,3,5,11,-45,32]

    print('%s' % (Filt(arr,MyFilter)))

哦，之前忘記了說，什麼叫做高階函數，我們給出定義：

在數學和計算機科學中，高階函數是至少滿足下列一個條件的函數: 接受一個或多個函數作為輸入 輸出一個函數

那麼，毫無疑問上面的濾波器，就是高階函數的一種應用。

在函數式程式設計中，函數是基本機關，是第一型，他幾乎被用作一切，包括最簡單的計算，甚至連變量都被計算所取代。在函數式程式設計中，變量隻是一個名稱，而不是一個存儲單元，這是函數式程式設計與傳統的指令式程式設計最典型的不同之處。

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

    func = MyFilter

    print('%s' % (Filt(arr,func)))

當然，我們還可以把程式更精簡一些，利用函數式程式設計中的利器，map,filter和reduce :

    print('%s' % (map(lambda x : 0 if x<0 else x ,arr)))

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

這樣我們就看到了，函數是我們程式設計的基本機關。

7. 函數式程式設計的數學本質

忘了是誰說過：一切問題，歸根結底到最後都是數學問題。

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

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

這裡我們再看在第四節中，我們提到的指派模型，同一個函數，同一個參數，卻會在不同的場景下計算出不同的結果，這是在數學函數中完全不可能出現的情況，f(x) = y ，那麼這個函數無論在什麼場景下，都會得到同樣的結果，這個我們稱之為函數的确定性。

這也是指派模型與數學模型的不相容之處。而函數式程式設計取消了指派模型，則使數學模型與程式設計模型完美地達成了統一。

8. 函數式程式設計的抽象本質

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

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

在面向對象中，我們把事物抽象。而在函數式程式設計中，我們則是在将函數方法抽象，第六節的濾波器已經讓我們知道，函數一樣是可重用，可置換的抽象機關。

那麼我們說函數式程式設計的抽象本質則是将函數也作為一個抽象機關，而反映成代碼形式，則是高階函數。

9.狀态到底怎麼辦

我們說了一大堆函數式程式設計的特點，但是我們忽略了，這些都是在理想的層面，我們回頭想想第四節的變量不變性，确實，我們說，函數式程式設計是無狀态的，可是在我們現實情況中，狀态不可能一直保持不變，而狀态必然需要改變，傳遞，那麼我們在函數式程式設計中的則是将其儲存在函數的參數中，作為函數的附屬品來傳遞。

ps：在Erlang中，程序之間的互動傳遞變量是靠“信箱”的收發信件來實作，其實我們想一想，從本質而言，也是将變量作為一個附屬品來傳遞麼！

我們來看個例子，我們在這裡舉一個求x的n次方的例子，我們用傳統的指令式程式設計來寫一下：

def expr(x,n):

    result = 1

    for i in range(1,n+1):

        result = result * x

    print(expr(2,5))

這裡，我們一直在對result變量指派，但是我們知道，在函數式程式設計中的變量是具有不變性的，那麼我們為了保持result的狀态，就需要将result作為函數參數來傳遞以保持狀态：

def expr(num,n):

    if n==0:

        return 1

    return num*expr(num,n-1)

呦，這不是遞歸麼！

10. 函數式程式設計和遞歸

遞歸是函數式程式設計的一個重要的概念，循環可以沒有，但是遞歸對于函數式程式設計卻是不可或缺的。

在這裡，我得承認，我确實不知道我該怎麼解釋遞歸為什麼對函數式程式設計那麼重要。我能想到的隻是遞歸充分地發揮了函數的威力，也解決了函數式程式設計無狀态的問題。（如果大家有其他的意見，請賜教）

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

而遞歸與循環在程式設計模型和思維模型上最大的差別則在于：

循環是在描述我們該如何地去解決問題。

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

那麼就讓我們以斐波那契數列為例來看下這兩種程式設計模型。

先說我們最常見的遞歸模型，這裡，我不采用動态規劃來做臨時狀态的緩存，隻是說這種思路：

def Fib(a):

    if a==0 or a==1:

    else:

        return Fib(a-2)+Fib(a-1)

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

那接下來，我們看下循環模型：

def Fib(n):

    a=1

    b=1

    n = n - 1

    while n>0:

        temp=a

        a=a+b

        b=temp

        n = n-1

    return b

這裡則是在描述我們該如何求解斐波那契數列，應該先怎麼樣再怎麼樣。

而我們明顯可以看到，遞歸相比于循環，具有着更加良好的可讀性。

但是，我們也不能忽略，遞歸而産生的StackOverflow，而指派模型呢？我們懂的，函數式程式設計不能指派，那麼怎麼辦？

11.  尾遞歸，僞遞歸

我們之前說到了遞歸和循環各自的問題，那怎麼來解決這個問題，函數式程式設計為我們抛出了答案，尾遞歸。

什麼是尾遞歸，用最通俗的話說：就是在最後一部單純地去調用遞歸函數，這裡我們要注意“單純”這個字眼。

那麼我們說下尾遞歸的原理，其實尾遞歸就是不要保持目前遞歸函數的狀态，而把需要保持的東西全部用參數給傳到下一個函數裡，這樣就可以自動清空本次調用的棧空間。這樣的話，占用的棧空間就是常數階的了。

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

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

def Fib(a,b,n):

        return b

        return Fib(b,a+b,n-1)

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

這就是尾遞歸。其實我們想一想，這不是在描述問題，而是在尋找一種問題的解決方案，和上面的循環有什麼差別呢？我們來做一個從尾遞歸到循環的轉換把！

最後傳回b是把，那我就先聲明了，b=0

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

要計算到n==0是把，還是循環while n!=0

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

那麼按照這個思路一步步轉換下去，是不是就是我們在上面寫的那段循環代碼呢？

那麼這個尾遞歸，其實本質上就是個“僞遞歸”，您說呢？

既然我們可以優化，對于大多數的函數式程式設計語言的編譯器來說，他們對尾遞歸同樣提供了優化，使尾遞歸可以優化成循環疊代的形式，使其不會造成堆棧溢出的情況。

12. 惰性求值與并行

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

在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的值并行呢？也就是說，直到執行到a+b的時候我們編譯器才意識到a和b直到現在才需要，那麼我們雙核處理器就自然去發揮去最大的功效去計算了呢！

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

當然，惰性求值有着這樣的優點也必然有着缺點，我記得我看過一個例子是最經典的：

def Test():

    print('Please enter a number:')

    a = raw_input()

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

13. 函數式程式設計總覽

我們看完了函數式程式設計的特點，我們想想函數式程式設計的應用場合。

1. 數學推理

2. 并行程式

那麼我們總體地說，其實函數式程式設計最适合地還是解決局部性的數學小問題，要讓函數式程式設計來做CRUD，來做我們傳統的邏輯性很強的Web程式設計，就有些免為其難了。

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

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

好吧，那就讓我們忘記那些C#中Lambda背後的實作機制，在C#中，還是在那些更純粹地支援函數式程式設計的語言中，盡情地去體驗函數式程式設計帶給我們的快樂把！