Open and Efficient Type Switch for C++ -- Solodkyy, Dos Reis, and Stroustrup

Here's a recent highlight from the pre-Portland mailing that you might have missed:

Open and Efficient Type Switch for C++

Yuriy Solodkyy, Gabriel Dos Reis, Bjarne Stroustrup

... we implement a type switch construct as an ISO C++11 library, called Mach7. This library-only implementation provides concise notation and outperforms the visitor design pattern. ... For closed sets of types, its performance roughly equals equivalent code in functional languages, such as OCaml and Haskell.

C++ is a powerful library-building language. Whenever possible, we prefer to add new functionality as a library rather than in the language. This is an excellent example of where a C++ library-only solution can get equivalent performance to the language support included in some popular functional languages.

Add a Comment

Comments are closed.

Comments (7)

1 0

Leszek Swirski said on Feb 14, 2013 05:18 AM:

This is some pretty heavy macro magic, especially with the "EndMatch" macro breaking normal C++ syntax. I thought that macro magic this heavy was usually not recommended?
1 0

Bjarne Stroustrup said on Feb 14, 2013 07:12 AM:

Mach7 is an experimental tool, not a style guide
0 0

Arthur Langereis said on Feb 14, 2013 10:32 AM:

The macros allow for a very terse syntax, but syntax errors may be difficult to work with. I will gladly trade some extra characters for better diagnostics, if possible.
Compiling in clang with libc++ gives a syntax error in unordered_map, which is most curious. The concept is great tho, I look forward to see what comes out of this.

Would this work when combined with ideas like std::any, wherein I could match against types of non-overlapping type hierarchies, or is this only suitable for matching against subclasses of a single base class?
1 0

Yuriy Solodkyy said on Feb 14, 2013 10:30 PM:

Indeed as Dr. Stroustrup said the library is just an experimental tool - we just wanted to try the idea without having to change a compiler. The library so far has been tested with Visual C++ 2010 and 2012 as well as g++ 4.5.2, 4.6.1 and 4.7.2 (the snapshot on the webpage was uploaded before I got the last one, so have to double check). I did not get around yet to try it with Clang (hence your errors), but should there be interest, I can definitely look into that.

With diagnostics, the approach is the following: everything we can check with meta-programming, we do, and static assert. For the rest, for those mistakes I made myself while using the library, I've been sprinkling comments in code like: if you get this kind of error around this line, you probably did this wrong etc.
0 0

Thiago R Adams said on Feb 16, 2013 05:57 AM:

In case of compiler implementation what do you think of this syntax?


// kind of "virtual non-member"
loc point_within(const Shape* shape) = 0;

loc point_within(const Circle* matched) {
return matched->center;
}

loc point_within(const Square* matched) {
return matched->upper_left;
}
...

//select the best match of "point_within" in runtime
Shape *shape = new Circle;
point_within(runtime_type(shape));


And for double dispatch



check_collision(Circle&, Square&) {...}
etc...

check_collision(runtime_type(shape1), runtime_type(shape2));



Is there any chance to get this syntax using only library?
Or something like:


dynamic_call(point_within, shape);

0 0

Marcin said on Feb 16, 2013 10:42 AM:

It will be possible to add in next standard something like variadic switch that will work with Variadic template parameters?
Something like that:

template<int... A>
int foo(int i)
{
switch(i)
{
default:
return 0;
case A...:
return bar<A...>::f();
}
}

right now you can made switch work like that but its tedious to write and have hard limit on number of cases.
this new feature could simplify many task like in this paper.
0 0

Yuriy Solodkyy said on Feb 16, 2013 12:50 PM:

To Thiago R Adams: the feature you are looking for is [url="http://en.wikipedia.org/wiki/Multi-methods"]multi-methods[/url]. We had a technical report [url="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2216.pdf"]N2216=07-0076[/url] submitted to WG21 back in 2007 detailing a possible C++ implementation. A more polished version of it can be found in [url="http://dl.acm.org/citation.cfm?doid=1289971.1289993"]GPCE'07[/url] proceedings and in a [url="http://www.sciencedirect.com/science/article/pii/S016764230900094X"]journal article[/url]. In the paper, we list several approaches people took to multi-methods in C++ and one of them was a library-based approach. It is part of Andrei Alexandrescu's [url="http://en.wikipedia.org/wiki/Loki_(C++)"]Loki library[/url], where he explores several different alternatives that differ in flexibility and speed. You can find a detailed description of his solution in his book [url="http://amzn.to/ModernCppDesign"]Modern C++ Design[/url]. Multi-methods are indeed related to type switching, but they are not quite the same. We will have a comparison of the two at some point.

To Arthur Langereis: the solution can handle multiple inheritance (both repeated and virtual) and the subject type does not have to be related to target types by inheritance. They must be polymorphic classes (for the open solution), but other than that can be completely unrelated. The type switch will perform a proper cross-cast if needed as long as dynamic_cast from the subject to a given target type is defined (see the paper for more details). The library can also support non-polymorphic classes in a more limited form. This usually assumes that the user already has a dedicated member in the base class (a tag) that uniquely identifies derived class. In this case, the user retroactively (through traits) tells the library in which member the tag is stored and which tag values correspond to which derived classes. The library then provides the same unified syntax with slight difference in semantics - best-fit instead of first-fit (please see the paper for details).