STL之父訪(fǎng)談錄
翻譯者 : myan
出處: http://www.sgi.com/technology/stl
1995年3月，dr.dobb‘s journal特約記者, 著(zhù)名技術(shù)書(shū)籍作家al stevens采訪(fǎng)了stl創(chuàng )始人alexander stepanov. 這份訪(fǎng)談紀錄是迄今為止對于stl發(fā)展歷史的最完備介紹, 侯捷先生在他的stl有關(guān)文章里推薦大家閱讀這篇文章. 因此我將該文全文翻譯如下:
q: 您對于generic programming進(jìn)行了長(cháng)時(shí)間的研究, 請就此談?wù)?
a: 我開(kāi)始考慮有關(guān)gp的問(wèn)題是在7o年代末期, 當時(shí)我注意到有些算法并不依賴(lài)于數據結構的特定實(shí)現，而只是依賴(lài)于該結構的幾個(gè)基本的語(yǔ)義屬性. 于是我開(kāi)始研究大量不同的算法，結果發(fā)現大部分算法可以用這種方法從特定實(shí)現中抽象出來(lái), 而且效率無(wú)損. 對我來(lái)說(shuō),效率是至關(guān)重要的, 要是一種算法抽象在實(shí)例化會(huì )導致性能的下降, 那可不夠棒.
當時(shí)我認為這項研究的正確方向是創(chuàng )造一種編程語(yǔ)言. 我和我的兩個(gè)朋友一起開(kāi)始干起來(lái).一個(gè)是現在的紐約州立大學(xué)教授deepak kapur, 另一個(gè)是倫塞里爾技術(shù)學(xué)院教授david musser.當時(shí)我們三個(gè)在通用電器公司研究中心工作. 我們開(kāi)始設計一種叫tecton的語(yǔ)言. 該語(yǔ)言有一種我們稱(chēng)為"通用結構"的東西, 其實(shí)不過(guò)是一些形式類(lèi)型和屬性的集合體, 人們可以用它來(lái)描述算法. 例如一些數學(xué)方面的結構充許人們在其上定義一個(gè)代數操作, 精化之,擴充之, 做各種各樣的事.
雖然有很多有趣的創(chuàng )意, 最終該項研究沒(méi)有取得任何實(shí)用成果, 因為tecton語(yǔ)言是函數型語(yǔ)言. 我們信奉backus的理念，相信自己能把編程從von neumann風(fēng)格中解放出來(lái). 我們不想使用副效應, 這一點(diǎn)限制了我們的能力, 因為存在大量需要使用諸如"狀態(tài)", "副效應"等觀(guān)念的算法.
我在70年代末期在tecton上面所認識到了一個(gè)有趣的問(wèn)題: 被廣泛接受的adt觀(guān)念有著(zhù)根本性的缺陷. 人們通常認為adt的特點(diǎn)是只暴露對象行為特征, 而將實(shí)現隱藏起來(lái). 一項操作的復雜度被認為是與實(shí)現相關(guān)的屬性, 所以抽象的時(shí)候應予忽略. 我則認識到, 在考慮一個(gè)(抽象)操作時(shí), 復雜度(或者至少是一般觀(guān)念上的復雜度)必須被同時(shí)考慮在內. 這一點(diǎn)現在已經(jīng)成了gp的核心理念之一.
例如一個(gè)抽象的棧stack類(lèi)型, 僅僅保證你push進(jìn)去的東西可以隨后被pop出來(lái)是不夠的,同樣極端重要的是, 不管stack有多大, 你的push操作必須能在常數時(shí)間內完成. 如果我寫(xiě)了一個(gè)stack, 每push一次就慢一點(diǎn), 那誰(shuí)都不會(huì )用這個(gè)爛玩藝.
我們是要把實(shí)現和界面分開(kāi), 但不能完全忽略復雜度. 復雜度必須是, 而且也確實(shí)是橫陳于模塊的使用者與實(shí)現者之間的不成文契約. adt觀(guān)念的引入是為了允許軟件模塊相互可替換. 但除非另一個(gè)模塊的操作復雜度與這個(gè)模塊類(lèi)似, 否則你肯定不愿意實(shí)現這種互換.如果我用另外一個(gè)模塊替換原來(lái)的模塊, 并提供完全相同的接口和行為, 但就是復雜度不同, 那么用戶(hù)肯定不高興. 就算我費盡口舌介紹那些抽象實(shí)現的優(yōu)點(diǎn), 他肯定還是不樂(lè )意用. 復雜度必須被認為是接口的一部分.
1983年左右, 我轉往紐約布魯克林技術(shù)大學(xué)任教. 開(kāi)始研究的是圖的算法, 主要的合作伙伴是現在ibm的aaron kershenbaum. 他在圖和網(wǎng)絡(luò )算法方面是個(gè)專(zhuān)家, 我使他相信高序(high order)的思想和gp能夠應用在圖的算法中. 他支持我與他合作開(kāi)始把這些想法用于實(shí)際的網(wǎng)絡(luò )算法. 某些圖的算法太復雜了, 只進(jìn)行過(guò)理論分析, 從來(lái)沒(méi)有實(shí)現過(guò). 他企圖建立一個(gè)包含有高序的通用組件的工具箱, 這樣某些算法就可以實(shí)現了. 我決定使用lisp語(yǔ)言的一個(gè)變種scheme語(yǔ)言來(lái)建立這樣一個(gè)工具箱. 我們倆建立了一個(gè)巨大的庫, 展示了各種編程技術(shù).網(wǎng)絡(luò )算法是首要目標. 不久當時(shí)還在通用電器的david musser加了進(jìn)來(lái), 開(kāi)發(fā)了更多的組件,一個(gè)非常大的庫. 這個(gè)庫供大學(xué)里的本科生使用, 但從未商業(yè)化. 在這項工作中, 我了解到副效應是很重要的, 不利用副效應, 你根本沒(méi)法進(jìn)行圖操作. 你不能每次修改一個(gè)端點(diǎn)(vertex)時(shí)都在圖上兜圈子. 所以, 當時(shí)得到的經(jīng)驗是在實(shí)現通用算法時(shí)可以把高序技術(shù)和副效應結合起來(lái). 副效應不總是壞的, 只有在被錯誤使用時(shí)才是.
1985年夏, 我回到通用電器講授有關(guān)高序程序設計的課程. 我展示了在構件復雜算法時(shí)這項技術(shù)的應用. 有一個(gè)聽(tīng)課的人叫陳邇, 當時(shí)是信息系統實(shí)驗室的主任. 他問(wèn)我是否能用ada語(yǔ)言實(shí)現這些技術(shù), 形成一個(gè)工業(yè)強度的庫, 并表示可以提供支持. 我是個(gè)窮助教, 所以盡管我當時(shí)對于ada一無(wú)所知, 我還是回答"好的". 我跟dave musser一起建立這個(gè)ada庫. 這是很重要的一個(gè)時(shí)期, 從象scheme那樣的動(dòng)態(tài)類(lèi)型語(yǔ)言(dynamically typed language)轉向ada這樣的強類(lèi)型語(yǔ)言, 使我認識到了強類(lèi)型的重要性. 誰(shuí)都知道強類(lèi)型有助于糾錯. 我則發(fā)現在ada的通用編程中, 強類(lèi)型是獲取設計思想的有力工具. 它不僅是查錯工具, 而且是思想工具.這項工作給了我對于組件空間進(jìn)行正交分解的觀(guān)念. 我認識到, 軟件組件各自屬于不同的類(lèi)別.oop的狂熱支持者認為一切都是對象. 但我在ada通用庫的工作中認識到, 這是不對的. 二分查找就不是個(gè)對象, 它是個(gè)算法. 此外, 我還認識到, 通過(guò)將組件空間分解到幾個(gè)不同的方向上, 我們可以減少組件的數量, 更重要的是, 我們可以提供一個(gè)設計產(chǎn)品的概念框架.
隨后, 我在貝爾實(shí)驗室c++組中得到一份工作, 專(zhuān)事庫研究. 他們問(wèn)我能不能用c++做類(lèi)似的事.我那時(shí)還不懂c++, 但當然, 我說(shuō)我行. 可結果我不行, 因為1987年時(shí), c++中還沒(méi)有模板, 這玩意兒在通用編程中是個(gè)必需品. 結果只好用繼承來(lái)獲取通用性, 那顯然不理想.直到現在c++繼承機制也不大用在通用編程中, 我們來(lái)說(shuō)說(shuō)為什么. 很多人想用繼承實(shí)現數據結構和容器類(lèi), 結果幾乎全部一敗涂地. c++的繼承機制及與之相關(guān)的編程風(fēng)格有著(zhù)戲劇性的局限. 用這種方式進(jìn)行通用編程, 連等于判斷這類(lèi)的小問(wèn)題都解決不了. 如果你以x類(lèi)作為基類(lèi), 設計了一個(gè)虛函數operater==, 接受一個(gè)x類(lèi)對象, 并由x派生類(lèi)y, 那么y的operator==是在拿y類(lèi)對象與x類(lèi)對象做比較. 以動(dòng)物為例, 定義animal類(lèi), 派生giraffe(長(cháng)頸鹿)類(lèi). 定義一個(gè)成員函數mate(), 實(shí)現與另一個(gè)哺乳動(dòng)物的交配操作, 返回一個(gè)animal對象. 現在看看你的派生類(lèi)giraffe,它當然也有一個(gè)mate()方法, 結果一個(gè)長(cháng)頸鹿同一個(gè)動(dòng)物交配, 返回一個(gè)動(dòng)物對象. 這成何體統?當然, 對于c++程序員來(lái)說(shuō), 交配函數沒(méi)那么重要, 可是operator==就很重要了.
對付這種問(wèn)題, 你得使用模板. 用模板機制, 一切如愿.
盡管沒(méi)有模板, 我還是搞出來(lái)一個(gè)巨大的算法庫, 后來(lái)成了unix system laboratory standard component library的一部分. 在bell lab, 我從象andy koenig, bjarne stroustrup(andrew koenig, 前iso c++標準化委員會(huì )主席; bjarne stroustrup, c++之父 -- 譯者)這類(lèi)專(zhuān)家身上學(xué)到很多東西. 我認識到c/c++的重要, 它們的一些成功之處是不能被忽略的. 特別是我發(fā)現指針是個(gè)好東東. 我不是說(shuō)空懸的指針, 或是指向棧的指針. 我是說(shuō)指針這個(gè)一般觀(guān)念. 地址的觀(guān)念被廣泛使用著(zhù). 沒(méi)有指針我們就沒(méi)法描述并行算法.
我們現在來(lái)探討一下為什么說(shuō)c是一種偉大的語(yǔ)言. 通常人們認為c是編程利器并且獲得如此成功,是因為unix是用c寫(xiě)的. 我不同意. 計算機的體系結構是長(cháng)時(shí)間發(fā)展演變的結果, 不是哪一個(gè)聰明的人創(chuàng )造的. 事實(shí)上是廣大程序員在解決實(shí)際問(wèn)題的過(guò)程中提出的要求推動(dòng)了那些天才提出這些體系. 計算機經(jīng)過(guò)多次進(jìn)化, 現在只需要處理字節地址索引的內存, 線(xiàn)性地址空間和指針. 這個(gè)進(jìn)化結果是對于人們要求解決問(wèn)題的自然反映. dennis ritchie天才的作品c, 正反映了演化了30年的計算機的最小模型. c當時(shí)并不是什么利器. 但是當計算機被用來(lái)處理各種問(wèn)題時(shí), 作為最小模型的c成了一種非常強大的語(yǔ)言, 在各個(gè)領(lǐng)域解決各種問(wèn)題時(shí)都非常高效. 這就是c可移植性的奧秘, c是所有計算機的最佳抽象模型, 而且這種抽象確確實(shí)實(shí)是建立在實(shí)際的計算機, 而不是假想的計算機上的. 人們可以比較容易的理解c背后的機器模型, 比理解ada和scheme語(yǔ)言背后的機器模型要容易的多. c的成功是因為c做了正確的事, 不是因為at&t的極力鼓吹和unix.
c++的成功是因為bjarne stroustrup以c為出發(fā)點(diǎn)來(lái)改進(jìn)c, 引入更多的編程技術(shù), 但始終保持在c所定義的機器模型框架之內, 而不是閉門(mén)造車(chē)地自己搞出一個(gè)新的機器模型來(lái). c的機器模型非常簡(jiǎn)單. 你擁有內存, 對象保存在那里面, 你又有指向連續內存空間的指針, 很好理解. c++保留了這個(gè)模型, 不過(guò)大大擴展了內存中對象的范疇, 畢竟c的數據類(lèi)型太有限了, 它允許你建立新的類(lèi)型結構, 但不允許你定義類(lèi)型方法. 這限制了類(lèi)型系統的能力. c++把c的機器模型擴展為真正類(lèi)型系統.
1988年我到惠普實(shí)驗室從事通用庫開(kāi)發(fā)工作. 但實(shí)際上好幾年我都是在作磁盤(pán)驅動(dòng)器. 很有趣但跟
gp毫不相關(guān). 92年我終于回到了gp領(lǐng)域, 實(shí)驗室主任bill worley建立了一個(gè)算法研究項目, 由我
負責. 那時(shí)候c++已經(jīng)有模板了. 我發(fā)現bjarne的模板設計方案是非常天才的. 在bell lab時(shí), 我參
加過(guò)有關(guān)模班設計的幾個(gè)早期的討論, 跟bjarne吵得很兇, 我認為c++的模板設計應該盡可能向ada的
通用方案看齊. 我想可能我吵得太兇了, 結果bjarne決定堅決拒絕我的建議. 我當時(shí)就認識到在c++
中設置模板函數的必要性了, 那時(shí)候好多人都覺(jué)得最好只有模板類(lèi). 不過(guò)我覺(jué)得一個(gè)模板函數在使用
之前必須先顯式實(shí)例化, 跟ada似的. bjarne死活不聽(tīng)我的, 他把模板函數設計成可以用重載機制來(lái)
隱式實(shí)例化. 后來(lái)這個(gè)特別的技術(shù)在我的工作中變得至關(guān)重要, 我發(fā)現它容許我做很多在ada中不可能
的任務(wù). 非常高興bjarne當初沒(méi)聽(tīng)我的.
q: 您是什么時(shí)候第一次構思stl的, 最初的目的是什么?
a: 92年那個(gè)項目建立時(shí)由8個(gè)人, 漸漸地人越來(lái)越少, 最后剩下倆, 我和李夢(mèng), 而且李小姐是這個(gè)領(lǐng)域的新手. 在她的專(zhuān)業(yè)研究中編譯器是主要工作, 不過(guò)她接受了gp研究的想法, 并且堅信此項研究將帶給軟件開(kāi)發(fā)一個(gè)大變化, 要知道那時(shí)候有這個(gè)信念的認可是寥寥無(wú)幾. 沒(méi)有她, 我可不敢想象我能搞定stl, 畢竟stl標著(zhù)兩個(gè)人的名字:stepanov和lee. 我們寫(xiě)了一個(gè)龐大的庫, 龐大的代碼量, 龐大的數據結構組件,函數對象, 適配器類(lèi), 等等. 可是雖然有很多代碼, 卻沒(méi)有文檔. 我們的工作被認為是一個(gè)驗證性項目,其目的是搞清楚到底能不能在使算法盡可能通用化的前提下仍然具有很高的效率. 我們化了很多時(shí)間來(lái)比較, 結果發(fā)現, 我們算法不僅最通用, 而且要率與手寫(xiě)代碼一樣高效, 這種程序設計風(fēng)格在性能上是不打折扣的! 這個(gè)庫在不斷成長(cháng), 但是很難說(shuō)它是什么時(shí)候成為一個(gè)"項目"的. stl的誕生是好幾件事情的機緣巧合才促成的.
q: 什么時(shí)候, 什么原因促使您決定建議使stl成為ansi/iso標準c++一部分的?
a: 1993年夏, andy koenig跑到斯坦福來(lái)講c++課, 我把一些有關(guān)的材料給他看, 我想他當時(shí)確實(shí)是很興奮.他安排我9月到圣何塞給c++標準委員會(huì )做一個(gè)演講. 我演講的題目是"c++程序設計的科學(xué)", 講得很理論化, 要點(diǎn)是存在一些c++的基本元素所必須遵循的, 有關(guān)基本操作的原則. 我舉了一些例子, 比如構造函數, 賦值操作, 相等操作. 作為一種語(yǔ)言, c++沒(méi)有什么限制. 你可以用operator==()來(lái)做乘法. 但是相等操作就應該是相等操作. 它要有自反性, a == a; 它要有對稱(chēng)性, a == b 則 b == a; 它還要有傳遞性. 作為一個(gè)數學(xué)公理, 相等操作對于其他操作是基本的要素. 構造函數和相等操作之間的聯(lián)系就有公理性的東西在里邊. 你用拷貝構造函數生成了一個(gè)新對象, 那么這個(gè)對象和原來(lái)那個(gè)就應該是相等的. c++是沒(méi)有做強行要求, 但是這是我們都必須遵守這個(gè)規則. 同樣的, 賦值操作也必須產(chǎn)生相等的對象. 我展示了一些基本操作的"公理", 還講了一點(diǎn)迭代子(iterator), 以及一些通用算法怎樣利用迭代子來(lái)工作. 我覺(jué)得那是一個(gè)兩小時(shí)的枯燥演講, 但卻非常受歡迎. 不過(guò)我那時(shí)并沒(méi)有想把這個(gè)東西塞在標準里, 它畢竟是太過(guò)先進(jìn)的編程技術(shù), 大概還不適于出現在現實(shí)世界里, 恐怕那些做實(shí)際工作的人對它沒(méi)什么興趣.
我是在9月做這個(gè)演講的, 直到次年(1994)月, 我都沒(méi)往ansi標準上動(dòng)過(guò)什么腦筋. 1月6日, 我收到andy koenig的一封信(他那時(shí)是標準文檔項目編輯), 信中說(shuō)如果我希望stl成為標準庫的一部分, 可以在1月25日之前提交一份建議到委員會(huì ). 我的答復是:"andy, 你發(fā)瘋了嗎?", 他答復道:"不錯, 是的我發(fā)瘋了, 為什么咱們不瘋一次試試看?"
當時(shí)我們有很多代碼, 但是沒(méi)有文檔, 更沒(méi)有正式的建議書(shū). 李小姐和我每星期工作80小時(shí), 終于在期限之前寫(xiě)出一份正式的建議書(shū). 當是時(shí)也, 只有andy一個(gè)人知道可能會(huì )發(fā)生些什么. 他是唯一的支持者, 在那段日子里他確實(shí)提供了很多幫助. 我們把建議寄出去了, 然后就是等待. 在寫(xiě)建議的過(guò)程中我們做了很多事. 當你把一個(gè)東西寫(xiě)下來(lái), 特別是想到你寫(xiě)的可能會(huì )成為標準, 你就會(huì )發(fā)現設計中的所有紕漏. 寄出標準后,我們不得不一段一段重寫(xiě)了庫中間的代碼, 以及幾百個(gè)組件, 一直到3月份圣迭戈會(huì )議之前. 然后我們又重新修訂了建議書(shū), 因為在重新寫(xiě)代碼的過(guò)程中, 我們又發(fā)現建議書(shū)中間的很多瑕疵.
q: 您能描述一下當時(shí)委員會(huì )里的爭論嗎? 建議一開(kāi)始是被支持呢, 還是反對?
a: 我當時(shí)無(wú)法預料會(huì )發(fā)生些什么. 我做了一個(gè)報告, 反響很好. 但當時(shí)有許多反對意見(jiàn). 主要的意見(jiàn)是:這是一份龐大的建議, 而且來(lái)得太晚, 前一次會(huì )議上已經(jīng)做出決議, 不在接受任何大的建議. 而這個(gè)東西是有史以來(lái)最大的建議, 包括了一大堆新玩藝. 投票的結果很有趣, 壓倒多數的意見(jiàn)認為應對建議進(jìn)行再考慮, 并把投票推遲到下次會(huì )議, 就是后來(lái)眾所周知的滑鐵盧會(huì )議.
bjarne stroustrup成了stl的強有力支持者. 很多人都通過(guò)建議、更改和修訂的方式給予了幫助。bjarne干脆跑到這來(lái)跟我們一起工作了一個(gè)禮拜。andy更是無(wú)時(shí)無(wú)刻的幫助我們。c++是一種復雜的語(yǔ)言，不是總能搞得清楚確切的含義的。差不多每天我都要問(wèn)andy和bjarne c++能不能干這干那。我得把特殊的榮譽(yù)歸于andy， 是他提出把stl作為c++標準庫的一部分；而bjarne也成了委員會(huì )中stl的主要鼓吹者。其他要感謝的人還有：mike vilot，標準庫小組的負責人； rogue wave公司的nathan myers(rogue wave是boland c++builder中stl方案的提供商 —— 譯者)，andersen咨詢(xún)公司的larry podmolik。確實(shí)有好多人要致謝。
在圣迭戈提出的stl實(shí)際與當時(shí)的c++，我們被要求用新的ansi/iso c++語(yǔ)言特性重寫(xiě)stl，這些特性中有一些是尚未實(shí)現的。為了正確使用這些新的、未實(shí)現的c++特性，bjarne和andy花了無(wú)以計數的時(shí)間來(lái)幫助我們。
人們希望容器獨立于內存模式，這有點(diǎn)過(guò)分，因為語(yǔ)言本身并沒(méi)有包括內存模式。所以我們得要想出一些機制來(lái)抽象內存模式。在stl的早期版本里，假定容器的容積可以用size_t類(lèi)型來(lái)表示，迭代子之間的距離可以用ptrdiff_t來(lái)表示?，F在我們被告知，你為什么不抽象的定義這些類(lèi)型？這個(gè)要求比較高，連語(yǔ)言本身都沒(méi)有抽象定義這些類(lèi)型，而且c/c++數組還不能被這些類(lèi)型定義所限定。我們發(fā)明了一個(gè)機制稱(chēng)作"allocator"，封裝了內存模式的信息。這個(gè)機制深刻地影響了庫中間的每一個(gè)組件。你可能疑惑：內存模式和算法或者容器類(lèi)接口有什么關(guān)系？如果你使用size_t這樣的東西，你就無(wú)法使用 t* 對象，因為存在不同的指針類(lèi)型(t*, t huge *, 等等)。這樣你就不能使用引用，因為內存模式不同的話(huà)，會(huì )產(chǎn)成不同的引用類(lèi)型。這樣就會(huì )導致標準庫產(chǎn)生龐大的分支。
另外一件重要的事情是我們原先的關(guān)聯(lián)類(lèi)型數據結構被擴展了。這比較容易一些，但是最為標準的東西總是很困難的，因為我們做的東西人們要使用很多年。從容器的觀(guān)點(diǎn)看，stl做了十分清楚的二分法設計。所有的容器類(lèi)被分成兩種：順序的和關(guān)聯(lián)的，就好像常規的內存和按內容尋址的內存一般。這些容器的語(yǔ)義十分清楚。
當我到滑鐵盧以后，bjarne用了不少時(shí)間來(lái)安慰我不要太在意成敗與否，因為雖然看上去似乎不會(huì )成功，但是我們畢竟做到了最好。我們試過(guò)了，所以應該坦然面對。成功的期望很低。我們估計大部分的意見(jiàn)將是反對。但是事實(shí)上，確實(shí)有一些反對意見(jiàn)，但不占上風(fēng)?；F盧投票的結果讓人大跌眼鏡，80%贊成，20%反對。所有人都預期會(huì )有一場(chǎng)惡戰，一場(chǎng)大論戰。結果是確實(shí)有爭論，但投票是壓倒性的。
q: stl對于1994年2月發(fā)行的ansi/iso c++工作文件中的類(lèi)庫有何影響？
a: stl被放進(jìn)了滑鐵盧會(huì )議的工作文件里。stl文檔被分解成若干部分，放在了文件的不同部分中。mike
vilot負責此事。我并沒(méi)有過(guò)多地參與編輯工作，甚至也不是c++委員會(huì )的成員。不過(guò)每次有關(guān)stl的
建議都由我來(lái)考慮。委員會(huì )考慮還是滿(mǎn)周到的。
q: 委員會(huì )后來(lái)又做了一些有關(guān)模板機制的改動(dòng)，哪些影響到了stl？
a: 在stl被接受之前，有兩個(gè)變化影響到了我們修訂stl。其一是模板類(lèi)增加了包含模板函數的能力。stl廣泛地使用了這個(gè)特性來(lái)允許你建立各種容納容器的容器。一個(gè)單獨的構造函數就能讓你建立一個(gè)能容納list或其他容器的vector。還有一個(gè)模板構造函數，從迭代子構造容器對象，你可以用一對迭代子當作參數傳給它，這對迭代子之間的元素都會(huì )被用來(lái)構造新的容器類(lèi)對象。另一個(gè)stl用到的新特性是把模板自身當作模板參數傳給模板類(lèi)。這項技術(shù)被用在剛剛提到的allocator中。
q: 那么stl影響了模板機制嗎？
a: 在弗基山谷的會(huì )議中，bjarne建議給模板增加一個(gè)“局部特殊化”(partial specialization)的特性。這個(gè)特性可以讓很多算法和類(lèi)效率更高，但也會(huì )帶來(lái)代碼體積上的問(wèn)題。我跟bjarne在這個(gè)建議上共同研究了一段時(shí)間，這個(gè)建議就是為了使stl更高效而提出的。我們來(lái)解釋一下什么是“局部特殊化”。你現在有一個(gè)模板函數 swap( t&, t& )，用來(lái)交換兩個(gè)參數。但是當t是某些特殊的類(lèi)型參數時(shí)，你想做一些特殊的事情。例如對于swap( int&, int& )，你想用一種特別的操作來(lái)交換數據。這一點(diǎn)在沒(méi)有局部特殊化機制的情況下是不可能的。有了局部特殊化機制，你可以聲明一個(gè)模板函數如下：
template <class t> void swap( vector<t>&, vector<t>& );
這種形式給vector容器類(lèi)的swap操作提供了一種特別的辦法。從性能的角度講，這是非常重要的。如果你用通用的形式去交換vector，會(huì )使用三個(gè)賦值操作，vector被復制三次，時(shí)間復雜度是線(xiàn)性的。然而，如果我們有一個(gè)局部特殊化的swap版本專(zhuān)門(mén)用來(lái)交換兩個(gè)vector，你可以得到一個(gè)時(shí)間復雜度為常數的，非?？斓牟僮?，只要移動(dòng)vector頭部的兩個(gè)指針就ok。這能讓vector上的sort算法運行得更快。沒(méi)有局部特殊化，讓某一種特殊的vector，例如vector<int>運行得更快的唯一辦法是讓程序員自己定一個(gè)特殊的swap函數，這行得通，但是加重了程序員的負擔。在大部分情況下，局部特殊化機制能夠讓算法在某些通用類(lèi)上表現得更高效。你有最通用的swap，不那么通用的swap，更不通用的swap，完全特殊的swap這么一系列重載的swap，然后你使用局部特殊化，編譯器會(huì )自動(dòng)找到最接近的那個(gè)swap。另一個(gè)例子copy?，F在我們的copy就是通過(guò)迭代子一個(gè)一個(gè)地拷貝。使用模板特殊化可以定義一個(gè)模板函數：
template <class t> t** copy( t**, t**, t** );
這可以用memcpy高效地拷貝一系列指針來(lái)實(shí)現，因為是指針拷貝，我們可以不必擔心構造對象和析構對象的開(kāi)銷(xiāo)。這個(gè)模板函數可以定義一次，然后供整個(gè)庫使用，而且用戶(hù)不必操心。我們使用局部特殊化處理了一些算法。這是個(gè)重要的改進(jìn)，據我所知在弗基山谷會(huì )議上得到了好評，將來(lái)會(huì )成為標準的一部分。(后來(lái)的確成了標準的一部分 —— 譯者）
q: 除了標準類(lèi)庫外，stl對那一類(lèi)的應用程序來(lái)說(shuō)最有用處？
a: 我希望stl能夠引導大家學(xué)習一種新的編程風(fēng)格：通用編程。我相信這種風(fēng)格適用于任何種類(lèi)的應用程序。這種風(fēng)格就是：用最通用的方式來(lái)寫(xiě)算法和數據結構。這些結構所要求的語(yǔ)義特性應該能夠被清楚地歸類(lèi)和分類(lèi)，而這些歸類(lèi)分類(lèi)的原則應該是任何對象都能滿(mǎn)足的。理解和發(fā)展這種技術(shù)還要很長(cháng)時(shí)間，stl不過(guò)是這個(gè)過(guò)程的起點(diǎn)。
我們最終會(huì )對通用的組件有一個(gè)標準的分類(lèi)，這些組件具有精心定義的接口和復雜度。程序員們將不必在微觀(guān)層次上編程。你再也不用去寫(xiě)一個(gè)二分查找算法。就是在現在，stl也已經(jīng)提供了好幾個(gè)通用的二分查找算法，凡是能用二分查找算法的場(chǎng)合，都可以使用這些算法。算法所要求的前提條件很少：你只要在代碼里使用它。我希望所有的組件都能有這么一天。我們會(huì )有一個(gè)標準的分類(lèi)，人們不用再重復這些工作。
這就是douglas mcilroy的夢(mèng)想，他在1969年關(guān)于“構件工廠(chǎng)”的那篇著(zhù)名文章中所提出來(lái)的東西。stl就是這種“構件工廠(chǎng)”的一個(gè)范例。當然，還需要有主流的力量介入這種技術(shù)的發(fā)展之中，光靠研究機構不行，工業(yè)界應該想程序員提供組件和工具，幫助他們找到所需的組件，把組件粘合到一起，然后確定復雜度是否達到預期。
q: stl沒(méi)有實(shí)現一個(gè)持久化(persistent)對象容器模型。map和multimap似乎是比較好的候選者，它們可以把對象按索引存入持久對象數據庫。您在此方向上做了什么工作嗎，或者對這類(lèi)實(shí)現有何評論？
a：很多人都注意到這個(gè)問(wèn)題。stl沒(méi)實(shí)現持久化是有理由的。stl在當時(shí)已經(jīng)是能被接受的最巨大的庫了。再大一點(diǎn)的話(huà)，我認為委員會(huì )肯定不會(huì )接受。當然持久化是確實(shí)是一些人提出的問(wèn)題。在設計stl，特別是設計allocator時(shí)，bjarne認為這個(gè)封裝了內存模式的組件可以用來(lái)封裝持久性?xún)却婺Ｊ?。bjarne的洞察秋毫非常的重要和有趣，好幾個(gè)對象數據庫公司正在盯著(zhù)這項技術(shù)。1994年10月我參加了object database management group的一個(gè)會(huì )議，我做了一個(gè)關(guān)于演說(shuō)。他們非常感興趣，想讓他們正在形成中的組件庫的接口與stl一致，但不包括allocator在內。不過(guò)該集團的某些成員仔細分析了allocator是否能夠被用來(lái)實(shí)現持久化。我希望與stl接口一致的組件對象持久化方案能在接下來(lái)的一年里出現。
q：set，multiset，map和multimap是用紅黑樹(shù)實(shí)現的，您試過(guò)用其他的結構，比如b*樹(shù)來(lái)實(shí)現嗎？
a：我不認為b*適用于內存中的數據結構，不過(guò)當然這件事還是應該去做的。應該對許多其他的數據結構，比如跳表(skip list)、伸展樹(shù)(splay tree)、半平衡樹(shù)(half-balanced tree)等，也實(shí)現stl容器的標準接口。應該做這樣的研究工作，因為stl提供了一個(gè)很好的框架，可以用來(lái)比較這些結構的性能。結口是固定的，基本的復雜度是固定的，現在我們就可一個(gè)對各種數據結構進(jìn)行很有意義的比較了。在數據結構領(lǐng)域里有很多人用各種各樣的接口來(lái)實(shí)現不同的數據結構，我希望他們能用stl框架來(lái)把這些數據結構變成通用的。
（譯者注：上面所提到的各種數據結構我以為大多并非急需，而一個(gè)stl沒(méi)有提供而又是真正重要的數據結構是哈希結構。后來(lái)在stepanov和matt austern等人的sgi*stl中增補了hashset，hashmap和hashtable三種容器，使得這個(gè)stl實(shí)現才比較完滿(mǎn)。眾所周知，紅黑樹(shù)的時(shí)間復雜度為o(logn), 而理想hash結構為o(1)。當然，如果實(shí)現了持久化，b+樹(shù)也是必須的。）
q：有沒(méi)有編譯器廠(chǎng)商跟您一起工作來(lái)把stl集成到他們的產(chǎn)品中去？
a：是的，我接到了很多廠(chǎng)家的電話(huà)。borland公司的peter becker出的力特別大。他幫助我實(shí)現了對應borland編譯器的所有內存模式的allocator組件。symantec打算為他們的macintosh編譯器提供一個(gè)stl實(shí)現。edison設計集團也很有幫助。我們從大多數編譯器廠(chǎng)商都得到了幫助。
（譯者注：以目前的stl版本來(lái)看，最出色的無(wú)疑是sgi*stl和ibm stl for as/390，所有windows下的的stl實(shí)現都不令人滿(mǎn)意。根據測試數據，windows下最好的stl運行在piii 500mhz上的速度遠遠落后與在250mhz sgi工作站（irix操作系統）上運行的sgi*stl。以我個(gè)人經(jīng)驗，linux也是運行stl的極佳平臺。而在windows的stl實(shí)現中，又以borland c++builder的rogue wave stl為最差，其效率甚至低于jit執行方式下的java2。visual c++中的stl是著(zhù)名大師p. j. plauger的個(gè)人作品，性能較好，但其queue組件效率很差，慎用）
q：stl包括了對ms-dos的16位內存模式編譯器的支持，不過(guò)當前的重點(diǎn)顯然是在32位上線(xiàn)性?xún)却婺Ｊ?flat model)的操作系統和編譯器上。您覺(jué)得這種面向內存模式的方案以后還會(huì )有效嗎？
a：拋開(kāi)intel的體系結構不談，內存模式是一個(gè)對象，封裝了有關(guān)指針的信息：這個(gè)指針的整型尺寸和距離類(lèi)型是什么，相關(guān)的引用類(lèi)型是什么，等等。如果我們想利用各種內存，比如持久性?xún)却?，共享內存等等，抽象化的工作就非常重要了。stl的一個(gè)很漂亮的特性是整個(gè)庫中唯一與機器類(lèi)型相關(guān)的部分——代表真實(shí)指針，真實(shí)引用的組件——被封裝到大約16行代碼里，其他的一切，容器、算法等等，都與機器無(wú)關(guān)（真是牛?。。?。從移植的觀(guān)點(diǎn)看，所有及其相關(guān)的東西，象是地址記法，指針等，都被封裝到一個(gè)微小的，很好理解的機制里面。這樣一來(lái)，allocator對于stl而言就不是那么重要了，至少不像對于基本數據結構和算法的分解那么重要。
q：ansi/iso c標準委員會(huì )認為像內存模式這類(lèi)問(wèn)題是平臺相關(guān)的，沒(méi)有對此做出什么具體規定。c++委員會(huì )會(huì )不會(huì )采取不同的態(tài)度？為什么？
a：我認為stl在內存模式這一點(diǎn)上跟c++標準相比是超前的。但是在c和c++之間有著(zhù)顯著(zhù)的不同。c++有構造函數和new操作符來(lái)對付內存模式問(wèn)題，而且它們是語(yǔ)言的一部分?，F在看來(lái)似乎讓new操作符像stl容器使用allocater那樣來(lái)工作是很有意義的。不過(guò)現在對問(wèn)題的重要性不像stl出現之前那么顯著(zhù)了，因為在大多數場(chǎng)合，stl數據結構將讓new失業(yè)。大部分人不再需要分配一個(gè)數組，因為stl在做這類(lèi)事情上更為高效。要知道我對效率的迷信是無(wú)以復加的，可我在我的代碼里從不使用new，匯編代碼表明其效率比使用new時(shí)更高。隨著(zhù)stl的廣泛使用，new會(huì )逐漸淡出江湖。而且stl永遠都會(huì )記住回收內存，因為當一個(gè)容器，比如vector退出作用域時(shí)，它的析構函數被調用，會(huì )把容器里的所有東西都析構。你也不必再擔心內存泄漏了。stl可以戲劇性地降低對于垃圾收集機制的需求。使用stl容器，你可以為所欲為，不用關(guān)心內存的管理，自有stl構造函數和析構函數來(lái)對付。
q：c++標準庫子委員會(huì )正在制訂標準名空間（namespace）和異常處理機制。stl類(lèi)會(huì )有名空間嗎，會(huì )拋出異
常嗎？
a：是的。該委員會(huì )的幾個(gè)成員正在考慮這件事，他們的工作非常卓越。
q：現在的stl跟最終作為標準的stl會(huì )有多大不同？委員會(huì )會(huì )不會(huì )干預某些變化，新的設計會(huì )不會(huì )被嚴格地控
制起來(lái)？
a：多數人的意見(jiàn)看起來(lái)是不希望對stl做任何重要的改變。
q：在成為標準之前，程序員們怎樣的一些stl經(jīng)驗？
a：他們可以從butler.hpl.hp.com/stl當下stl頭文件，在borland和ibm或其他足夠強勁的的編譯器中使用它。學(xué)習這種編程技術(shù)的唯一途徑是編程，看看范例，試著(zhù)用這種技術(shù)來(lái)編程。
q：您正在和p. j. plauger合作一本stl的書(shū)。那本書(shū)的重點(diǎn)是什么？什么時(shí)候面世？
a：計劃95年夏天面世，重點(diǎn)是對stl實(shí)現技術(shù)的詳解，跟他那本標準c庫實(shí)現和標準c++庫實(shí)現的書(shū)類(lèi)似。他是
這本書(shū)的第一作者。該書(shū)可以作為stl的參考手冊。我希望跟bjarne合作另寫(xiě)一本書(shū)，在c++/stl背景下介紹語(yǔ)言與庫的交互作用。
好多工作都等著(zhù)要做。為了stl的成功，人們需要對這種編程技術(shù)進(jìn)行更多的試驗性研究，更多的文章和書(shū)籍應該對此提供幫助。要準備開(kāi)設此類(lèi)課程，寫(xiě)一些入門(mén)指南，開(kāi)發(fā)一些工具幫助人們漫游stl庫。stl是一個(gè)
框架，應該有好的工具來(lái)幫助使用這個(gè)框架。
（譯者注：他說(shuō)這番話(huà)時(shí)，并沒(méi)有預計到在接下來(lái)的幾年里會(huì )發(fā)生什么。由于internet的大爆炸和java、vb、delphi等語(yǔ)言的巨大成功，工業(yè)界的重心一下子從經(jīng)典的軟件工程領(lǐng)域轉移到internet上。再加上標準c++直到98年才制訂，完全符合要求的編譯器直到現在都還沒(méi)有出現，stl并沒(méi)有立刻成為人們心中的關(guān)注焦點(diǎn)。他提到的那本書(shū)也遲遲不能問(wèn)世，直到前幾天（2001年元旦之后），這本眾人久已期盼的書(shū)終于問(wèn)世，由p. j. plauger, alexander stepanov, meng lee, david musser四大高手聯(lián)手奉獻，prentice hall出版。不過(guò)該書(shū)主要關(guān)注的是stl的實(shí)現技術(shù)，不適用于普通程序員。
另外就p. j. plauger做一個(gè)簡(jiǎn)介：其人是標準c中stdio庫的早期實(shí)現者之一，91年的一本關(guān)于標準c庫的書(shū)使他名滿(mǎn)天下。他現在是c/c++ use‘s journal的主編，與microsoft保持著(zhù)良好的，甚至是過(guò)分親密的關(guān)系，visual c++中的stl和其他的一些內容就是出自他的那只生花妙筆。不過(guò)由于跟ms的關(guān)系已經(jīng)影響到了他的中立形象，現在有不少人對他有意見(jiàn)。
至于stepanov想象中的那本與stroustrup的書(shū)，起碼目前是沒(méi)聽(tīng)說(shuō)。其實(shí)這兩位都是典型的編程圣手，跟ken thompson和dennis ritchie是一路的，懶得親自寫(xiě)書(shū)，往往做個(gè)第二作者。如果作為第一作者，寫(xiě)出來(lái)的書(shū)肯定是學(xué)院味十足，跟標準文件似的，不適合一般程序員閱讀。在計算機科學(xué)領(lǐng)域，編程圣手同時(shí)又是寫(xiě)作高手的人是鳳毛麟角，最著(zhù)名的可能是外星人d. e. knuth, c++領(lǐng)域里則首推前面提到的andrew koenig?？上覀冎袊绦騿T無(wú)緣看到他的書(shū)。）
q：通用編程跟oop之間有什么關(guān)系？
a：一句話(huà)，通用編程是oop基本思想的自然延續。什么是oop的基本思想呢？把組件的實(shí)現和接口分開(kāi)，并且讓組件具有多態(tài)性。不過(guò)，兩者還是有根本的不同。oop強調在程序構造中語(yǔ)言要素的語(yǔ)法。你必須得繼承，使用類(lèi)，使用對象，對象傳遞消息。gp不關(guān)心你繼承或是不繼承，它的開(kāi)端是分析產(chǎn)品的分類(lèi)，有些什么種類(lèi)，他們的行為如何。就是說(shuō)，兩件東西相等意味著(zhù)什么？怎樣正確地定義相等操作？不單單是相等操作那么簡(jiǎn)單，你往深處分析就會(huì )發(fā)現“相等”這個(gè)一般觀(guān)念意味著(zhù)兩個(gè)對象部分，或者至少基本部分是相等的，據此我們就可以有一個(gè)通用的相等操作。再說(shuō)對象的種類(lèi)。假設存在一個(gè)順序序列和一組對于順序序列的操作。那么這些操作的語(yǔ)義是什么？從復雜度權衡的角度看，我們應該向用戶(hù)提供什么樣的順序序列？該種序列上存在那些操作？那種排序是我們需要的？只有對這些組件的概念型分類(lèi)搞清楚了，我們才能提到實(shí)現的問(wèn)題：使用模板、繼承還是宏？使用什么語(yǔ)言和技術(shù)？gp的基本觀(guān)點(diǎn)是把抽象的軟件組件和它們的行為用標準的分類(lèi)學(xué)分類(lèi)，出發(fā)點(diǎn)就是要建造真實(shí)的、高效的和不取決于語(yǔ)言的算法和數據結構。當然最終的載體還是語(yǔ)言，沒(méi)有語(yǔ)言沒(méi)法編程。stl使用c++，你也可以用ada來(lái)實(shí)現，用其他的語(yǔ)言來(lái)實(shí)現也行，結果會(huì )有所不同，但基本的東西是一樣的。到處都要用到二分查找和排序，而這就是人們正在做的。對于容器的語(yǔ)義，不同的語(yǔ)言會(huì )帶來(lái)輕微的不同。但是基本的區別很清楚是gp所依存的語(yǔ)義，以及語(yǔ)義分解。例如，我們決定需要一個(gè)組件swap，然后指出這個(gè)組件在不同的語(yǔ)言中如果工作。顯然重點(diǎn)是語(yǔ)義以及語(yǔ)義分類(lèi)。而oop所強調的（我認為是過(guò)分強調的）是清楚的定義類(lèi)之間的層次關(guān)系。oop告訴了你如何建立層次關(guān)系，卻沒(méi)有告訴你這些關(guān)系的實(shí)質(zhì)。
（這段不太好理解，有一些術(shù)語(yǔ)可能要過(guò)一段時(shí)間才會(huì )有合適的中文翻譯——譯者）
q：您對stl和gp的未來(lái)怎么看?
a：我剛才提到過(guò)，程序員們的夢(mèng)想是擁有一個(gè)標準的組件倉庫，其中的組件都具有良好的、易于理解的和標準的接口。為了達成這一點(diǎn)，gp需要有一門(mén)專(zhuān)門(mén)的科學(xué)來(lái)作為基礎和支柱。stl在某種程度上開(kāi)始了這項工作，它對于某些基本的組件進(jìn)行了語(yǔ)義上的分類(lèi)。我們要在這上面下更多的功夫，目標是要將軟件工程從一種手工藝技術(shù)轉化為工程學(xué)科。這需要一門(mén)對于基本概念的分類(lèi)學(xué)，以及一些關(guān)于這些基本概念的定理，這些定理必須是容易理解和掌握的，每一個(gè)程序員即使不能很清楚的知道這些定理，也能正確地使用它。很多人根本不知道交換律，但只要上過(guò)學(xué)的人都知道2+5等于5+2。我希望所有的程序員都能學(xué)習一些基本的語(yǔ)義屬性和基本操作：賦值意味著(zhù)什么？相等意味著(zhù)什么？怎樣建立數據結構，等等。
當前，c++是gp的最佳載體。我試過(guò)其他的語(yǔ)言，最后還是c++最理想地達成了抽象和高效的統一。但是我覺(jué)得可能設計出一種語(yǔ)言，基于c和很多c++的卓越思想，而又更適合于gp。它沒(méi)有c++的一些缺陷，特別是不會(huì )像c++一樣龐大。stl處理的東西是概念，什么是迭代子，不是類(lèi)，不是類(lèi)型，是概念。說(shuō)得更正式一些，這是bourbaki所說(shuō)的結構類(lèi)型（structure type），是邏輯學(xué)家所說(shuō)的理念（theory），或是類(lèi)型理論學(xué)派的人所說(shuō)的種類(lèi)（sort），這種東西在c++里沒(méi)有語(yǔ)言層面上的對應物（原文是incarnation，直譯為肉身——譯者），但是可以有。你可以擁有一種語(yǔ)言，使用它你可以探討概念，精化概念，最終用一種非常“程序化”（programmatic，直譯為節目的，在這里是指符合程序員習慣的——譯者）的手段把它們轉化為類(lèi)。當然確實(shí)有一些語(yǔ)言能處理種類(lèi)（sorts），但是當你想排序（sort）時(shí)它們沒(méi)什么用處。我們能夠有一種語(yǔ)言，用它我們能定義叫做foward iterator（前向迭代子）的東西，在stl里這是個(gè)概念，沒(méi)有c++對應物。然后我們可以從forword iterator中發(fā)展出bidirectional iterator（雙向迭代子），再發(fā)展出random iterator?？赡茉O計一種語(yǔ)言大為簡(jiǎn)化gp，我完全相信該語(yǔ)言足夠高效，其機器模型與c/c++充分接近。我完全相信能夠設計出一種語(yǔ)言，一方面盡可能地靠近機器層面以達成絕對的高效，另一方面能夠處理非常抽象化的實(shí)體。我認為該語(yǔ)言的抽象性能夠超過(guò)c++，同時(shí)又與底層的機器之間契合得天衣無(wú)縫。我認為gp會(huì )影響到語(yǔ)言的研究方向，我們會(huì )有適于gp的實(shí)用語(yǔ)言。從這些話(huà)中你應該能猜出我下一步的計劃。
mengyan
譯于2001年1月
