Freigeben über

Covariance and Contravariance In C#, Part Five: Higher Order Functions Hurt My Brain

  • Artikel

Last time I discussed how we could in a hypothetical future version of C# allow delegate types to be covariant in their return type and contravariant in their formal parameter types. For example, we could have a contravariant action delegate:

delegate void Action< -A > (A a);

and then have

Action<Animal> action1 = (Animal a)=>{ Console.WriteLine(a.LatinName); };
Action<Giraffe> action2 = action1;

Because action2’s caller will always pass in something that action1 can handle.

Based on my discussion so far, I hope that you have a strong intuition that the normal, sensible use of variance is “stuff going ‘in’ may be contravariant, stuff going ‘out’ may be covariant”. Though I believe that would be the most common use of variance were we to enable this feature in a hypothetical future version of C#, the real situation would actually be rather more complicated than that. There is a situation where it is legal to use a covariant parameter in the formal parameter of a delegate. Doing so makes my brain hurt, but this also builds character, so here we go!

Suppose you want to do "higher order" functional programming. For example, perhaps you want to define a meta-action – a delegate which takes actions and does something with them:

delegate void Meta<A> (Action<A> action);

for example,

Meta<Mammal> meta1 = (Action<Mammal> action)=>{action(new Giraffe());};
// The next line is legal because Action<Animal> is smaller than Action<Mammal>;
// remember, Action is contravariant
meta1(action1);

So this Meta thing takes an Action on Mammals – say, action1 above, which prints the Latin name of any Animal, and therefore can do so to any Mammal – and then invokes that action on a new Giraffe.

Clearly the type parameter A is used in an input position in the definition of Meta<A>, so we should be able to make it contravariant, right? Suppose we did so. That would mean that this assignment would be legal:

Meta<Tiger> meta2 = meta1; // would be legal if Meta were contravariant in its parameter

But that means that this would then be legal:

Action<Tiger> action3 = tiger=>{ tiger.Growl(); };
meta2(action3);

Follow the logic through and you’ll see that we end up calling (new Giraffe()).Growl(), which is clearly a violation of both the type system and of nature’s laws.

Thus Meta<A> cannot be contravariant in A. It can however be covariant:

Meta<Animal> meta3 = meta1; // legal if Meta were covariant

Now everything works. meta3 takes an Action on Animals and passes a Giraffe to that Action. We’re all good.

Contravariance is tricky; the fact that it reverses the bigger/smaller relationship between types means that a type parameter used in a "doubly contravariant" position (being an input of Action, which is itself an input of Meta) becomes covariant. The second reversal undoes the first.

We do not expect that most people will use variance in this manner; rather, we expect that people will almost always use covariant parameters in output positions and contravariant parameters in input positions. As we’ll see a bit later in this series, whether this expectation is reasonable or not would influence the syntax we might choose were we to add variance to a hypothetical future version of C#.

Next time: we’ll leave delegates behind and talk about variance in interfaces.

