STL之父A.Stepanov专访
Graziano Lo Russo Edizioni Infomedia srl 著 荣耀 译
问：
可以先做个自我简介吗？
答：
1950年11月16日，我出生于苏联莫斯科。在莫斯科大学研究数学，但我从未成为一名数学家。我实在不能对Tamagawa算术感到兴奋，尽管别人以为我擅长Coxeter群和一些别的东西。Hardy的念头对我毫无吸引力─他的数学从来都不打算被实用化。我想干一些哪怕只有那么一丁点儿实际意义的事。不过，话说回来，我还是幸运的，能够看到很多伟大的数学家是如何做的，使我能彻底对那些批着数学外衣的所谓严谨免疫。不幸的是，这在计算机科学中司空见惯。因此，能成为一名程序员对我来说真是一件好事。1972年，我作为一名小组成员，参与开发一个用于控制大型水电站的新的小型机系统。我参与了所有部分的设计，从架构到OS硬件测试（我的第一篇公开发表的论文就是关于实时操作系统的）到编程工具。我学到了关于软件可靠性和效率的第一手知识─电站系统是不能轻易重新启动的，水流也总是实时冲泄而下的。
那时，我还探索了两位伟大的计算机科学家Donald Knuth和Edsger Dijkstra的著作，从他们那儿，我学到了奠定我职业基础的科学知识。前者告诉我答案，后者则引我深思。我一次又一次地到他们的著作中寻觅新的见解。我的下一个重要的职业生涯阶段是在纽约Schenectady的通用电器研究中心计算机科学分部工作了5年。我致力于一个叫Tecton的非常高级的语言，阅读了大量的资料，从繁多的程序语言设计论文到William of Occam的逻辑纲要─亚里斯多德和中世纪逻辑学家知道许多出现在自然语言里的不同种类的逻辑结构以及它们的正式属性。从那时起直到现在，我和Dave Musser合作，进行了硕果累累的研究。1984年，我成为一名纽约布鲁克林理工大学助理教授。教授计算机科学使我受益非浅，我要对付各种研究生课程。在此过程中，我学到了很多新东西。我还用Scheme语言开发了一个巨大的数据结构和算法库，这项工作导致了Ada泛型库的诞生（和Dave Musser合作）。在贝尔实验室短暂地研究了一段时间C++算法库后，我便去了位于Palo Alto的惠普实验室（1988年）。在这儿，我花了四年时间研究存储系统─我不得不学习磁盘控制器程序设计。1993年，我得到了一个短暂的回头研究泛型编程的机会。STL就是这次研究的结果。1995年我又到了Silicon Graphics，在此，我正试图组建一个小组进行进一步的STL开发工作。
问：
你刚才提到了William of Occam。William of Occam曾说过“Entia non sunt multiplicanda”─我把它译为“[抽象]对象是不必要的”。好象你已经对OOP举起了Occam的剃刀。以算法而不是对象为起点之类的东西使我想起了中世纪关于宇宙的争论，是这样吗？
答：
这个比方很妙，但我并不认为它是对的。我从来都不认为OO和现实主义者的哲学有什么联系，我也压根不是一个唯名论者。一个不容否认的事实是，Franciscan学派的Alexander of Hales、Bonaventure和Scotus都非常亲近奥古斯丁教义/柏拉图式的传统。Occam是不折不扣的个异端分子。作为他的Opera Omnia的编辑， Gideon Gal曾说过：“但是这家伙真的疯了！”
问：
对于绝大多数意大利读者来说，“Stepanov”的名字和STL是不可分割的。STL究竟是指Standard Template Library（标准模板库）还是 Stepanov and Lee？另外，在STL的历史里，D.Musser和A.Koenig扮演了什么样的角色？
答：
哦，它真的是指Standard Template Library。我曾经在Dr. Dobb的杂志做的那个专访里开玩笑说，STL是指“Stepanov and Lee”，但它只是个玩笑而已。我已经和Dave Musser合作近20年了，我们之间的合作是如此紧密，以致于很难说清到底谁贡献了什么。他之所以没有出现在官方的STL作者的名单里，仅仅因为在撰写标准提议的那一小段时间里，他在忙些别的。Andy Koenig负责向我解释抽象C机（abstract C machine）的结构。STL，从某种意义上说，是Dave Musser和我一直进行C机模型开发的泛型编程技术的一个应用。如果不是Andy，我可能还在处理装箱、堆分配对象问题并为垃圾收集而憔悴。当然，Andy还和Bjarne Stroustrup负责把STL弄到标准里去了。当要把美妙的想法变成完整的实现时，Meng Lee是一位无可挑剔的合作伙伴。她使我专注─我经常会在问题得到解决之后失去兴趣─我知道解决办法就够了，干吗还要费神让世界上其他人也知道呢？她在代码和文档上花了大量的令人筋疲力尽的时间。从某种意义上说，她是唯一坚信能从那些原材料中加工出实际东西的人。我想，在这一点上，对于能向任何人解释清楚我们搞了许久的究竟是啥玩意，Dave Musser和我都早已不抱任何希望。
问：
STL起源于什么？STL一开始就被设想为今天这个样子吗？即所谓的C++标准库，或者，它来自于别的什么项目？告诉我们一些关于STL的历史好吗？
答：
1976年，又要说回到苏联了，我因为吃生鱼片得了严重的食物中毒。当住在医院的时候，在精神错乱的状态下，我忽然意识到，并行的加法计算能力依赖于加法具有结合性的事实。（因此，简单地说，STL是细菌感染的结果。）换句话说，我意识到并行的减法运算是和半群结构类型有关联的。这就是基本点：算法是定义于代数结构基础之上的。意识到必须对正规公理加入复杂性必要条件以扩展结构的概念，又花了我另外一些年头，接着我又花了15年使之行得通。（我直到现在都不能确定我已经成功地使我朋友小圈子之外的任何人理解了这一点。）我相信迭代器理论是计算科学的中心，就象环或Banach空间理论是数学的中心一样。每当我找到一个算法时，我都要努力去寻求它所定义的结构基础。我想做的就是泛化地描述算法，并乐此不疲。我愿意花一个月时间去发现某个著名算法的泛化表示。迄今为止，在向人们解释我这种行为的重要性方面，我是异乎寻常的失败。但是，不知何故，这种行为的结果─STL，却是如此成功。
问：
我曾认为STL的复杂性纯粹是由于实现的效率而不得不如此，而你好象暗示复杂性的确是功能上的需要？果真如此吗？
答：
选择不同的算法依赖于数据结构提供的基本运算的复杂性。对于SCSI存储设备来说，磁盘和磁带在功能是等效的，但对于一个想把磁带当成磁盘使用的软件设计人员来说无疑是苦恼的。再看看STL，你总可以为前向迭代器实现p+n，为什么还要费心提供随机存取迭代器呢？
问：
何谓泛型编程？我只在JOOP上看到A.Koenig写的一些“泛型编程”专栏。在大多数C++语言书籍里，包括Coplien Meyer、Stroustrup、Lippman等人的，都很难看到泛型编程。我想，STL应该描述为“用你从未认为可能的方式编写C++程序”，你赞同这个说法吗？
答：
STL，至少对我来说，代表用一致的方式编程是可能的。实际上，它完全不同于我们过去看到的C++编程，也完全不同于大多数教科书里所描述的方式。但是，你知道，我并不是试图用C++编程，我只是试图找到一种正确的方式，来处理软件。我已经为寻找一个可以表达我的想法的语言好长时间了。换句话说，我知道我想说什么。我能用C++说，我能用Ada说，我能用Scheme说。我可以让自己去适应语言，但本质上，我试图要说的，和语言无关。迄今为止，C++是我发现可以表达我想说的最好的语言。它虽不是理想的媒介，但用它我可以比用别的语言表达得更多。实际上，我的梦想是哪天会出现一种专为泛型编程而设计的语言。
问：
你可以为普通C++程序员解释一下什么是泛型编程、泛型编程和C++以及STL的关系吗？并且，你是怎么想到在C++环境里进行泛型编程的？
答：
泛型编程是一种基于发现高效算法的最抽象表示的编程方法。也就是说，以算法为起点并寻找能使其工作且有效率工作的最一般的必要条件集。令人惊讶的是，很多不同的算法都需要相同的必要条件集，并且这些必要条件有多种不同的实现方式。类似的事实在数学里也可以看到。大多数不同的定理都依赖于同一套公理，并且对于同样的公理存在多种不同的模型。抽象机制！泛型编程假定有某些基本的法则在支配软件组件的行为，并且基于这些法则有可能设计可互操作的模块。甚至还有可以使用此法则去指导我们的软件设计。STL就是一个泛型编程的例子。C++是我可以实现出令人信服的例子的语言。
问：
我认为STL和泛型编程标志着一个不同于一般C++编程风格（我发现这种风格基本上是从SmallTalk继承过来的）的新起点。你赞成这个说法吗？
答：
是的。STL不是面向对象的。我认为面向对象和人工智能差不多，都是个骗局。我已经看到了来自那些OO的人们写的“有趣的”代码。从某种程度上说，我对人工智能（AI）有偏见。我听说好多关于MIT AI实验室的一帮人的东西了，他们真正干了一些基础性的工作：Bill Gosper的Hakmem是程序员最好的读物之一。AI或许没有一个严肃的基础，但它制造出了Gosper和Stallman（Emacs）， Moses（Macsyma）和Sussman（Scheme， 连同Guy Steele）。我发现OOP在技术上是荒谬的，它妄图依照因单个类型而异的接口来分解世界，为了处理实际问题你需要多种代数方法─横跨多种类型的接口族；我发现OOP在哲学上是荒谬的，它声称一切都是对象。即使真的是这样这也不是很有趣，说一切都是对象跟什么都没说一样；我发现OOP的方法论是错误的，它从类开始，就好像数学要从公理开始一样。你不是从公理开始，你是从证明开始。直到你找到了一大堆相关证据后你才能归纳出公理，你是以公理结束。在程序设计方面存在着同样的事实：你要从有趣的算法开始。只有很好地理解了算法，你才有可能提出接口以让其工作。
问：
我可以总结你的思想为“发现隐藏在算法之中的[泛型]数据结构”，而不是“发现隐藏在对象之中的[虚]算法”吗？
答：
没错。总是开始于算法。
问：
这需要从思想上做一个激进的改变，无论在命令式（imperative）还是OO思想方面。相比“标准”OO程序设计，比如SmallTalk或Java，这种方式利弊在于？
答：
我的方式行得通，他们的行不通。试试用OO方式来实现一个简单的东西，比如说max，我不知道OO怎么能办得到。使用泛型编程，我可以这么写：
template <class StrictWeakOrdered>
inline StrictWeakOrdered& max(StrictWeakOrdered& x,StrictWeakOrdered& y)
{return x < y ? y : x;}
和
template <class StrictWeakOrdered>
inline const StrictWeakOrdered& max(const StrictWeakOrdered& x,const StrictWeakOrdered& y)
{return x < y ? y : x;}
（&和const &两个都要）。然后，我可以定义strict weak ordered的含义。用Java试试。你不能用Java写一个泛型的max()，传入两个某种类型的参数并返回一个同类型的结果。继承和接口在这儿无济于事。假如连max或swap或linerar search都不能实现，那它们还有多大的把握去实现真正复杂的东西呢？这些就是我的石蕊试验法：如果一种语言能让我实现泛型的max、swap和linear search，那它还是有那么一些潜力的（译注：指泛型编程）。
问：
Java是一门非常新的语言，它还没有模板，因此禁用泛型编程，一切都必须是类。你对Java怎么看？
答：
我花了几个月用Java来写程序。跟它的作者预言的相反，它并没有勾起我的兴趣。我没有从中发现任何新的见解。有生以来，我第一次在一种新语言里编程而没有发现新见解。它保留了所有我在C++里从来都不使用的东西─继承、虚机制（OO垃圾），并且拿掉了我认为有用的东西。它可能会成功，毕竟，MS DOS就成功过，而且对于你们学习Java的读者来说可能有利可图，但它毫无任何知识价值。看看他们对散列表的实现，瞧瞧那些“酷”的sorting applet所使用的排序例程，再试试AWT。评判一门语言的最好的办法是看看它的鼓吹者们写的代码。“!@#$%^&%$！×￥#”，（译注：原文是“Radix enim omnium malorum est cupiditas”），Java显然是一个面向金钱编程（MOP）的例子。SGI的Java首要倡导者曾对我说：“Alex，你必须去有钱的地方。”但我并不太想去有钱的地方，那种地方，味道通常都好不到哪里去。
问：
你认为基于模板的编程和泛型编程会被大多数C++程序员采用吗？或者，它们仅仅局限于使用在STL内，有点象操纵器（manipulators），它从不在iostream库以外使用。
答：
我不知道。STL背后蕴藏的思想需要一段很长的时间才会成为主流。10到15年后，一切都会真相大白。
问：
有一件事情我一直都很惊奇，C++标准委员会那么快就采纳了STL。我的意思是，这些委员会可都是以谨慎和保守而出名的。对此，你怎么解释？
答：
Bjarne Stroustrup的支持是至关重要的。如果说Bjarne想要什么东西的话，那就是他真的想把STL弄到标准里。他办到了。他象骡子一样固执。甚至逼着我去改STL，我从来都不会为第二个人这么做，我也是个顽固分子，但他是我所认识的最有主见的人。他成功了。理解STL是干啥的花了他一些时间，但当他明白之后，他决定使其更进一步。他对STL的贡献还在于他支持这个观点：不止一种编程方法是“合法的”。这反对了十来年的无休止的争吵和谎言，并坚持把弹性、效率、重载、类型安全结合在模板里，以使得STL成为可能。我很乐意明明白白地声明，Bjarne是我们这一代卓越的语言设计者。
问：
STL完全是对模板的创造性使用，比如从类中导出符号类型，或是对迭代器标记的一系列重载算法的模式匹配，当然足够了，没有任何标准C++书籍提到这些术语，你是怎么想出这些C++代码习语的？
答：
我清楚地知道我要努力达到的目标，于是我“拧”这个语言直到我能够过得去，但这花了我好多年去探索所有的技术。我有很多错误的开始。比方说，在我意识到为什么那种机制从根本上具有缺陷而不应该使用它之前，我浪费了好多年试图从继承和虚机制里找到一些有用的东西。我非常高兴没有人能看到任何中间步骤，它们大都是愚蠢可笑的。我花了好长时间才弄出一些象点样子的东西。这也对Bjarne愿意往语言里加入某些能使我的术语工作的特性起到了推动作用。有一次，他把这说成是“即时语言设计”。
问：
你认为向C++程序员教授泛型编程和STL的最佳方式是？你认为在学习STL之前、期间或之后，应该学习继承以及其他OO技术吗？
答：
我计划在SGI教授一门关于泛型编程的课，我非常希望这也能促使我出一本书，但我是一个声名狼藉的懒惰作者，我从来都没有完成论文过，除非我有一个合作伙伴来干这个事。
问：
我已经使用Lycos（译注：一种WWW搜索引擎）搜索过你的论文，我只找到两条，是你提供给标准委员会的关于STL的指南和摘要。
答：
是吗，我是懒，但我还没懒到那个份上。我大概发表了20来篇的论文并出了一本书。它们大都在不同的STL站点上。（Dave Musser的站点上可能有几篇。）
问：
那本书是？
答：
那本书叫《The Ada Generic Library: Linear List Processing Packages》，作者David R. Musser/Alexander A. Stepanov， 指南针系列，Springer-Verlag，1989。它并不值得一读。
问：
STL使C++编译器达到了它们的极限，同时代的C++编译器还不能正确地编译某些STL代码，你是怎么开发和测试STL的？
答：
为了试图编译STL我都白了不少头发了。不幸的现实是，当我开发STL时，因为编译器的限制和编译器里的bug，许多代码在当时的STL的实现中是不够理想的。幸运的是，我从Bjarne那儿得到了不少帮助，他指出某种尚未实现的特性假定会被实现。如果能有一位语言设计者告诉你，已经给出的设施究竟干了些什么，那是大有帮助的。
问：
配置器（allocators）是怎么到STL里的？你对它们怎么看？
答：
我发明了配置器去处理英特尔内存架构问题。理论上它们并不坏—添一层封装所有内存有关的东西：pointers、references、 ptrdiff_t、size_t。不幸的是，它们实际上不能工作。例如：
vector<int, alloc1> a(...);
vector<int, alloc2> b(...);
你现在不能说：
find(a.begin(), a.end(), b[1]);
b[1] 返回一个alloc2::reference并不是int&。它可能会导致类型不匹配。有必要改变实现方式—应该让语言核心去处理引用从而使配置器真正有用。
问：
这是不是指出了C++模板的一个严重的缺点？我可以使用模板引数（template argument）定制一个类，但不同的特化实现并非类型兼容，但一个类不同的子类（在OO意义上）和其根类是类型兼容的。
答：
我认为问题比“T* 是被hardwired在语言里”来得深。一般而言，我相信需要从头开始设计一种程序语言，可以一致方式进行泛型编程。我希望能有人雇我去干这个事。
问：
我在D.Musser站点上看到了两个散列表的实现，它们都可以工作并且十分灵巧，比一般类库里的要灵巧得多。为什么散列表没有纳入STL呢？
答：
“政治原因”（译注：意思是“有关公众的意愿”，下文皆然。）。它们应该包括进来。我们新的STL实现包括它们。大体上说，我们需要发展一个往STL里添东西的机制。毕竟，STL是个可扩展的框架，它也被请求扩展。有很多数据结构都还没加进来，比如，单向链接表、矩阵和图。SGI乐意在扩展STL方面起到领导作用。
问：
你还搞STL吗？具体搞什么？
答：
我在SGI的团队—Matt Austern、Hans Boehm和我自己，刚刚完成一个STL的新版本。它包括散列容器、线程安全内存配置以及壮观的WEB文档。SGI把它发布在http://www.sgi.com/Technology/STL，我们希望我们能保持STL不断成长。多维数据结构、持久化、多线程都是我们计划要加入的东西。唔，我不清楚我们还能搞这个东西多长时间。我的管理者们对STL/泛型编程活动没提供任何支持。向他们解释为什么SGI有责任扩展STL非常困难。（同样困难的是向惠普的管理层解释。在STL被接纳为标准之后，他们取消了我5个月的项目）。
问：
好像STL依然还存在某些不足之处。首先HP STL不是线程安全的。而且模板导致了要把大量的代码放到头文件中。你无法拥有真正的模板库，不管是DLL形式还是共享库（未具现化的）形式的模板—STL通常是编译时库。最后一点是几乎没有任何CASE工具和OOD方法学有效地支持泛型编程。比如，没有CASE工具能让你定义泛型函数，也只有Booch符号能在某种程度上表达模板，但它产生的图表并不直观（至少对我来说）。
答：
SGI STL是线程安全的。“单独编译”（separate compilation）已经被标准采纳，它是由我的SGI同事John Wilkinson、Jim Dehnert和Matt Austern设计的，它解决了你的第二个问题。它已经经投票纳入标准，但还需要一段时间才能有支持“单独编译”的编译器。我坚信“单独编译”最终需要交付共享模板库。这也是我在SGI发起单独编译工作的主要原因。设计处理泛型编程的工具并不困难，我敢肯定，只要市场需要，Grady Booch会改进他的符号来处理泛型编程的。
问：
让C++程序员感到痛苦的一件事是，那些标准委员会们好像彼此都无动于衷。OMG刚刚定义了一套分布式编程（CORBA）标准，但STL里并没有从CORBA到C++的映射。他们各自定义了自己的一套类，比如Sequence<T> 和 CORBA::String。同样的问题也出现在ODMG和ODMG-93对象数据库标准上。怎么会发生这种事？这种状况能得到改变吗？
答：
我老得都记不得70年代提出的所有网络标准了。谁现在还能记得它们？
问：
泛型编程在分布式环境里会是什么样子？泛型编程是基于这样的思想的：编译器在编译时知道所有可能的类型。这在分布式环境里是不现实的。我们是不是应该考虑在编译器中集成某种ORB？或者泛型编程压根就不适合分布式编程？在这个意义上，是不是Java更合适？
答：
泛型编程和“运行时”、“编译时”之类的东西没有任何关系。问题是我发现OOP不单是慢，它还不允许我表达可能是最简单的算法。再提一遍，max的记号为：
max: T x T -> T
Java无法表达，因为从某个类或接口T继承导致它变为：
max: T' x T -> T
你需要协变记号转换（covariant signature transformation），并且要能够从类型取得类型信息，如果你喜欢，虚类型的概念—v-table包含了类型描述符。
问：
什么是迭代器（iterator）？
答：
迭代器是两个理论的联合体。第一个理论是命名理论（例如handle、cookie、address等）。一个命名实际上是指向另外一个东西的东西。（operator*）。我们称之为Trivial Iterator理论。再加上解引用（dereferencing），它同样被定义从而满足以下公理：
i == j iff &*i == &*j
也就是说，两个迭代器是完全相等的，当且仅当它们指向同一个对象时。（“相等”当然要满足所有标准公理）。第二个理论是关于精致的后继操作（++i）：后继－前继（++和--）以及（++、--、+和-），满足标准公理。当然，指针只是一个随机存取迭代器模型。
问：
有些人争论说指针会以任何能够想到的可怕的方式和不可思议的方式破坏内存。Java和Delphi就没这个问题，因为它们不允许指针。（译注：作者只是为了强调，不必深究此句话。）
答：
不允许指针还能让你做指针算法是件好事。在C和C++中，指针算法只应该允许用在它真正被允许的地方，换而言之，比如数组里的指针。但泛泛地不接受指针是非常愚蠢的做法。你不能做泛型交换（swap）除非你的语言里有指针或引用。
问：
“category”（范畴）是一个被C++社团滥用的词。你怎么称呼iterator categories（迭代器范畴）？
答：
我常常称之为concepts（概念）。
问：
我试图开发一个STL风格的单向链接表。但是我决定不实现size()成员函数，因为我不想仅仅为了以常数时间实现size()而保持一个计数的负担，就象C++ CD所声称的那样。这个决定正确吗？
答：
STL列表的size()曾以线性时间方式实现的，那一个正确的决定，因为假如用户想保持一个计数的话也容易做到。但通常来说，你不需要那么做，并且它造成了衔接的线性时间（splice linear time）。但标准委员会坚持让我改成常数时间。我别无选择。我们最终将不得不改变这个要求。
问：
我正在研究怎样在STL里表达一个树，我碰到了一些问题：每一个节点都有一个父亲和两个儿子。移动到父亲可以描述为operator--，但我需要两个不同的operator++以移动到它的儿子们。迭代器怎样来处理非线性结构，比如树或图？
答：
即使在序列（sequence）上你也有不同的迭代器。反向迭代器（Reverse iterators）就是一个例子。步幅迭代器（Stride iterators）非常重要，最终将被加入到STL。
问：
我必须得承认我的无知。什么是步幅迭代器？
答：
从i到i+5再到i+10。
问：
它和随机迭代器的不同之处在于？
答：
步幅迭代器是这样的一种迭代器适配器（iterator adaptor），它带有一个随机存取迭代器范围并提供一个随机存取迭代器，在其上++就可以通过一个步幅（一个迭代器序列， n步间隔。）。
问：
这和树的遍历有什么关系？
答：
我并没有说步幅迭代器或反向迭代器跟树的遍历有什么关系，但是，对于一种数据结构来说，可以有多种迭代器类型以满足不同迭代顺序，例如树的前序、中序和后序遍历。
问：
我常常会碰到一个棘手的决定：我应该把一个函数设计成成员函数还是泛型（全局）函数？在STL中做出这种决定的基本原则是什么？
答：
只要有可能就把它设计成全局的。如果从头到尾都是全局的话会更好。那就允许我们用C数组来定义它们。如果operator*具有全局缺省定义，那会更好：
template <class T> T& operator*(T& x) { return x;}
template <class T> const T& operator*(const T& x) { return x;}