STL之父访谈录STL之父访谈录.doc

STL之父访谈录 1995年3月，Dr。Dobbs Journal特约记者， 著名技术书籍作家Al Stevens采访了STL创始人Alexander Stepano。这份访谈纪录是迄今为止对于STL发展历史的最完备介绍， 侯捷先生在他的STL有关文章里 推荐大家阅读这篇文章。 因此我将该文全文翻译如下： Q：您对于generic programming进行了长时间的研究， 请就此谈谈。 A：我开始考虑有关GP的问题是在7O年代末期， 当时我注意到有些算法并不依赖于数据结构的特定实现，而只是依赖于该结构的几个基本的语义属性。 于是我开始研究大量不同的算法，结果发现大部分算法可以用这种方法从特定实现中抽象出来， 而且效率无损。 对我来说，效率是至关重要的， 要是一种算法抽象在实例化会导致性能的下降， 那可不够棒。 当时我认为这项研究的正确方向是创造一种编程语言。 我和我的两个朋友一起开始干起来。一个是现在的纽约州立大学教授Deepak Kapur， 另一个是伦塞里尔技术学院教授David Musser。当时我们三个在通用电器公司研究中心工作。 我们开始设计一种叫Tecton的语言。 该语言有一种我们称为通用结构的东西， 其实不过是一些形式类型和属性的集合体， 人们可以用它来描述算法。 例如一些数学方面的结构充许人们在其上定义一个代数操作， 精化之，扩充之， 做各种各样的事。 虽然有很多有趣的创意， 最终该项研究没有取得任何实用成果， 因为Tecton语言是函数型语言。 我们信奉Backus的理念，相信自己能把编程从von Neumann风格中解放出来。 我们不想使用副效应， 这一点限制了我们的能力， 因为存在大量需要使用诸如“状态”， “副效应”等观念的算法。 我在70年代末期在Tecton上面所认识到了一个有趣的问题： 被广泛接受的ADT(注释1)观念有着根本性的缺陷。 人们通常认为ADT的特点是只暴露对象行为特征， 而将实现隐藏起来。 一项操作的复杂度被认为是与实现相关的属性， 所以抽象的时候应予忽略。 我则认识到， 在考虑一个(抽象)操作时， 复杂度(或者至少是一般观念上的复杂度)必须被同时考虑在内。 这一点现在已经成了GP(注释2)的核心理念之一。 例如一个抽象的栈stack类型， 仅仅保证你push进去的东西可以随后被pop出来是不够的，同样极端重要的是， 不管stack有多大， 你的push操作必须能在常数时间内完成。 如果我写了一个stack， 每push一次就慢一点， 那谁都不会用这个烂玩艺。 我们是要把实现和界面分开， 但不能完全忽略复杂度。 复杂度必须是， 而且也确实是横陈于模块的使用者与实现者之间的不成文契约。 ADT观念的引入是为了允许软件模块相互可替换。 但除非另一个模块的操作复杂度与这个模块类似， 否则你肯定不愿意实现这种互换。 如果我用另外一个模块替换原来的模块， 并提供完全相同的接口和行为， 但就是复杂度不同， 那么用户肯定不高兴。 就算我费尽口舌介绍那些抽象实现的优点， 他肯定还是不乐意用。 复杂度必须被认为是接口的一部分。 1983年左右， 我转往纽约布鲁克林技术大学任教。 开始研究的是图的算法， 主要的合作伙伴是现在IBM的Aaron Kershenbaum。 他在图和网络算法方面是个专家， 我使他相信高序(high order)的思想和GP能够应用在图的算法中。 他支持我与他合作开始把这些想法用于实际的网络算法。 某些图的算法太复杂了， 只进行过理论分析， 从来没有实现过。 他企图建立一个包含有高序的通用组件的工具箱， 这样某些算法就可以实现了。 我决定使用Lisp语言的一个变种Scheme语言来建立这样一个工具箱。 我们俩建立了一个巨大的库， 展示了各种编程技术。网络算法是首要目标。 不久当时还在通用电器的David Musser加了进来， 开发了更多的组件，一个非常大的库。 这个库供大学里的本科生使用， 但从未商业化。 在这项工作中， 我了解到副效应是很重要的， 不利用副效应， 你根本没法进行图操作。 你不能每次修改一个端点(vertex)时都在图上兜圈子。 所以， 当时得到的经验是在实现通用算法时可以把高序技术和副效应结合起来。 副效应不总是坏的， 只有在被错误使用时才是。 1985年夏， 我回到通用电器讲授有关高序程序设计的课程。 我展示了在构件复杂算法时这项技术的应用。 有一个听课的人叫陈迩， 当时是信息系统实验室的主任。 他问我是否能用Ada语言实现这些技术， 形成一个工业强度的库， 并表示可以提供支持。 我是个穷助教， 所以尽管我当时对于Ada一无所知， 我还是回答“好的”。 我跟Dav