Covariant return types in C# and how to not to carefully change a library

C# doesn't allow covariant return types in interface method implementations. Briefly

class A { }
class B : A { }

interface I
{
   A M();
}

class C : I
{
   B M() { ... }
}

will not compile. class C's implementation of M must return A. In Java and C++ (with the appropriate syntactic changes) the original code will have worked as written.

I'm not going to argue strongly one way or the other for the feature of covariant return types in C#, but it's absence illuminated a corner of the pitfalls of evolving a library that don't think I would have noticed otherwise.

To set the stage I will go through the abstract evolution of a library and a client.

First the library (or framework really) appeared:

interface I { ... }
abstract class Base {
   I GetI() { ... }
  ...
}

Base has various methods intended to be overridden by clients, and its all documented as you would expect.

Then a client appears

class Client : Base {
   ...
}

The client code works happily. The library evolves some, specificly, GetI changes to return a richer object. In the library:

interface I2 : I {
  ...
}

abstract class Base {
   I2 GetI() { ... }
}

The client code continues to work happily, the values returned from GetI still do all the I things they did before, they just happen to do more. After some time the client changes again:

interface IBase {
   I2 GetI();
   ...
}

class Client : Base, IBase {
    ...
}

Some important things to note. IBase is defined in the _client_ it does not exist in the library, it was not introduced by the library, the client code just extracted it out of some of the methods on Base. This is fine, client code is allowed to create interfaces after all. The other important thing to do note is that the client does implement IBase in the body of the Client class. Rather it simply lets the implementation of Base.GetI serve as the implementation of IBase.GetI. The client has other classes that do not inherit from Base and implement IBase, i.o.w. this was not done just to have some extra code lying around. The client is "borrowing" some of the abstractions of the framework. This was down to allow reuse of the client code in contexts where the framework of the library was not being used. I mention these reasons not to have a debate about the design of the client but merely to emphasize that their was a real reason for this.

The library now changes again, once again adding more functionality to the object returned from GetI().

interface I3 : I2 {
  ...
}

class Base {
   I3 GetI() { .... }
   ...
}

This time however, this change actually breaks the compilation of the client. Because the Client class is no longer implementing IBase. IBase was created in the client, the class Client was created in the client, but the client code effectively imposed a responsibility on the library code of implementing IBase, which it no longer does.

I find this to be fascinating situation. Each individual change on the part of the library was done in a way that was mindful of not breaking consumers. Likewise it is hard to say the client code did anything wrong. Is this a flaw in the language? If so is the flaw simply not supporting covariant return types? Or is it that base classes are allowed to implicitly interfaces? Or is it that the library is actually wrong, that changing the return type of a public method, even if it's a subtype of the previous version of the method? I'm not sure what the correct answer is, but I don't think the answer is as simple as "C# should support covariant return types", because it seems to me this fixes this problem by accident. As far as I can tell the writer of IBase wasn't thinking "C# has covariant return types so library can still evolve GetI and likewise the writer of Base was not thinking "someone may write an interface and use us to implement it by simply inheriting, but that's ok because C# has covariant return types." The writer of Base was certainly thinking in terms of the LSP when they changed the return type of GetI, granted.

At the end of the day this was fixed by the client simply explicitly implementing IBase.GetI, something like:

class Client : Base, IBase {
    I2 Ibase.GetI() { return GetI(); }
}

This is unsatisfying for the obvious reasons of the library went out of its way to ensure clients wouldn't have to change, and they ended up having to anyway.

It is clear that "obey LSP" is not a sufficient principle for determining how to perform backwards compatible library changes. So here are some guidelines about what can and cannot be done in a backwards compatible manner.

First, there is a minimum of one convention that can't be checked by the compiler unfortunately. That is, the library's namespace is the library's namespace. Many of the suggestions I am going to make rely on that. Fortunately this should not be too onerous on client code, and this is generally accepted as an unwritten rule anyway. I am making it explicit here because the entire impetus for this a seemingly backwards compatible change that actually relied on some fairly intricate unwritten rules.

I will use the term "member" below to refer to both methods and  variables.

1) Prefer sealed classes. A sealed class can't be inherited from, so you may add new members to it with impunity.
2) In all classes never remove public members. This I hope is obvious.
3) In non-sealed classes never remove protected members. A protected member is effectively public to any sub class.
4) Never change the signature of a public method, even if the changes would satisfy LSP. The preceding explains why sufficiently I hope.
5) The addition of new members in a non-sealed class must be accompanied by the addition of a new type in the library's namespace, to scope them properly. This is because names from the base class are visible in sub classes, and sub classes may have already used those names. Since the names of the members themselves can't be scoped to the namespace, we take advantage of a type. This can be done in two ways:

Introduce a new subclass:

class Base { ... }
class BaseWithX : Base { MemberType newMember; ... }

Existing client subclasses will only subclass existing subclasses of Base, and so can continue to use their own newMember if they happen to have  a member named that. If they want to take advantage of newMember they have to actively change their code, inheriting from BaseWithX, at which point they will be forced to deal with the ambiguity. If they don't touch their code, this change can't impact them.

Introduce a new type (probably an enum) that serves purely to separate client overloads from library overloads

enum GetI3E { Value };

class Base
{
     I2 GetI() { ... }
     I3 GetI(GetI3E e) { ... }
}
While clients may use a name you want to use for a method in a future release, they can't use a type that's in your library's namespace that doesn't exist yet. This allows the overloading mechanism to avoid you stepping on each other's toes. Note that you cannot reuse these types for different releases, once the client has access to the type they can use it in their own overloads, so new members in new releases must come with their new types.

If these guidelines are followed it is pretty difficult to break a client inadvertently, and with the exception of (1) it should be possible to follow them for C++ as well (or with an additional written rule that classes with no virtual methods shall not be inherited from). Next time though, GetI is just going to return a sealed class instead of an interface.

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).

I did Two Shoes Weekend II: The Shoesening

Two Shoes Weekend is an event put on by my friend Casey. The basic idea is that you do two projects (two shoes if you will) over a weekend. It is inspired by Shoes, which is a _why the Lucky Stiff thing, but you don't have to use Shoes. This is the second run of two shoes weekend. Last time I almost did something, but I got distracted. At the time, I was using Vista (mock my operating system all you want, it's not germane to story time), and the Windows version of shoes had some issues there. Specifically, the background of the window was an inky black darkness, impervious to light. You could "fix" this problem by lying to Shoes, and saying you were XP. Unfortunately, this triggered the Vista bug that the code that created the inky blackness was designed to avoid, an abominable amount of flickering that would give you a headache. Part of my day job involves wrangling GDI and windows so I started to take a look at the code. I didn't really accomplish anything by doing this, and the weekend largely ended with me having little to nothing to show for it.

This year, I decided to avoid that whole class of problem by making one of my shoes shoes itself. More specifically, I took one part IronRuby, and one part WPF and whipped up a reasonable facisimle of Shoes. It has the "advantage" of being pure ruby since the IronRuby guys did all the work of binding ruby to the CLR for me, and the WPF guys did all the hard work of implementing the moral equivalent of "slots" for me. I took a rather haphazard approach though, basically implementing the bits that were needed for some initial sample projects. It wasn't until relatively late in the weekend that I actually started going through the manual and adding the features in the right way. It will probably never replace real Shoes for Shoes use case, for one thing you have to install IronRuby to run it, but it is sort of interesting for slapping a GUI on to some existing .NET functionality perhaps. Shoes seems remarkably well-suited for being implemented in WPF, stack might as well be a StackPanel, and flow might as well be a WrapPanel, and that's what I did really. WPF's pervasive tendency to use URIs might things like image "http://thing.png" worked with almost no effort on my part.

My second shoe was pretty boring, but I felt compelled to do two. I made a "lonely blog", aka a diary. It displays a stream of text and images that it saves/loads from a local file on your computer. It looks like this:

You enter either image urls or commentary and click the appropriate button. The save button saves the blog, and the entries will appear the next time you load it.

All in all, a fun time. I haven't done anything in Ruby in a while so that was fun. The code for the WPF/IronRuby shoes work-a-like is here, and the lonelyblog shoes app is here.

Lambda didn't (or won't) kill the expression template star

Now that C++0x is on it's way, and many compilers already implement lambdas, it may be thought that the venerable "functor" is on it's way out. Well aside from the obvious reasons of supporting legacy code, that's simply not true. operator() is here to stay, and I will tell you why.

Lambdas, though convenient, are opaque. You can't peek inside of a lambda or peel back it's inner workings, and the vast majority of the time, that's fine, you don't need to. The same is true for normal named functions and member functions. On occasion however, a slightly more transparent tool can be useful, and operator() can help you build such translucent functions.

Let me try to justify this with an example. LLVM is a library for building compiler backends. It is written in C++, and it happens to have a coding standards document. One of the style points is "Turn Predicate Loops into Predicate Functions".

Basically, instead of code like

bool pred = false;
for(unsigned i = 0; i < list.size(); ++i)
{
  if( list[i].satisfies() )
  {
     pred = true;
     break;
  }
}

if( pred )
{
  ...
}

You should have code like

if( TestPred(list) )
{
  ...
}

They have their justifications, which you can read if you're interested. This really isn't about whether this is a good idea or not, but rather how to write TestPred. There is an obvious approach:

bool TestPred(const std::vector<Something>& list)
{
  for(unsigned i = 0; i < list.size(); ++i)
  {
    if( list[i].satisfies() ) return true;
  }
  return false;
}

The problem with this, is that you can't reuse the predicate. Or rather, that you can, but only in a very specific way. If you need to test a std::list of Something instead you need to either copy the list or duplicate the code. Worse, if you don't know what the code is, you don't even have duplication as an option.

