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

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

Rate This
  • Comments 19

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.

  • Meta<A> is the same thing as Action<Action<A>> ie Action<- Action<- A>> so it is covariant in A

  • 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 { ... }"

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

  • Amen to mstrobel!

    Also (not strictly related but similar) the ability to override a readonly property with a readwrite one.

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

  • Eric, thanks for writing a great series on the "variance" story. It's really interesting stuff you're presenting.

    ..

    I definitely second the comment on covariant return types for method and property overrides. It's a quite common use to provide richer return types and it leads to code bloat (casting returned object to concrete subclass type).

    Eric, please take this request to the design committe again. It's a much needed feature.

    Here's a really quick example of what I'm asking for (just to make sure we're on the same page). I'm looking at defining a common hierarchical base class and implement concrete types that overrides the graph members (Parent, ChildNodes) with richer type (i.e. want to return (and expose) Page as Parent instead of the inherited type):

    abstract class HierarchyNode

    {

      abstract HierarchyNode Parent { get; internal set; }

    }

    sealed class Page : HierarchyNode

    {

      // fully complies with the interface of 'Parent' but is invalid code as of C# 3.0 in VS 2008 beta 2

      override Page Parent { get; internal set; }

    }

    If I don't have this feature, I'd have to cast Page.Parent to the concrete type whenever I want to access the richer interface (which is the common requirement).

    One way I tried to come around this requirement is to use generic baseclasses (but that approach was abandoned because of coveriance problems). Here's a sample implementation:

    abstract class HierarchyNode<T>

    {

      abstract HierarchyNode Parent { get; internal set; }

    }

    sealed class Page : HierarchyNode<Page>

    {

      override Page Parent { get; internal set; }

    }

    static void Do<T>(HierarchyNode<T> arg) where T : HierarchyNode<T>

    {

      // do something with arg

    }

    Kind of ugly compared to the much cleaner implementation possible with the richer return types. If you're supposed to implement methods that operate on the (generic) base types (which too is a common requirement in good OO abstracted design), life becomes really complex and verbose as exemplified above.

    Another approach would be to provide a "new" member, but that approach hides the type of the base class.

    It all makes sense. Ensure that overridden members adhere to the base contract and allow richer types be returned.

    I really really really hope this feature makes in C# 3.0. What are your comments on the above?

    Thanks in advance

    Anders Borum / SphereWorks

  • 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!)

  • 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

  • Hey Eric, if you're going to take return type covariance to the design committee, I have an extra point for them to take into consideration.  Since return type covariance isn't currently supported in C#, I would get around it by doing member hiding like so:

    public class MyBaseClass

    {

       public Animal MyProperty { get; set; }

    }

    public class MyDerivedClass

    {

       public new Giraffe MyProperty

       {

           get { return base.MyProperty as Giraffe; }

           set { base.MyProperty = value; }

       }

    }

    This as always worked fine for me, until I tried to bind to such a property in XAML:

    <ContentPresenter Content="{Binding Path=MyProperty}"/>

    Runtime exception!  The WPF databinding engine can't figure out which property to use.  A seasoned WPF developer might be able to figure out that you can get around it by qualifying the declaring type:

    <ContentPresenter Content="{Binding Path=(local:MyBaseClass.MyProperty)}"/>

    -or-

    <ContentPresenter Content="{Binding Path=(local:MyDerivedClass.MyProperty)}"/>

    However, a lot of developers might get stuck on that issue.  Just thought I'd throw that out there, as covariance in method/property overrides would negate the need for member hiding in this case, and thus avoid those nasty data binding runtime exceptions.

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

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

  • 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 :)

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

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

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

Page 1 of 2 (19 items) 12