STL Parent A.Stepanov Interview
Graziano Lo Russo Edizioni Infomedia SRL Glory Translation
ask:
Can you be a self-introduction first?
answer:
On November 16, 1950, I was born in Moscow, Soviet Union. In the University of Moscow, studying mathematics, but I have never become a mathematician. I really can't be excited to Tamagawa arithmetic, even though others think I good at Coxeter groups and something else. Hardy's idea is unattractive to me - his mathematics never intended to be practical. I want to do something, even if there is only one thing that is practical. However, if you come back, I am still lucky, how many great mathematicians can do, so that I can completely have the so-called rigorous immunity of mathematics coats. Unfortunately, this is usually used in computer science. Therefore, it is a good thing to be a programmer for me. In 1972, as a member of a group, I participated in the development of a new small machine system for controlling large hydropower stations. I am involved in the design of all parts, from architecture to OS hardware test (my first public published papers is about real-time operating system) to programming tools. I have learned the first-hand knowledge of software reliability and efficiency - the power station system cannot be easily restarted, and the water flow is always in real time.
At that time, I also explored the work of two great computer scientists Donald Knuth and Edsger Dijkstra, from them, I learned about the scientific knowledge of our professional foundation. The former tells me the answer, the latter will lead me. I will find new insights in their work again and again. My next important career stage is a five-year working in computer science segment in New York Schenectady's General Electric Research Center. I am committed to a very advanced language called Tecton, reading a lot of information, designing the logical outline of William of Occam from a wide program language - Aristotle and medieval logic knows that many appearance in natural language Different kinds of logical structures and their formal properties. Since then, until now, I have cooperated with Dave Musser to carry out fruitful research. In 1984, I became an assistant professor in Brooklyn Polytechnic University, New York. Professor computer science made me benefit, I have to deal with various graduate courses. In this process, I learned a lot of new things. I also develop a huge data structure and algorithm library in Scheme language, which has led to the birth of the ADA generic library (cooperated with Dave Musser). After a short study of the C algorithm in the Bell laboratory, I went to the HP Lab in Palo Alto (1988). Here, I spent four years of studying storage system - I have to learn disk controller programming. In 1993, I got a short-lived back to study the opportunity of generic programming. STL is the result of this study. In 1995, I came to Silicon Graphics, here, I am trying to form a group of further STL development work.
ask:
You just mentioned William of Occam. William of Occam has said "Entia Non Sunt MultiPlicanda" - I translated it as "[abstract] object is unnecessary." It seems that you have raised the OCCAM razor to OOP. Things, in algorithms, not the object, made me think of the controversy about the universe in the Middle Ages, is this?
answer:
This is very wonderful, but I don't think it is right. I never think that there is anything in the philosoprine of oo and realist, and I am not a flyer name. A fact that the Franciscan's Alexander of Hales, Bonaventure, and Scotus are very close to the tradition of Augus Pan / Plato. OCCAM is an independent different molecule. As a editor of his Opera Omnia, Gideon Gal has said: "But this guy is really crazy!" Q: For most Italian readers, "Stepanov" name and STL are indivisible. Is STL refer to Standard Template Library or Stepanov and LEE? In addition, in the history of STL, what role does D.Musser and A.koenig play?
answer:
Oh, it really refers to Standard Template Library. I once joke in the interview that Dr. Dobb's magazine, STL refers to "Stepanov and Lee", but it is just a joke. I have been working with Dave Musser for nearly 20 years. The cooperation between us is so close, so that it is difficult to say what to contribute to the end. He did not appear in the official STL author's list, just because he was busy with the standard proposal, he was busy. Andy Koenig is responsible for explaining the structure of Abstract C Machine. STL, in a sense, it is an application of Dave Musser and I have been developing a C-model model development. If not Andy, I may still have a packing, a pile allocation object problem and collect it for garbage. Of course, Andy is also responsible for the Stand and Bjarne Stroustrus. When you want to turn the wonderful ideas into a complete implementation, Meng Lee is an impeccable partner. She makes me a focus - I often lose interest after the problem is - I know that the solution is enough, do you want to make the world to let others know? She spent a lot of exhausted time on code and document. In a sense, she is the only person who can work out from those raw materials to actual things. I think, at this point, I will explain to anyone understanding that we have made a wish, Dave Musser and I have already had any hope.
ask:
What STL originated from? Is the STL be imagined as today? The so-called C standard library, or, what is it from other items? Tell us some historical history about STL?
answer:
In 1976, it is necessary to return to the Soviet Union, I have a serious food poisoning because of the eating sashimi. When living in the hospital, in the state of mental disorder, I suddenly realized that the parallel addition computational power relied on the fact that the addition is combined. (So, simply, STL is the result of bacterial infection. In other words, I realized that the parallel subtraction operation is associated with the half group structure type. This is the basic point: the algorithm is defined above the algebraic structure. It is realized that the necessary conditions must be added to the complexity of complexity to extend the concept of the structure, and it takes another year, then I spent 15 years. (I can't sure I have successfully made anyone in my small circle.) I believe that the iterator theory is the center of the scientific center, just like the center of Math or Banach space. . Whenever I find an algorithm, I have to work hard to seek the structural foundation it define. What I want to do is generally describing the algorithm and I am not tired. I am willing to spend a month to discover the generalization of a famous algorithm. So far, I am an exotic failure to explain my importance of this behavior. However, I don't know what to do, this behavior - STL is so successful. ask:
I have considered that the complexity of STL is purely because of the efficiency of achieving, and you seem to impress the complexity of the complexity? As so than?
answer:
Selecting a different algorithm relies on the complexity of the basic operations provided by the data structure. For SCSI storage devices, disk and tape are equivalent to functionality, but for a software designer who wants to use a magnetic plate as a disk is undoubtedly distressed. Take a look at STL, you can always implement P N to forward iterators, why is it necessary to provide random access to itmakers?
ask:
What is generic programming? I only see some "generic programming" columns written by A.koenig on JOOP. In most C language books, it is difficult to see generic programming in most C language books, including Coplien Meyer, Stroustrup, Lippman. I think STL should describe "writing C programs in a way that you have never thought it may be possible", do you agree with this statement?
answer:
STL, at least for me, representing consistent ways to programmatically. In fact, it is completely different from the C programming we have seen in the past, and it is completely different from the ways described in most textures. However, you know, I don't try to program with C , I just try to find a correct way to handle the software. I have been looking for a language that can express my thoughts for a long time. In other words, I know what I want to say. I can say C , I can use ADA, I can use Scheme. I can let myself adapt to the language, but in essence, I tried to say, and language has nothing to do. So far, C is what I found that I can express the best language I want to say. Although it is not an ideal medium, but I can use it to express more than other languages. In fact, my dream is the language that will appear for generic programming.
ask:
Can you explain what generic programming, generic programming, and C and STL do: generic C programmers? And, how did you think of generic programming in a C environment?
answer:
Pan-programming is a programming method based on the most abstract representation of the discovery efficient algorithm. That is to say, the most general necessary set of necessary conditions that can work and efficiently work with the algorithm. Surprisingly, many different algorithms need the same necessary conditional sets, and these necessary conditions have a variety of different implementations. Similar facts can be seen in mathematics. Most different theorems are dependent on the same axiom, and there are a variety of different models for the same axiom. Abstract mechanism! Pan-type program assumes that some basic rules are dominate the behavior of software components, and may design interoperable modules based on these rules. Even if you can use this method to guide our software design. STL is an example of a generic programming. C is the language I can implement a convincing example. ask:
I think STL and generic programming marks a new starting point different from a general C programming style (I found this style basically inherited from SmallTalk). Do you agree with this?
answer:
Yes. STL is not object-oriented. I think the object-oriented and artificial intelligence is almost the same, it is a scam. I have seen the "interesting" code written by people from those OO. To some extent, I have a prejudice to artificial intelligence (AI). I have heard a lot of things about Mit Ai Laboratory, they really do some basic work: Bill Gosper's Hakmem is one of the best readings of programmers. AI may not have a serious basis, but it creates Gosper and Stallman (Emacs), MOSES (Macsyma) and Sussman (Scheme, along with Guy Stelec). I found that OOP is technically ridiculous. It is in vain to break down the world according to the interface of a single type. In order to deal with practical problems, you need multiple algebraic methods - across multiple types of interface people; I found OOP in philosophy It is ridiculous, it claims that everything is an object. Even if this is really, it is not very interesting, saying that everything is nothing to say; I found that OOP methodology is wrong, it starts from class, as if mathematics should start from the beginning of the axiom. You are not starting with axiom, you start from prove. Until you find a lot of relevant evidence, you can summarize the axiom, you are ending in the axiom. There is the same fact in programming: you have to start with interesting algorithms. Only well understood the algorithm, you may make an interface to make it work.
ask:
I can summarize your thoughts to "find the [generic] data structure hidden in the algorithm, not" find the [virtual] algorithm hidden in the object?
answer:
Yes. Always start at the algorithm.
ask:
This needs to be a radical change from the ideological, regardless of the imperative or OO idea. In contrast, such as SmallTalk or Java, this way is it?
answer:
My way is in the way, and their can't do it. Try to achieve a simple thing with OO, such as Max, I don't know how Oo can get. Use generic programming, I can write this:
Template
Inline strictweakordred & max
{RETURN X with Template Inline const strictweakordered & max (const strictweakordred & x, const strictweakordred & y) {return x (& And Const & both). Then, I can define the meaning of the Strict Weak Ordered. Try it with Java. You can't write a generic max (), incompose two types of parameters and return a result of one type. Inheritance and interface are here. If you don't even be implemented, how much will they have a real complicated thing? These are my stone test method: If a language can make me achieve generic Max, Swap and Linear Search, then it still has some potential (translation: refer to generic programming). ask: Java is a very new language that has no template, so disable generic programming, everything must be class. How do you see Java? answer: I spent a few months to write the program with Java. In contrast to its authors, it did not evoke my interest. I didn't find any new insights. Since birth, I first programmed in a new language without finding new insights. It retains all I have never used in C - inherit, virtual machine (OO garbage), and take off what I think useful. It may succeed. After all, MS DOS has succeeded, and it may be profitable for you to learn Java readers, but it does not have any knowledge value. Look at the implementation of their dealing table, licking the sort routines used by "Cool" Sorting Applet, try AWT. The best way to judge a language is to look at the code written by it. "! @ # $% ^ &% $! × ¥ #", (Translation: The original "Radix Enim Omnium Malorum Est Cupiditas"), Java is obviously an example of money-oriented programming (MOP). SGI's Java primary advocate has said to me: "Alex, you have to have money." But I don't want to have money, that kind of place, taste, usually, I'm going to go. ask: Do you think template-based programming and generic programming will be used by most C programmers? Alternatively, they are limited only to use in STL, a bit icon manipulator, which is never used outside the iostream library. answer: I do not know. The idea behind the STL needs a long time to become mainstream. 10 to 15 years later, everything will be true. ask: There is a thing I have always been very surprised, and the C Standards Committee adopted STL. I mean, these committees can be known for cautious and conservative. For this, how do you explain? answer: The support of Bjarne Stroustrup is critical. If Bjarne wants something, that is, he really wants to get STL. He did it. He is as stubborn like a scorpion. Even forced me to change STL, I never do this for the second person, I am also a stubborn molecule, but he is the most changing person I know. He succeeded. Understanding STL is a dry flower, but when he understands, he decided to make it further. His contribution to STL is that he supports this view: more than one programming method is "legal". This opposes the endless quarrel and lies of the ten years, and insists on combining the elasticity, efficiency, overloading, and type safety in the template to make STLs possible. I am happy to clearly declare that Bjarne is our generation of outstanding language designers. ask: STL is completely creative use of templates, such as exporting symbol types from classes, or model matching of a series of overload algorithms for iterator tags, is of course sufficient, without any standard C books to mention these terms, how did you Think of these C code idioms? answer: I clearly know that I have to work hard, so I "screw" this language until I can go, but this spent many years to explore all technologies. I have a lot of mistakes. For example, in I realized why that mechanism fundamentally has a defect without using it, I wasted to find some useful things in the inheritance and virtual machine system. I am very happy that no one can see any intermediate steps, which are mostly stupid. I spent a long time to get something like something. This also promotes the characteristics of Bjarne to the language to make the characteristics of my terminology. Once, he said this is "instant language design". ask: What do you think teaches generic programming and STL to C programmers? Do you think that before or after learning STL, should you learn inheritance and other OO technology? answer: I plan to professor in SGI on generic programming lessons, I am very hoped that this can also prompted me to have a book, but I am a lazy author, I have never completed the paper, unless I have a cooperation Partners will do this. ask: I have searched your paper using Lycos (Mr. WWW Search Engine), I only find two, which is the guide and summary of STL you provide to the Standards Committee. answer: Yes, I am lazy, but I have not lazy to that. I probably published 20 papers in papers and broke out. They are mostly on different STL sites. (There may be a few on the site of Dave Musser.) ask: What is this book? answer: The book is called "The Ada Generic Library: Linear List Processing Packages", the author David R. Musser / Alexander A. Stepanov, Compass Series, Springer-Verlag, 1989. It is not worth reading. ask: STL makes the C compiler reaches their limits, and the C compiler of the same time cannot compile some STL code correctly. How did you develop and test STL? answer: I have a lot of hair in trying to compile STL. Unfortunate reality is that when I develop STL, because of the compiler's restrictions and bugs in the compiler, many of the code is not ideal in the implementation of STL at the time. Fortunately, I got a lot from Bjarne, and he pointed out that some of the unreally implemented features assumption will be implemented. If a language designer tells you, what has been given to the facility, it is greatly helpful. ask: How is allocators to STL? What do you think about them? answer: I invented the configurator to deal with the Intel memory architecture problem. Theoretically they are not bad - add a layer of packaging all memory: Pointers, References, Ptrdiff_T, Size_t. Unfortunately, they can't work. E.g: Vector Vector You can't say it now: Find (A.BEGIN (), A.End (), B [1]); B [1] Returns an alloc2 :: Reference is not int &. It may cause types that do not match. It is necessary to change the implementation method - should make the language core to deal with reference to make the configurator truly useful. ask: Is this a serious disadvantage of the C template? I can customize a class using template quotes, but different specialties are not type compatible, but a different subclass (in the oo sense) and its root classes are type compatible. answer: I think the problem is deep than "t * is Hardwired in the language". In general, I believe that you need to design a program language from your head, you can make generic programming. I hope someone will hire me to do this. ask: I saw the implementation of two hash tables on the D.Musser site, they all worked and very dexterous, much smarter than in the normal class. Why is the lague table not included in STL? answer: "Political reasons" (the translation: It means "about the public's will", which is all below.). They should include coming in. Our new STL implementation includes them. In general, we need to develop a mechanism to add things to STL. After all, STL is an extensible framework that is also expanded. There are many data structures that have not been added yet, such as one-way link tables, matrices, and diagrams. SGI will play a leadership in extending STL. ask: Do you still do STL? What do you do? answer: I am in the SGI team - Matt Austern, Hans Boehm and I have just completed a new version of STL. It includes a hash container, thread secure memory configuration, and spectacular web documentation. SGI is posted in http://www.sgi.com/technology/stl, we hope that we can keep STL grow. Multi-dimensional data structures, persistence, multithreading are all things we plan to join. Hey, I don't know how long we can make this thing. My managers do not provide any support for STL / generic programming activities. Explain why SGI has a responsibility to expand STL very difficult. (The same is to explain to HP's management. After STL is accepted as a standard, they canceled my 5 month project). ask: It seems that STL still has some shortcomings. First HP STL is not a thread. And the template leads to placing a lot of code in the header file. You can't have a real template library, whether it is a DLL form or a shared library (unplanted) form --stl is usually compiled time library. The last point is that there is almost no CASE tool and OOD method effectively support generic programming. For example, there is no CASE tool that allows you to define generic functions, and only Booch symbols can express templates to some extent, but the chart it produces is not intuitive (at least for me). answer: SGI STL is a thread safe. "Separate Compilation" has been adopted by standard, which is designed by my SGI colleague John Wilkinson, Jim dehnert and Matt Austern, which solves your second problem. It has been incorporated into standards, but it takes a while to have a compiler that supports "single compilation". I firmly believe that "Single Compilation" will eventually be delivered to the shared template library. This is also the main reason why I launched separate compilation in SGI. Designed to handle generic programming tools is not difficult, I am sure, as long as the market needs, Grady Booch will improve his symbol to handle generic programming. ask: One thing that makes C programmers feel that those standard committees seem to have no movement. OMG has just defined a set of distributed programming (CORBA) standards, but there is no mapping from CORBA to C . They each define their own set of classes, such as Sequence answer: I have to remember all the network standards proposed in the 1970s. Who can remember them now? ask: What will generic programming look like a distributed environment? Pan-programming is based on such ideas: The compiler knows how the possible type is compiled. This is unrealistic in a distributed environment. Do we have to consider integrating some orb in the compiler? Or is the generic programming is not suitable for distributed programming? In this sense, is it more appropriate? answer: There is no relationship with generic programming and "running", "compile time". The problem is that I found that OOP is not only slow, it doesn't allow me to express it may be the easiest algorithm. Moreover, the MAX's marker is: Max: T x t -> t Java cannot be expressed because it causes it from a class or interface T caused to: Max: t 'x t -> t You need to Covariant Signature Transformation, and you can get type information from the type, if you like, the virtual type concept -V-Table contains a type descriptor. ask: What is an iterator? answer: The iterator is two theoretical consortium. The first theory is name theory (such as Handle, Cookie, Address, etc.). A naming is actually pointing to another thing. (Operator *). We call Trivial Iterator theory. Adding a decrementation, it is also defined to meet the following axiom: i == J IFF & * i == & * J That is, the two iterators are completely equal, and when they point to the same object. ("Equal" Of course, you must meet all standard axioms). The second theory is about the exquisite subsequent operation ( i): Subsequent - processes ( and -) and ( , -, , and -) to meet standard axioms. Of course, the pointer is just a random access iterator model. ask: Some people argue that the pointer will destroy memory with any terrible way and incredible ways that can be thought of. Java and Delphi have no problem because they do not allow pointers. (Translation: The author is just to emphasize that there is no need to know this sentence.) answer: Do not allow your pointer to make you a pointer algorithm is a good thing. In C and C , the pointer algorithm should only be used to be used in its truly permit, in other words, such as pointers in an array. But it is a very stupid practice that is unacceptable to unacceptably. You can't do generic exchange (SWAP) unless your language has a pointer or reference. ask: "Category" is a word abused by a C community. How do you call Iterator Categories (iterator category)? answer: I am often called Concepts. ask: I have tried to develop a STL style one-way linked table. But I decided not to implement a size () member function, because I don't want to keep one count burden in order to achieve Size (), as I claims like the C CD. Is this decision correct? answer: The SIZE () of the STL list has been implemented in linear time, that a correct decision, because if the user wants to keep a count, it is easy to do. But in general, you don't need to do that, and it causes a linear time of the connection. But the Standards Committee insisted me changed into constant time. I don't have a choice. We will eventually change this requirement. ask: I am studying how to express a tree in STL, I have encountered some questions: Every node has a father and two sons. Moving to your father can describe Operator -, but I need two different Operator to move to its son. How to deal with nonlinear structures, such as trees or pictures? answer: Even in sequence, you have different iterators. The reverse iterators is an example. The stride itrators is very important and will eventually be added to STL. ask: I have to admit my ignorance. What is the step iterator? answer: Take I 10 from I to i 5. ask: It doesn't differ from the random iterator? answer: The step iterator is a random access iterator range with a random access iterator, which provides a random access iterator, which can pass one step by (one iteration) Sequence, N step interval.). ask: What is the relationship between this traversal of the tree? answer: I didn't say that the step iterator or the reverse iterator is related to the traversal of the tree. However, for a data structure, there can be multiple iterator types to meet different iterative sequences, such as the preamble of the tree. Sub-sequence and sequence traversal. ask: I often encounter a tricky decision: I should design a function as a member function or a generic (global) function? What is the basic principle of this decision in STL? answer: As long as it is possible to design it into a global. If the head to the end is a global, it will be better. Then allow us to define them with a C array. If Operator * has a global default default, it will be better: Template Template Const T & Operator * (const t & x) {return x;} It will allow us to write: Copy (0, 25, Ostream_IstRerator In general, for the non-iterator object, Operator * should return to the object, unnamed things refer to yourself. I even wanted to write a constructor and a sectator into a global function. If the language allows this, you will be able to do some amazing things. ask: If I define a generic Operator * in your way, I am so defined in my program: Template { T * PTR; PUBLIC: Smartptr (t * _ptr = 0): Ptr (_ptr) {} T * Operator * () const {return ptr;} // ... } So, the following code will not cause ambiguous two: INT i = 0; Smartptr INT j = * i; // use smartptr answer: no, I can not. Your definition is better than the global match (deep level). That is what is told by Partial Specialization. ask: Now, I have some curios: Why is STLs without "Sorted Container adapters, etc. answer: SET is a sort container. ask: Set is not an adapter. Why can I write a heap, but I don't write a sorting container that is independent of any container that supports random access. answer: Remember, because STL size problems cause it to be reviewed by the Standards Committee. I have thrown away a lot of useful things. (Think about what happened to the lapse table) ask: Why is the __adjust_heap function in answer: I have a lot of hardships to get the heap function. I originally wanted to disclose all the auxiliary functions in the STL, but there is no possibility of "political". ask: For me, it is difficult to imagine the "political factor" about the heap function. answer: It is not a function of a function, but because of their quantity. BJARNE personally is responsible for reducing the number of components in STLs, there is a reason for two. He tried to make it as small as possible to appease the opponents. ask: Have you been to Italy, business or leisure? answer: I have been in Pisa for ten days and visited Florence and Ruka. I dreamed to Ansis, in my heart, I am a Frank, a branch of Catholicism. I cried in the third scene of Tosca and the third scene of La Traviata. I put Ding Ding (Italian!) Posing in the bed. I like italian noodles, prosciutto and Kittian wine, I am a traditional Chinese, I seem to be more like John XXIII instead of PIUS XII. ask: Your Italian is definitely good if you can read the original works of DAN. Few Italians can read. answer: Hey, my Italian is very poor. I can read the work of Ding Ding because I have an English. I used it to read the English translation loudly. Graziano: Thank you very much, Alex, I hope that you can come to Italy and go to Ansis to see, reading but Ding, in Anxis's ancient town, which may be the most fascinating medieval town of Italy. - Full text -
