標題: 函數(shù)式編程掃盲篇 [打印本頁]

作者: liuyang    時間: 2013-8-23 01:58
標題: 函數(shù)式編程掃盲篇

1. 概論
在過去的近十年的時間里,面向?qū)ο缶幊檀笮衅涞。以至于在大學的教育里,老師也只會教給我們兩種編程模型,面向過程和面向?qū)ο蟆?br /> 孰不知,在面向?qū)ο螽a(chǎn)生之前,在面向?qū)ο笏枷氘a(chǎn)生之前,函數(shù)式編程已經(jīng)有了數(shù)十年的歷史。
那么,接下來,就讓我們回顧這個古老又現(xiàn)代的編程模型,讓我們看看究竟是什么魔力將這個概念,將這個古老的概念,在21世紀的今天再次拉入了我們的視野。
2. 什么是函數(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ù)式編程的一些特征。
3. 從并發(fā)說開來
說來慚愧,我第一個真正接觸到函數(shù)式編程,要追溯到兩年以前的《Erlang程序設(shè)計》,我們知道Erlang是一個支持高并發(fā),有著強大容錯性的函數(shù)式編程語言。
因為時間太久了,而且一直沒有過真正地應用,所以對Erlang也只是停留在一些感性認識上。在我眼里,Erlang對高并發(fā)的支持體現(xiàn)在兩方面,第一,Erlang對輕量級進程的支持(請注意此處進程并不等于操作系統(tǒng)的進程,而只是Erlang內(nèi)部的一個單位單元),第二,就是變量的不變性。
4. 變量的不變性
在《Erlang程序設(shè)計》一書中,對變量的不變性是這樣說的,Erlang是目前唯一變量不變性的語言。具體的話我記不清了,我不知道是老爺子就是這么寫的,還是譯者的問題。我在給這本書寫書評的時候吹毛求疵地說:
我對這句話有異議,切不說曾經(jīng)的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
        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),無論多少個進程在跑,因為我們本身沒有賦值操作,所以都不會影響到我們的最終結(jié)果。
但是這樣也像大家看到的一樣,采用這樣的方式?jīng)]有辦法保持狀態(tài)。
這也就是我們在之前概念中看到的無狀態(tài)性。
5. 再看函數(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è)計就這樣被推到了前線,而命令式編程天生的缺陷卻使并行編程模型變得非常復雜,無論是信號量,還是鎖的概念,都使程序員不堪其重。
就這樣,函數(shù)式編程終于在數(shù)十年后,終于走出實驗室,來到了真實的生產(chǎn)環(huán)境中,無論是冷門的Haskell,Erlang,還是Scala,F(xiàn)#,都是函數(shù)式編程成功的典型。
6. 函數(shù)式編程的第一型
我們知道,對象是面向?qū)ο蟮牡谝恍,那么函?shù)式編程也是一樣,函數(shù)是函數(shù)式編程的第一型。
我們在函數(shù)式編程中努力用函數(shù)來表達所有的概念,完成所有的操作。
在面向?qū)ο缶幊讨,我們把對象傳來傳去,那在函?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ù)是我們編程的基本單位。

7. 函數(shù)式編程的數(shù)學本質(zhì)
忘了是誰說過:一切問題,歸根結(jié)底到最后都是數(shù)學問題。
編程從來都不是難事兒,無非是細心,加上一些函數(shù)類庫的熟悉程度,加上經(jīng)驗的堆積,而真正困難的,是如何把一個實際問題,轉(zhuǎn)換成一個數(shù)學模型。這也是為什么微軟,Google之類的公司重視算法,這也是為什么數(shù)學建模大賽在大學計算機系如此被看重的原因。
先假設(shè)我們已經(jīng)憑借我們良好的數(shù)學思維和邏輯思維建立好了數(shù)學模型,那么接下來要做的是如何把數(shù)學語言來表達成計算機能看懂的程序語言。
這里我們再看在第四節(jié)中,我們提到的賦值模型,同一個函數(shù),同一個參數(shù),卻會在不同的場景下計算出不同的結(jié)果,這是在數(shù)學函數(shù)中完全不可能出現(xiàn)的情況,f(x) = y ,那么這個函數(shù)無論在什么場景下,都會得到同樣的結(jié)果,這個我們稱之為函數(shù)的確定性。
這也是賦值模型與數(shù)學模型的不兼容之處。而函數(shù)式編程取消了賦值模型,則使數(shù)學模型與編程模型完美地達成了統(tǒng)一。
8. 函數(shù)式編程的抽象本質(zhì)
相信每個程序員都對抽象這個概念不陌生。
在面向?qū)ο缶幊讨,我們說,類是現(xiàn)實事物的一種抽象表示。那么抽象的最大作用在我看來就在于抽象事物的重用性,一個事物越具體,那么他的可重用性就越低,因此,我們再打造可重用性代碼,類,類庫時,其實在做的本質(zhì)工作就在于提高代碼的抽象性。而再往大了說開來,程序員做的工作,就是把一系列過程抽象開來,反映成一個通用過程,然后用代碼表示出來。
在面向?qū)ο笾,我們把事物抽象。而在函?shù)式編程中,我們則是在將函數(shù)方法抽象,第六節(jié)的濾波器已經(jīng)讓我們知道,函數(shù)一樣是可重用,可置換的抽象單位。
那么我們說函數(shù)式編程的抽象本質(zhì)則是將函數(shù)也作為一個抽象單位,而反映成代碼形式,則是高階函數(shù)。
9.狀態(tài)到底怎么辦
我們說了一大堆函數(shù)式編程的特點,但是我們忽略了,這些都是在理想的層面,我們回頭想想第四節(jié)的變量不變性,確實,我們說,函數(shù)式編程是無狀態(tài)的,可是在我們現(xiàn)實情況中,狀態(tài)不可能一直保持不變,而狀態(tài)必然需要改變,傳遞,那么我們在函數(shù)式編程中的則是將其保存在函數(shù)的參數(shù)中,作為函數(shù)的附屬品來傳遞。
ps:在Erlang中,進程之間的交互傳遞變量是靠“信箱”的收發(fā)信件來實現(xiàn),其實我們想一想,從本質(zhì)而言,也是將變量作為一個附屬品來傳遞么!
我們來看個例子,我們在這里舉一個求x的n次方的例子,我們用傳統(tǒng)的命令式編程來寫一下:
def expr(x,n):
    result = 1
    for i in range(1,n+1):
        result = result * x
    return result

