STL之父訪談錄 - 執著 - CSDNBlog正在處理您的請求...   
       MzForm
       
        
      StatusBar

         
         
         
   
      執著
      braveroc

        CSDN |  技術中心 |  BLOG首頁 |  我的首頁 |  我的文章 |  聯系作者 |  聚合  |   |  搜索 |  登錄   
             5篇原創: 0篇翻譯: 3篇轉載: 2541次點擊: 24個評論: 0個Trackbacks 


Csdn Blog User的個人信息
      我的博客 | 我的空間   
數據讀取中，請稍候...文章
  北漂游記(RSS)
  編程練習之路(RSS)
  編程心得(RSS)
  感悟人生(RSS)
  計算數學(RSS)
收藏
  程序人生
  技術點滴
相冊
存檔
  2006年04月(3)


上一篇: 一則故事，一點感悟 | 下一篇: 回歸原點


 STL之父訪談錄 
STL之父訪談錄
1995年3月，Dr.Dobb's Journal特約記者, 著名技術書籍作家Al Stevens采訪了STL創始人Alexander
Stepanov. 這份訪談紀錄是迄今為止對于STL發展歷史的最完備介紹, 侯捷先生在他的STL有關文章里
推薦大家閱讀這篇文章.
Q: 您對于generic programming進行了長時間的研究, 請就此談談.
A: 我開始考慮有關GP的問題是在7O年代末期, 當時我注意到有些算法并不依賴于數據結構的
   特定實現，而只是依賴于該結構的幾個基本的語義屬性. 于是我開始研究大量不同的算法，
   結果發現大部分算法可以用這種方法從特定實現中抽象出來, 而且效率無損. 對我來說,
   效率是至關重要的, 要是一種算法抽象在實例化會導致性能的下降, 那可不夠棒.
   
   當時我認為這項研究的正確方向是創造一種編程語言. 我和我的兩個朋友一起開始干起來.
   一個是現在的紐約州立大學教授Deepak Kapur, 另一個是倫塞里爾技術學院教授David Musser.
   當時我們三個在通用電器公司研究中心工作. 我們開始設計一種叫Tecton的語言. 該語言
   有一種我們稱為"通用結構"的東西, 其實不過是一些形式類型和屬性的集合體, 人們可以
   用它來描述算法. 例如一些數學方面的結構充許人們在其上定義一個代數操作, 精化之,
   擴充之, 做各種各樣的事.
 
   雖然有很多有趣的創意, 最終該項研究沒有取得任何實用成果, 因為Tecton語言是函數型
   語言. 我們信奉Backus的理念，相信自己能把編程從von Neumann風格中解放出來. 我們
   不想使用副效應, 這一點限制了我們的能力, 因為存在大量需要使用諸如"狀態", "副效
   應"等觀念的算法.   
   我在70年代末期在Tecton上面所認識到了一個有趣的問題: 被廣泛接受的ADT觀念有著根本
   性的缺陷. 人們通常認為ADT的特點是只暴露對象行為特征, 而將實現隱藏起來. 一項操作
   的復雜度被認為是與實現相關的屬性, 所以抽象的時候應予忽略. 我則認識到, 在考慮一
   個(抽象)操作時, 復雜度(或者至少是一般觀念上的復雜度)必須被同時考慮在內. 這一點
   現在已經成了GP的核心理念之一.
   例如一個抽象的棧stack類型,  僅僅保證你push進去的東西可以隨后被pop出來是不夠的,
   同樣極端重要的是, 不管stack有多大, 你的push操作必須能在常數時間內完成. 如果我
   寫了一個stack, 每push一次就慢一點, 那誰都不會用這個爛玩藝.
   我們是要把實現和界面分開, 但不能完全忽略復雜度. 復雜度必須是, 而且也確實是橫陳
   于模塊的使用者與實現者之間的不成文契約. ADT觀念的引入是為了允許軟件模塊相互可
   替換. 但除非另一個模塊的操作復雜度與這個模塊類似, 否則你肯定不愿意實現這種互換.
   如果我用另外一個模塊替換原來的模塊, 并提供完全相同的接口和行為, 但就是復雜度不
   同, 那么用戶肯定不高興. 就算我費盡口舌介紹那些抽象實現的優點, 他肯定還是不樂意
   用. 復雜度必須被認為是接口的一部分.
   1983年左右, 我轉往紐約布魯克林技術大學任教. 開始研究的是圖的算法, 主要的合作伙
   伴是現在IBM的Aaron Kershenbaum. 他在圖和網絡算法方面是個專家, 我使他相信高序(high
   order)的思想和GP能夠應用在圖的算法中. 他支持我與他合作開始把這些想法用于實際的
   網絡算法. 某些圖的算法太復雜了, 只進行過理論分析, 從來沒有實現過. 他企圖建立一個
   包含有高序的通用組件的工具箱, 這樣某些算法就可以實現了. 我決定使用Lisp語言的一個
   變種Scheme語言來建立這樣一個工具箱. 我們倆建立了一個巨大的庫, 展示了各種編程技術.
   網絡算法是首要目標. 不久當時還在通用電器的David Musser加了進來, 開發了更多的組件,
   一個非常大的庫. 這個庫供大學里的本科生使用, 但從未商業化. 在這項工作中, 我了解到
   副效應是很重要的, 不利用副效應, 你根本沒法進行圖操作. 你不能每次修改一個端點(vertex)
   時都在圖上兜圈子. 所以, 當時得到的經驗是在實現通用算法時可以把高序技術和副效應結
   合起來. 副效應不總是壞的, 只有在被錯誤使用時才是.
   1985年夏, 我回到通用電器講授有關高序程序設計的課程. 我展示了在構件復雜算法時這項
   技術的應用. 有一個聽課的人叫陳邇, 當時是信息系統實驗室的主任. 他問我是否能用Ada語
   言實現這些技術, 形成一個工業強度的庫, 并表示可以提供支持. 我是個窮助教, 所以盡管我
   當時對于Ada一無所知, 我還是回答"好的". 我跟Dave Musser一起建立這個Ada庫. 這是很重
   要的一個時期, 從象Scheme那樣的動態類型語言(dynamically typed language)轉向Ada這
   樣的強類型語言, 使我認識到了強類型的重要性. 誰都知道強類型有助于糾錯. 我則發現在
   Ada的通用編程中, 強類型是獲取設計思想的有力工具. 它不僅是查錯工具, 而且是思想工具.
   這項工作給了我對于組件空間進行正交分解的觀念. 我認識到, 軟件組件各自屬于不同的類別.
   OOP的狂熱支持者認為一切都是對象. 但我在Ada通用庫的工作中認識到, 這是不對的. 二分查找
   就不是個對象, 它是個算法. 此外, 我還認識到, 通過將組件空間分解到幾個不同的方向上, 我
   們可以減少組件的數量, 更重要的是, 我們可以提供一個設計產品的概念框架.
   隨后, 我在貝爾實驗室C++組中得到一份工作, 專事庫研究. 他們問我能不能用C++做類似的事.
   我那時還不懂C++, 但當然, 我說我行. 可結果我不行, 因為1987年時, C++中還沒有模板, 這玩
   藝在通用編程中是個必需品. 結果只好用繼承來獲取通用性, 那顯然不理想.
   直到現在C++繼承機制也不大用在通用編程中, 我們來說說為什么. 很多人想用繼承實現數據結構
   和容器類, 結果幾乎全部一敗涂地. C++的繼承機制及與之相關的編程風格有著戲劇性的局限. 用
   這種方式進行通用編程, 連等于判斷這類的小問題都解決不了. 如果你以X類作為基類, 設計了
   一個虛函數operater==, 接受一個X類對象, 并由X派生類Y, 那么Y的operator==是在拿Y類對象與
   X類對象做比較. 以動物為例, 定義animal類, 派生giraffe(長頸鹿)類. 定義一個成員函數
   mate(), 實現與另一個哺乳動物的交配操作, 返回一個animal對象. 現在看看你的派生類giraffe,
   它當然也有一個mate()方法, 結果一個長頸鹿同一個動物交配, 返回一個動物對象. 這成何體統?
   當然, 對于C++程序員來說, 交配函數沒那么重要, 可是operator==就很重要了.
   對付這種問題, 你得使用模板. 用模板機制, 一切如愿. 
   盡管沒有模板, 我還是搞出來一個巨大的算法庫, 后來成了Unix System Laboratory Standard
   Component Library的一部分. 在Bell Lab, 我從象Andy Koenig, Bjarne Stroustrup(Andrew 
   Koenig, 前ISO C++標準化委員會主席; Bjarne Stroustrup, C++之父 -- 譯者)這類專家
   身上學到很多東西. 我認識到C/C++的重要, 它們的一些成功之處是不能被忽略的. 特別是我發
   現指針是個好東東. 我不是說空懸的指針, 或是指向棧的指針. 我是說指針這個一般觀念. 地
   址的觀念被廣泛使用著. 沒有指針我們就沒法描述并行算法.
   我們現在來探討一下為什么說C是一種偉大的語言. 通常人們認為C是編程利器并且獲得如此成功,
   是因為UNIX是用C寫的. 我不同意. 計算機的體系結構是長時間發展演變的結果, 不是哪一個聰明
   的人創造的. 事實上是廣大程序員在解決實際問題的過程中提出的要求推動了那些天才提出這些
   體系. 計算機經過多次進化, 現在只需要處理字節地址索引的內存, 線性地址空間和指針. 這個
   進化結果是對于人們要求解決問題的自然反映. Dennis Ritchie天才的作品C, 正反映了演化了
   30年的計算機的最小模型. C當時并不是什么利器. 但是當計算機被用來處理各種問題時, 作為
   最小模型的C成了一種非常強大的語言, 在各個領域解決各種問題時都非常高效. 這就是C可移植
   性的奧秘, C是所有計算機的最佳抽象模型, 而且這種抽象確確實實是建立在實際的計算機, 而
   不是假想的計算機上的. 人們可以比較容易的理解C背后的機器模型, 比理解Ada和Scheme語言背
   后的機器模型要容易的多. C的成功是因為C做了正確的事, 不是因為AT&T的極力鼓吹和UNIX.
   C++的成功是因為Bjarne Stroustrup以C為出發點來改進C, 引入更多的編程技術, 但始終保持在
   C所定義的機器模型框架之內, 而不是閉門造車地自己搞出一個新的機器模型來. C的機器模型非
   常簡單. 你擁有內存, 對象保存在那里面, 你又有指向連續內存空間的指針, 很好理解. C++保留
   了這個模型, 不過大大擴展了內存中對象的范疇, 畢竟C的數據類型太有限了, 它允許你建立新的
   類型結構, 但不允許你定義類型方法. 這限制了類型系統的能力. C++把C的機器模型擴展為真正
   類型系統.
   1988年我到惠普實驗室從事通用庫開發工作. 但實際上好幾年我都是在作磁盤驅動器. 很有趣但跟
   GP毫不相關. 92年我終于回到了GP領域, 實驗室主任Bill Worley建立了一個算法研究項目, 由我
   負責. 那時候C++已經有模板了. 我發現Bjarne的模板設計方案是非常天才的. 在Bell Lab時, 我參
   加過有關模班設計的幾個早期的討論, 跟Bjarne吵得很兇, 我認為C++的模板設計應該盡可能向Ada的
   通用方案看齊. 我想可能我吵得太兇了, 結果Bjarne決定堅決拒絕我的建議. 我當時就認識到在C++
   中設置模板函數的必要性了, 那時候好多人都覺得最好只有模板類. 不過我覺得一個模板函數在使用
   之前必須先顯式實例化, 跟Ada似的. Bjarne死活不聽我的, 他把模板函數設計成可以用重載機制來
   隱式實例化. 后來這個特別的技術在我的工作中變得至關重要, 我發現它容許我做很多在Ada中不可能
   的任務. 非常高興Bjarne當初沒聽我的. 
Q: 您是什么時候第一次構思STL的, 最初的目的是什么?
A: 92年那個項目建立時由8個人, 漸漸地人越來越少, 最后剩下倆, 我和李夢, 而且李小姐是這個領域的新
   手. 在她的專業研究中編譯器是主要工作, 不過她接受了GP研究的想法, 并且堅信此項研究將帶給軟件開
   發一個大變化, 要知道那時候有這個信念的認可是寥寥無幾. 沒有她, 我可不敢想象我能搞定STL, 畢竟