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的一部份. 在贝尔, 我从象Andrew 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做了正确的事, 不是因为UNIX和 AT&T的极力鼓吹。

C++的成功是因为Bjarne Stroustrup以C为出发点来改进C, 虽然引入了更多的编程技术, 但始终保持在C所定义的机器模型框架之内, 而不是闭门造车地自己搞出一个新的机器模型来. C的机器模型非常简单. 你拥有内存, 对象保存在那里面, 你又有指向连续内存空间的指针, 很好理解. C++保留了这个模型, 不过大大扩展了内存中对象的范畴, 毕竟C的数据类型太有限了, 它允许你建立新的类型结构, 但不允许你定义属於类型方法. 这限制了类型系统的能力. C++把C的机器模型扩展为真正类型系统.

1988年我到惠普实验室从事通用库开发工作，但实际上好几年我都是在作磁盘驱动器，很有趣但跟 GP毫不相关. 92年我终於回到了GP领域, 实验室主任Bill Worley建立了一个算法研究项目, 由我负责. 那时候C++已经有模板了. 我发现Bjarne的模板设计方案是非常天才的. 在贝尔时, 我叁加过有关模板设计的几个早期的讨论, 跟Bjarne吵得很凶, 我认为C++的模板设计应该尽可能向Ada的通用方案看齐. 我想可能我吵得太凶了, 结果Bjarne决定坚决拒绝我的建议. 那时候好多人都觉得最好只有模板类，而我当时就认识到在C++中有必要设置模板函数机制。不过我觉得一个模板函数在使用之前必须先显式实例化, 跟Ada似的. Bjarne死活不听我的, 他把模板函数设计成可以用重载机制来隐式实例化. 後来这个特别的技术在我的工作中变得至关重要, 我发现它容许我做很多在Ada中不可能的任务. 非常高兴Bjarne当初没听我的.


Q: 除了标准类库外，STL对那一类的应用程序来说最有用处？

A: 我希望STL能够引导大家学习一种新的编程风格：通用编程。我相信这种风格适用于任何种类的应用程序。这种风格就是：用最通用的方式来写算法和数据结构。这些结构所要求的语义特性应该能够被清楚地归类和分类，而这些归类分类的原则应该是任何对象都能满足的。理解和发展这种技术还要很长时间，STL不过是这个过程的起点。

我们最终会对通用的组件有一个标准的分类，这些组件具有精心定义的接口和复杂度。程序员们将不必在微观层次上编程。你再也不用去写一个二分查找算法。就是在现在，STL也已经提供了好几个通用的二分查找算法，凡是能用二分查找算法的场合，都可以使用这些算法。算法所要求的前提条件很少：你只要在代码里使用它。我希望所有的组件都能有这麽一天。我们会有一个标准的分类，人们不用再重复这些工作。