Comments

  • Anonymous
    October 24, 2007
    Meta<A> is the same thing as Action<Action<A>> ie Action<- Action<- A>> so it is covariant in A

  • Anonymous
    October 24, 2007
    Honestly, I'd be happy just having support for covariant return types for method and property overrides :). e.g. "public virtual Animal MyProperty { ... }" could get overridden by "public override Giraffe MyProperty { ... }"

  • Anonymous
    October 24, 2007
    Yeah, I'm getting that feedback a lot. I'll take it to the design committee again.

  • Anonymous
    October 24, 2007
    Amen to mstrobel! Also (not strictly related but similar) the ability to override a readonly property with a readwrite one.

  • Anonymous
    October 24, 2007
    and they still tell me that an equivalent for ldtoken of type members would be too complicated to implement in any two-digit C# version ;-) variance in interfaces sounds like fun. for colleciton types we could separate immutable interfaces, so collection types wouldn't have to be as broken as arrays. like this: IList<T>, but IEnumerable<+T>; and Collection<T> could implement both. hypothetically, I'd like to see that work... but then again, mstrobel does have a point here.

  • Anonymous
    October 24, 2007
    The comment has been removed

  • Anonymous
    October 24, 2007
    static void Do<T>(HierarchyNode<T> arg) where T : HierarchyNode<T> This looks wonderfully recursive, if a bit over the top (you just need to specify HierarchyNode<> once). Too bad that the really interesting cases of recursive generics don't work (e.g. variadic generics, but since we're talking about a hypothetic future version of C#, Eric, how about those? christmas is not too far away anyhow!)

  • Anonymous
    October 24, 2007
    That always makes my brain hurt as well. It is possible to create a generic type definition which causes the CLR to go into an infinite regress of expansion -- the CLR actually has a check to see how many times it has expanded a particular generic type and it bails out after a certain threshhold, rather than attempting to detect all the pathological cases analytically. And I wouldn't expect to see generic types with a variable number of arguments any time soon -- though I agree, it would make Func, Action, Tuplle, etc, much easier to define and use

  • Anonymous
    October 24, 2007
    The comment has been removed

  • Anonymous
    October 24, 2007
    er, in the above example, MyDerivedClass should derive from MyBaseClass, though I neglected to code it that way ;).

  • Anonymous
    October 24, 2007
    Stefan, I'm afraid that leaving out the T constraint isn't a viable solution as it makes the C# compiler complain with the following error (shortened before posting here): "The type 'T' cannot be used as type parameter 'T' in the generic type or method 'HierarchyNode<T>'. There is no boxing conversion or type parameter conversion from 'T' to 'Node'." The "smallest" constraint for compilation of the generic method is the following: static void Do<T>(HierarchyNode<T> arg) where T : Node instead of: static void Do<T>(HierarchyNode<T> arg) where T : HierarchyNode<T> Perhaps Eric can shred some light on this particular case. Again, I'd much rather implement this with overriden members returning richer typers (as seen in the previous messages).

  • Anonymous
    October 24, 2007
    I Nth the request for the simpler but more useful to the wider world covariant return on virtual methods. The brain bending caused by this series is sufficient to make me think that it will cause more confusion than it saves. syntactic sugar for the delegate casting would be nice too... Fun series though :)

  • Anonymous
    October 24, 2007
    Today there is no delegate casting possible because of lack of contravariance of Action<T>. You need to at least build a new Action<Giraffe> from the Action<Animal>, which allocates memory, and even then calling Delegate.CreateDelegate(tyepof(Action<Giraffe>), action1.Target, action1.Method) does not work in all cases (when the delegate has been built from a DynamicMethod). So you can only build a delegate calling the other one, which must have a performance penalty. Contravariance of Action<T> would even suppress the need to allocate new memory. The CLR is supporting that since version 2 exists, what we lack is Framework and language support for an existing feature.

  • Anonymous
    October 25, 2007
    Anders, I don't know about your C# compiler, but mine likes this enough to compile it without complaining:    static void Do<T> (HierarchyNode<T> arg)    {      Console.WriteLine (typeof(T).FullName);      T t = arg.Parent;    }    Do (new Page()); and we're talking about my aged C# 2.0 compiler here... (I would never have dared to make such a statement without a test! after all, this is about slightly recursive generic constructs.)

  • Anonymous
    October 25, 2007
    Seems pretty obvious to me. Given: delegate void Action< -A > (A a); delegate void Meta<A> (Action<A> action); Then (using A<B to mean B-can-be-assigned-to-A): A < B => Action<A> > Action<B> => Meta<A> < Meta<B>. So the argument to Meta is covariant.

  • Anonymous
    October 25, 2007
    > Seems pretty obvious to me. That's probably because you're smarter than me. > Then (using A<B to mean B-can-be-assigned-to-A): Your logic is exactly correct, but your choice of notation is unfortunate, as I have defined "A is smaller than B" to mean "A is assignable to a variable of type B".  

  • Anonymous
    October 25, 2007
    With the current Framework implementation of the Delegate class, you can not combine (with the Combine method or the + operator) two delegates of different types, so you would not be able to combine an Action<Animal> and an Action<Giraffe> even if it would produce a valid Action<Giraffe>. You would need a change in Framework anyway, even as the CLR already handles contravariant delegates.

  • Anonymous
    August 10, 2008
    Just checked and according to https://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=90909 more than 240 people have votes covariant return types to 4,7 (where 5 is the most important value). I think the C# team (and the CLR team) should take a moment and reflect on this signal from the community. It's not like people are voting for fun ..

  • Anonymous
    December 18, 2008
    So nicely step by step blogged by Eric Lippert for &quot;Covariance and Contravariance&quot; as &quot;Fabulous