stl之父访谈录.txt

学习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, 毕竟
   STL标着两个人的名字:Stepanov和Lee. 我们写了一个庞大的库, 庞大的代码量, 庞大的数据结构组件,
   函数对象, 适配器类, 等等. 可是虽然有很多代码, 却没有文档. 我们的工作被认为是一个验证性项目,
   其目的是搞清楚到底能不能在使算法尽可能通用化的前提下仍然具有很高的效率. 我们化了很多时间来
   比较, 结果发现, 我们算法不仅最通用, 而且要率与手写代码一样高效, 这种程序设计风格在性能上是
   不打折扣的! 这个库在不断成长, 但是很难说它是什么时候成为一个"项目"的. STL的诞生是好几件事情
   的机缘巧合才促成的.

Q: 什么时候, 什么原因促使您决定建议使STL成为ANSI/ISO标准C++一部分的?
A: 1993年夏, Andy Koenig跑到斯坦福来讲C++课, 我把一些有关的材料给他看, 我想他当时确实是很兴奋.
   他安排我9月到圣何塞给C++标准委员会做一个演讲. 我演讲的题目是"C++程序设计的科学", 讲得很理