Interview with the creator of C ++ STL, 1995 Part 3
The final part of the translation of the interview (the first part , the second part ) taken from the creator of the Standard Template Library Alex Stepanov in 1995. Here, Alex talks about why the templates do not include support for persistence and serialization, about the future of the library, and about the connection between the PLO and generalized programming.
Alex, STL does not implement the object model of the persistence (persistent storage) of objects. Map and Multimap are particularly good candidates for permanent storage of containers as inverted indexes in persistent object databases. Tell me, did you work in this direction, or can you at least comment on the implementation of this idea?
This circumstance was noted by many. STL does not implement persistence for a good reason. STL is as great as you could imagine at the time. I do not think that any larger set of components would pass through the Standards Committee. But persistence is what some people thought about then. When designing the STL, and especially during the design of the distribution component, Bjarn noted that the allocators that encapsulate the model's memory can be used to encapsulate the persistent model. The insight belongs to Bjarn, and this is an important and interesting epiphany. Several companies developing object databases are considering this idea. In October 1994, I attended a meeting of the Object Database Management System Group. I gave a talk on STL, and after that there was a great interest in making the containers with their evolving interface corresponding to STL. They did not consider distributors as such. Some of the members of the group, however, tried to find out whether the distributors could be used to implement persistence. I expect that over the next year there will be storage facilities with STL-compatible interfaces that will fit into the framework of STL.
Set, Multiset, Map and Multimap are implemented by red and black trees. Have you experimented with other structures, such as B * trees?
')
I don't think this will be true enough for data structures in memory, but this is something that needs to be done. The same interfaces defined by STL must also be implemented by other data structures — pass lists, semi-balanced trees, etc. This is a serious research activity that must be carried out, because STL provides us with a framework (framework) in which we can compare the performance of these structures. The interface is fixed. Basic complexity requirements are fixed. Now we can conduct meaningful experiments to compare different data structures with each other. Representatives of the community associated with data structures are known who invented all possible types of data structures for such interfaces. I hope that they will implement them as generalized data structures within the framework of STL.
Do compiler developers interact with you to implement STL in their products?
Yes. I get a lot of calls from compiler vendors. Pete Becker from Borland was extremely helpful. He helped by writing code, so that we were able to implement allocators for all Borland compiler memory models. Symantec is about to release an STL implementation for their Macintosh compiler. Edison Design Group was very helpful. We had good support from most compiler vendors.
STL includes templates that support the memory model of 16-bit MS-DOS compilers. With the current emphasis on 32-bit architectures, the flat model of compilers and operating systems, do you think the current memory model will remain true?
Regardless of Intel's architecture, a memory model is an object that encapsulates information about what a pointer is, what is the size of an integer and the type of difference of pointers, what is the reference type associated with this pointer, and so on. Abstraction is important if we introduce other types of memory, such as permanent memory, shared memory, etc. A nice feature of STL is that the only place where STL mentions machine types is that it refers to a real pointer, a real link and etc. - enclosed in about 16 lines of code. Everything else, all containers, all algorithms, are built abstractly, without mentioning anything related to the machine. From the point of view of portability, all things relating to specific devices and related to the concepts of address, pointer, and so on, are encapsulated in a small and well understood mechanism. Distributors, however, are not necessary for STL, or rather, are not as important as decomposition of fundamental data structures and algorithms.
The ANSI / ISO C committee standards addressed platform-specific issues, such as memory models, implementation details, and did not attempt to systematize them. Will the C ++ committee take a different look at these questions? If so, why?
I think STL is ahead of the C ++ standard in terms of memory models. But there is a significant difference between C and C ++. C ++ has constructors and a new operator that deal with a memory model and that are part of the language. Now it may be important to look at generalizing things like the new operator in order to be able to accept valves in the same way as STL containers do. This is not as important now as it was before adopting STL, because STL data structures will eliminate most of the requirements for using new. Most people should not allocate arrays, because STL is effective in this task. I will never have to use new in my code, and I pay great attention to efficiency. It is common for a code to be more efficient without using new. With the adoption of STL new will become an endangered species. STL also solves the problem of deletion, because, for example, in the case of a vector, the destructor will destroy it at the output of the block. You do not need to worry about cleaning up the repository, as you do when using new. STL can significantly reduce the need for garbage collection. The disciplined use of containers allows you to do everything you need to do without automatic memory management. STL constructors and destructors do the distribution correctly.
The C ++ Subcommittee on the Standard Library defines standard namespaces and exception handling conventions. Will STL classes have namespaces and exceptions?
Yes, they will. Committee members work with it, and do an excellent job.
How much will a possible standard differ from the current definition of STL? Will the committee be influenced by changes or designs with a greater degree of control?
It seems there is a consensus that there should be no significant changes in STL.
How can programmers get their first experience with STL while waiting for its standardization?
They can download the STL butler.hpl.hp.com header files in / STL and use it with a Borland or IBM compiler, or with any other compiler powerful enough to deal with STL. The only way to master a certain programming style is direct programming in this style. They should look at examples and write programs in this style.
You work with PJ (Bill) Pladzherom to write a book about STL. What will be the main idea of the book, and when is it scheduled for publication?
This is scheduled for the summer of 1995 and will be an annotated implementation of STL. This will be similar to Bill’s C standard books and the draft C ++ Library standard. He patronizes the book, so the book will serve as a reference for the standard and use of STL. I hope to write an article with Bjarn in which the interaction of the language and the Library will be discussed in the context of C ++ and STL. And this may lead to another book.
Much more work to be done. For STL to become successful, it is required that people research and experiment with this programming style. More books and articles should be written explaining how to program in this style. Courses should be developed, textbooks written. Tools must be created to help people navigate the Libraries. STL is a framework (working environment), and it would be nice to have a tool that allows you to view this environment.
What is the relationship between generic and object-oriented programming?
In a sense, generic programming is a natural continuation of the fundamental ideas of object-oriented programming — the separation of interface and implementation and the polymorphic behavior of components. However, there is a fundamental difference. Object-oriented programming emphasizes the syntax of language elements in the design of programs. You must use inheritance, you must use classes, you must use objects, objects send messages. Generic programming does not begin by determining whether you use inheritance or not. It begins with an attempt to identify or generate taxonomies, which objects in them and how they behave. That is, what does it mean - two things are identical? What is the right way to determine identity? The point is not only what the behavior of identical objects is. You can analyze identity more deeply and discover that there is a general concept of equality in which two objects are equal, if their parts, or at least their main parts, are equal. We can get a general recipe for the equality operation. We can discuss what types of objects are. There are sequences. There are operations on sequences. What is the semantics of these operations? What types of sequences in terms of complexity trade-offs should we offer to the user? What are the algorithms on the sequences? What different sorting functions do we need? And only after we define it and get a conceptual taxonomy of the components, we decide how to implement them. Will we use templates? Do we use inheritance? Do we use macros? What language technology do we use? The basic idea of generalized programming is the classification of abstract software components and their behavior and the creation of a standard taxonomy. The starting point is real, efficient algorithms and data structures, not language. Of course, this is always embodied in a particular language. You cannot have generic programming outside the language. STL is written in C ++. You could implement it on Ada. You could implement it in other languages. They will be slightly different, but there are some fundamental things that will be there. Binary search should be everywhere. Sorting should be everywhere. This is what people usually do. There will be some changes in the semantics of the containers, minor changes determined by the language. In some languages you can use inheritance to a greater extent, in some languages you must use patterns. But the fundamental difference is that generalized programming begins with semantics and semantic decomposition. For example, we decide that we need a component called swap. Then we find out how this component will work in different languages. The emphasis is on semantics and semantic classification, while in object-oriented programming, especially if we recall how it developed, much more attention, and, I think, too much attention is paid to exactly how to create things, that is, with using class hierarchy. OOP tells you how to build class hierarchies, but it does not tell you what should be inside these class hierarchies.
How do you imagine the future of STL and generic programming?
I have already said that the dream of programmers is standard repositories of abstract components with interfaces that are well understood and follow common paradigms. To do this, there must be a lot more effort to develop the scientific foundations of this programming style. STL starts it to a certain extent, classifying the semantics of some basic components. We need to work more on this. The goal is to turn software development from a craft into an engineering discipline. It needs a taxonomy of basic concepts and some laws that govern these concepts, which are well understood, which can be taught, which every programmer knows, even if he is not able to formulate them correctly. Many people know arithmetic, even if they have never heard of commutativity. Anyone who graduated from school knows that 2 + 5 is 5 + 2. Not all of them know that this is a commutative property of addition. I hope that most programmers know the fundamental semantic properties of basic operations. What does assignment mean? What does equality mean? How to construct data structures.
Currently, C ++ is the best tool for this programming style. I have tried different languages, and I think that C ++ provides the most remarkable combination of abstraction and efficiency. However, I think that it is possible to develop a language based on C and many ideas that C ++ brought, but a language more suitable for this programming style that lacks some of the drawbacks of C ++, especially its enormous size. STL deals with concepts. What is an iterator? Not a class. Not type. This is a concept. (Or, if we want to be more formal, this is what Bourbaki calls a structural type, what logicians call theories, or what people in the field of type theory call a type). This is something that does not have a language embodiment in C ++. But it could. You could have a language where you could formulate concepts, refine them, and finally turn them into classes in a certain way. (There are, of course, languages that relate to views, but they don't make much sense if you just want to sort.) We could have a language with the ability to define something called a forward iterator, which is defined in STL simply as a concept — and C ++ is no incarnation. Next, we can specify the forward iterator to the bidirectional iterator. Then a random iterator can be refined from bidirectional. You can develop a language that would allow even more programming in this style. I am fully convinced that it should be efficient and as close to the machine as C and C ++. And I believe that you can build a language that allows you to get close to the machine, on the one hand, and is able to deal with very abstract objects, on the other. I think that there can be even more abstractness than in C ++ without a gap between the underlying machines. I think generalized programming can affect language research, and we will have practical languages that are easy to use and well suited for this programming style. From this you can understand what I plan to work on further.
Alex, STL does not implement the object model of the persistence (persistent storage) of objects. Map and Multimap are particularly good candidates for permanent storage of containers as inverted indexes in persistent object databases. Tell me, did you work in this direction, or can you at least comment on the implementation of this idea?
This circumstance was noted by many. STL does not implement persistence for a good reason. STL is as great as you could imagine at the time. I do not think that any larger set of components would pass through the Standards Committee. But persistence is what some people thought about then. When designing the STL, and especially during the design of the distribution component, Bjarn noted that the allocators that encapsulate the model's memory can be used to encapsulate the persistent model. The insight belongs to Bjarn, and this is an important and interesting epiphany. Several companies developing object databases are considering this idea. In October 1994, I attended a meeting of the Object Database Management System Group. I gave a talk on STL, and after that there was a great interest in making the containers with their evolving interface corresponding to STL. They did not consider distributors as such. Some of the members of the group, however, tried to find out whether the distributors could be used to implement persistence. I expect that over the next year there will be storage facilities with STL-compatible interfaces that will fit into the framework of STL.
Set, Multiset, Map and Multimap are implemented by red and black trees. Have you experimented with other structures, such as B * trees?
')
I don't think this will be true enough for data structures in memory, but this is something that needs to be done. The same interfaces defined by STL must also be implemented by other data structures — pass lists, semi-balanced trees, etc. This is a serious research activity that must be carried out, because STL provides us with a framework (framework) in which we can compare the performance of these structures. The interface is fixed. Basic complexity requirements are fixed. Now we can conduct meaningful experiments to compare different data structures with each other. Representatives of the community associated with data structures are known who invented all possible types of data structures for such interfaces. I hope that they will implement them as generalized data structures within the framework of STL.
Do compiler developers interact with you to implement STL in their products?
Yes. I get a lot of calls from compiler vendors. Pete Becker from Borland was extremely helpful. He helped by writing code, so that we were able to implement allocators for all Borland compiler memory models. Symantec is about to release an STL implementation for their Macintosh compiler. Edison Design Group was very helpful. We had good support from most compiler vendors.
STL includes templates that support the memory model of 16-bit MS-DOS compilers. With the current emphasis on 32-bit architectures, the flat model of compilers and operating systems, do you think the current memory model will remain true?
Regardless of Intel's architecture, a memory model is an object that encapsulates information about what a pointer is, what is the size of an integer and the type of difference of pointers, what is the reference type associated with this pointer, and so on. Abstraction is important if we introduce other types of memory, such as permanent memory, shared memory, etc. A nice feature of STL is that the only place where STL mentions machine types is that it refers to a real pointer, a real link and etc. - enclosed in about 16 lines of code. Everything else, all containers, all algorithms, are built abstractly, without mentioning anything related to the machine. From the point of view of portability, all things relating to specific devices and related to the concepts of address, pointer, and so on, are encapsulated in a small and well understood mechanism. Distributors, however, are not necessary for STL, or rather, are not as important as decomposition of fundamental data structures and algorithms.
The ANSI / ISO C committee standards addressed platform-specific issues, such as memory models, implementation details, and did not attempt to systematize them. Will the C ++ committee take a different look at these questions? If so, why?
I think STL is ahead of the C ++ standard in terms of memory models. But there is a significant difference between C and C ++. C ++ has constructors and a new operator that deal with a memory model and that are part of the language. Now it may be important to look at generalizing things like the new operator in order to be able to accept valves in the same way as STL containers do. This is not as important now as it was before adopting STL, because STL data structures will eliminate most of the requirements for using new. Most people should not allocate arrays, because STL is effective in this task. I will never have to use new in my code, and I pay great attention to efficiency. It is common for a code to be more efficient without using new. With the adoption of STL new will become an endangered species. STL also solves the problem of deletion, because, for example, in the case of a vector, the destructor will destroy it at the output of the block. You do not need to worry about cleaning up the repository, as you do when using new. STL can significantly reduce the need for garbage collection. The disciplined use of containers allows you to do everything you need to do without automatic memory management. STL constructors and destructors do the distribution correctly.
The C ++ Subcommittee on the Standard Library defines standard namespaces and exception handling conventions. Will STL classes have namespaces and exceptions?
Yes, they will. Committee members work with it, and do an excellent job.
How much will a possible standard differ from the current definition of STL? Will the committee be influenced by changes or designs with a greater degree of control?
It seems there is a consensus that there should be no significant changes in STL.
How can programmers get their first experience with STL while waiting for its standardization?
They can download the STL butler.hpl.hp.com header files in / STL and use it with a Borland or IBM compiler, or with any other compiler powerful enough to deal with STL. The only way to master a certain programming style is direct programming in this style. They should look at examples and write programs in this style.
You work with PJ (Bill) Pladzherom to write a book about STL. What will be the main idea of the book, and when is it scheduled for publication?
This is scheduled for the summer of 1995 and will be an annotated implementation of STL. This will be similar to Bill’s C standard books and the draft C ++ Library standard. He patronizes the book, so the book will serve as a reference for the standard and use of STL. I hope to write an article with Bjarn in which the interaction of the language and the Library will be discussed in the context of C ++ and STL. And this may lead to another book.
Much more work to be done. For STL to become successful, it is required that people research and experiment with this programming style. More books and articles should be written explaining how to program in this style. Courses should be developed, textbooks written. Tools must be created to help people navigate the Libraries. STL is a framework (working environment), and it would be nice to have a tool that allows you to view this environment.
What is the relationship between generic and object-oriented programming?
In a sense, generic programming is a natural continuation of the fundamental ideas of object-oriented programming — the separation of interface and implementation and the polymorphic behavior of components. However, there is a fundamental difference. Object-oriented programming emphasizes the syntax of language elements in the design of programs. You must use inheritance, you must use classes, you must use objects, objects send messages. Generic programming does not begin by determining whether you use inheritance or not. It begins with an attempt to identify or generate taxonomies, which objects in them and how they behave. That is, what does it mean - two things are identical? What is the right way to determine identity? The point is not only what the behavior of identical objects is. You can analyze identity more deeply and discover that there is a general concept of equality in which two objects are equal, if their parts, or at least their main parts, are equal. We can get a general recipe for the equality operation. We can discuss what types of objects are. There are sequences. There are operations on sequences. What is the semantics of these operations? What types of sequences in terms of complexity trade-offs should we offer to the user? What are the algorithms on the sequences? What different sorting functions do we need? And only after we define it and get a conceptual taxonomy of the components, we decide how to implement them. Will we use templates? Do we use inheritance? Do we use macros? What language technology do we use? The basic idea of generalized programming is the classification of abstract software components and their behavior and the creation of a standard taxonomy. The starting point is real, efficient algorithms and data structures, not language. Of course, this is always embodied in a particular language. You cannot have generic programming outside the language. STL is written in C ++. You could implement it on Ada. You could implement it in other languages. They will be slightly different, but there are some fundamental things that will be there. Binary search should be everywhere. Sorting should be everywhere. This is what people usually do. There will be some changes in the semantics of the containers, minor changes determined by the language. In some languages you can use inheritance to a greater extent, in some languages you must use patterns. But the fundamental difference is that generalized programming begins with semantics and semantic decomposition. For example, we decide that we need a component called swap. Then we find out how this component will work in different languages. The emphasis is on semantics and semantic classification, while in object-oriented programming, especially if we recall how it developed, much more attention, and, I think, too much attention is paid to exactly how to create things, that is, with using class hierarchy. OOP tells you how to build class hierarchies, but it does not tell you what should be inside these class hierarchies.
How do you imagine the future of STL and generic programming?
I have already said that the dream of programmers is standard repositories of abstract components with interfaces that are well understood and follow common paradigms. To do this, there must be a lot more effort to develop the scientific foundations of this programming style. STL starts it to a certain extent, classifying the semantics of some basic components. We need to work more on this. The goal is to turn software development from a craft into an engineering discipline. It needs a taxonomy of basic concepts and some laws that govern these concepts, which are well understood, which can be taught, which every programmer knows, even if he is not able to formulate them correctly. Many people know arithmetic, even if they have never heard of commutativity. Anyone who graduated from school knows that 2 + 5 is 5 + 2. Not all of them know that this is a commutative property of addition. I hope that most programmers know the fundamental semantic properties of basic operations. What does assignment mean? What does equality mean? How to construct data structures.
Currently, C ++ is the best tool for this programming style. I have tried different languages, and I think that C ++ provides the most remarkable combination of abstraction and efficiency. However, I think that it is possible to develop a language based on C and many ideas that C ++ brought, but a language more suitable for this programming style that lacks some of the drawbacks of C ++, especially its enormous size. STL deals with concepts. What is an iterator? Not a class. Not type. This is a concept. (Or, if we want to be more formal, this is what Bourbaki calls a structural type, what logicians call theories, or what people in the field of type theory call a type). This is something that does not have a language embodiment in C ++. But it could. You could have a language where you could formulate concepts, refine them, and finally turn them into classes in a certain way. (There are, of course, languages that relate to views, but they don't make much sense if you just want to sort.) We could have a language with the ability to define something called a forward iterator, which is defined in STL simply as a concept — and C ++ is no incarnation. Next, we can specify the forward iterator to the bidirectional iterator. Then a random iterator can be refined from bidirectional. You can develop a language that would allow even more programming in this style. I am fully convinced that it should be efficient and as close to the machine as C and C ++. And I believe that you can build a language that allows you to get close to the machine, on the one hand, and is able to deal with very abstract objects, on the other. I think that there can be even more abstractness than in C ++ without a gap between the underlying machines. I think generalized programming can affect language research, and we will have practical languages that are easy to use and well suited for this programming style. From this you can understand what I plan to work on further.
Source: https://habr.com/ru/post/167909/
All Articles