特化，圖靈完備性，元編程 C++的模板是支持特化的，這就給了它實(shí)現(xiàn)編譯期控制結(jié)構(gòu)的可能性，進(jìn)而帶來(lái)了一個(gè)圖靈完備的子語(yǔ)言。模板特化的引入原本只是為了效率目的——針對(duì)不同的類型提供不同的實(shí)現(xiàn)。但后來(lái)卻被發(fā)現(xiàn)能夠?qū)崿F(xiàn)編譯期的if/else和遞歸等控制結(jié)構(gòu)。 模板元編程最初由Erwin Unruh在1994年的一次會(huì)議上提出；當(dāng)時(shí)他寫了一個(gè)程序，在編譯錯(cuò)誤里面打印出一個(gè)素?cái)?shù)序列。這個(gè)事件在C++歷史上的地位就仿佛哥倫布發(fā)現(xiàn)新大陸。用Bjarne Stroustrup的話來(lái)說(shuō)就是當(dāng)時(shí)他當(dāng)時(shí)和其他幾個(gè)人覺(jué)得太神奇了。實(shí)際上，這個(gè)事情正標(biāo)志了C++模板系統(tǒng)的圖靈完備性被發(fā)現(xiàn)；后來(lái)Todd Veldhuizen寫了一篇paper，用C++模板構(gòu)建了一個(gè)元圖靈機(jī)，從而第一次系統(tǒng)證明了C++模板的圖靈完備性。接下來(lái)的事情就順理成章了——一些ad hoc的模板元編程技巧不斷被發(fā)掘出來(lái)，用于建造高效、高適應(yīng)性的通用組件。最終，David Abrahams編寫了boost庫(kù)中的基本組件之一：Boost.MPL庫(kù)。Boost.MPL以類型和編譯期常量為數(shù)據(jù)，以模板特化為手段，實(shí)現(xiàn)了一個(gè)編譯期的STL。你可以看到常見(jiàn)的vector，你可以看到transform算法，只不過(guò)算法操縱的對(duì)象和容器存放的對(duì)象不再是運(yùn)行期的變量或?qū)ο?，而是編譯期的類型和常量。想知道模板元編程是如何用在庫(kù)構(gòu)建中的，可以打開(kāi)一個(gè)Boost的子庫(kù)（比如Boost.Tuple或Boost.Variant）看一看。 然而，畢竟C++的模板元編程是一門被發(fā)現(xiàn)而不是被發(fā)明的子語(yǔ)言。一方面，它在構(gòu)建泛型庫(kù)的時(shí)候極其有用。然而另一方面，由于它并非語(yǔ)言設(shè)計(jì)初始時(shí)考慮在內(nèi)的東西，所以不僅在語(yǔ)法上面顯得不那么first-class（比較笨拙）；更重要的是，由于本不是一個(gè)first-class的語(yǔ)言特性，所以C++編譯器并不知道C++元編程的存在。這就意味著，比如對(duì)下面這樣一個(gè)編譯期的if/else設(shè)施[8]： template<bool b, class X, class Y> struct if_ { typedef X type; // use X if b is true }; template<class X, class Y> struct if_<false,X,Y> { typedef Y type; // use Y if b is false }; typedef if_<(sizeof(Foobar)<40), Foo, Bar>::type type; 編譯器并沒(méi)有真的去進(jìn)行if/else的分支選擇，而是按部就班毫不知情地進(jìn)行著模板的特化匹配。如果遇到Boost.MPL這樣的模板元編程非常重的庫(kù)，就會(huì)嚴(yán)重拖累編譯速度，編譯器進(jìn)行了一重一重的特化匹配，實(shí)例化了一個(gè)又一個(gè)的模板實(shí)例，就是為了去獲取里面定義的一個(gè)typedef，完了之后中間所有實(shí)例化出來(lái)的模板實(shí)例類型全都被丟棄[9]。 模板元編程最全面深入的介紹是Boost.MPL庫(kù)的作者David Abrahams的《C++ Template Metaprogramming》，其中的樣章（第三章）[10]對(duì)模板元編程作了一個(gè)非常高屋建瓴的概覽[11]。 關(guān)于模板元編程，需要提醒的是，它并不屬于“大眾技術(shù)”。日常編程中極少需要用到元編程技巧。另一方面，C++模板里面有大量ad hoc的技巧，如果一頭扎進(jìn)去的話，很容易只見(jiàn)樹(shù)木不見(jiàn)森林，所以需要提醒初學(xué)者的是，即便要學(xué)習(xí)，也要時(shí)刻保持“高度”，始終記得元編程的意義和目的，這樣才不至于迷失在無(wú)窮無(wú)盡的語(yǔ)言細(xì)節(jié)中。 C++09——進(jìn)化 泛型編程在C++中取得了工業(yè)程度上的成功，得益于其高效性和通用性。但同時(shí)，在經(jīng)過(guò)了近十年的使用之后，C++模板，這個(gè)作為C++實(shí)現(xiàn)泛型的機(jī)制的缺點(diǎn)也逐漸暴露出來(lái)。比如其中對(duì)于初學(xué)者最嚴(yán)重的一個(gè)問(wèn)題就是在使用一個(gè)模板庫(kù)時(shí)常常遇到無(wú)法理解的編譯錯(cuò)誤，動(dòng)輒長(zhǎng)達(dá)上K字節(jié)。這些編譯錯(cuò)誤很容易把一個(gè)初學(xué)者嚇走。究其本質(zhì)原因，為什么編譯器會(huì)報(bào)出令人難以卒讀的編譯錯(cuò)誤，是因?yàn)樵诰幾g器的眼里，只有類型，而沒(méi)有“類型的類型”。比如說(shuō)，迭代器就是一個(gè)類型的類型，C++里面也把它稱為“概念”（Concept）。例如，std::sort要求參數(shù)必須是隨機(jī)訪問(wèn)迭代器，如果你一不小心給了它一個(gè)非隨機(jī)訪問(wèn)的迭代器，那么編譯器不是抱怨“嘿！你給我的不是隨機(jī)訪問(wèn)迭代器”，而是抱怨找不到某某重載操作符（典型的比如operator+(int)）。因?yàn)樵诰幾g器眼里，沒(méi)有“迭代器”這么個(gè)概念，這個(gè)概念只存在于程序員腦子里和STL的文檔里。為了幫助編譯器產(chǎn)出更友好的信息（當(dāng)然，還有許多非常重要的其它原因[12]），C++09將對(duì)“類型的類型”加入first-class的支持，其帶來(lái)的眾多好處會(huì)將C++中的泛型編程帶向一個(gè)新的高度：更友好、更實(shí)用、更直觀。 此外，C++的模板元編程尚沒(méi)有first-class的語(yǔ)言支持，一方面是因?yàn)槠溥\(yùn)用不像一般的模板編程這么廣泛，因而沒(méi)有這么緊急。另一方面，C++09的時(shí)間表也等不及一個(gè)成熟的提案。如果以后模板元編程被運(yùn)用得越來(lái)越廣泛的話，那first-class的語(yǔ)言支持是難免的。 總結(jié) 本文對(duì)C++模板，以及C++模板所支持的泛型編程作了一個(gè)概覽。著重介紹了泛型編程誕生的原因，泛型編程的過(guò)程和意義，與其它抽象手段的比較。并對(duì)C++中的模板元編程做了一些介紹。最后介紹了C++模板在C++09中的增強(qiáng)。 [1] B. Stroustrup: A History of C++: 1979-1991. Proc ACM History of Programming Languages conference (HOPL-2). March 1993. [2] http://en.wikipedia.org/wiki/Alexander_Stepanov [3] http://www.cs.rpi.edu/~musser [4] 實(shí)際上，STL的區(qū)間概念被證明是一個(gè)不完美的抽象。你有沒(méi)有發(fā)現(xiàn)，要傳遞一個(gè)區(qū)間給一個(gè)函數(shù)，如std::sort，你需要傳遞兩個(gè)參數(shù)，一個(gè)是區(qū)間的 開(kāi)頭，一個(gè)是區(qū)間的末尾。這種分離的參數(shù)傳遞方式被證明是不明智的，在一些場(chǎng)合會(huì)帶來(lái)使用上不必要的麻煩。比如你想迭代一組文件，代表這組文件的區(qū)間由一 個(gè)readdir_sequence函數(shù)返回，由于要分離表達(dá)一個(gè)區(qū)間，你就必須寫： readdir_sequence entries(".", readdir_sequence::files); std::for_each(entries.begin(), entries.end(), ::remove); 如果你只想遍歷這個(gè)區(qū)間一次的話，你也許不想聲明entries這個(gè)變量，畢竟多一個(gè)名字就多一個(gè)累贅，你也許只想： std::for_each(readdir_sequence(".", readdir_sequence::files), ::remove); 下一代C++標(biāo)準(zhǔn)（C++09）會(huì)解決這個(gè)問(wèn)題（將區(qū)間這個(gè)抽象定義為一個(gè)整體）。 [5] 當(dāng)然，語(yǔ)言并沒(méi)有規(guī)定模板實(shí)例化的底層實(shí)現(xiàn)一定要是對(duì)每組參數(shù)類型組合實(shí)例化一個(gè)版本出來(lái)。但目前的實(shí)現(xiàn)，這種方案是最高效的。完全消除了抽象懲罰。另一 方面，One size fit all的方案也不是不可行，但總會(huì)有間接調(diào)用。這也正說(shuō)明了靜態(tài)類型系統(tǒng)的一個(gè)典型優(yōu)點(diǎn)：幫助編譯器生成更高效的代碼。 [6] http://en.wikipedia.org/wiki/Don't_repeat_yourself [7] http://en.wikipedia.org/wiki/Duck_typing [8] 摘自Bjarne Stroustrup的paper：Evolving a language in and for the real world: C++ 1991-2006 [9] 也正因此，D語(yǔ)言加入了語(yǔ)言直接對(duì)模板元編程的支持，比如真正工作在編譯期的static if-else語(yǔ)句。 [10] http://www.boost-consulting.com/mplbook/ [11] 第三章的翻譯見(jiàn)我的blog：《深度探索元函數(shù)》http://blog.csdn.net/pongba/archive/2004/09/01/90642.aspx [12] 由于篇幅原因，這里無(wú)法展開(kāi)詳述Concept對(duì)C++泛型編程的其它重要意義，有興趣的可以參見(jiàn)我的一篇blog：《C++0x漫談系列 之：Concept! Concept!》。http://blog.csdn.net/pongba/archive/2007/08/04/1726031.aspx |
聯(lián)系客服
