In-depth: Functional programming in C++ - 在C++上面使用函數式編程

原文作者為遊戲界的傳奇人物John Carmack


本譯文張貼已經過作者同意
原文網址:
http://gamasutra.com/view/news/169296/Indepth_Functional_programming_in_C.php


譯者:
網路上有很多關於用FP風格寫C++的文章,其中John Carmack所寫的這一篇Functional programming in C++是最讓我起共鳴的,原文在2012年已經有人翻譯過了,不過因為我很喜歡這篇文章,所以用個人方式理解再翻譯一遍。

原諒我為了語意通順,並沒有逐句翻譯,但不用擔心,技術內容並沒有打折扣,這篇文章真的很讚。

因為我的翻譯能力有限,所以在這裡先做一些閱讀前的說明,會讓你讀起來更舒服點。

1.Functional Programming在文中都用FP來簡稱。
2.純函式是FP的中心思想,遵守純函式的規則就可以得到FP帶來的好處了。
3."純"指的是沒有副作用,副作用越少的函式就越"純"。
4.副作用是指函式執行時對外部造成的影響,只有回傳值的影響不算副作用。
5.純函式的行為跟數學上的函式是一樣的。



本文:

也許各位早已聽過一種名為FP的程式編寫思維,它被視為軟體開發者的福音,甚至有人認為FP就是銀彈(註1)。不過查了一下維基上的資料卻讓我倒盡胃口,網頁上劈頭就講了λ演算法(註2)跟形式系統(註3),當下的確看不出來這些理論對軟體開發有什麼幫助。


個人站在實務面所歸納的結論是:軟體開發過程產生的疑難雜症,大多是因為工程師沒有掌握好程式執行過程裡各時期的狀態所導致的。在多執行緒環境下這情況會變的更嚴重(假如你曾留意過這問題)。使用FP思維來編寫程式會讓程式碼的流程狀態變得清楚明確,程式碼也變得更有條理,而且完全遵守FP規則的程式是不可能發生執行緒衝突的。


我認為FP確實有它存在的價值,但是光憑這點就去呼籲大家放棄C++然後改用LispHaskell這些語言是不負責任的發言。


程式語言的設計者總是擔心語法的優點會被外在因素抹滅,而這種事情在遊戲界特別容易發生,我們在專案開發上必須面對跨平台問題、被特定的工具庫、認證門檻、授權技術綁死以及嚴苛的性能要求等等外在因素,再加上還要用有限的人手去維護前人遺留下的程式碼。


如果你的工作環境條件允許你使用非主流語言的話,那麼恭喜你,但也要做好挨罵的心理準備,罪名是拖慢開發進度之類的。


不管你用的是哪一種語言,使用FP風格來撰寫程式都能帶來好處,只要覺得情況允許使用FP就該用,如果覺得情況不適合也要再好好想想為何不用。如果打算使用FP的話你可以去查一下λ演算法、單子(註4)、柯里化(註5)、在無窮集合上組合惰性求值函式(註6)、以及學習其他FP導向的語言。


C++並不鼓勵你採用FP,但也不阻止你使用,而且C++允許你深入底層使用平行處理的指令集來操作記憶體上的資料,還允許你使用其他你需要的強大功能。


註1:銀彈是傳說中可以有效傷害吸血鬼的武器,在IT界則用銀彈比喻對軟體開發有卓越效果的技巧。
註2:λ演算法(lambdas)思維就是將function當參數或回傳值使用。
註3:形式系統(formal system),用於邏輯推導的一種主義思想,直接想成是數學上的邏輯推導就行了。
註4:單子(monad)是FP裡面提到的一種抽象型別,用來表示一段計算而非數據資料。
註5:柯里化(Currying)就是把一個多參數的函式包裝成一個只接受一個參數的新函式,舉例就是把 f(x,y,z)=x+y+z 包成 g(x)=f(x,3,5)
註6:惰性求值的意思是算式執行的當下沒有真的去計算答案,不儲存結果只儲存算式,然後等到該答案真的需要使用時才開始做計算。(這麼說我以前就會惰性求學跟惰性寫作業了)



純函式

一個純函式只注意外部傳進來的參數,它唯一的工作就是依據輸入參數求出回傳值,邏輯上不會有副作用,當然我指的是抽象概念上的副作用,以硬體角度來看,任何函式都有副作用,但在抽象角度上它的確沒有副作用。

