第三課 常用范式（1）
課前導讀
這一課介紹了四個常用的編程范式：泛型式、元編程、切面式和事件驅動式。
本課共分四節——
1.泛型范式
2.超級范式
3.切面范式
4.事件驅動
3.1泛型范式——抽象你的算法
以類行雜，以一行萬 ——《荀子•王制篇》
關鍵詞：編程范式,泛型編程,STL,算法
摘要：泛型式編程簡談
？提問
泛型編程有哪些優點？
STL有哪些要素？各自有什麼作用？
泛型編程的泛化對象是什麼？
泛型編程的核心思想是什麼？
：講解
冒號重新開講：“你們會不會經常遇到這樣的情景：一遍又一遍地寫著相似的代碼，有心將其歸並，卻因種種原因無法踐行。”
逗號心有戚戚焉道：“是啊，有時明明兩個函數的實現幾乎一模一樣的，就因為某些參數不匹配，無法合而為一。”
“有一種編程范式可以解決這個問題，它打破了不同數據結構之間的壁壘，讓你的代碼不再臃腫，這——就是泛型編程。”冒號的語調和說辭不免令人聯想到電視上的減肥廣告，“Generic Programming，簡稱GP，其基本思想是：將算法與其作用的數據結構分離，並將後者盡可能泛化，最大限度地實現算法重用。這種泛化是基於模板（template）的參數多態（parametric polymorphism），相比OOP基於繼承的子類型多態（subtype polymorphism），不僅普適性更強，而且效率也更高。這不能不說是一種異數——我們知道，普適性往往是以效率為代價的。如果一定要找出代價的話，那就是其用法稍微復雜一些，可讀性稍微差一些。GP最著名的代表是C++中的STL（Standard Template Library），其後亦為Java，C#等所吸納。此外，一些函數式語言如Ocaml、Standard ML、Generic Haskell等也支持GP。”
冒號寫下兩段代碼——
C++（泛型編程）：
template <typename T>
T max(T a, T b) // 求出兩個數中的較大者
{
return(a > b) ? a : b;
}
C（宏定義）：
#define max(a,b) ((a) > (b) ? (a) : (b))
“求兩個數中的較大值是經常遇到的問題。”冒號解說著，“對於靜態類型語言[1]來說，若參數類型不同，即使函數體相同也不能合為一體。如果語言不支持重載（overload），還可能出現maxInt、maxLong、maxFloat、 maxDouble之類的函數名，冗贅而丑陋。盡管在C中可用宏定義來實現，但無法保證類型安全，而C++模板則兼顧類型安全和代碼重用，並且由於是在編譯期間展開的，效率上也不損失。不止於此，C++支持運算符重載，除數值類型外，一切定義了‘>’ 運算的數據類型均可調用max函數，真是一舉N得，N趨向無窮大啊！”
冒號邊說邊比劃，誇張的語氣和手勢逗得大家都笑了。
引號提出疑問：“Java的一切對象都是Object，將所有參數都換成Object類型，豈不也是一種泛化？”
冒號答道：“首先，基本類型如int，float等不是Object的子類，雖然Java 新增了自動裝拆箱（autoboxing/unboxing）的功能，但要付出性能的代價。更重要的是，這將不可避免地需要類型的強制轉換（explicit Conversion或cast），無法在編譯期間施行嚴格的類型檢查，由此喪失了靜態類型語言的優勢，為bug大開方便之門。這也是Java最終引入模板的原因，雖然有些姗姗來遲。類似地，C/C++中的通用指針void *也有類型安全問題。”
句號發表他的看法：“泛型雖好，似乎只是某些局部才用到的技術，不具有前面幾種范式的滲透性。”
冒號聽罷不語，返身在黑板上寫下幾道題——
1．從一個整數數組中隨機抽取十個數，對其中的素數求和
2．將一個無序整數集中所有的完全平方數換成其平方根
3．從學生成績表中，列出門門都及格且平均分在70分以上的學生名單
4．在一個著色二元樹中，將所有的紅色結點塗成藍色
5．將一個字符串從倒數第三個字符開始反向拷貝到另一個字符串中
6．每從標准輸入讀取一個非數字的字符X，於標准輸出打印‘X不是數字字符’
句號暗忖，這有何難？不過是些常規題罷了。不料冒號的問題卻出人意表：“請問它們之間有何共同之處？能否共享同一段代碼？”
見眾人緘默已久，冒號接著投影出一段代碼——
template <class Iterator, class Act, class Test>
void process(Iterator begin, Iterator end, Act act, Test test)
// 對容器中在給定范圍內（即起於begin止於end）所有滿足給定條件的元
//素（即test（元素）==true）進行處理（即act（元素））
{
for ( ; begin != end; ++begin) // 從頭至尾遍歷容器內元素
if (test(*begin)) act(*begin); // 若當前元素滿足條件，則對其采取行動
}
“STL有三要素：算法（algorithm）、容器（container）和迭代器（iterator）。算法是一系列切實有效的步驟；容器是數據的集合，可理解為抽象的數組；迭代器是算法與容器之間的接口，可理解為抽象的指針或者游標。”冒號講述道，“算法串聯數據，如脊貫肉；數據實化算法，如肉附脊。只有抽象出表面的數據，算法的脊梁才能顯現。以上幾題看似風馬牛不相及，若運用泛型思維，便可發現它們的共性：對指定集合中滿足指定條件的元素進行指定處理。用模板語言，寥寥數行即勾勒完畢。”
問號詫異道：“相比前面的max模板，這兒連元素的數據類型T都不見了？”
冒號回答：“元素被容器封裝了。”
問號追問：“可連容器也看不到啊？”
冒號料有此問：“容器通過它的迭代器參與算法。”
句號豁然開朗：“通過模板，泛化了容器——可以是數組、列表、集合、映射、隊列、棧、字符串等等；泛化了元素——可以是任何數據類型；泛化了處理方法和限定條件——可以是任何函數。”
冒號提醒道：“補上兩點：這裡的處理方法和限定條件不限於函數，還可以是函子（functor）[2]——自帶狀態的函數對象；另外迭代器也被泛化了——可以從前往後移動，可以從後往前移動，可以來回移動，可以隨機移動，可以按任意預先定義的規律移動。”
歎號由衷感歎：“果然強悍無比啊！”
逗號倒也心細：“最後一題中標准輸入也算容器嗎？”
“為什麼不呢？只要一個對象配備了迭代器，它就可以作為容器來對待。I/O流上就有現成的迭代器，當然你也可以自行定制。索性我們來看看這道題的解法吧。”冒號給出了第六題的實現代碼——
#include <iostream>
#include “process.h” // 前述process所在的頭文件
using namespace std;
// 判斷字符是否為非數字字符
bool notDigit(char c)
{
return (c < '0') || (c > '9');
}
// 打印非數字字符
void printNondigit(char c)
{
cout << c << "不是數字字符" << endl;
}
int main()
{
process(istream_iterator<char>(cin), istream_iterator<char>(),
printNondigit, notDigit);
return 0;
}
逗號打量了半天：“這裡完全看不到I/O讀取的過程，也看不到通常的迭代循環，簡潔得難以置信。”
冒號補充道：“不光是代碼簡潔，它還讓人擺脫了底層編碼的細節，在更高更抽象的層次上進行編程設計。”
引號發覺：“開始談起泛型編程時，您特別強調它對數據類型的抽象。現在看起來，它也能對函數進行抽象呢。”
“說得沒錯，條件是被抽象的函數或者方法具有相同的簽名（signature）或接口（interface）。不過別忘了，在C和C++中的函數——准確地說是函數指針——也能作為數據類型。但不管怎樣，這都表明泛型編程不僅能泛化概念，還能泛化行為。”冒號目光轉向句號，“現在還有人認為泛型編程的滲透性不夠強嗎？”
句號腆然一笑。
“這些只是泛型編程的冰山一角。重要的是，我們不是在玩弄花哨的技巧，而是在用一種新的視角去審視問題。”冒號總結道，“泛型編程是算法導向（Algorithm-Oriented）的，即以算法為起點和中心點，逐漸將其所涉及的概念（如數據結構、類）內涵模糊化、外延擴大化，將其所涉及的運算（函數、方法、接口）抽象化、一般化，從而擴展算法的適用范圍。這非常類似數學思維——當數學家證明完一個定理後，總會試圖在保持核心思想的前提下，盡可能地放寬題設，增強結論，從而推廣定理。外行人常以為數學定理最重要，其實數學思想才是數學的精髓。比如舉世皆知的哥德巴赫猜想和費爾馬大定理，人們在攻克它們的過程中產生的新思想、新理論、新方法，已遠遠超過了定理本身的意義。數學家甚至不願這些猜想被過早地解決，怕扼殺了會下金蛋的雞。在他們眼裡，思想是雞，結論是蛋。這也無怪乎STL會出自一位學數學的人之手了。”
“我怎麼覺得更像是出自一位菜場大媽之口呢？”逗號打趣道，“不信你們聽嘛，算法好比脊骨、數據好比豬肉、思想好比母雞、結論好比雞蛋。我沒說錯吧？”。
眾人啞然失笑。
，插語
[1] 靜態類型語言在編譯期間或運行之前施行類型檢查（type checking）。後有詳論。
[2]又稱function object，在C++中指重載了函數調用算符（operator()）的類，在Java中可通過interface來實現。
。總結
泛型編程能打破靜態類型語言的數據類型之間的壁壘，在不犧牲效率並確保類型安全的情況下，最大限度地提高算法的普適性。
STL有三要素：算法、容器和和迭代器。算法是一系列可行的步驟；容器是數據的集合，是抽象化的數組；迭代器是算法與容器之間的接口，是抽象化的指針。算法串聯數據，數據實化算法。
泛型編程不僅能泛化算法中涉及的概念（數據類型），還能泛化行為（函數、方法、運算）。
泛型編程是算法導向的，以算法為中心，逐漸將其所涉及的概念內涵模糊化、外延擴大化，將其所涉及的運算抽象化、一般化，從而提高算法的可重用性。
