第四課 重溫范式（1）
課前導讀
本課對函數式編程與邏輯式編程作了更詳細的展開，並對前面介紹的范式進行了匯總分析，最後用情景式編程貫穿所學范式。
本課共分四節——
函數范式
邏輯范式
匯總范式
情景范式
4.1 函數范式——精巧的數學思維
知不知，上；不知不知，病 ——《老子·德經》
關鍵詞：編程范式,函數式編程,Haskell,Groovy
摘要： 再談函數式編程
？提問
掌握編程范式對編程語感的提高有什麼作用？
為什麼聲明式程序一般比命令式程序更簡潔？
函數式編程有哪些特征？為何簡潔而不失強大？
函數的無副作用性的意義何在？
相比過程式和OOP，函數式編程的弱點是什麼？
：講解
眾人落座之後，冒號鳴鑼開場：“上兩節課為大家介紹了多種編程范式，雖未將所有類型盡囊其中，但最具代表性的均在其列。我們也不必貪多求全，俗話說得好：貪多嚼不爛啊。現在給大家一個知識反刍的機會。”
問號正感求之不得：“總算可以喘口氣了。我們就像觀光客，被導游帶著從一個景點趕往另一景點。一天下來，雖然大開眼界，但都是走馬觀花，無法充分領略各地的風光。”
“你說得沒錯，我就是那個不近情理的導游。”冒號哈哈一笑，“類似時下流行的歐洲N國M日游，大部分人的收獲就是一堆照片和日漸模糊的記憶。不出多日，如果不看標注，八成連照片上的背景是在法國還是在意大利都分不清了。”
逗號頗有同感：“差不多，目前我的收獲就是一堆幻燈片和似懂非懂的概念。”
冒號料有此果：“這一點也不奇怪。別說幾天游一個國家，單一個羅馬，沒有一個月是不可能深入了解的。至於編程范式，單一個OOP，沒有兩年以上的實踐和思考，是難以真正領會其精髓的。”
歎號深表懷疑：“OOP需要兩年以上才能領會？！”
“那還得看你是否有足夠的勤奮和悟性。”冒號加強了語氣，“前面說過，單靠記憶只能觸及知識之表，單靠練習只能深入知識之裡，唯有培養方能滲透知識之根。編程范式正處知識的根部，你們又怎能奢望只聽幾堂課即豁然貫通呢？”
引號表達自己的感受：“雖然學了不少東西，但也存了不少疑惑，擱在心裡有點不舒服。”
“我明白你的意思。凡事追根究底是一種良好的學習習慣，也是一種可貴的學習精神。” 冒號表示理解和肯定，“但學習如打仗，除了要有直線式的縱深攻擊，還要有曲線式的迂回包抄。回顧我們中學的課堂，往往是每引入一個概念或理論，便圍繞其作深入的學習和反復的練習。在此過程中的種種疑惑，隨著學習的深入都會煙消雲散。這樣穩扎穩打、層層推進，學得扎實，心裡也踏實。但這種方法並不總是最好的，尤其在面臨動態的、開放的知識體系時，難免左支右绌。為此，我們必須學會適度地容忍無知。請注意，容忍無知不是放任無知，而是一種學習的技巧，讓無知成為求知的動力而不是障礙。容忍無知能使我們既不沮喪氣餒，也不急於求成。在學習時不妨略過一些細節或難點，先概覽全貌以獲取感性認識，然後在逐步積累中升華為理性認識。要而言之，我們不僅需要強調鑽勁和深度的‘釘子精神’，還需要強調磨功和廣度的‘刨子精神’。我一口氣兜售這麼多編程范式，就是為了刺激大家求知欲，同時為大家進行第一道刨磨。”
引號得到一些安慰：“看來今後我們還會故地重游的。”
“不僅會重游，而且會‘深度游’。” 冒號肯定地說，“此番我們一路行色匆匆，若能感受到途中景色帶來的感官沖擊，便算是不枉此行了。其實，把編程范式類比旅游景點並不十分准確，或許比作當地的風俗文化更確切些。”
句號立刻會意：“景點是具體的，背後的風俗文化是抽象的；編程語言是具體的，背後的編程范式是抽象的。”
“此乃其一。”冒號右手伸出食指，“其二，如果不了解景點的歷史文化和風俗人情，僅僅滿足於表面的奇觀異景，一切很快便會淡忘。比如說，你若不了解聖經文化、不了解文藝復興史，則歐洲之行至多只是視覺的盛宴，而非文化的洗禮，收獲將是有限的，印象將是膚淺的。同樣，如果你不了解編程范式，那麼眼中的編程語言只是語法、語義、核心庫、規范等組成的集合，寫出的代碼雖能編譯、能工作，卻會顯得生硬、別扭。就像中式英語，語法正確、表達也正確，可就是不正宗、不地道。其症結我們在第一節課中已經提過了，即所謂的語感缺失。”
問號實話實說：“可我還是不明白編程范式如何提高我們的編程語感。”
“那就讓我們再說說范式吧。”冒號並不著急，“范式可以粗略理解為模范、模型、模式、風格、流派等等。軟件中的范式除了編程范式外，還有架構范式[1]、數據庫范式[2]等。比如，對象導向式（Object-Oriented）可以應用於編程、架構和數據庫中，分別成為OOP（Object-Oriented Programming）、OOA（Object-Oriented Architecture）和OODB（object-oriented database）；類似地，事件驅動式（Event-Driven）可以是一種編程范式，可以是一種架構模型，也可以是一種設計模式。總之，每種范式都代表著一套獨特而有效的解決問題的思想和方法。掌握范式對編程語感的提高至少有兩層作用：首先，編程語言的語法、語義等都是從編程范式的樹根衍生而出的枝葉，把握了這種脈絡和節奏，代碼才會如音樂舞蹈般韻律有致；其次，每種范式擅長的問題領域不盡相同，只有博聞廣識，方可揚長避短，程序才會如行雲流水般流暢自然。”
逗號添油加醋：“武功練至化境，一定是博采眾長，就像楊過融合了東邪、西毒、南帝、北丐、中神通等各派武功，才能隨心所欲地打出黯然銷魂掌來。”
提起武俠人物，眾人俱是逸興遄飛，哪能體會到半點黯然消魂之傷？
冒號道：“天下之理，殊途同歸。我們停止玄玄之論，用實例來說明吧。誰來介紹一下快速排序法(quicksort)？”
眾人飛舞的思緒漸漸收斂，終於由引號作答：“快速排序法的思想是：在列表中找一個基准元素，將所有小於它的元素劃歸一個子列，置於其前；將所有大於等於它的元素劃歸另一子列，置於其後。然後遞歸地對前後兩個子列作同樣處理，直至最終。”
“很好，讓我們用Java來實現一下該算法。”冒號顯示出一段代碼——
/** 快速排序法的Java實現 */
public class Sorter
{
public static <T extends Comparable<? super T>> void qsort(T[] list)
{
qsort(list, 0, list.length - 1);
}
private static <T extends Comparable<? super T>> void qsort(T[] list, int low, int high)
{
if (low >= high) return;
int i = low - 1, j = high + 1;
T pivot = list[low]; // 基准元素
for ( ; ; )
{
do { ++i; } while (list[i].compareTo(pivot) < 0);
do { --j; } while (list[j].compareTo(pivot) > 0);
if (i >= j) break;
// 交換
T tmp = list[i]; list[i] = list[j]; list[j] = tmp;
}
// 找到分割點j，遞歸
qsort(list, low, j);
qsort(list, j + 1, high);
}
}
“請問這裡用到了哪些編程范式？”冒號提問。
歎號心想，有何難哉？遂答：“既然是用Java實現的，自然少不了OOP。同時為了使算法更具普適性，還用到了泛型編程。”
“你好像忘記了最重要的過程式，反倒是OOP的色彩極淡。”冒號顯然不滿意他的答案。
歎號不解：“不是說Java是100%的OOP語言嗎？”
冒號頗為不屑：“不要輕信這種浮淺之論。且不說Java的基本類型（primitive type）不屬於類（class），本就不是100%的OOP，即使是100%的OOP，那與過程式也不矛盾啊。此例中的Sorter類連一個實例成員（instance member）也沒有，唯一與OOP沾邊的是作為interface的Comparable，在C中也可用函數指針代替。如果不考慮泛型式的特征，本例無論用Java還是用C，並沒有本質差別。事實上，對於這類純算法的問題，OOP范式本無太多用武之地。換句話說，quicksort雖然是通過以OOP著稱的Java來實現的，但用的主要還是過程式的思想和方法。”
問號趕緊問道：“還能用其他范式來實現嗎？”
此問正合冒號之意：“我們改用純函數式語言Haskell來試試——”
-- 快速排序法的Haskell實現
qsort :: (Ord a) => [a] -> [a]--函數聲明
qsort[] = [] --遞歸終點
qsort(pivot : rest) = qsort[x| x <- rest, x < pivot] --對前面的子列遞歸
++ [pivot]
++ qsort[x| x <- rest, x >= pivot] --對後面的子列遞歸
歎號幾不能信：“竟然可以如此精煉？”
“上面的Java代碼很難再精簡了，但與Haskell代碼相比還是太冗長了。後者省去了所有的賦值、迭代和流程控制，只有單純的遞歸，反映了典型的函數式特征。”冒號解說著，“鑒於你們對Haskell不太熟悉，我稍微解釋一下。第一步，聲明函數類型[3]：同類型列表之間的變換，其中Ord可類比Java中的Comparable，以保證列表元素之間能進行比較；第二步，聲明遞歸終點：空列排序後仍是空列；第三步，描述遞歸原則：基准元素pivot與剩余子列rest進行排序後的列表，正是將小於基准的子列和超過基准的子列分別排序，中間插入基准元素後的結果。”
句號思有所得，不禁喜形於色：“我明白了，這兩段代碼生動地反映了命令式編程與聲明式編程之間的差別：前者需要指定計算的過程，後者只需指定計算的原則。一個著重微觀的細節，一個著重宏觀的方向，自有繁簡之別。”
冒號亦有所慰：“非常好！類似的話我以前也說過，但你們自己說的才是真正的收獲啊。我們還提過，過程式與函數式的差別同時也是機器思維與數學思維的差別。不妨對比Haskell表達式與數學中的集合表達式，它們是多麼地相近！”
黑板上出現兩行式子——
數學表達式： {x| x ∈ rest, x < pivot}
Haskell表達式：[x| x <- rest, x < pivot]
逗號仔細打量著：“嗯，的確像，跟哥倆似的，連符號<-都是仿照集合屬於符∈的。”
“還有另一種表達方法。”冒號又添加了一行——
Haskell表達式2：(filter (< pivot) rest)
“雖然與前一表達式的簡潔度相差無幾，但可讀性更強。filter即是過濾，將列表rest中的元素進行篩選，條件是小於基准元素。”冒號講解道。
問號略感迷惑：“（< pivot）的用法看起來有點怪異。”
“它是一個函數，也是filter的第一個參數，用來判斷第二個參數rest的元素是否合格，即 < pivot。這體現了函數式的一個重要特征：函數是頭等公民（first-class citizen）[4]——可作為傳遞參數、可作為表達式的值、可嵌入數據結構、也可與某變量綁定，與普通的基本數據類型毫無二致。這是函數式編程簡潔而強大的重要根源。”冒號細加解釋，“大家還記得上節課談到的回調函數吧？callback無非是將函數作為參數來傳遞，本質上是將代碼當數據來使用，回調機制的巨大威力均拜此高級用法所賜。”
眾人又一段筋脈被打通了。
引號提出一個很實際的問題：“函數式編程的確很酷，可Java並不支持。如果采用Haskell之類的函數式語言，會不會帶來系統集成上的困難？”
冒號打消了他的疑慮：“Java平台下已經集成了不少的支持函數式編程的語言，如JRuby、Jython、Groovy、Scala等，甚至Haskell在JVM下也有相應的Jaskell。其中Groovy與Java的結合最為自然，我們看一下它是如何實現quicksort的——”
/** 快速排序法的Groovy實現 */
def qsort(list) {
if (list.size() <= 1) return list
def pivot = list[0]
return (qsort(list.findAll{x -> x < pivot})
+ list.findAll{x -> x == pivot}
+ qsort(list.findAll{x -> x > pivot}))
}
“雖然比Haskell的代碼略長了些，並且還帶著過程式的烙印，但總體思想還是函數式的。”冒號緊扣本質，“函數式還有一個重要特征：無副作用或盡量減少副作用[5]。所謂無副作用，是指一個函數在被調用前後保持程序的狀態不變。無副作用的函數不會改變非局部變量的值，不會改變傳入的參數，也沒有I/O操作。”
逗號脫口而出：“什麼狀態都不變，那這樣的函數有什麼用？”
冒號不以為奇：“你的這種想法源自根深蒂固的命令式思維。我們曾把命令式程序比作狀態自動機，其運行過程就是在不斷地修改機器的狀態。而函數式程序則是進行表達式變換，一般不會改變變量的值。其實函數式並非完全不改變內存，只不過改變的是棧內存（stack）罷了。換言之，無副作用函數的作用關鍵在於其估值結果，按過程式的說法是返回值。”
逗號如夢初醒。
問號仍有疑問：“藥物最好沒有副作用，函數沒有副作用的好處是什麼？”
冒號嘴一咧：“好處太多了。首先，沒有副作用的函數易於重構、調試和單元測試。其次，代碼有效性與函數順序無關，方便並發處理和優化處理。舉個簡單的例子，計算兩個函數的乘積：f(x) * g(y)。由於無副作用，f(x) 和g(y)的估值過程是獨立的，估值順序也不重要，因此理論上可以對二者並行計算。另外，還可利用惰性計算（lazy evaluation）：如果算出f(x)為零，那麼不用計算g(y)便可知乘積為零了。”
歎號忍不住贊歎：“聽起來真不錯！”
冒號言猶未盡：“最後，沒有副作用的函數是引用透明的（referential transparency），即一個表達式隨時可以用它的值來替換[6]，正如數學中的函數一樣，保證了數學思維的貫徹和運用。”
引號自感獲益頗豐：“前面介紹范式時，覺得函數式最為神秘。現在總算有了些感性認識了。”
冒號道出緣由：“函數式編程不僅有許多獨特的概念和方法，還有很深的數學背景——λ-演算（λ-Calculus）。如果一開始便傾囊相授，你們必會望而卻步，我豈不是打草驚蛇了？”
眾人始覺：老冒原來是在誘敵深入啊。
“盡管函數式有這麼多優點，運算能力從理論上比諸過程式也毫不遜色[7]，但一直沒有成為主流范式，”冒號話鋒一轉，“細究之，至少有兩方面的原因：主觀上，程序員更習慣機器風格的過程式思維和現實風格的OOP思維，不容易接納數學風格的函數式思維；客觀上，函數式語言在表現力和運行效率等方面與過程式和OOP語言也有一定的差距。饒是如此，支持它的語言還是越來越多，其簡潔精巧的特性也為越來越多的人所青睐。它的整體應用雖然主要集中於數學計算、人工智能等領域，但局部應用早已遍地開花了。”
，插語
[1] 如OOA（Object-Oriented Architecture），COA(Component-Oriented Architecture)，SOA(Service- Oriented Architecture) 、EDA（Event-Driven Architecture）等。
[2] 如關系數據庫（relational database）、對象導向式數據庫（object-oriented database）等。
[3] 這一步可省略，但出於對代碼的清晰度以及性能、調試等方面的考慮，最好保留。
[4] 這類函數更數學化的說法是高階函數（higher-order function）。
[5] 沒有副作用的函數式語言被稱為純函數式（purely functional），如Haskell和SISAL；有副作用的被稱為非純函數式（impurely functional），如Lisp和ML。
[6] 這是因為函數的無副作用性保證了相同的輸入一定有相同的輸出。
[7] λ-演算被證明是圖靈完備的。
。總結
學習知識之表須通過記憶，掌握知識之裡須通過練習，滲透知識之根須通過培養。編程范式正是知識之根。
適度地容忍無知也是一種學習技巧。
“釘子精神”固然可貴，“刨子精神”也不可少。
不同的編程范式代表不同的解決問題的思想和方法。不同的編程語言提倡不同的編程范式，並在語法上給予支持。只有掌握范式，才能更合理、更有效地運用編程語言的語法和語義特征，並能針對不同的問題領域使用不同的編程風格，編寫的代碼才會和諧自然、富於美感。
命令式編程需要指定計算的過程，著重微觀的細節；聲明式編程只需指定計算的原則，著重宏觀的方向。因此二者繁簡有別。
在函數式編程中，函數是程序的核心，是頭等公民，一般沒有或很少副作用，同時沒有顯式的內存管理。
由於函數式編程中的函數與基本數據類型平起平坐，故可將代碼作數據用，這是程序既簡潔又強大的原因之一。回調機制采用的正是函數式風格。
無副作用的函數容易重構、調試和測試，便於並發和優化處理，並能貫徹和運用數學思維。
相比過程式和OOP，函數式編程思想過於數學化和抽象化，語言的表現力和運行效率也有所不足。