純函式不會去讀寫全域變數,內部不保存靜態變數,不進行IO操作,不修改傳進來的參數,最理想的狀況是連那種有可能跟外部連動的參數都不要傳進來,像是傳遞全域變數的指標進來就偏離純函式的宗旨了。

純函式有以下優良特質:

*執行緒安全性
一個使用實體參數的純函式是完全沒有執行緒問題的,但如果使用指標或參考作為參數的話,你有必要注意一下其他執行緒有可能也引用一樣的指標來操作同一塊資料,甚至釋放掉記憶體。即使避不開這樣的風險,純函式依然是能讓多執行緒更加安全的有效技巧之一。

你可以簡單的把這些函式拿來平行執行或者個別執行比較結果,這樣測試跟展開函式會安全很多。


*重覆使用性
要將純函式移植到其他環境非常容易,雖然還是要處理參數型別問題以及轉接內部呼叫的其他純函式,但是至少不會牽一髮而動全身。你不知道有多少程式碼從舊架構環境中抽出來時,所花費的時間比重寫一個新的還要久。


*可測試性
純函式具有引用公開化的特質,意思是每次輸入同一組參數都會得到相同的結果,這使得純函式比糾結的程式更容易做調試。


我向來都盡寫些不負責任的測試程式,程式中有太多地方跟系統相連了,需要搭配複雜的配套措施進行測試修改,我總是認為這不值得花時間去寫(也許我這想法也不對)。

純函式可以方便你做細部測試,測試碼看起來就跟教科書上寫的一樣漂亮。每當遇到結構刁鑽的程式時,我會切割成一個個純函式來分別做測試,驚人的是,常常還是能測出小毛病來,這意味著我佈下的防護網還不夠周全。


*可讀性與可維護性
因為參數輸入跟輸出的直接影響範圍很有限,你可以很容易搞懂以前寫的純函式,跟函式外部有關的潛規則也變的更少。


形式系統跟程式自我推理(註7:)在未來會越來越重要,靜態程式分析在現今就已經很重要了,程式寫得越符合FP規範,程式分析工具會運作的更好,不然至少也會讓速度快的局部分析工具的分析範圍變得更大,分擔更多全域分析工具的工作。
我覺得對於Eclipse之類的工具而言,OO跟FP都能分析的很好,差別在於OO的寫法如果封裝不好的話會很難閱讀的,當你要追查一個變數的影響範圍時,OO會追的比較辛苦。


我們這領域重視的是"完成品",架構正確性的形式證明(註8)還沒被列為開發重點,但是去證明有哪些還沒浮現的潛在危險仍然是值得的。我們可以在開發過程中應用更多的學術理論。


正在修計算機概論的同學可能會一邊抓著頭一邊想:"程式不都是這麼寫的嗎?",現實中卻是搞成"大泥球"(註9)的專案比較多,傳統的指令式程式語言提供了緊急應變手段,結果大家沒事就拿來用。如果你寫的是免洗程式,那倒無所謂,一直用全域變數也沒差。


如果你寫的是過了一年都還會用到的程式碼,那就要衡量一下是現在方便重要,還是避免日後一定會發生的問題重要。大部分軟體開發者都沒有用長遠的眼光去預測修改程式引發的麻煩。



註7:自我推理(automated reasoning)是AI領域的名詞,指的是電腦能自己進行邏輯推理。
註8:形式證明(formal proof),就是高等數學裡的論證方式,這沒什麼好翻的。
註9:大泥球(Big Balls of Mud)是一種反面模式,指的是程式結構混亂不清晰這種常犯的錯誤。



純度的實現

並不是每個地方都可以純函式化,除非整個程式都是自己親手寫的,不然總有些地方必須跟外界交流。盡力去提昇程式的純度(註10)是很有趣沒錯,但是在實作上必須承認在某些情況下,最低限度的副作用是必要的。


即使針對單一函式而言,純度的實現也不是那種會功虧一簣的工作。純度的價值隨著純度的提昇只會越來越高,而且從"一團亂"提昇到"大致上純化"所得到的好處比從"幾乎純化"提昇到"完全純化"還要高。即使無法達到完全的純化,也應當盡可能提高純度。使用全域計數器或全域旗幟是拉低純度的行為,不過如果除此之外都已純化,那麼還是能得到純函式化所帶來的好處。


