📄 drdobbs-interview.html
字号:
<HTML><HEAD><TITLE>Dr. Dobb's Journal Interview with Alex Stepanov</Title></HEAD><BODY><H1><Center>Al Stevens Interviews Alex Stepanov</Center></H1><P>This interview appeared in the March 1995 issue of<Cite><A Href="http://www.ddj.com">Dr. Dobb's Journal</A></Cite>,and is reprinted with permission.</P><HR><P><B>Tell us something about your long-term interest in genericprogramming.</B></P><P> I started thinking about generic programming in the late 70swhen I observed that some algorithms depended not on someparticular implementation of a data structure but only on a fewfundamental semantic properties of the structure. I startedgoing through many different algorithms, and I found that mostalgorithms can be abstracted away from a particularimplementation in such a way that efficiency is not lost.Efficiency is a fundamental concern of mine. It is silly toabstract an algorithm in such a way that when you instantiate itback it becomes inefficient.</P><P> At that time I thought that the right way of doing this kindof research was to develop a programming language, which is whatI started doing with two of my friends, Deepak Kapur, who atpresent is a professor at State University of New York, Albany,and David Musser, professor at Rensselaer Polytechnic Institute.At that time the three of us worked at the General ElectricResearch Center at Schenectady, NY. We started working on alanguage called Tecton, which would allow people to describealgorithms associated with what we called generic structures,which is just a collection of formal types and properties ofthese types. Sort of mathematical stuff. We realized that onecan define an algebra of operations on these structures, you canrefine them, you can enrich them, and do all sorts of things.</P><P> There were some interesting ideas, but the research didn'tlead to practical results because Tecton was functional. Webelieved Backus's idea that we should liberate programming fromthe von Neumann style, and we didn't want to have side effects.That limited our ability to handle very many algorithms thatrequire the notion of state and side effects.</P><P> The interesting thing about Tecton, which I realizedsometime in the late 70s, was that there was a fundamentallimitation in the accepted notion of an abstract data type.People usually viewed abstract data types as something whichtells you only about the behavior of an object and theimplementation is totally hidden. It was commonly assumed thatthe complexity of an operation is part of implementation and thatabstraction ignores complexity. One of the things that iscentral to generic programming as I understand it now, is thatcomplexity, or at least some general notion of complexity, has tobe associated with an operation.</P><P> Let's take an example. Consider an abstract data typestack. It's not enough to have Push and Pop connected with theaxiom wherein you push something onto the stack and after you popthe stack you get the same thing back. It is of paramountimportance that pushing the stack is a constant time operationregardless of the size of the stack. If I implement the stack sothat every time I push it becomes slower and slower, no one willwant to use this stack.</P><P> We need to separate the implementation from the interfacebut not at the cost of totally ignoring complexity. Complexityhas to be and is a part of the unwritten contract between themodule and its user. The reason for introducing the notion ofabstract data types was to allow interchangeable softwaremodules. You cannot have interchangeable modules unless thesemodules share similar complexity behavior. If I replace onemodule with another module with the same functional behavior butwith different complexity tradeoffs, the user of this code willbe unpleasantly surprised. I could tell him anything I likeabout data abstraction, and he still would not want to use thecode. Complexity assertions have to be part of the interface.</P><P> Around 1983 I moved from GE Research to the faculty of thePolytechnic University, formerly known as Brooklyn Polytechnic,in NY. I started working on graph algorithms. My principalcollaborator was Aaron Kershenbaum, now at IBM Yorktown Heights.He was an expert in graph and network algorithms, and I convincedhim that some of the ideas of high order and generic programmingwere applicable to graph algorithms. He had some grants andprovided me with support to start working with him to apply theseideas to real network algorithms. He was interested in buildinga toolbox of high order generic components so that some of thesealgorithms could be implemented, because some of the networkalgorithms are so complex that while they are theoreticallyanalyzed, but never implemented. I decided to use a dialect ofLisp called Scheme to build such a toolbox. Aaron and Ideveloped a large library of components in Scheme demonstratingall kinds of programming techniques. Network algorithms were theprimary target. Later Dave Musser, who was still at GE Research,joined us, and we developed even more components, a fairly largelibrary. The library was used at the university by graduatestudents, but was never used commercially. I realized duringthis activity that side effects are important, because you cannotreally do graph operations without side effects. You cannotreplicate a graph every time you want to modify a vertex.Therefore, the insight at that time was that you can combine highorder techniques when building generic algorithms withdisciplined use of side effects. Side effects are not necessarilybad; they are bad only when they are misused.</P><P> In the summer of 1985 I was invited back to GE Research toteach a course on high order programming. I demonstrated how youcan construct complex algorithms using this technique. One ofthe people who attended was Art Chen, then the manager of theInformation Systems Laboratory. He was sufficiently impressed toask me if I could produce an industrial strength library usingthese techniques in Ada, provided that I would get support.Being a poor assistant professor, I said yes, even though Ididn't know any Ada at the time. I collaborated with Dave Musserin building this Ada library. It was an important undertaking,because switching from a dynamically typed language, such asScheme, to a strongly typed language, such as Ada, allowed me torealize the importance of strong typing. Everybody realizes thatstrong typing helps in catching errors. I discovered that strongtyping, in the context of Ada generics, was also an instrument ofcapturing designs. It was not just a tool to catch bugs. It wasalso a tool to think. That work led to the idea of orthogonaldecomposition of a component space. I realized that softwarecomponents belong to different categories. Object-orientedprogramming aficionados think that everything is an object. WhenI was working on the Ada generic library, I realized that thiswasn't so. There are things that are objects. Things that havestate and change their state are objects. And then there arethings that are not objects. A binary search is not an object.It is an algorithm. Moreover, I realized that by decomposing thecomponent space into several orthogonal dimensions, we can reducethe number of components, and, more importantly, we can provide aconceptual framework of how to design things.</P><P> Then I was offered a job at Bell Laboratories working in theC++ group on C++ libraries. They asked me whether I could do itin C++. Of course, I didn't know C++ and, of course, I said Icould. But I couldn't do it in C++, because in 1987 C++ didn'thave templates, which are essential for enabling this style ofprogramming. Inheritance was the only mechanism to obtaingenericity and it was not sufficient.</P><P> Even now C++ inheritance is not of much use for genericprogramming. Let's discuss why. Many people have attempted touse inheritance to implement data structures and containerclasses. As we know now, there were few if any successfulattempts. C++ inheritance, and the programming style associatedwith it are dramatically limited. It is impossible to implement adesign which includes as trivial a thing as equality using it.If you start with a base class X at the root of your hierarchyand define a virtual equality operator on this class which takesan argument of the type X, then derive class Y from class X. Whatis the interface of the equality? It has equality which comparesY with X. Using animals as an example (OO people love animals),define mammal and derive giraffe from mammal. Then define amember function mate, where animal mates with animal and returnsan animal. Then you derive giraffe from animal and, of course,it has a function mate where giraffe mates with animal andreturns an animal. It's definitely not what you want. Whilemating may not be very important for C++ programmers, equalityis. I do not know a single algorithm where equality of some kindis not used.</P><P> You need templates to deal with such problems. You can havetemplate class animal which has member function mate which takesanimal and returns animal. When you instantiate giraffe, matewill do the right thing. The template is a more powerfulmechanism in that respect.</P><P> However, I was able to build a rather large library ofalgorithms, which later became part of the Unix System LaboratoryStandard Component Library. I learned a lot at Bell Labs bytalking to people like Andy Koenig and Bjarne Stroustrup aboutprogramming. I realized that C/C++ is an important programminglanguage with some fundamental paradigms that cannot be ignored.In particular I learned that pointers are very good. I don'tmean dangling pointers. I don't mean pointers to the stack. ButI mean that the general notion of pointer is a powerful tool.The notion of address is universally used. It is incorrectlybelieved that pointers make our thinking sequential. That is notso. Without some kind of address we cannot describe any parallelalgorithm. If you attempt to describe an addition of n numbersin parallel, you cannot do it unless you can talk about the firstnumber being added to the second number, while the third numberis added to the fourth number. You need some kind of indexing.You need some kind of address to describe any kind of algorithm,sequential or parallel. The notion of an address or a locationis fundamental in our conceptualizing computational processes---algorithms.</P><P> Let's consider now why C is a great language. It iscommonly believed that C is a hack which was successful becauseUnix was written in it. I disagree. Over a long period of timecomputer architectures evolved, not because of some clever peoplefiguring how to evolve architectures---as a matter of fact,clever people were pushing tagged architectures during thatperiod of time---but because of the demands of differentprogrammers to solve real problems. Computers that were able todeal just with numbers evolved into computers with byte-addressablememory, flat address spaces, and pointers. Thiswas a natural evolution reflecting the growing set of problemsthat people were solving. C, reflecting the genius of DennisRitchie, provided a minimal model of the computer that hadevolved over 30 years. C was not a quick hack. As computersevolved to handle all kinds of problems, C, being the minimalmodel of such a computer, became a very powerful language tosolve all kinds of problems in different domains veryeffectively. This is the secret of C's portability: it is thebest representation of an abstract computer that we have. Ofcourse, the abstraction is done over the set of real computers,not some imaginary computational devices. Moreover, people couldunderstand the machine model behind C. It is much easier for anaverage engineer to understand the machine model behind C thanthe machine model behind Ada or even Scheme. C succeeded becauseit was doing the right thing, not because of AT&T promoting it orUnix being written with it.</P><P> C++ is successful because instead of trying to come up withsome machine model invented by just contemplating one's navel,Bjarne started with C and tried to evolve C further, allowingmore general programming techniques but within the framework ofthis machine model. The machine model of C is very simple. Youhave the memory where things reside. You have pointers to theconsecutive elements of the memory. It's very easy tounderstand. C++ keeps this model, but makes things that residein the memory more extensive than in the C machine, because C hasa limited set of data types. It has structures that allow a sortof an extensible type system, but it does not allow you to defineoperations on structures. This limits the extensibility of thetype system. C++ moved C's machine model much further toward atruly extensible type system.</P><P> In 1988 I moved to HP Labs where I was hired to work ongeneric libraries. For several years, instead of doing that Iworked on disk drives, which was exciting but was totallyorthogonal to this area of research. I returned to genericlibrary development in 1992 when Bill Worley, who was my labdirector established an algorithms project with me being itsmanager. C++ had templates by then. I discovered that Bjarne haddone a marvelous job at designing templates. I had participatedin several discussions early on at Bell Labs about designingtemplates and argued rather violently with Bjarne that he shouldmake C++ templates as close to Ada generics as possible. I thinkthat I argued so violently that he decided against that. Irealized the importance of having template functions in C++ andnot just template classes, as some people believed. I thought,however, that template functions should work like Ada generics,that is, that they should be explicitly instantiated. Bjarne didnot listen to me and he designed a template function mechanismwhere templates are instantiated implicitly using an overloadingmechanism. This particular technique became crucial for my workbecause I discovered that it allowed me to do many things thatwere not possible in Ada. I view this particular design byBjarne as a marvelous piece of work and I'm very happy that hedidn't follow my advice.</P><P><B>When did you first conceive of the STL and what was its originalpurpose?</b></P><P>In 1992, when the project was formed, there were eight people init. Gradually the group diminished, eventually becoming twopeople, me and Meng Lee. While Meng was new to the area---shewas doing compilers for most of her professional life---sheaccepted the overall vision of generic programming research, andbelieved that it could lead to changing software development atthe point when very few people shared this belief. I do notthink that I would be able to build STL without her help. (Afterall, STL stands for Stepanov and Lee...) We wrote a huge library,a lot of code with a lot of data structures and algorithms,function objects, adaptors, and so on. There was a lot of code,but no documentation. Our work was viewed as a research projectwith the goal of demonstrating that you can have algorithmsdefined as generically as possible and still extremely efficient.We spent a lot of time taking measurements, and we found that wecan make these algorithms as generic as they can be, and stillbe as efficient as hand-written code. There is no performancepenalty for this style of programming! The library was growing,but it wasn't clear where it was heading as a project. It tookseveral fortunate events to lead it toward STL.</P><P><B>When and why did you decide to propose STL as part of theANSI/ISO Standard C++ definition?</B></P><P>During the summer of 1993, Andy Koenig came to teach a C++ courseat Stanford. I showed him some of our stuff, and I think he wasgenuinely excited about it. He arranged an invitation for me togive a talk at the November meeting of the ANSI/ISO C++ StandardsCommittee in San Jose. I gave a talk entitled "The Science ofC++ Programming." The talk was rather theoretical. The mainpoint was that there are fundamental laws connecting basicoperations on elements of C++ which have to be obeyed. I showeda set of laws that connect very primitive operations such asconstructors, assignment, and equality. C++ as a language doesnot impose any constraints. You can define your equalityoperator to do multiplication. But equality should be equality,and it should be a reflexive operation. A should be equal to A.It should be symmetric. If A is equal to B, then B should beequal to A. And it should be transitive. Standard mathematicalaxioms. Equality is essential for other operations. There areaxioms that connect constructors and equality. If you construct⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -