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.

Conditional Critical Regions: State sidebar

I'm going to try and explain this better and justify it in my next post, but here is the State Monad (ala Haskell) in C++11. I have to say, without C++11 this would be even more painful than it already is.

Conditional Critical Regions: Implementing (or not) in C++

Two notes. First I'm using embedded gists for the code examples. This may not work in RSS. Secondly, I thought this would be two parts but it's getting long so it's going to be three.

First let's set the stage. This code is written with C++11 in mind, I assume lambda support. I also assume C++11 type mutex/condition_variable support, but since I didn't actually have that I wrote my own, so in this code their not explicitly in the std namespace. You should be able to to use std ones or boost ones or what have you by dropping in the appropriate using declarations. I also whipped up a simple scope guard doodad.

Before I forget, you probably should have read the last post. So let's start with the simple versions of these, the with r do and the with r when Condition do.


That's actually not bad at all, no? Lambdas and std::function make this all a bit smoother than the C++ of yore would have. Ok, let's talk about problems. What happens when we nest? Actually, not at all what I expected! This blog post might turn out to be about compiler bugs.

  So what happens when we compile this? We get a compiler error (I'm using VS2010): error C2872: ' ?? A0xc6bc40fc' : ambiguous symbol. Oops. Your C++ is showing. Intellisense has a better message, telling me that it's an "Invalid reference to a outer-scope local variable in a lambda body". My first instinct was to believe the compiler error and try and disambiguate it:

I should have listened to Intellisense.


fatal error C1001: An internal error has occurred in the compiler.
1>  (compiler file 'msc1.cpp', line 1420)
1>   To work around this problem, try simplifying or changing the program near the locations listed above.
1>  Please choose the Technical Support command on the Visual C++ 
1>   Help menu, or open the Technical Support help file for more information


I broke my compiler :(. Anyway, I suppose this is what happens when we try to point out a specific problem with a small example, we find new, different problems. We can solve this problem, and demonstrate what I really wanted to. Take that, lambda nesting! So what is the problem, I was trying to demonstrate? Well it's not necessarily safe for a mutex to be locked multiple times on the same thread, so if we want to support nesting of with blocks on the same resource we'd better make sure that's a recursive_mutex. Simple enough. Now, let's get to the real meat of the matter, the await statement. So above is the naive implementation of await. So what's wrong with it? Oops. It's not legal to wait if we don't have the lock. Well, that's fine, we're using a recursive_mutex now, we can fix this. Warning: notation abuse. There's still a problem here. It's unsatisfying from a correctness standpoint in at least two scenarios. Before your bug would do something weird, not it has a defined semantic, but it probably wasn't what you wanted. And now you can write this: The limitations of nesting lambdas is really making this uglier than I intended. What do we want? We want a version of await that we can only call in the right circumstances. We can of course check these things at runtime, and throw exceptions, but I'd much rather await not even mention the resource, in other words be impossible to be incorrect. Of course if we make await a free function we can do that, but then we're back to runtime detection in the case when we're not inside a block at all. This is the real problem I want to solve, and we'll look at some approaches next time.

Conditional Critical Regions

Hoare, in "Towards a Theory of Parallel Programming" describes something called a "conditional critical region", this is an expansion of an idea of Dijkstra's, called critical regions.

Briefly then, a critical region is a syntactic construct that looks something like:

         with r do C

where r is the name of the critical region or resource, and C is the statement to be executed without interference from any other such statements also executed under the auspices of with r. This is pretty much exactly the sort of thing we have in C# and Java with the lock and synchronized statements, respectively.

Stop me if I am going too fast. So what is a conditional critical region then? It, as Hoare described it originally adds a Boolean condition to which the critical region will not be entered until such time as the condition is or becomes true. It looks like

       with r when B do C

So if B is false, we block until it becomes true through the intervention of some other thread of execution. Java and C# do not have this construct. Instead they have a lower level mechanism, await and Monitor.Wait respectively. These are a little bit similar to an extension to condtional critical regions, the await statement.

      with r do 

         begin

                 C1

                 await B

                 C2

         end

After C1, if B is false, control of the region will be relinquished until B becomes true. Then C2 will be executed again with the resource held. The difference between this, and Java's await is that await in Java releases the critical region unconditionally, you have to check B yourself. Consequently, the correct way to write this in Java (or C#) looks like

      synchronized( r ) {

          C1

          while( ! B ) {

             r.await();

          }

          C2

     }

This is, as you can imagine a source of errors, commonly using if instead of while to test B. 

So that is what conditional critical regions are. I think that when and await are probably the appropriate level of abstraction and utility when compared to something like pthread-style condition variables or Java/C# monitors. So I would like to implement them in C++. When I started doing that I found myself facing a problem, which is actually going to be the focus of my next post (and will have nothing to do with concurrency at all really).