Slashdot Mirror
Interviews: Ask Alexander Stepanov and Daniel E. Rose a Question
An anonymous reader writes "Alexander Stepanov studied mathematics at Moscow State University and has been programming since 1972. His work on foundations of programming has been supported by GE, Brooklyn Polytechnic, AT&T, HP, SGI, and, since 2002, Adobe. In 1995 he received the Dr. Dobb's Journal Excellence in Programming Award for the design of the C++ Standard Template Library. Currently, he is the Senior Principal Engineer at A9.com. Daniel E. Rose is a programmer and research scientist who has held management positions at Apple, AltaVista, Xigo, Yahoo, and is the Chief Scientist for Search at A9.com. His research focuses on all aspects of search technology, ranging from low-level algorithms for index compression to human-computer interaction issues in web search. Rose led the team at Apple that created desktop search for the Macintosh. In addition to working together, the pair have recently written a book, From Mathematics to Generic Programming. Alexander and Daniel have agreed to answer any questions you may have about their book, their work, or programming in general. As usual, ask as many as you'd like, but please, one per post."
Alexander Stepanov, I have never had a chance to ask someone as qualified as you about this topic. I grew up on the opposite side of the Iron Curtain and have constantly wondered if (surely there must have been) alternative computing solutions developed in the USSR prior to Elbrus and SPARC. So my question is whether or not you know of any hardware or instruction set alternatives that died on the vine or were never mass fabricated in Soviet times? I don't expect to you to reveal some super advanced or future predicting instruction set but it has always disturbed me that these things aren't documented somewhere -- as you likely know failures can provide more fruit than successes. Failing that, could you offer us any tails of early computing that only seem to run in Russian circles?
If you can suggest references (preferably in English) I would be most appreciative. I know of only one book and it seems to be a singular point of view.
My work here is dung.
Compare search technology to genetic programming. Will search technology progress to the point of "Computer -- write me a program that does ..." ?
This is more for Daniel Roseis, but to what do you attribute the seeming decline in the quality of search results? I used Digital's Alta Vista search engine when it was fairly new and it seemed revolutionary and seemed to provide me with exactly what I wanted. Over time that declined and Alta Vista as it was ceased to be, and Google initially also seemed to provide me with exactly what I wanted. Now it seems like I have to put a whole lot of thought into faking Google into performing a somewhat-boolean-style search for me, and normal boolean expressions themselves no longer seem to work.
Is this the result of attempting to dumb-down the interface for tailored results, or something else or more insidious? Obviously the amount of content on the Internet is growing, but the computing power to process through all of it is growing too, so I would expect it wouldn't be getting this much worse, this quickly.
Do not look into laser with remaining eye.
Have you had regret nightmares since unleashing STL?
I'm a huge fan of the STL, and I think the design has stood the test of time amazingly well.
That said, you now hae a bunch of hindsight. What would you do differently knowing what you know now.
Also if you were doing it today and using today's languages, how do you think it would differ?
SJW n. One who posts facts.
I remember reading you settled on C++ back in the 90s to implement STL.
Why the choice for an existing language and not craft your own language?
Alexander Alexandrovich, two questions:
1. What advices would you give to the younger generation of Russian software scientists and engineers?
2. Which ways would you suggest to benefit their fatherland?
I remember you wrote that STL has nothing to do with C++, it was a framework for generic programming and that C++ was chosen for its first implementation because it was less deficient for that purpose compared with other commercial programming languages.
That implies you'd like to develop a programming language from scratch. Is that so? If so, how is it going?
How to achieve excellence in programming and design ? I am working as a programmer for a year now. but I don't know what i am doing
Russian programmers and hackers are famous for being extremely smart. This is also a fame your fellow countryman hold from Chess tournaments and other competitions of the mind.
In your opinion:
Thanks
Alex: I regard my first encounter with the STL (very shortly after its first public release) as one of the great eye-opening moments in my software development career. Unfortunately, as I'm sure you well know, quality of implementation issues in compiler support for the C++ template idiom cultified (i.e. made cult-like) the deeper principles for at least five (if not ten) years thereafter.
GotW #50
I've long regarded the criticism against vector[bool]—I'm not going to fugger with angle brace entitiesâ"not being a container were misguided. Of course, it *must* be a container for reasons of sanity, but to portray the problem as a standardization committee brain fart seems to miss the main point.
Just as STL introduced a hierarchy of iterator potency (that was the main technical innovation behind the STL, was it not?) one could likewise introduce a hierarchy of container potency. The container we ended up returns interators which promise a dereference operator returning an lvalue (it's been a long time since I've used this terminology) which is why the following statement from the linked discussed is expected to work:
typename T::value_type* p2 = &*t.begin();
But actually, of all the uses of containers found in the wild, I highly doubt that more than a small percentage (potentially a very small percentage) exploit the property that interator dereference returns an lvalue rather than an rvalue.
The net effect is that the standard containers promise us a potency we rarely exploit, yet the burden of this potency is universal. Forsake it in even the smallest way, and you'll be shouted out of the room for non-containerhood.
We could have handled vector[bool] by changing the standard container to not promise IDLV (container iterators dereference to lvalue). In cases where the programmer goes ahead and tries to do this, he or she obtains a simple syntax error (ha ha ha) and knows to either reformulate the algorithm to not require this property or to go back and add a specification override to the container setting the IDVL property to true.
With IDVL set, vector[bool] does not specialize.
With IDVL unset, vector[bool] will specialize.
Problem solved, except for the language overhead of introducing (and managing) a container strength hierarchy.
But instead, Herb Sutter decides to write this:
Doesn't that attitude make you want to pound your head upon a table somewhere? Seriously, if one repeats that remark 1000 times, we could almost make the entire STL go away (and return to the world we would have had instead had the STL not rescued us from parsimony mass produced.)
Clearly, there was enough of a pain point in the C++ standarization effort around iterators that the STL gained traction exceedingly quickly (and very late in the day), yet the C++ community is also extremely hidebound about minor pain points, as evidenced by Sutter's explanatory tack.
Obviously, there were some advantages in demonstrating that the STL approach could achieve performance comparable to C (and in some cases, better than C) in proving that the STL was not just another abstraction gained at the expense of runtime overhead (which all looks fine until five or ten different runtime overheads—however small each of these appears in isolation—begin to interact adversely).
But very quickly, the initial quality of implementation issues and the quirky (to be extremely kind) limitations of the C++ template mechanisms threw up some major walls in pursuing the underlying ideas behind the STL more extensively.
So, my question is this, more or less: in retrospect, was the early victory with C++ worth it (it's extremely easy to understimate the value of having a good idea noticed at all), or does the eternal puberty of the C++ STL continue to grate?
How much of your time do you dedicate to computing vs doing other things; what are your other hobbies or is the work you do also your play time?
How difficult would it be to eliminate heap overflows, buffer overruns & stack exploits on the current x86 PC compatible architecture?
Heheh... well, designing c++ templates, in my mind, ranks as low as Java genetics design....
IMHO the C++ STL is a great library, and most criticism I've heard of it is more about particular implementations than its design. That said, when you look at other languages' standard libraries (or nonstandard libraries), are there things you wish the STL did differently or missed out on?
We see many programming languages with at least some support for Generics, but usually as a second class citizen, and often added as an afterthought in later releases, and subordinate to some other programming paradigm. Java is primarily OO, with generics added later. C# is also primarily OO, though with generic support. It took C++ several iterations to get generics, and C++ is "multi paradigm". Go doesn't have generics, and doesn't seem like it will not a while.
It seems to me like generic programming is sufficiently powerful as a paradigm to not need other paradigms like OO in the same language. In fact, in many ways, OO, which ties together data and alogrithms, seems antithetical to generic programming.
So, do you see a possibility of a programming language whose primary paradigm is generic programming? Why do language designers not get generics into the first releases of their languages, even now, when the issues would seem to be well known? What would such a language look like?
Alex, I saw some of interesting programming lecture video at A9 lab. What is the outcome of your teaching? Do you think the audiences applied your methodologies in daily programming work?
Often times I search for something and I want to search for a regular expression. Is there any technique that allows for indices on such?
Dear Alexander
In this interview, http://www.stlport.org/resources/StepanovUSA.html , you said:
"I love pasta, prosciutto and Chianti, - while I am a traditionalist, I look much more like John XXIII than Pius XII."
What did you please mean by this sentence, notably the word "Traditionalist" ?
Many thanks
Remi
Why did nobody extend the STL sensibly in order to prevent the complete mess called 'boost' to arise ?
Why the C++ community does not understand that difference between good abstraction (STL) and overengineering/ boilerplate / pointless genericity (BOOST) ?
Is there a domain that is better for generic programming than others? When Alexander talks about efficiency in "Elements of Programming", it seems that generic programming is specifically targeted for writing libraries. So, are there areas that benefit more from generic programming (like libraries) and areas that benefit less, such as user interfaces?
What is your current view on Dijkstra classic claim:
"go to statement considered harmful"
in Communications of the ACM / March 1968
The mathematical/generic programming approach you present in "From Mathematics to Generic Programming" has clearly been very successful in the design of libraries like STL, and has been adopted by languages other than C++. However, most day-to-day programming is very different from the kinds of problems that STL solves, or that you discuss in your books. Most programmers spend most of their time solving one-off problems that are very specific to their application, and writing code that is only ever intended to be used in one specific context (i.e. not intended to be generic).
As David Brooks said, "Einstein repeatedly argued that there must be simplified explanations of nature, because God is not capricious or arbitrary. No such faith comforts the software engineer. Much of the complexity he must master is arbitrary complexity..."
Is generic programming applicable to day-to-day lives of working programmers? Do you know of examples where these ideas have been applied to messy, irregular, real-world applications?
I watched some of your A9 lectures on YouTube, and discovered some amazing algorithmic ideas --- for example, the binary counter, the minmax algorithm, and quicksort implementation tricks/optimizations --- which I have not encountered in any algorithms books. Since the number of people who implement basic algorithms is rapidly dwindling these days, I am worried that basic algorithmic knowledge is being lost. Is there a resource where I can learn more about these techniques? I would love for you to write a series of articles (or give a series of lectures) about these topics (suggested title: "algorithmic gems").
You have argued in the past that making code generic makes it simpler. In my experience, it is the reverse: reading, understanding, and debugging generic code seems to be harder than non-generic code. This is also consistent with mathematics. It is easier to teach someone arithmetic than to teach abstract algebra. And, you yourself say in your books and lectures that one should start with concrete code before making it generic.
In what sense then is generic code simpler? Is complexity a disadvantage of generic programming?
The STL is about three decades old. In that time, we've seen both OS and hardware evolution. What is the impact of these changes on how the STL should be used? How would the STL be different if it where implemented targeting modern environments?
If you were to re-write STL in today's modern C++ or any feature that is proposed for C++ but not yet implemented. Which features do you think you would find most useful or be excited to have available to you that you didn't have when you first imagined STL in old C++.
Mr Stepanov, do you follow the ongoing efforts to standardise Concepts as a language feature in iso c++? If so, how do you think it's going? Would you do anything differently? To what extent do you think the standard library should provide Concepts? I recall learning about Concepts from the SGI STL doc many years ago and being very surprised to find that things like ForwardIterator weren't part of the iso spec.
STL was a pretty radical departure from the way classes and libraries were designed pre-STL. I am very keen to know a bit about the history of STL’s inclusion into the standard.
When you originally proposed STL for adoption into the C ++ standard, how receptive / enthusiastic was the C++ committee towards STL? What design decisions / compromises did you have to make to get it accepted? How much resistance did you face?
For example, you have noted that it took a major effort to convince the committee that vector must be contiguous. Was such instances common?
STL has been wildly successful and has pretty much completely changed the way libraries are designed not just in C++ but also in in other languages. Most mainstream languages have added facilities to write generic code.
When designing and proposing STL for inclusion into the standard, did you expect it to be this successful? Why do you think it has been this successful?
In you book "Elements of Programming", you spend a lot of time on concepts. The paper "A Concept Design for the STL", the basis of the latest concept design for C++, references your book extensively. You of course co-authored that paper. I am therefore quite keen to hear your views on C++ Concepts.
Do you think that language support for concepts (or equivalent constructs like Haskell typeclasses) is important for writing generic code? How deeply are you involved in the effort to get concepts into the C++ standard?
As we all know, C++ is far from perfect. There are several features which you discuss in your books and papers, like concepts and UNDERLYING_TYPE, which C++ is currently missing but proposed for C++17 (e.g. destructive move). However there are things you have criticized before, like the memory allocation interface, which are still as they were 25 years back.
What do you dislike the most about C++? What would you change or add to the language to make it better?
The iterator based approach of STL works very elegantly for 1 dimensional data structures but fails to generalize cleanly for higher dimensional structures. For example, there is no easily defined way of iterating over a 2d array or a graph. Also, the notion of regular types, discussed in your book Elements of Programming, also fails to generalize for 2 or higher dimensional types, like complex numbers and matrices. They lack the total ordering property.
Of course, you can artificially define an ordering, say force a row-by-row iteration over a 2D-Array or a breadth-first iterator over a tree or an artificial ordering on complex numbers, but such constructs feel artificial. Do you think this limitation is fundamental to the iterator based design approach?
In your "Spoils of the Egyptians" talk, you said "We have to develop our sense of beauty, and use it, to succeed in programming." I agree. I also agree that studying Mathematics is a good way to develop our sense of beauty. Conversely, learning how to program helped me write better proofs.
Do you suggest any particular people or works outside of engineering and mathematics that are helpful for becoming better programmers? I am thinking of literature, philosophy, "soft" sciences, or humanities more than visual arts and music.
Hello,
It's always been interesting to me to see how many programmers do not come from math backgrounds, and yet we
know that there's a correspondence between computer programs and certain kinds of construction proofs. This suggests
that the foundations of logical thought don't need to come from traditional mathematics, but what would you say are the
essential things that should be brought to the attention of such a programmer?
C(++) allocates local objects on the stack and dynamically allocated objects on the heap.
However, Linux provides the alloca() function that allocates memory in the stack frame of the caller. This temporary space is automatically freed when the function that called alloca() returns to its caller.
How could C++ take advantage of that? (other than custom allocators and such). Are any new language features needed?
Hi,
so far I read parts of your book: "From Mathematics to Generic Programming"
While it is an interesting read I find there is a lack of profiling.
For example, the multiplication of int32 was fastest on my machine when using the naive approach and Egyptian multiplication was worse.
After that the algorithm was constantly micro-optimised, yet the performance on my machine degraded and an initially beautiful algorithm appeared distorted.
That is especially bad since this is basically the intro to an otherwise interesting book.
Granted, you are talking about generic algorithms and I am talking about int32 in an introductory example. Applying this algorithm to other types might actually pay off.
Baseline what do you think of adding also remarks (!) [1] for practical application in following editions?
Like profiling algorithms before adopting a more complex one that has worse results in practice.
Cheers!
Matthias
[1] I know that giving actual numbers would make the book outdated on its release.
In your book you mention Euclid's Elements. It is the oldest continuously use textbook in history, but is it really relevant to a computer science education?
The STL iterator approach as proven very successful for data structures like lists/vectors/tree/etc. Yet for data structures that have a segmented structure such as deque, hash tables, sub-matrices, B-trees, STL has a high abstraction cost for iterators, forcing you to make extra unnecessary checks when comparing two iterators. (see for example Matthew H. Austern's paper "Segmented Iterators and Hierarchical Algorithms": http://lafstern.org/matt/segme...) Do you believe STL should be extended with an additional iterator abstraction to handle such data structures (like Austern's proposed segmented iterators) or do you believe it's too difficult to handle such data structures in a optimal generic way?
Eric Niebler recently proposed a major TS (https://github.com/ericniebler/range-v3) that aims to refactor STL to introduce ranges. It also breaks compatibility in minor ways (e.g. by allowing for two iterators specifying first and last positions to be of different types), so it will likely be introduced as a new additional library to eventually replace the existing STL, while being very close to compatible. Given that such a rewrite is open to making some changes that break compatibility, are there any other modifications you'd like to see? And what else would you like to see in a C++17 version of STL?