Interview with the creator of C ++ STL, 1995 Part 2
The continuation of the first part of the translation of the interview taken from the creator of the Standard Template Library Alex Stepanov in 1995. In this part, Alex talks about why templates are designed exactly and why they are good. It also describes a very exciting story about how to make STL Standard.
Alex, where and when did you decide to offer STL as part of the ANSI / ISO C ++ Standard Definition?
During the summer of 1993, Andrew König attended Stanford to teach the C ++ course. I showed him some of our materials, and I think he was genuinely captured by what he saw. He arranged for an invitation for me as a speaker at the November meeting of the C ++ Standard Committee in San Jose. I read the report, labeled “The Science of C ++ Programming”. My speech was rather theoretical. The main position was that there are fundamental laws that link very primitive operations, such as constructors, assignment and equality. C ++ as a language does not impose any restrictions. You can define your own equality operator in order to perform multiplication. But equality must be equality, and it must be a reflexive operation. A must be equal to A. It must be symmetrical. If A is equal to B, then B is equal to A. A must be transitive. Common mathematical axioms. Equality is inherent in other operations. There are axioms connecting the constructor and the equality. If you are constructing an object with a copy constructor from another object, then the two objects must be equal. C ++ does not commit to this, but it is one of the basic laws to which we must obey. The assignment must create the same objects. Thus, I presented a group of axioms that are associated with these basic operations. I talked a little about the iterator axioms and showed some generalized algorithms that handle iterators. It was a two-hour lecture and, I think, quite dry. However, she was very well received. At that time I did not think about using this thing as part of the standard, since it was usually perceived that it was some kind of advanced programming technique that would not be widely used in the “real world”. I thought practical people had no interest in any of these works.
This speech was in November, and I did not think about ANSI until January. On January 6th, I received a letter from Andy Koenig, who is the editor of the Standard document, which said that if I want to make my library part of the Standard, I must submit a proposal by January 25th. My answer was “Andy, are you crazy?”, To which he replied, “Yes, I'm crazy, but why not try?”.
')
At that moment there was a lot of code and there was no documentation at all - much less than a formal proposal. Meng and I spent several 80-hour working weeks to catch the offer on time, before the possible time of its dispatch. At that time, the only person who knew about the upcoming proposal was Andy. He was the only support and helped a lot during this period. We sent an offer and waited. In the process of preparation, we identified a lot of things. When you write something down, especially when you design it as a Standard, you discover all the possible flaws in your project. We had to reimplement every single piece of code in the library, several hundred components, between sending the letter in January and the next meeting in San Diego in March. Then we had to revise the proposal, because revealed a lot of problems in the process of writing code.
Can you characterize the discussions and discussions on the proposal in the Committee? Was there immediate support? Resistance?
We did not believe that something would come of it. I gave a talk that was very well received. There were many objections, most of which took this form: this is a huge proposal, too late for him, at the previous meeting the resolution was approved not to take any serious proposals - and this huge thing, the largest proposal ever considered, with many completely new things. A vote was taken, and, interestingly, the overwhelming majority voted to consider this proposal at the next meeting, and sent it to vote at the next meeting in Waterloo, Ontario.
Bjarn Straustrup became an ardent supporter of STL. Many people helped with suggestions, modifications and inspections. Bjarn came here for a week to work with us. Andy was constantly helping. C ++ is a complex language, so it is not always clear what a given construct means. Almost every day I called Andy or Bjarna to ask if this and that is possible in C ++. I have to give Andy special respect. He conceived STL as part of the standard library. Bjarn became the main lobbyist for the STL committee. There were other people who brought benefits: Mike Vilot, head of the Library Group, Nathan Myers from Rogue Wave, Larry Podmolik from Andersen Consulting. There were many others.
STL as we proposed it in San Diego was written in the current version of C ++. We were asked to rewrite it using the new ANSI / ISO language features, some of which have not yet been implemented. There was a big dependence on the time of Bjarn and Andy, who tried to verify that we used these unrealized opportunities correctly.
Future users wanted the containers to be independent of the memory model, which was somewhat excessive because the language does not include memory models. They wanted the library to provide some kind of mechanism for abstracting the memory model. Earlier versions of STL assumed that the container size is expressed as an integer of type
The next important thing was to expand our original set of data structures with associative structures. It was easier, but it was always difficult to reach the Standard state, because we needed something that people would use for their containers for years. From the point of view of containers, STL is very clearly divided in half. Namely, it provides two basic types of container classes: sequences and associative containers. Drawing analogies - they are like ordinary memory and associative memory. This definition has clear semantics explaining what these containers do.
When I arrived in Waterloo, Bjarn spent a lot of time explaining to me that I shouldn’t worry about the result, that the attempt would most likely fail, but we did our best, we tried, and we had to take heart. The level of expectations was low. We were preparing for the opposition majority. As a result, there was some resistance, but insignificant. The voting results in Waterloo were unexpected, since there were about 80% "for" and 20% "against." Everyone was waiting for the battle, everyone was waiting for the controversy. There was a fight, but the vote was an absolute majority.
What effect does STL have on class libraries published in ANSI / ISO working paper of February 1994?
STL was included in the working paper in Waterloo. The STL document is divided into parts, and is located in different parts of the working document relating to the Library. Mile Vilot is responsible for this. I will not take an active part in editorial activities. I am not a member of the Committee, but every time a change is proposed regarding STL, it is under my jurisdiction. The committee is very delicate.
A number of template changes were adopted by the committee. Which ones have an effect on STL?
Before the adoption of STL, there were two changes that were used in the revised STL. One of them is the ability to have template member functions. STL makes extensive use of them so that you can build any container from any other container. A single constructor is available that allows you to build vectors from lists or from other containers. There is also a template constructor parameterized by the iterator, so if you pass a pair of iterators to the container constructor, then the container is created from the elements defined by this range. A range is a set of elements defined by a pair of iterators, generalized pointers, or addresses. The second essential feature used in the STL was the template arguments, which are templates themselves, it was with them that the allocators that were originally proposed were implemented.
Did the STL requirements have any effect on the proposed changes to the templates?
In Valley Forge, Bjarn offered a significant addition to the templates — a “partial specialization” that would allow many algorithms and classes to be much more efficient and solve the problem of code size. I worked with Bjarn on the proposal, and it was motivated by the need to provide even more effective STL. Let me explain that there is a partial specialization. Now you can have a template function parameterized by the class T, say
Alex, where and when did you decide to offer STL as part of the ANSI / ISO C ++ Standard Definition?
During the summer of 1993, Andrew König attended Stanford to teach the C ++ course. I showed him some of our materials, and I think he was genuinely captured by what he saw. He arranged for an invitation for me as a speaker at the November meeting of the C ++ Standard Committee in San Jose. I read the report, labeled “The Science of C ++ Programming”. My speech was rather theoretical. The main position was that there are fundamental laws that link very primitive operations, such as constructors, assignment and equality. C ++ as a language does not impose any restrictions. You can define your own equality operator in order to perform multiplication. But equality must be equality, and it must be a reflexive operation. A must be equal to A. It must be symmetrical. If A is equal to B, then B is equal to A. A must be transitive. Common mathematical axioms. Equality is inherent in other operations. There are axioms connecting the constructor and the equality. If you are constructing an object with a copy constructor from another object, then the two objects must be equal. C ++ does not commit to this, but it is one of the basic laws to which we must obey. The assignment must create the same objects. Thus, I presented a group of axioms that are associated with these basic operations. I talked a little about the iterator axioms and showed some generalized algorithms that handle iterators. It was a two-hour lecture and, I think, quite dry. However, she was very well received. At that time I did not think about using this thing as part of the standard, since it was usually perceived that it was some kind of advanced programming technique that would not be widely used in the “real world”. I thought practical people had no interest in any of these works.
This speech was in November, and I did not think about ANSI until January. On January 6th, I received a letter from Andy Koenig, who is the editor of the Standard document, which said that if I want to make my library part of the Standard, I must submit a proposal by January 25th. My answer was “Andy, are you crazy?”, To which he replied, “Yes, I'm crazy, but why not try?”.
')
At that moment there was a lot of code and there was no documentation at all - much less than a formal proposal. Meng and I spent several 80-hour working weeks to catch the offer on time, before the possible time of its dispatch. At that time, the only person who knew about the upcoming proposal was Andy. He was the only support and helped a lot during this period. We sent an offer and waited. In the process of preparation, we identified a lot of things. When you write something down, especially when you design it as a Standard, you discover all the possible flaws in your project. We had to reimplement every single piece of code in the library, several hundred components, between sending the letter in January and the next meeting in San Diego in March. Then we had to revise the proposal, because revealed a lot of problems in the process of writing code.
Can you characterize the discussions and discussions on the proposal in the Committee? Was there immediate support? Resistance?
We did not believe that something would come of it. I gave a talk that was very well received. There were many objections, most of which took this form: this is a huge proposal, too late for him, at the previous meeting the resolution was approved not to take any serious proposals - and this huge thing, the largest proposal ever considered, with many completely new things. A vote was taken, and, interestingly, the overwhelming majority voted to consider this proposal at the next meeting, and sent it to vote at the next meeting in Waterloo, Ontario.
Bjarn Straustrup became an ardent supporter of STL. Many people helped with suggestions, modifications and inspections. Bjarn came here for a week to work with us. Andy was constantly helping. C ++ is a complex language, so it is not always clear what a given construct means. Almost every day I called Andy or Bjarna to ask if this and that is possible in C ++. I have to give Andy special respect. He conceived STL as part of the standard library. Bjarn became the main lobbyist for the STL committee. There were other people who brought benefits: Mike Vilot, head of the Library Group, Nathan Myers from Rogue Wave, Larry Podmolik from Andersen Consulting. There were many others.
STL as we proposed it in San Diego was written in the current version of C ++. We were asked to rewrite it using the new ANSI / ISO language features, some of which have not yet been implemented. There was a big dependence on the time of Bjarn and Andy, who tried to verify that we used these unrealized opportunities correctly.
Future users wanted the containers to be independent of the memory model, which was somewhat excessive because the language does not include memory models. They wanted the library to provide some kind of mechanism for abstracting the memory model. Earlier versions of STL assumed that the container size is expressed as an integer of type
size_t and that the distance between two iterators is of type ptrdiff_t . And now we were told - why do not you disengage from this? This is a difficult task, because the language does not abstract from this; C and C ++ arrays are not parameterized by these types. We invented a mechanism called “allocator” (allocator) that encapsulates information about the memory model. This has serious implications for each component in the library. You may wonder what memory models should do with container algorithms or interfaces. If you cannot use things like size_t , then you also cannot use things like T * because of different types of pointers ( T *, T huge * , etc.). Then you cannot use links, because with different memory models you have different types of links. There were huge implications for the library.The next important thing was to expand our original set of data structures with associative structures. It was easier, but it was always difficult to reach the Standard state, because we needed something that people would use for their containers for years. From the point of view of containers, STL is very clearly divided in half. Namely, it provides two basic types of container classes: sequences and associative containers. Drawing analogies - they are like ordinary memory and associative memory. This definition has clear semantics explaining what these containers do.
When I arrived in Waterloo, Bjarn spent a lot of time explaining to me that I shouldn’t worry about the result, that the attempt would most likely fail, but we did our best, we tried, and we had to take heart. The level of expectations was low. We were preparing for the opposition majority. As a result, there was some resistance, but insignificant. The voting results in Waterloo were unexpected, since there were about 80% "for" and 20% "against." Everyone was waiting for the battle, everyone was waiting for the controversy. There was a fight, but the vote was an absolute majority.
What effect does STL have on class libraries published in ANSI / ISO working paper of February 1994?
STL was included in the working paper in Waterloo. The STL document is divided into parts, and is located in different parts of the working document relating to the Library. Mile Vilot is responsible for this. I will not take an active part in editorial activities. I am not a member of the Committee, but every time a change is proposed regarding STL, it is under my jurisdiction. The committee is very delicate.
A number of template changes were adopted by the committee. Which ones have an effect on STL?
Before the adoption of STL, there were two changes that were used in the revised STL. One of them is the ability to have template member functions. STL makes extensive use of them so that you can build any container from any other container. A single constructor is available that allows you to build vectors from lists or from other containers. There is also a template constructor parameterized by the iterator, so if you pass a pair of iterators to the container constructor, then the container is created from the elements defined by this range. A range is a set of elements defined by a pair of iterators, generalized pointers, or addresses. The second essential feature used in the STL was the template arguments, which are templates themselves, it was with them that the allocators that were originally proposed were implemented.
Did the STL requirements have any effect on the proposed changes to the templates?
In Valley Forge, Bjarn offered a significant addition to the templates — a “partial specialization” that would allow many algorithms and classes to be much more efficient and solve the problem of code size. I worked with Bjarn on the proposal, and it was motivated by the need to provide even more effective STL. Let me explain that there is a partial specialization. Now you can have a template function parameterized by the class T, say
swap ( & , &) and swap their values. This is the most generalized possible type of function. If you want to specialize a function, and do something different for a particular type, you can have the swap (Int &, Int &) function swap (Int &, Int &) , which makes the exchange of integer values ​​in some other way. However, it was impossible to have an intermediate partial specialization in order to have a function template of the following form:template void swap(vector&, vector&);
. . swap, , , . , swap , , . , , . STL, , - , , , swap, , . . swap , , , swap . , . copy . copy , , . , :
template T ** copy(T**,T**,T**);
memcpy, , , (), memcpy. , . . , , , Valley Forge .
, , STL?
, STL , . , , , . , , , . , . STL .
. -. . STL , . , , . , , , . , . .
, 1969 . STL , . , , , , , , , , , , .
...Source: https://habr.com/ru/post/167257/
All Articles