冒號(hào)和他的學(xué)生們
——程序員提高班紀(jì)事
- 泛型范式
算法是脊，數(shù)據(jù)是肉；思想是雞，結(jié)論是蛋 ——題記
冒號(hào)重新開講：“你們會(huì)不會(huì)經(jīng)常遇到這種情景：一遍又一遍地寫著相似的代碼，有心將其歸并，卻因種種原因無法踐行。”
逗號(hào)心有戚戚焉道：“是啊，有時(shí)明明兩個(gè)函數(shù)的實(shí)現(xiàn)幾乎一模一樣的，就因?yàn)槟承﹨?shù)不匹配，無法合而為一。”
“有一種編程范式可以解決這個(gè)問題，它打破了不同數(shù)據(jù)結(jié)構(gòu)之間的壁壘，讓你的代碼不再臃腫，這——就是泛型編程。”冒號(hào)的語調(diào)和說辭不免令人聯(lián)想到電視上的減肥廣告，“Generic
Programming，簡稱GP，其基本思想是：將算法與其作用的數(shù)據(jù)結(jié)構(gòu)分離，并將后者盡可能泛化，最大限度地實(shí)現(xiàn)算法重用。這種泛化是基于模板的參數(shù)多態(tài)（parametric
polymorphism），相比OOP基于繼承的子類型多態(tài)（subtype polymorphism），不僅普適性更強(qiáng)，而且效率也更高。這不能不說是一種異數(shù)——我們知道，普適性往往是以效率為代價(jià)的。GP最著名的代表是C++中的STL，其后亦為Java，C#等所吸納。此外，一些函數(shù)式語言如Ocaml、Standard ML、Generic
Haskell等也支持GP。”
冒號(hào)寫下兩段代碼——
C++（泛型編程）：
template <typename T>
T max(T a, T b) // 求出兩個(gè)數(shù)中的較大者
{
return (a > b) ? a : b;
}
C（宏定義）：
#define max(a,b) ((a) > (b) ?
(a) : (b))
“求兩個(gè)數(shù)中的較大值是經(jīng)常遇到的問題。”冒號(hào)解說著，“對(duì)于靜態(tài)類型語言來說，若參數(shù)類型不同，即使函數(shù)體相同也不能合為一體。如果語言不支持重載（overload），還可能出現(xiàn)maxInt、maxLong、maxFloat、 maxDouble之類的函數(shù)名，冗贅而丑陋。盡管在C中可用宏定義來實(shí)現(xiàn)，但無法保證類型安全，而C++模板則兼顧類型安全和代碼重用，并且由于是在編譯期間展開的，效率上也不損失。不止于此，C++支持運(yùn)算符重載，除數(shù)值類型外，一切定義了‘>’ 運(yùn)算的數(shù)據(jù)類型均可調(diào)用max函數(shù)，真是一舉N得，N趨向無窮大啊！”
冒號(hào)邊說邊比劃，夸張的語氣和手勢逗得大家都笑了。
引號(hào)提出疑問：“Java的一切對(duì)象都是Object，將所有參數(shù)都換成Object類型，豈不也是一種泛化？”
冒號(hào)答道：“首先，基本類型如int，float等不是Object的子類，雖然Java
新增了自動(dòng)裝拆箱（autoboxing/unboxing）的功能，但要付出性能的代價(jià)。更重要的是，這將不可避免地需要類型強(qiáng)制轉(zhuǎn)換，喪失了靜態(tài)類型語言的優(yōu)勢，為Bug大開方便之門。這也是Java最終引入模板的原因，雖然有些姍姍來遲。類似地，C/C++中的通用指針void *也有類型安全問題。”
句號(hào)發(fā)表他的看法：“泛型雖好，似乎只是某些局部才用到的技術(shù)，不具有前面幾種范式的滲透性。”
冒號(hào)聽罷不語，返身在黑板上寫下幾道題——
1．從一個(gè)整數(shù)數(shù)組中隨機(jī)抽取十個(gè)數(shù)，對(duì)其中的素?cái)?shù)求和
2．將一個(gè)無序整數(shù)集中所有的完全平方數(shù)換成其平方根
3．從學(xué)生成績表中，列出門門都及格且平均分在70分以上的學(xué)生名單
4．在一個(gè)著色二元樹中，將所有的紅色結(jié)點(diǎn)涂成藍(lán)色
5．將一個(gè)字符串從倒數(shù)第三個(gè)字符開始反向拷貝到另一個(gè)字符串中
6．每從標(biāo)準(zhǔn)輸入讀取一個(gè)非數(shù)字的字符，于標(biāo)準(zhǔn)輸出打印‘請(qǐng)輸入數(shù)字’
句號(hào)暗忖，不過是些常規(guī)題嘛。不料冒號(hào)的問題卻出人意表：“請(qǐng)問它們之間有何共同之處？能否共享一段代碼？”
見眾人緘默已久，冒號(hào)接著投影出一段代碼——
template <class Iterator, class
Act, class Test>
void process(Iterator begin,
Iterator end, Act act, Test test)
// 對(duì)容器中在給定范圍內(nèi)（即起于begin止于end）所有滿足給定條件的元
//素（即test（元素）==true）進(jìn)行處理（即act（元素））
{
for ( ; begin != end;
++begin) // 從頭至尾遍歷容器內(nèi)元素
if (test(*begin)) act(*begin); // 若當(dāng)前元素滿足條件，則對(duì)其采取行動(dòng)
}
“STL有三要素：算法（algorithm）、容器（container）和迭代器（iterator）。容器是數(shù)據(jù)的集合，可理解為抽象的數(shù)組；迭代器是算法與容器之間的接口，可理解為抽象的指針或者游標(biāo)。”冒號(hào)講述道，“算法串聯(lián)數(shù)據(jù)，如脊貫肉；數(shù)據(jù)實(shí)化算法，如肉附脊。只有抽象出表面的數(shù)據(jù)，算法的脊梁才能顯現(xiàn)。以上幾題看似風(fēng)馬牛不相及，若運(yùn)用泛型思維，便可發(fā)現(xiàn)它們的共性：對(duì)指定集合中滿足指定條件的元素進(jìn)行指定處理。用模板語言，寥寥數(shù)行即勾勒完畢。”
問號(hào)詫異道：“相比前面的max模板，這里連元素的數(shù)據(jù)類型T都不見了？”
冒號(hào)回答：“元素被容器封裝了。”
問號(hào)追問：“可這里連容器也看不到啊？”
冒號(hào)料有此問：“容器通過它的迭代器參與算法。”
句號(hào)豁然開朗：“通過模板，泛化了容器——可以是數(shù)組、列表、集合、映射、隊(duì)列、棧、字符串等等；泛化了元素——可以是任何數(shù)據(jù)類型；泛化了處理方法和限定條件——可以是任何函數(shù)。”
冒號(hào)提醒道：“補(bǔ)充兩點(diǎn)：處理方法和限定條件不限于函數(shù)，還可以是函子（Functor）——自帶狀態(tài)的函數(shù)對(duì)象；另外還有一個(gè)隱蔽的泛化：迭代器——可以從前往后移動(dòng)，可以從后往前移動(dòng)，可以隨機(jī)移動(dòng)，也可以按任意預(yù)先定義的規(guī)律移動(dòng)。”
嘆號(hào)由衷感嘆：“果然強(qiáng)悍啊！”
逗號(hào)倒也心細(xì)：“最后一題中標(biāo)準(zhǔn)輸入也算容器嗎？”
“為什么不呢？只要一個(gè)對(duì)象配備了迭代器，它就算容器。I/O流上就有現(xiàn)成的迭代器，當(dāng)然你也可以自行定制。”冒號(hào)目光轉(zhuǎn)向句號(hào)，“現(xiàn)在還有人說泛型編程滲透性不強(qiáng)嗎？”
句號(hào)腆然一笑。
“這只是泛型編程的冰山一角。重要的是，我們不是在玩弄花哨的技巧，而是在用一種新的視角去審視問題。”冒號(hào)總結(jié)道，“泛型編程是算法導(dǎo)向（Algorithm-Oriented）的，即以算法為起點(diǎn)和中心點(diǎn)，逐漸將其所涉及的數(shù)據(jù)結(jié)構(gòu)內(nèi)涵模糊化、外延擴(kuò)大化，從而擴(kuò)展算法的適用范圍。這非常類似數(shù)學(xué)思維——當(dāng)數(shù)學(xué)家證明完一個(gè)定理后，總會(huì)試圖在保持核心思想的前提下，盡可能地放寬題設(shè)，增強(qiáng)結(jié)論，從而推廣定理。外行人以為數(shù)學(xué)定理最重要，其實(shí)數(shù)學(xué)思想才是數(shù)學(xué)的精髓，在數(shù)學(xué)家眼里，思想是雞，結(jié)論是蛋。這也無怪乎STL會(huì)出自一位學(xué)數(shù)學(xué)的人之手了。”
新版請(qǐng)見：冒號(hào)課堂§3.1：泛型范式