05 March 2009

Bjarne Stroustrup is so metal!

Bjarne Stroustrup is so metal!On Wednesday, Bjarne Stroustrup made a visit to Princeton, and the Liberty Research Group scheduled a private meeting with him before his colloquium. We spent a little over an hour discussing the C++0x and the future of C++. Overall, Bjarne is a cool guy, and I had an excellent time talking with him.

The wikipedia article about C++0x is painfully out of date. Bjarne mentioned some upcoming features that are hardly mentioned, if at all. Of these, the ones which took my interest the most were Concepts, Axioms, and the future of static typing in C++.

I'll disclaim that I haven't read any C++0x standardization documents, not even drafts, so take everything here as a grain of salt. These are simply my take-away points from the talk.

Bjarne is concerned that the template feature of C++ does not allow programmers to sufficiently constrain template parameters. For instance, a sort algorithm may be implemented to operate on a random-access iterator. However, recall that iterators in the C++ STL do not share a common inheritance (and there are fair arguments that they shouldn't). C++ templates cannot capture the notion that one of its formals must be a iterator-like type, and so specializing the template against, say a string, will likely yield hundreds of uninformative type errors instead of a simple error stating that we expect an iterator.


One solution to this problem would be to create base iterator classes in order to ensure an interface (this is the approach taken by Java, for instance). However, one could argue that this is an inappropriate use of inheritance---it's not code re-use, and although we give many concepts the name iterator, they really have little in common.

Some languages use a notion of structural equivalence (or, less formally, duck typing) to capture these constraints. I think this is the appropriate technique. The earlier example of a sorting algorithm simply requires some object which can provide random access to a data structure, and the most direct test for compatibility is whether the interface is a satisfied. In C++0x, Concepts are an implementation of structural equivalence (from the high-level, language view). In the low-level view, concepts are a special case of templating, and produce multiple implementations of the same code according to the specific type.

In a C++0x Concept, one can specify the methods which must be supported. For instance, one may have a Concept named TotalOrder, which must support a less-than-or-equal-to operator. Many types satisfy the TotalOrder concept, such as int, double, std::string, yet they are not required to have a common ancestor. In this sense, a concept allows you to communicate many of the traits to a type, without paying the penalty of multiple inheritance.

But Concepts get cooler. Although I describe them as a mechanism for structural equivalence in C++, they can also be viewed as mixins, since they allow a programmer to specify a default implementation for many methods. With the prior example of TotalOrder, one could also add default implementations of greater-than, equal-to, etc, operators as functions of less-than-or-equal-to. In this way, it becomes very easy for programmers to bootstrap support for all operators while writing minimal code.

Suppose that I implement some class that satisfies TotalOrder. This information simply means that my class supports comparison operators. One wonders, however, if these operations actually behave as a total order. As a counter example, I could write a random number generator to produce the result of the less-than-or-equal-to comparison---can a language be made to disallow this? Or, can a compiler be taught to rely upon deeper qualities of total orders, without having a special case for total orders?

Axioms allow the programmer to specify additional qualities of operations that transcend simple typing. For instance, one could write axioms that signify that the less-than-or-equal-to relation is transitive, or that it is always the logical inverse of the greater-than relation. With axioms, we can state that a sort algorithm not only requires a random-access-iterator, but also that there is a total order of the elements which satisfies transitivity. The use of concepts and axioms allows us to specify all of the constraints of the sort algorithm.

But how can the compiler use axioms? It is unlikely that any compiler will ever be able to verify that the listed axioms are true for a given implementation. Instead, axioms will provide additional transformations to the compiler's arsenal of optimizations. With support for axioms, many compiler optimizations including constant-folding (especially with associativity), reduction in strength, and common-subexpression elimination can be lifted from the compiler and expressed at the language level. I think this is really cool.

I think the notion of concepts and axioms struck home with me because they resemble some of my thinking on one of my side projects. I've been working on a language for years now (never enough time, alas!) in which I plan to feature structural equivalence in typing for reasons similar to those outlined by Bjarne. The axioms are a natural extension which I now realize I would like to support as well.

Finally, before the meeting was over, I had to ask a question about type safety. Throughout his book The Design and Evolution of C++, Bjarne laments the type (un)safety of C. Repeatedly, and with each new language feature, he attempts to make C++ more typesafe, but is repeatedly foiled by inherited features such as void pointers and unrestricted casting. So, I asked: are you ever going to take the plunge and drop support for pointers in C++? His answer was intelligent, and showed a great understanding of not simply the technical considerations of C++, but also the political considerations.

Mr. Stroustrup suggested that he hopes to add more and more features to C++ until type-safe alternatives are available for each and every unsafe aspect of C++. Once that has happened, he hopes to define a safe subset of C++. At that point, all existing C++ tools could be given a flag to provide warnings of unsafe features. This safe sub-C++ will immediately have rich toolchain support, but will be able to provide strong guarantees, such as those provided by ML. Excellent plan.

Bjarne is a very interesting person indeed; I recommend you talk with him if you ever have the chance.

4 comments:

Dennis Ferron said...

You got to meet Bjarne Stroustroup?! Ah, I so jealous. I've watched every video I can find online of him speaking about C++0x. He's not just a brilliant man, but also a good speaker; one of those people who makes you feel like you just gained 2 IQ points just from grokking what he's got to say.

Oh yeah, C++0x is going to totally rock our socks off. I have in fact read some of the technical documents, and as far as I can remember you have it right about concepts; I hadn't read about or perhaps failed to grasp axioms until now, so thanks for explaining those.

My business partner and I are impatiently awaiting the release of C++0x so that we can update our MMO game codebase to use it. The design of our game engine actually requires lambda functions to be at all convenient to use. We're doing this neat thing whereby most of the functionality of the game is implemented using functors, so for instance game->draw() doesn't know about the graphics api, it takes a functor and the functor talks to the graphics api. When you use this technique all over the place, it's a pain to create a class for every functor, and much better to be able to declare the code of the functor near the usage of the functor. Right now I'm using a hack that simulated lambdas in ordinary C++, but it's limited, although I did come up with a really sick way of shoehorning closures onto current C++! Incidently, it's the topic of a blog post I've had in draft for a while; you might have just spurred me to publish it.

Also funny you should mention duck typing in relation to concepts, because I have an upcoming blog entry about that as well. My premise is that current C++ templates actually already implement "static duck typing", which is frankly a downright weird and absolutely fun combination, and I want to talk about some of the implications of that. I say C++ templates are already duck typed because they don't care about either the types or the signatures of objects and methods that are templated; they only care about whether the names of the methods are implemented. The problem is that if you make a mistake, you don't see the error where you made it, but 15 nested classes down inside some library header you've never heard of where the mismatch finally bottoms out. Concepts will fix that by letting the author of the template catch those at the top level, not the bottom. You are right, however, in that the way concepts themselves are implemented is duck typed. I like that; I think in a way the existing de facto duck typed way templates have been used forced them into making concepts work this way for compatibility, so the result is they were forced to implement them the way I would have wanted them to do it regardless.

Dennis Ferron said...

(A bug in the input form sliced my comment, I had more to say:)

I'd like to have a discussion with you about the language you're designing. I have some (incomplete) ideas about a language design and I'd like to see if you either want to incorporate them or have some suggestions for my language. One idea is every block of code in curly braces would implicitly be a block/lambda function, so for instance while (x) { do_something; } is the same as var block = { do_something; }; while (x) block;

Anyhow great post, bravo.

Nick Johnson said...

Dennis,

I definately want to talk about it sometime.

The language you describe sounds interesting. It reminds me of a language described in an academic paper several years back named Z (I'll try to find a link). Having said that, it of course has some similarities to lisp.

Bjarne had an interesting prediction about lambdas in C++0x: he thinks that in the first year-or-so after their adoption they will be overused. After that, people will calm down and use them more conservatively. Having said that, I caution: your MMO codebase doesn't *require* them, since lambdas can be efficiently emulated with function classes (especially those which capture some environment during construction). Bjarne's lambdas don't deal well with escaped variables---stack variables still disappear upon scope exit, even if you return a lambda that captures them.

Though it is quite different than what I am planning. I'm looking more towards static type systems, but providing some very high level features that are generally only available with dynamic typing (e.g. safe variadic functions) or in scripting languages (fancy syntax for literals of many classes, including ranges, xml, regexen, etc). Also, a lot of my work will go into a decent standard library (I'm so unhappy with the standard libraries of C++ and Java)... I have one focus which is clear: make software development easier without sacrificing performance. I pull in high level features only after I'm sure they can be efficiently implemented. Too much to discuss here, we'll talk over email.

Shoot me an email; without telling the spammers (they're always listening), you can google for "nick johnson princeton" and find my email address at my princeton site.

Nick

Anonymous said...

Haskell.