..на полях..
Пишу сейчас здоровый пост про С++ :) Читаю http://www.research.att.com/~bs/hopl-almost-final.pdf Наткнулся на такое:
4.1.8 Stepanov’s view
The description of the STL here is (naturally) focused on language and library issues in the context of C++. To get a complementary view, I asked Alexander Stepanov for his perspective [106]:
In October of 1976 I observed that a certain algorithm - parallel reduction - was associated with monoids: collections of elements with an associative operation. That observation led me to believe that it is possible to associate every useful algorithm with a mathematical theory and that such association allows for both widest possible use and meaningful taxonomy. As mathematicians learned to lift theorems into their most general settings, so I wanted to lift algorithms and data structures. One seldom needs to know the exact type of data on which an algorithm works since most algorithms work on many similar types. In order to write an algorithm one needs only to know the properties of operations on data. I call a collection of types with similar properties on which an algorithm makes sense the underlying concept of the algorithm. Also, in order to pick an efficient algorithm one needs to know the complexity of these operations. In other words, complexity is an essential part of the interface to a concept.
In the late ’70s I became aware of John Backus’s work on FP [7]. While his idea of programming with functional forms struck me as essential, I realized that his attempt to permanently fix the number of functional formswas fundamentallywrong. The number of functional forms - or, as I call them now, generic algorithms - is always growing as we discover new algorithms. In 1980 together with Dave Musser and Deepak Kapur I started working on a language Tecton to describe algorithms defined on algebraic theories. The language was functional since I did not realize at the time that memory and pointers were a fundamental part of programming. I also spent time studying Aristotle and his successors which led me to better understanding of fundamental operations on objects like equality and copying and the relation between whole and part.
In 1984 I started collaborating with Aaron Kershenbaum who was an expert on graph algorithms. He was able to convince me to take arrays seriously. I viewed sequences as recursively definable since it was commonly perceived to be the “theoretically sound” approach. Aaron showed me that many fundamental algorithms depended on random access. We produced a large set of components in Scheme and were able to implement generically some complicated graph algorithms.
The Scheme work led to a grant to produce a generic library in Ada. Dave Musser and I produced a generic library that dealt with linked structures. My attempts to implement algorithms that work on any sequential structure (both lists and arrays) failed because of the state of Ada compilers at the time. I had equivalences to many STL algorithms, but could not compile them. Based on this work, Dave Musser and I published a paper where we introduced the notion of generic programming insisting on deriving abstraction from useful efficient algorithms. The most important thing I learned from Ada was the value of static typing as a design tool. Bjarne Stroustrup had learned the same lesson from Simula.
In 1987 at Bell Labs Andy Koenig taught me semantics of C. The abstract machine behind C was a revelation. I also read lots of UNIX and Plan 9 code: Ken Thompson’s and Rob Pike’s code certainly influenced STL. In any case, in 1987 C++ was not ready for STL and I had to move on.
At that time I discovered the works of Euler and my perception of the nature of mathematics underwent a dramatic transformation. I was de-Bourbakized, stopped believing in sets, and was expelled from the Cantorian paradise. I still believe in abstraction, but now I know that one ends with abstraction, not starts with it. I learned that one has to adapt abstractions to reality and not the other way around. Mathematics stopped being a science of theories but reappeared to me as a science of numbers and shapes.
In 1993, after five years working on unrelated projects, I returned to generic programming. Andy Koenig suggested that I write a proposal for including my library into the C++ standard, Bjarne Stroustrup enthusiastically endorsed the proposal and in less than a year STL was accepted into the standard. STL is the result of 20 years of thinking but of less than two years of funding.
STL is only a limited success. While it became a widely used library, its central intuition did not get across. People confuse generic programming with using (and abusing) C++ templates. Generic programming is about abstracting and classifying algorithms and data structures. It gets its inspiration from Knuth and not from type theory. Its goal is the incremental construction of systematic catalogs of useful, efficient and abstract algorithms and data structures. Such an undertaking is still a dream.
You can find references to the work leading to STL at www.stepanovpapers.com.
I am more optimistic about the long-term impact of Alex’s ideas than he is. However, we agree that the STL is just the first step of a long journey.
Слегка офигел. Не, я, конечно, понимал, что С++ разрабатывали не дураки. Но такой теоритической проработки - с Аристотелем, Эйлером, Кантором и моноидами - не ожидал :)
4.1.8 Stepanov’s view
The description of the STL here is (naturally) focused on language and library issues in the context of C++. To get a complementary view, I asked Alexander Stepanov for his perspective [106]:
In October of 1976 I observed that a certain algorithm - parallel reduction - was associated with monoids: collections of elements with an associative operation. That observation led me to believe that it is possible to associate every useful algorithm with a mathematical theory and that such association allows for both widest possible use and meaningful taxonomy. As mathematicians learned to lift theorems into their most general settings, so I wanted to lift algorithms and data structures. One seldom needs to know the exact type of data on which an algorithm works since most algorithms work on many similar types. In order to write an algorithm one needs only to know the properties of operations on data. I call a collection of types with similar properties on which an algorithm makes sense the underlying concept of the algorithm. Also, in order to pick an efficient algorithm one needs to know the complexity of these operations. In other words, complexity is an essential part of the interface to a concept.
In the late ’70s I became aware of John Backus’s work on FP [7]. While his idea of programming with functional forms struck me as essential, I realized that his attempt to permanently fix the number of functional formswas fundamentallywrong. The number of functional forms - or, as I call them now, generic algorithms - is always growing as we discover new algorithms. In 1980 together with Dave Musser and Deepak Kapur I started working on a language Tecton to describe algorithms defined on algebraic theories. The language was functional since I did not realize at the time that memory and pointers were a fundamental part of programming. I also spent time studying Aristotle and his successors which led me to better understanding of fundamental operations on objects like equality and copying and the relation between whole and part.
In 1984 I started collaborating with Aaron Kershenbaum who was an expert on graph algorithms. He was able to convince me to take arrays seriously. I viewed sequences as recursively definable since it was commonly perceived to be the “theoretically sound” approach. Aaron showed me that many fundamental algorithms depended on random access. We produced a large set of components in Scheme and were able to implement generically some complicated graph algorithms.
The Scheme work led to a grant to produce a generic library in Ada. Dave Musser and I produced a generic library that dealt with linked structures. My attempts to implement algorithms that work on any sequential structure (both lists and arrays) failed because of the state of Ada compilers at the time. I had equivalences to many STL algorithms, but could not compile them. Based on this work, Dave Musser and I published a paper where we introduced the notion of generic programming insisting on deriving abstraction from useful efficient algorithms. The most important thing I learned from Ada was the value of static typing as a design tool. Bjarne Stroustrup had learned the same lesson from Simula.
In 1987 at Bell Labs Andy Koenig taught me semantics of C. The abstract machine behind C was a revelation. I also read lots of UNIX and Plan 9 code: Ken Thompson’s and Rob Pike’s code certainly influenced STL. In any case, in 1987 C++ was not ready for STL and I had to move on.
At that time I discovered the works of Euler and my perception of the nature of mathematics underwent a dramatic transformation. I was de-Bourbakized, stopped believing in sets, and was expelled from the Cantorian paradise. I still believe in abstraction, but now I know that one ends with abstraction, not starts with it. I learned that one has to adapt abstractions to reality and not the other way around. Mathematics stopped being a science of theories but reappeared to me as a science of numbers and shapes.
In 1993, after five years working on unrelated projects, I returned to generic programming. Andy Koenig suggested that I write a proposal for including my library into the C++ standard, Bjarne Stroustrup enthusiastically endorsed the proposal and in less than a year STL was accepted into the standard. STL is the result of 20 years of thinking but of less than two years of funding.
STL is only a limited success. While it became a widely used library, its central intuition did not get across. People confuse generic programming with using (and abusing) C++ templates. Generic programming is about abstracting and classifying algorithms and data structures. It gets its inspiration from Knuth and not from type theory. Its goal is the incremental construction of systematic catalogs of useful, efficient and abstract algorithms and data structures. Such an undertaking is still a dream.
You can find references to the work leading to STL at www.stepanovpapers.com.
I am more optimistic about the long-term impact of Alex’s ideas than he is. However, we agree that the STL is just the first step of a long journey.
Слегка офигел. Не, я, конечно, понимал, что С++ разрабатывали не дураки. Но такой теоритической проработки - с Аристотелем, Эйлером, Кантором и моноидами - не ожидал :)