Interview with the creator of C ++ STL, 1995 Part 1
In recent years, when the demand for C ++ is growing again , it is interesting to look into the recent past and recall how this classic development platform was created. In this question, certainly unconstructive are the books of Straustrup, like “ Design and Evolution of C ++ ”. However, it is equally interesting to hear about the language from its very first followers, and sometimes full-fledged collaborators. Perhaps the most famous of them is our (in general :) compatriot Alex Stepanov , the author of the Standard Template Library . The interview, cited below, was taken from Alex in 1995 by columnist Dr.Dobbs magazine Al Stevens . The material will be interesting for both beginners to learn C ++, and experienced users of the language.
Alex, tell us something about your long-standing interest in generic programming.
I started thinking about generalized programming in the late 70s, when I noticed that some algorithms do not depend on the specific implementation of the data structure, but only on a small number of essential semantic properties of this structure. So I began to consider a variety of algorithms, and found that most of them can be abstracted from a specific implementation so that efficiency is not lost. Efficiency is one of my main concerns. It is foolish to abstract the algorithm in such a way that when you use it for the resulting implementation, it becomes inefficient.
At that time, I thought that the right way to do this kind of research was to develop a programming language, which I started to do with my two friends, Deepak Kapoor (currently a professor at the University of New York, Albani) and David Musser, Professor at the Rensselaer Polytechnic Institute. Then the three of us worked at the General Electric Research Center in Schenectady, New York. We started working on a language called Tecton, which would allow people to describe the algorithms associated with what we called generic structures. They are simply collections of formal types and their properties. Something like math tools. We realized that it is possible to define the algebra of operations on these structures: you can replenish them, enrich them and do various things with them.
')
There were some interesting ideas, but the research did not lead us to practical results, since Tecton was a functional language. We believed in the idea of ​​Backus Naur that programming should be freed from the Von Neumann style , and we did not want to have side effects in the language as a result of the work of a procedure or function. As a result, it was not possible to touch on many algorithms, which in essence required the concepts of state and side effect.
An interesting fact about Tecton, which I realized somewhere in the late 70s, was that this language had a basic limitation on the accepted representation of an abstract data type (ADT). Typically, ADT is presented as something that tells you only about the behavior of the object, while the implementation is completely hidden. It was considered generally accepted that the complexity of the operation is part of the implementation, and the abstraction ignores the complexity. One of the facts that I now consider to be central to generic programming is that complexity, or at least some general idea of ​​complexity, must be associated with an operation.
Consider an example. Imagine ATD "Stack". It is not enough to have the “Push to stack” and “Push out from stack” methods: the postulate - something is put on the stack, and after the top of the stack is pushed out, the same stack is obtained. The statement of paramount importance is that putting an item on the stack is an operation with a constant time regardless of the size of the stack. If I implement the stack in such a way that every time this element is added to it, this operation becomes slower and slower, then no one wants to use this stack.
We need to separate the implementation from the interface, but not at the price of completely ignoring the complexity. Complexity must be and is part of the unwritten agreement between the module and its user. The reason for introducing the concept of ADT was to allow the creation of interchangeable software modules. It is impossible to have interchangeable modules as long as these modules do not share similar complexity behavior. If I replace one module with another with the same functional behavior, but with excellent compromises in complexity, the user of this code will be unpleasantly surprised. I could tell him everything I like about data abstraction, but he still wouldn’t want to use code. Assertions of complexity should be part of the interface.
Around 1983, I moved from GE Research to the faculty of the Polytechnic University, formerly known as the Brooklyn Polytechnic, in New York. I started working on graph algorithms. My main co-author was Aaron Kershenbaum, now working at IBM Yorktown Heights. He was an expert in graph and network algorithms, and I convinced him that some ideas of high-level and generalized programming were applicable to graph algorithms. He had access to several research grants and provided me with support so that I could start working with him on applying these ideas to real network algorithms. He was interested in creating a set of tools in the form of high-level generalized components, so that some of these algorithms could be implemented. The fact is that some network algorithms are so complex that they were never implemented at that time, although they were well analyzed theoretically. I decided to use a Lisp dialect called Scheme to build such a toolkit. Aaron and I developed a large component library at Scheme that demonstrates all kinds of programming techniques. Network algorithms were the main goal. Later, Dave Musser, still working at GE Research, joined us, and we developed an even larger component, a fairly large library. It was used at university by students completing their studies, but was never employed for commercial purposes. Being engaged in this work, I realized that the side effects of the functions are important, because in fact, it is impossible to perform operations on graphs without side effects. You cannot copy a graph every time you need to modify a vertex. So the insight at the time was that when building generalized algorithms, you can combine high-order techniques with moderate use of side effects. Side effects are not necessarily bad; they are bad, just being misused.
In the summer of 1985, I was invited back to GE Research to teach a high-level programming course. There I showed how to construct complex algorithms using this technique. One of those attending the course was Art Chen, later on managing the Laboratory for Information Systems. He was impressed enough to ask me a question: could I create with the help of this technique a library ready for industrial use in the Ada language, while ensuring my support for it. Being a poor assistant professor, I agreed, although I did not know any Ada then. Together with Dave Musser, we began work on the creation of the Ada library. This was a significant circumstance, since switching from a dynamically typed language, such as Scheme, to a strongly typed language, such as Ada, allowed me to realize the importance of strong typing. Everyone understands that strong typing helps in finding errors. I found that strong typing in the context of the generics of the Ada language (generic procedures — that is, applicable to any type) was also a tool for identifying models. It was not only a tool for catching errors. She was also a tool for thought. This work led me to the idea of ​​orthogonal decomposition of the component space. I realized that software components belong to different categories. PLO supporters think that everything is an object. When I was working on a generic library for Ada, I realized that it was not. There are things that are objects. Things that have a state and change their state are objects. And at the same time there are things that are not objects. Binary search is not an object. This is an algorithm. Moreover, I realized that by decomposing the component space into several orthogonal dimensions, we can reduce the number of components, and, more importantly, we can provide a conceptual basis for how to design something.
Then I was offered a job at Bell Lab in the C ++ language group on C ++ libraries. They asked me if I could do the same in C ++. Of course, I did not know C ++, and of course I agreed. But I could not do this in C ++, because in 1987, C ++ did not have the templates needed for this programming style. Inheritance was the only mechanism for generalization, and it was not sufficient.
Even now, inheritance in C ++ is not particularly valuable for generic programming. Let's discuss why. Many have tried to use inheritance to implement data structures and container classes. As we know now, there have been very few successful attempts, if any. The C ++ inheritance and programming style associated with it are significantly limited. So, it is impossible to implement a design that includes such a simple thing as using the comparison operator for equality. If you start with the base class X as the root of your hierarchy and define a virtual equality operator for this class that takes an argument of type X, then inherit the class Y from X. What is the interface of the comparison operator for equality? It has an equality that compares Y with X. Using animals as an example (object-oriented people like animals), define a "mammal" and inherit the "giraffe" from a mammal. Then define a mate member function in which one animal mates with another and returns the animal. Then you remove the "giraffe" from the animal and, of course, it has the function of "mate", in which the giraffe mates with the animal and returns the animal. This is definitely not what you would like. While pairing may not be very important for C ++ programmers, the equality operator is one. I do not know of any algorithm in which some kind of equality comparison would not be used.
You need templates to deal with similar problems. You can have the “Animal” template class that has a mate member function that accepts an animal and returns an animal. When you instantiate Giraffe, mating will do the right thing. In this regard, the pattern is a more powerful mechanism.
However, I was able to create a very large library of algorithms, which later became part of the Standard Components Library of the Unix Systems Lab. I learned a lot at Bell Labs, talking about programming with people like Andy Koenig and Bjarn Straustrup. I realized that C / C ++ is an important programming language with some basic paradigms that can no longer be ignored. In particular, I learned that pointers are very good. I do not mean "hanging" pointers . I don't mean pointers to the stack. But I mean, general pointer notation is a powerful tool. The concept of address is used everywhere. It is incorrectly assumed that pointers make our thinking consistent. This is not true. Without some kind of address, we cannot describe any parallel algorithm. If you try to describe the parallel summation of n numbers, you will not be able to do this until you can talk about the first number that adds up to the second, while the third number adds up to the fourth. You need some kind of indexing. You need some kind of addressing to describe an algorithm of any kind, serial or parallel. The notation of an address or position is fundamental to our understanding and conceptualization of computational processes - algorithms.
Now let's think about why C is a great language. It is generally accepted that C is such a big “hack” that succeeded because Unix was written on it. I disagree. Over a long period of time, computer architectures evolved, not due to the fact that some smart people figured out how to develop architectures, but because of the needs of various programmers to solve real problems. In fact, “smart” people at that time promoted tagged ( LISP-oriented ) architectures, which, of course, was not very relevant to the basic needs of developers. Computers that were able to deal only with numbers evolved into computers with byte-by-byte memory, flat address spaces, and pointers. It was a natural evolution, reflecting a growing array of problems that people solved. C, who reflected the genius of Denis Ricci, provided a minimal computer model, which as a result of development was obtained during the past 30 years. C was not a quick hack. As computers evolved to handle all kinds of problems, C, being the minimum model for such a computer, has become a very popular language for solving all kinds of problems in various areas with a high degree of efficiency. This is the secret of C portability: it is the best representation of an abstract computer that we have. Of course, abstraction is carried out on a variety of real computers, and not some imaginary computing devices. Moreover, people understood the machine model underlying C. It is much easier for an average engineer to understand the machine model underlying C than the machine model Ada or even Scheme. C succeeded because he did the right thing, not because AT & T advertised it or because Unix was written on it.
C ++ is successful, because, instead of trying to propose a machine model, invented perhaps in the process of contemplating his navel, Bjarn began with C and tried to develop C further, providing more generalized programming techniques, but in the context of the framework of this machine model. Machine model C is very simple. You have a memory where the entities are located. You have pointers to consecutive memory elements. This is very easy to understand. C ++ retains this model, but makes entities located in memory more exhaustive than in the C machine, since C has a limited set of data types. Namely, C has structures that provide a kind of extensible type system, but it does not allow you to define operations on structures. This limits the extensibility of the type system. C ++ has greatly advanced the machine model C to a truly extensible type system.
In 1988, I moved to HP Labs, where I was hired to work on generic libraries. For several years, I worked instead on hard drives, and it was exciting, but completely orthogonal to this area of ​​research. I returned to the development of a generalized library in 1992, when Bill Worley, the former head of my laboratory, launched a project on algorithms with me as a manager. C ++ had templates by that moment. I found that Bjarn did an excellent job in designing patterns. A long time ago, I took part in several discussions at Bell Laboratories about designing patterns, and argued with Bjarn quite toughly that he should make C ++ patterns as close to Ada generics as possible. I think I argued so hard that he made the opposite decision. I realized the importance of having template functions in C ++, and not just template classes, as many believe. I thought, however, that the template functions should work as Ada generics, i.e. that they should have been explicitly instantiated. Bjarn did not listen to me and designed a template functions mechanism in which templates are explicitly instantiated using the overload mechanism. This particular technique was decisive for my work, because I found that she allowed me to do a lot of things that were impossible in Ada. I see this particular design, developed by Bjarn, as an excellent result, and I am happy that he did not follow my advice.
When did you start working on the STL and what was its original purpose?
In 1992, when the project was formed, there were 8 people in it. Gradually, the group decreased, and eventually included two - me and Meng Li. While Meng was new to the field — she developed compilers for most of her professional life, she accepted from start to finish the vision of generalized programming research, and believed that they could lead to changes in the software development process at a time when very few people shared this belief. I don’t think I could construct STL without her help (after all, STL means Stepanov and Lee). , , (), .. , . , , , , - . , , , , , , . - ! , , . , STL.
( )
( )
Alex, tell us something about your long-standing interest in generic programming.
I started thinking about generalized programming in the late 70s, when I noticed that some algorithms do not depend on the specific implementation of the data structure, but only on a small number of essential semantic properties of this structure. So I began to consider a variety of algorithms, and found that most of them can be abstracted from a specific implementation so that efficiency is not lost. Efficiency is one of my main concerns. It is foolish to abstract the algorithm in such a way that when you use it for the resulting implementation, it becomes inefficient.
At that time, I thought that the right way to do this kind of research was to develop a programming language, which I started to do with my two friends, Deepak Kapoor (currently a professor at the University of New York, Albani) and David Musser, Professor at the Rensselaer Polytechnic Institute. Then the three of us worked at the General Electric Research Center in Schenectady, New York. We started working on a language called Tecton, which would allow people to describe the algorithms associated with what we called generic structures. They are simply collections of formal types and their properties. Something like math tools. We realized that it is possible to define the algebra of operations on these structures: you can replenish them, enrich them and do various things with them.
')
There were some interesting ideas, but the research did not lead us to practical results, since Tecton was a functional language. We believed in the idea of ​​Backus Naur that programming should be freed from the Von Neumann style , and we did not want to have side effects in the language as a result of the work of a procedure or function. As a result, it was not possible to touch on many algorithms, which in essence required the concepts of state and side effect.
An interesting fact about Tecton, which I realized somewhere in the late 70s, was that this language had a basic limitation on the accepted representation of an abstract data type (ADT). Typically, ADT is presented as something that tells you only about the behavior of the object, while the implementation is completely hidden. It was considered generally accepted that the complexity of the operation is part of the implementation, and the abstraction ignores the complexity. One of the facts that I now consider to be central to generic programming is that complexity, or at least some general idea of ​​complexity, must be associated with an operation.
Consider an example. Imagine ATD "Stack". It is not enough to have the “Push to stack” and “Push out from stack” methods: the postulate - something is put on the stack, and after the top of the stack is pushed out, the same stack is obtained. The statement of paramount importance is that putting an item on the stack is an operation with a constant time regardless of the size of the stack. If I implement the stack in such a way that every time this element is added to it, this operation becomes slower and slower, then no one wants to use this stack.
We need to separate the implementation from the interface, but not at the price of completely ignoring the complexity. Complexity must be and is part of the unwritten agreement between the module and its user. The reason for introducing the concept of ADT was to allow the creation of interchangeable software modules. It is impossible to have interchangeable modules as long as these modules do not share similar complexity behavior. If I replace one module with another with the same functional behavior, but with excellent compromises in complexity, the user of this code will be unpleasantly surprised. I could tell him everything I like about data abstraction, but he still wouldn’t want to use code. Assertions of complexity should be part of the interface.
Around 1983, I moved from GE Research to the faculty of the Polytechnic University, formerly known as the Brooklyn Polytechnic, in New York. I started working on graph algorithms. My main co-author was Aaron Kershenbaum, now working at IBM Yorktown Heights. He was an expert in graph and network algorithms, and I convinced him that some ideas of high-level and generalized programming were applicable to graph algorithms. He had access to several research grants and provided me with support so that I could start working with him on applying these ideas to real network algorithms. He was interested in creating a set of tools in the form of high-level generalized components, so that some of these algorithms could be implemented. The fact is that some network algorithms are so complex that they were never implemented at that time, although they were well analyzed theoretically. I decided to use a Lisp dialect called Scheme to build such a toolkit. Aaron and I developed a large component library at Scheme that demonstrates all kinds of programming techniques. Network algorithms were the main goal. Later, Dave Musser, still working at GE Research, joined us, and we developed an even larger component, a fairly large library. It was used at university by students completing their studies, but was never employed for commercial purposes. Being engaged in this work, I realized that the side effects of the functions are important, because in fact, it is impossible to perform operations on graphs without side effects. You cannot copy a graph every time you need to modify a vertex. So the insight at the time was that when building generalized algorithms, you can combine high-order techniques with moderate use of side effects. Side effects are not necessarily bad; they are bad, just being misused.
In the summer of 1985, I was invited back to GE Research to teach a high-level programming course. There I showed how to construct complex algorithms using this technique. One of those attending the course was Art Chen, later on managing the Laboratory for Information Systems. He was impressed enough to ask me a question: could I create with the help of this technique a library ready for industrial use in the Ada language, while ensuring my support for it. Being a poor assistant professor, I agreed, although I did not know any Ada then. Together with Dave Musser, we began work on the creation of the Ada library. This was a significant circumstance, since switching from a dynamically typed language, such as Scheme, to a strongly typed language, such as Ada, allowed me to realize the importance of strong typing. Everyone understands that strong typing helps in finding errors. I found that strong typing in the context of the generics of the Ada language (generic procedures — that is, applicable to any type) was also a tool for identifying models. It was not only a tool for catching errors. She was also a tool for thought. This work led me to the idea of ​​orthogonal decomposition of the component space. I realized that software components belong to different categories. PLO supporters think that everything is an object. When I was working on a generic library for Ada, I realized that it was not. There are things that are objects. Things that have a state and change their state are objects. And at the same time there are things that are not objects. Binary search is not an object. This is an algorithm. Moreover, I realized that by decomposing the component space into several orthogonal dimensions, we can reduce the number of components, and, more importantly, we can provide a conceptual basis for how to design something.
Then I was offered a job at Bell Lab in the C ++ language group on C ++ libraries. They asked me if I could do the same in C ++. Of course, I did not know C ++, and of course I agreed. But I could not do this in C ++, because in 1987, C ++ did not have the templates needed for this programming style. Inheritance was the only mechanism for generalization, and it was not sufficient.
Even now, inheritance in C ++ is not particularly valuable for generic programming. Let's discuss why. Many have tried to use inheritance to implement data structures and container classes. As we know now, there have been very few successful attempts, if any. The C ++ inheritance and programming style associated with it are significantly limited. So, it is impossible to implement a design that includes such a simple thing as using the comparison operator for equality. If you start with the base class X as the root of your hierarchy and define a virtual equality operator for this class that takes an argument of type X, then inherit the class Y from X. What is the interface of the comparison operator for equality? It has an equality that compares Y with X. Using animals as an example (object-oriented people like animals), define a "mammal" and inherit the "giraffe" from a mammal. Then define a mate member function in which one animal mates with another and returns the animal. Then you remove the "giraffe" from the animal and, of course, it has the function of "mate", in which the giraffe mates with the animal and returns the animal. This is definitely not what you would like. While pairing may not be very important for C ++ programmers, the equality operator is one. I do not know of any algorithm in which some kind of equality comparison would not be used.
You need templates to deal with similar problems. You can have the “Animal” template class that has a mate member function that accepts an animal and returns an animal. When you instantiate Giraffe, mating will do the right thing. In this regard, the pattern is a more powerful mechanism.
However, I was able to create a very large library of algorithms, which later became part of the Standard Components Library of the Unix Systems Lab. I learned a lot at Bell Labs, talking about programming with people like Andy Koenig and Bjarn Straustrup. I realized that C / C ++ is an important programming language with some basic paradigms that can no longer be ignored. In particular, I learned that pointers are very good. I do not mean "hanging" pointers . I don't mean pointers to the stack. But I mean, general pointer notation is a powerful tool. The concept of address is used everywhere. It is incorrectly assumed that pointers make our thinking consistent. This is not true. Without some kind of address, we cannot describe any parallel algorithm. If you try to describe the parallel summation of n numbers, you will not be able to do this until you can talk about the first number that adds up to the second, while the third number adds up to the fourth. You need some kind of indexing. You need some kind of addressing to describe an algorithm of any kind, serial or parallel. The notation of an address or position is fundamental to our understanding and conceptualization of computational processes - algorithms.
Now let's think about why C is a great language. It is generally accepted that C is such a big “hack” that succeeded because Unix was written on it. I disagree. Over a long period of time, computer architectures evolved, not due to the fact that some smart people figured out how to develop architectures, but because of the needs of various programmers to solve real problems. In fact, “smart” people at that time promoted tagged ( LISP-oriented ) architectures, which, of course, was not very relevant to the basic needs of developers. Computers that were able to deal only with numbers evolved into computers with byte-by-byte memory, flat address spaces, and pointers. It was a natural evolution, reflecting a growing array of problems that people solved. C, who reflected the genius of Denis Ricci, provided a minimal computer model, which as a result of development was obtained during the past 30 years. C was not a quick hack. As computers evolved to handle all kinds of problems, C, being the minimum model for such a computer, has become a very popular language for solving all kinds of problems in various areas with a high degree of efficiency. This is the secret of C portability: it is the best representation of an abstract computer that we have. Of course, abstraction is carried out on a variety of real computers, and not some imaginary computing devices. Moreover, people understood the machine model underlying C. It is much easier for an average engineer to understand the machine model underlying C than the machine model Ada or even Scheme. C succeeded because he did the right thing, not because AT & T advertised it or because Unix was written on it.
C ++ is successful, because, instead of trying to propose a machine model, invented perhaps in the process of contemplating his navel, Bjarn began with C and tried to develop C further, providing more generalized programming techniques, but in the context of the framework of this machine model. Machine model C is very simple. You have a memory where the entities are located. You have pointers to consecutive memory elements. This is very easy to understand. C ++ retains this model, but makes entities located in memory more exhaustive than in the C machine, since C has a limited set of data types. Namely, C has structures that provide a kind of extensible type system, but it does not allow you to define operations on structures. This limits the extensibility of the type system. C ++ has greatly advanced the machine model C to a truly extensible type system.
In 1988, I moved to HP Labs, where I was hired to work on generic libraries. For several years, I worked instead on hard drives, and it was exciting, but completely orthogonal to this area of ​​research. I returned to the development of a generalized library in 1992, when Bill Worley, the former head of my laboratory, launched a project on algorithms with me as a manager. C ++ had templates by that moment. I found that Bjarn did an excellent job in designing patterns. A long time ago, I took part in several discussions at Bell Laboratories about designing patterns, and argued with Bjarn quite toughly that he should make C ++ patterns as close to Ada generics as possible. I think I argued so hard that he made the opposite decision. I realized the importance of having template functions in C ++, and not just template classes, as many believe. I thought, however, that the template functions should work as Ada generics, i.e. that they should have been explicitly instantiated. Bjarn did not listen to me and designed a template functions mechanism in which templates are explicitly instantiated using the overload mechanism. This particular technique was decisive for my work, because I found that she allowed me to do a lot of things that were impossible in Ada. I see this particular design, developed by Bjarn, as an excellent result, and I am happy that he did not follow my advice.
When did you start working on the STL and what was its original purpose?
In 1992, when the project was formed, there were 8 people in it. Gradually, the group decreased, and eventually included two - me and Meng Li. While Meng was new to the field — she developed compilers for most of her professional life, she accepted from start to finish the vision of generalized programming research, and believed that they could lead to changes in the software development process at a time when very few people shared this belief. I don’t think I could construct STL without her help (after all, STL means Stepanov and Lee). , , (), .. , . , , , , - . , , , , , , . - ! , , . , STL.
( )
( )
Source: https://habr.com/ru/post/166849/
All Articles