这就是Douglas McIlroy的梦想，他在1968年关於“构件工厂”的那篇着名文章中所提出来的东西(M.Douglas McIlroy博士现在在贝尔实验室计算机科学研究中心工作，那篇文章的题目是Mass Produced Software Components, 现在还可以在http://cm.bell-labs.com/cm/cs/who/doug/components.txt找到这篇论文  译者)。STL就是这种“构件工厂”的一个范例。当然，还需要有主流的力量介入这种技术的发展之中，光靠研究机构不行，工业界应该想程序员提供组件和工具，帮助他们找到所需的组件，把组件粘合到一起，然後确定复杂度是否满足预期要求。

Q: STL没有实现一个持久化(persistent)对象容器模型。map和multimap似乎是比较好的候选者，它们可以把对象按索引存入持久对象数据库。您在此方向上做了什麽工作吗，或者对这类实现有何评论？

A：很多人都注意到这个问题。STL没实现持久化是有理由的。STL在当时已经是能被接受的最巨大的库了。再大一点的话，我认为委员会肯定不会接受。当然持久化是确实是人们提出的要求。在设计STL，特别是设计allocator时，Bjarne认为这个封装了内存模式的组件可以用来封装持久性内存模式。Bjarne的洞察秋毫非常的重要和有趣，好几个对象数据库公司正在盯着这项技术。1994年10月我叁加了Object Database Management Group的一个会议，我做了一个关於STL的演说。他们非常感兴趣，想让他们正在形成中的组件库的接口与STL一致，但不包括allocator在内。不过该集团的某些成员仔细分析了allocator是否能够被用来实现持久化。我希望与STL接口一致的组件对象持久化方案能在接下来的一年里出现。


Q：ANSI/ISO C标准委员会认为像内存模式这类问题是平台相关的，没有对此做出什麽具体规定。C++委员会会不会采取不同的态度？为什麽？

A：我认为STL在内存模式这一点上跟C++标准相比是超前的。C和C++之间有着显着的不同。C++有构造函数和new操作符来对付内存模式问题，而且它们是语言的一部份。现在看来当时如果能让new操作符像STL容器使用allocater那样来工作就好了。不过现在问题的重要性不像STL出现之前那麽米明显了，因为在大多数场合，STL数据结构将让new失业。大部份人不再需要分配一个数组，因为STL在做这类事情上更为高效。要知道我对效率的迷信是无以复加的，可我在我的代码里从不使用new，汇编代码表明其效率
比使用new时更高。随着 STL的广泛使用，new会逐渐淡出江湖。而且STL永远都会记住回收内存，因为当一个容器，比如vector退出作用域时，它的析构函数被调用，会把容器里的所有东西都析构。你也不必再担心内存泄漏了。STL可以戏剧性地降低对於垃圾收集机制的需求。使用STL容器，你可以为所欲为，不用关心内存的管理，自有STL构造函数和析构函数来对付。


Q：通用编程跟OOP之间有什麽关系？

A：什麽是OOP的基本思想呢？把组件的实现和接口分开，并且让组件具有多态性。一句话，通用编程是OOP这个基本思想的自然延续。不过，两者还是有根本的不同。OOP强调在程序构造中语言要素的语法。你必须得继承，使用类，使用对象，对象传递消息。而GP不关心你继承或是不继承，它的开端是分析产品的分类，有些什麽种类，他们的行为如何。就是说，两件东西相等意味着什麽？怎样正确地定义相等操作？并不像想的那麽简单，你往深处份析就会发现“相等”这个一般观念意味着两个对象的部份，或者至少基本部份是相等的，据此我们就可以有一个通用的相等操作。再说对象的种类。假设存在一个顺序序列和一组对於顺序序列的操作。那麽这些操作的语义是什麽？从复杂度权衡的角度看，我们应该向用户提供什麽样的顺序序列？该种序列上存在那些操作？那种排序是我们需要的？只有对这些组件的概念型分类搞清楚了，我们才能提到实现的问题：使用模板 继承还是宏？使用什麽语言和技术？GP的基本观点是把抽象的软件组件和它们的行为用标准的分类学分类，出发点就是要建造真实的高效的和不取决于语言的算法和数据结构。当然最终的载体还是语言，没有语言没法编程。STL使用C++，你也可以用Ada来实现，用其他的语言来实现也行，结果会有所不同，但基本的东西是一样的。到处都要用到二分查找和排序，而这就是人们正在做的。对於容器的语义，不同的语言会带来轻微的不同。但是基本的区别很清楚是GP所依存的语义，以及语义分解。例如，我们决定需要一个组件swap，然後指出这个组件在不同的语言中如何工作。显然重点是语义以及语义分类。而OOP所强调的（我认为是过份强调的）是清楚的定义类之间的层次关系。OOP告诉了你如何建立层次关系，却没有告诉你这些关系的实质。（这段不太好理解，有一些术语可能要过一段时间才会有合适的中文翻译 译者）

Q：您对STL和GP的未来怎麽看?

A：我刚才提到过，程序员们的梦想是拥有一个标准的组件仓库，其中的组件都具有良好的易于理解的和标准的接口。为了达成这一点，GP需要有一门专门的科学来作为基础和支柱。STL在某种程度上开始了这项工作，它对於某些基本的组件进行了语义上的分类。我们要在这上面下更多的功夫，目标是要将软件工程从一种手工艺技术转化为工程学科。这需要一门对於基本概念的分类学，以及一些关於这些基本概念的定理，这些定理必须是容易理解和掌握的，每一个程序员即使不能很清楚的知道这些定理，也能正确地使用它。很多人根本不知道交换律，但只要上过学的人都知道2+5等於5+2。我希望所有的程序员都能学习一些基本的语义属性和基本操作：赋值意味着什麽？相等意味着什麽？怎样建立数据结构，等等。

当前，C++是GP的最佳载体。我试过其他的语言，最後还是C++最理想地达成了抽象和高效的统一。但是我觉得可能设计出一种语言，集成C和很多C++的卓越思想，而又更适合于GP。它没有C++的一些缺陷，特别是不会像C++一样庞大。STL处理的东西是概念。什麽是迭代子？不是类，不是类型，是概念。说得更正式一些，这是Bourbaki所说的结构类型（structure type），是逻辑学家所说的理念（theory），或是类型理论学派的人所说的种类（sort），这种东西在C++里没有语言层面上的对应物（原文是incarnation，直译为肉身 译者），但是可以有。你可以拥有一种语言，使用它你可以探讨概念，精化概念，最终用一种非常“程序化”的手段把它们转化为类。当然现在就有一些语言能处理种类（sorts），但是当你想排序（sort）时它们没什麽用处。我们能够有一种语言，用它我们能定义叫做foward iterator（前向迭代子）的东西，在STL里这是个概念，没有C++对应物。然後我们可以从forword iterator中发展出bidirectional iterator（双向迭代子），再发展出random iterator。可能设计一种语言大为简化GP，我完全相信该语言足够高效，其机器模型与C/C++充份接近。我完全相信能够设计出一种语言，一方面尽可能地靠近机器层面以达成绝对的高效，另一方面能够处理非常抽象化的实体。我认为该语言的抽象性能够超过C++，同时又与底层的机器之间契合得天衣无缝。我认为GP会影响到语言的研究方向，我们会有适于GP的实用语言。从这些话中你应该能猜出我下一步的计划。