修正大範圍中最糟糕的缺點通常會比雕琢幾個完美的小區塊還要重要。回想一下你碰過最棘手的功能面問題或者系統架構問題,我幾乎能篤定問題是起源於複雜的狀態溝通網絡,也許程式的錯誤行為是受到這些狀態的牽動,而且影響到的不止是參數而已。在發生問題的區塊加強管制,或至少拼命防止更多程式陷入類似的麻煩,做這種事比你花時間去最佳化底層的那些數學函式庫還要有意義。


朝著純化進行重構的過程裡通常會出現將一段算式做分割的行為,這十之八九會產生更多負責參數傳遞的程式碼,字數冗長的程式可是公認的差勁寫法,但FP的結果卻常常反而是減少了程式的字數,我知道這聽起來有點弔詭。

FP寫法之所以在某些情況下比指令式語言更加精簡的原因跟這些有關:純函式的使用、垃圾回收機制、強大的內建資料型態、模式匹配、條列式推導(註11)、函式編成、多種語法糖(註12)諸如此類。其實這些縮短程式碼的手段大多在指令式語言也找的到,並非FP特有。


如果只是呼叫個函式也要你填十幾個參數,不爽是正常的。可以試著重構程式來減少參數。


C++對純度維護沒有提供任何支援,這點不大理想,假如有人污染一個被大量呼叫的純函式,那麼所有呼叫該函式的純函式也會失去純度,這問題對形式系統來說很嚴重,但還是那句話,維護純度不是那種會功虧一簣的工作,破壞純度也不是說罪無可赦,對整體的程式開發而言,失去純度就只是有點可惜而已。


聽起來C/C++應該在新的標準裡增加pure這個關鍵字,目前已經有一個類似的關鍵字叫做const,一個用來讓編譯器幫忙監督、保護工程師的選項,而且這招常常是管用的,D語言已經有pure這個關鍵字了,請注意其中弱純度跟強純度的之間的差異,強純度的指標參數也需要加const關鍵字。


從某些角度來看,用關鍵字來強制要求純度是很狹隘的設計,純函式即使呼叫了不純的函式,只要沒有帶給外部副作用就還是很純。只接受命令列參數不讀取其他檔案的程式也可以視為一種純函式。


註10:純度(purity),我想不到什麼好的翻譯,因為原文名詞一樣令人費解,總之就是純函式化的程度。
註11:條列式推導(list comprehension),好的,這也是我亂翻的,這種寫法的程式看起來就像數學算式一樣全擠到同一行,根本是FP作風。
註12:語法糖(syntactic sugar)又稱糖衣語法,是程式語言設計者提供給你的一些偷懶語法。



物件導向設計

OO將經常變動的部份封裝起來以提高可讀性,FP則是縮短經常變動的部份以提高可讀性
- Michael Feathers(@mfeathers)


所謂"變動的部份"其實是指"變化的狀態",物件導向入門書籍最先教的就是操作物件改變自己的狀態,這對大部分軟體工程師也是非常根深蒂固的概念,但這行為跟FP是背道而馳的,顯而易見的,OO將函式跟變數封裝在一起是有它的價值的,但是要讓一段程式採用FP設計就必須捨棄某些OO特徵了。
這裡並不是說採用FP之後就無法貫徹OO了,這兩者其實是可以一起使用的武器,沒有人會嫌自己武器太多的


不能宣告為const的成員函式在FP定義上就已經不純了,因為這種函式會改變物件的狀態,也不是執行緒安全的,這種讓物件狀態漸漸失控的設計顯然是bug的主要來源。


如果被C++隱藏的物件指標"this"不算參數的話,宣告為const的成員函式在技術上也算是純函式。但是當物件規模大到讓成員變數用起來像全域變數時,純成員函式的好處會被埋沒。建構子也可以寫成純函式,而且最好都這麼寫,寫成一種輸入參數然後回傳物件的純函式。


就策略上,你可以用FP的思維來使用物件,也許還需要改一下介面,在id Software工作的時候,我們有個使用長達十年的向量類別叫做idVec3,它有個能將自己標準化的成員函式( void idVec3::Normalize(); ),但卻沒有一個同功能的全域函式( idVec3 Normalized(); )來產生標準化的向量類別。很多字串容器也是用類似的設計,它們修改自己的內容,而不是回傳一個修改過的副本,例如ToLowerCase()、StripFileExtension()等等。
考量到記憶體的配置時間,直接重複利用原本的記憶體是合理的,只是你必須確定該記憶體已經沒其他人在用了,才能回收使用



性能影響