if __name__ == '__main__':
    print(expr(2,5))



這里,我們一直在對result變量賦值,但是我們知道,在函數(shù)式編程中的變量是具有不變性的,那么我們?yōu)榱吮3謗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))


  呦,這不是遞歸么!

10. 函數(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)模型:
這里則是在描述我們該如何求解斐波那契數(shù)列,應該先怎么樣再怎么樣。
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


而我們明顯可以看到,遞歸相比于循環(huán),具有著更加良好的可讀性。
但是,我們也不能忽略,遞歸而產(chǎn)生的StackOverflow,而賦值模型呢?我們懂的,函數(shù)式編程不能賦值,那么怎么辦?
11.  尾遞歸,偽遞歸
我們之前說到了遞歸和循環(huán)各自的問題,那怎么來解決這個問題,函數(shù)式編程為我們拋出了答案,尾遞歸。
什么是尾遞歸,用最通俗的話說:就是在最后一部單純地去調(diào)用遞歸函數(shù),這里我們要注意“單純”這個字眼。
那么我們說下尾遞歸的原理,其實尾遞歸就是不要保持當前遞歸函數(shù)的狀態(tài),而把需要保持的東西全部用參數(shù)給傳到下一個函數(shù)里,這樣就可以自動清空本次調(diào)用的棧空間。這樣的話,占用的?臻g就是常數(shù)階的了。
在看尾遞歸代碼之前,我們還是先來明確一下遞歸的分類,我們將遞歸分成“樹形遞歸”和“尾遞歸”,什么是樹形遞歸,就是把計算過程逐一展開,最后形成的是一棵樹狀的結(jié)構(gòu),比如之前的斐波那契數(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)的轉(zhuǎn)換把!
最后返回b是把,那我就先聲明了,b=0
要傳入a是把,我也聲明了,a=1
要計算到n==0是把,還是循環(huán)while n!=0
每一次都要做一個那樣的計算是吧,我用臨時變量交換一下。temp=b ; b=a+b;a=temp。
那么按照這個思路一步步轉(zhuǎn)換下去,是不是就是我們在上面寫的那段循環(huán)代碼呢?
那么這個尾遞歸,其實本質(zhì)上就是個“偽遞歸”,您說呢?
既然我們可以優(yōu)化,對于大多數(shù)的函數(shù)式編程語言的編譯器來說,他們對尾遞歸同樣提供了優(yōu)化,使尾遞歸可以優(yōu)化成循環(huán)迭代的形式,使其不會造成堆棧溢出的情況。
12. 惰性求值與并行
第一次接觸到惰性求值這個概念應該是在Haskell語言中,看一個最簡單的惰性求值,我覺得也是最經(jīng)典的例子:
在Haskell里,有個repeat關(guān)鍵字,他的作用是返回一個無限長的List,那么我們來看下:
take 10 (repeat 1)   
就是這句代碼,如果沒有了惰性求值,我想這個進程一定會死在那里,可是結(jié)果卻是很正常,返回了長度為10的List,List里的值都是1。這就是惰性求值的典型案例。
我們看這樣一段簡單的代碼:
def getResult():
    a = getA()   //Take a long time
    b = getB()   //Take a long time
    c = a + b


這段代碼本身很簡單,在命令式程序設(shè)計中,編譯器(或解釋器)會做的就是逐一解釋代碼,按順序求出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í)行了。
13. 函數(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.torrancerestoration.com/bbs/) Powered by Discuz! X3.1