Sunday, December 30, 2012

C++11 (sort of kind of) has path dependent types (ish)

Scala has a neat feature called "Path Dependent Types". It's a form of dependent typing that sort of piggy backs on the idea of Java's inner classes. A nice brief little overview is here on Stackoverflow:

http://stackoverflow.com/questions/2693067/what-is-meant-by-scalas-path-dependent-types

If you're too lazy to read that (which would be disappointing, it's pretty brief), the general idea is that given:

   class A {
      class B {
         ...
      }
      ...
}

var a1 = new A;
var a2 = new A;
var b1 = a1.new B;
var b2 = a2.new B;

b1 and b2 actually have different types. This is actually something that would be super useful in C++. Consider perhaps:

vector a, b;
std::sort(a.begin(), b.end());

Would it not be nice if that didn't compile? With path dependent types you could make it so!

I think this feature is, the bee's knees, largely because I once ran into a problem that this functionality would have thwarted (granted there are many other ways of thwarting my particular problem, but PDTs would have given a result closest in spirit and runtime overhead (read: none), to the original interface).

C++11 gives us many interesting features, none of which are path dependent types. However, some of them in conjunction get us pretty close. One is auto, which works like "var" in my Java pseudocode above (or like val in the Stackoverflow example, which you should really read if you haven't yet), The other is the lambda. Now, I'm not going to be using a lambda as well a lambda. Instead I'm going to be using lambda expressions as a sort of compile-time unutterable type factory. Lambda expressions have the fascinating property that even syntactically identical lambda expressions don't have the same type. This ties into the fact that they cannot appear in an unevaluated expression like decltype or sizeof. What they've done in effect, is snuck a tiny little dependently typed value (in a very loose sense) into the language. We're going to take advantage of this feature (compile time type factory) and leverage lambdas to populate a sort of phantom type variable to mimic path dependent types. It'll probably be easier if I just show you:


You see the board class is templated on a template parameter that never appears again, this is our so called phantom type. The "make_board" macro uses a lambda expression to whip up a new lambda expression (and consequently a new type) every time we happen to need one, thus each new board, much like each new lambda expression has a unique type. Likewise, each nested Coordinate type is consequently different, and line 52 of our snippet, were it to be uncommented, would not compile.

I think this is sort of a neat trick. It has various problems when compared to the "real" thing, but given the presence of features like decltype is perhaps less painful that might initially be imagined. I suspect there are probably a whole world of meta-programming and type-system hacks that can be created by taking advantage of the ability of lambda expressions in conjunction with template argument deduction / auto to create new unutterable types.