絕大部分情況下,直接修改記憶體的資料是程式執行效率最高的做法,而且可以避免浪費效能。但是這只不過是理論上的空想罷了,現實中我們總是選擇犧牲效能來換取開發效率。


使用FP會導致更多資料複製行為,在一些情況下,基於性能考量FP反而是錯誤的策略。舉個極端的例子,你如果寫個用來改圖的純函式,它接受整張圖片作為參數複製進來,然後改好之後回傳改好的全新圖片,千萬別這麼做。


回傳實體變數是FP的編程風格,但是依賴編譯器做回傳值最佳化會有性能上的疑慮,改成傳遞參考來輸出複雜的資料結構可以避開這問題。但是這又帶來新的問題,你就算加上const關鍵字也無法讓回傳值遵守單賦值(註13)。
這裡我不懂為何參考加上const關鍵字無法遵守單賦值,另外C++11新增了std::move()這樣的工具,有機會降低傳遞變數時的開銷


在很多情況下會傾向更改結構變數中的某個成員而不是寫一份新的結構,但這會失去執行緒安全性,不該輕易這麼做。但list這麼做倒是挺合理的,遵守FP規則的list用法一樣是複製一份新list回傳,原本的list則原封不動。真正的FP語言會有特別的實作來實現這功能,所以沒有聽起來那麼嚴重,但是C++的容器也這麼做可就慘了。
這邊的list不知道該翻成什麼,可能是FP的專有名詞吧 



這裡有個可以緩頰的好理由,那就是如今追求執行效率都是針對平行運算的程式設計,相較於單執行緒程式,多執行緒就算是最佳化也通常需要更多的複製、合併行為,所以相較之下代價變小了,換來的好處是複雜度的降低、正確性的提升。


當你開始思考如何讓遊戲世界的所有角色同時動作時,你會馬上陷入因為採用物件導向而產生的多執行緒難題。也許可以規定所有物件都只能讀取全域狀態不能進行寫入,然後在繪圖迴圈跑完一圈的時候去讀取更新過的全域狀態,嘿!給我等一下...
因為大家都唯讀的話就沒有人可以去更新狀態了



能做的事

調查你程式中比較有規模的函式,追蹤所有跟它們有關的外部狀態以及所能造成的影響,即使你根本沒用這函式做什麼事情都還是會寫出一份龐大的註解。如果最後發現這函式的副作用居然還能影響螢幕畫面,那你可以舉雙手投降然後宣稱這函式已經算超自然現象了。


你的下一個任務是從源頭開始思考程式真正的運算結果,整理輸入的參數資料然後傳給一個純函式處理,接下來用這純函式的回傳值做點什麼。

當你除錯的時候,多留意背地裡變化的狀態跟隱藏參數在做什麼。

修改你的類別實作,讓它可以回傳一份新的複製品而不是修改自己的內容,試著把每個非累加變數都宣告為const。

其他參考資料:

http://www.haskell.org/haskellwiki/Introduction

http://lisperati.com/

http://www.johndcook.com/blog/tag/functional-programming/

http://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf

http://channel9.msdn.com/Shows/Going+Deep/Lecture-Series-Erik-Meijer-Functional-Programming-Fundamentals-Chapter-1

http://www.cs.utah.edu/~hal/docs/daume02yaht.pdf

http://www.cs.cmu.edu/~crary/819-f09/Backus78.pdf

http://fpcomplete.com/the-downfall-of-imperative-programming/


註13:單賦值(single assignment),把變數宣告成const就能符合單賦值,因為能防止不小心又對變數賦值。


讀後感:

靠近底層的程式會跟裝置緊密結合,而裝置就是一個會記住設定的狀態了,互動程式也一定需要留住許多外部輸入的狀態,所以遊戲程式有很多地方不能實施FP,但如同John Carmack所言,能用FP就盡量採用。

FP其實並不是用來批評、取代OO的,但我覺得玩OO玩到走火入魔的人剛好可以學FP來均衡一下,而且藉此檢討一下自己的OO有哪裡寫的不好,例如物件內部保存的狀態應該越少越好,這樣變化較少,也比較容易維護測試。物件跟物件之間的瓜葛應該越少越好,互動上越清晰越好,別讓物件背著你做出超出預期的行為。懂OO的缺點就會懂FP的優點。

別認為C語言會比物件導向的C++更適合實現FP,純函式會將其他函式做包裝再回傳,這種事要用boost::function才做得到(C++11的匿名函式更加適合實踐),C++其實比C更適合FP。