A brief aside, yes a solution to this mess would be to just use std::find_if in the first place. This is just however the motivating example that came to mind when I happened to be reading the LLVM coding guidelines, so bear with me.

So we can change TestPred to operate on iterators. Now we can use it with list, vector, etc.

template <typename FwdIter>
bool TestPred(FwdIter begin, FwdIter end)
{
  for(FwdIter i = begin; i != end; ++i)
  {
    if( i->satisfies() ) return true;
  }
  return false;
  // or return find_if(begin, end, [](const Something& s) { return s.satisfies(); }) != end
}

But before we had the nice feature of being able to call this on a std::vector directly. We could add overloads for that, but that gets tedious especially since we're writing one of these functions every time we have a new predicate we need to loop over. We can use templates to let us get that std::vector overload back (and more, std::list for example, and your plain old array) by writing the code for iteration once and plugging in the varying i->satisfies part.

template<typename F>
struct RangedAnyPredicate
{
 typedef F Tester;
 template<typename FwdIter>
   bool operator()(FwdIter begin, FwdIter end) const
   {
     for(FwdIter i = begin; i != end; ++i)
     {
       if(F::test(*i))
       {
         return true;
       }
     }
     return false;
   }
};

struct satisfier
{
 typedef const Something& testee_type;
 static bool test(const Something& s)
 {
   return s.satifies();
 }
};

static RangedAnyPredicate<satisfier> TestPred;

Here we've extracted out just the looping over part. TestPred will behave almost identically to our templated on a pair of iterators version of the function (exceptions being things like, we can't pass this TestPred around as a function pointer). This is more typing that previous version of course, even with multiple predicates the overhead of a struct for each one is high. Where it starts to pay dividends is when provide more overloads for free. We're going to need some traits to do that, and again while this is a bunch of code up front, some of these traits are independently useful and already exist.

We want to be able to call this on two iterators, on a container with begin and end methods, and on a standard array. We can distinguish between the two argument and single argument forms easily with the normal overloading mechanism. For distinguishing between containers with begin and end and standard arrays we'll assume anything not an array should have a begin and an end.

So to detect arrays will use an is_array trait:

template<typename T>
struct is_array
{ enum {val = false}; };

template<typename T, long N>
struct is_array<T [N]>
{ enum {val = true}; };

We can then use this information to decide to either call TestPred(arg.begin(), arg.end()) or TestPred(arg, arg + N).

 template<bool C>
    struct do_test;

    template<>
    struct do_test<true>
    {
       template <typename Self, typename T, int N>
       static bool go(const Self& self, T (&a)[N])
       {
         return self(a, a + N);
       }
   };

   template<>
   struct do_test<false>
   {
     template<typename Self, typename C>
     static bool go(const Self& self, const C& c)
     {
       return self(c.begin(), c.end());
     }
   };

   ...
   // back inside RangedAnyPredicate
    template<typename Container>
    bool operator()(const Container& c) const
    {
      return do_test<is_array<Container>::val>::go(*this, c);
    }
   ...

Now we've got overloads for vector, list, and any other container that might come along and behave like a standard sequence, as well as old fashioned arrays.

But there's more. You may have noticed we included a Tester typedef in RangedAnyPredicate. This is where the ability to make a functor less opaque than a regular function or a lambda starts to be useful. Let's say we have two predicates, PredA and PredB. And furthermore the coding guidelines were followed and we have TestPredA and TestPredB functions to work with. If we want to find out if a list has an eliminate that satisfies PredA or PredB we can do the obvious:

if( TestPredA(list) || TestPredB(list) )
{
   ...
}

But this is C++! The code above has the potential to needlessly traverse the list twice. We've got to be able to do something about that, right? Well not if TestPredA and TestPredB are regular functions. We can write a third function that does the or-ing, but it can't peek inside the functions. If however, we use RangedAnyPredicate to define TestPredA and TestPredB we can extend them as needed. First will need a predicate to represent the or-ing of the internal predicates of A and B:

template
struct OrCombiner
{
  typedef typename Lhs::testee_type testee_type;
  static bool test(testee_type testee)
  {
    return Lhs::test(testee) || Rhs::test(testee);
  }
};

Next we use a little operator-overloading-fu in RangedAnyPredicate to make this easy to use:

// Back in RangedAnyPredicate
template<typename TestF>
    RangedAnyPredicate< OrCombiner<F, TestF> > operator|(RangedAnyPredicate  )
    {
      return RangedAnyPredicate< OrCombiner<F, TestF> >();
    }

Now our code becomes

if( (TestPredA | TestPredB)(list) )
{
   ...
}

and only one pass is made over the list. If you want different semantics, of course you can just simply use the prior code. The same can be done for logical and as well of course.

This was of course a contrived example, but I hope of demonstrated how the functor still has its place, even in a world of lambdas.