Generic Variance Part1 : Do you really need it ?

Posted Mon, Aug 11 2008 14:21 by bill

Lucian has kicked off the conversation on generic variance in VB , so I thought I’d write a few posts outlining my perspectives on the subject… the first of which is this one, and what better place to start than to question whether or not it is really needed……

Generics came to .NET after the base framework and languages were implemented.  It was very much a bolt-on approach.  As such there was and still is an impedance mismatch between conventional concepts of polymorphism and generics. As I posted previously, I had raised this is issue with Anders and other language experts back at the 2003 PDC (at which time Anders suggested using a language other than VB or C# <g>). Fast forward to today, and this issue is now being looked at, but now I find myself questioning if it is really needed, or is the fault the mismatch of the original framework. 

Let’s take Lucian’s example :

Dim args As New List(Of ConstantExpression)
args.Add(Expression.Constant(2))
args.Add(Expression.Constant(3))
Dim y = Expression.Call(instance, method, args)

 

This code fails because the Call method is defined as :

  

   Public Shared Function [Call](ByVal instance As Expression, _
                                 ByVal method As MethodInfo, _
                                 ByVal arguments As IEnumerable(Of Expression)) _
                                 As MethodCallExpression

 

But if it was defined as follows then the code would work:

  

   Public Shared Function [Call](Of T As Expression) _
                                (ByVal instance As Expression, _
                                 ByVal method As MethodInfo, _
                                 ByVal arguments As IEnumerable(Of T)) _
                                 As MethodCallExpression

 

 

So where exactly is the problem ?  The simple rule is if you want polymorphism (read as “generic variance”) in your code, then you need to expose the types as generic parameters not as concrete types.

That is, the above is solved by better API design and some simple refactoring.  This in fact solves 90% or more of all the cases I have seen.  The one place where you can’t do this is when the type is late bound and defined only as Object (more on this in a future post no doubt ;))

Filed under: , , , , ,

Comments

# re: Generic Variance Part1 : Do you really need it ?

Monday, August 11, 2008 3:12 AM by int19h

You've demonstrated covariance in action, but not contravariance. Now try declaring a method that takes any ICollection(Of T) such that an object of class Foo can be safely added to it, without the need of explicit casts.

# re: Generic Variance Part1 : Do you really need it ?

Monday, August 11, 2008 3:45 AM by bill

int19h ?? Is that really what your parents named you ? ;)

As to your question, T and Foo have ot have a common base for contravariance to work, let's call that FooBase.  So you have a method:

Sub Add(Of T as FooBase)(collection As ICollection(Of T))

 collaction.Add(new Foo)

# re: Generic Variance Part1 : Do you really need it ?

Monday, August 11, 2008 5:29 AM by int19h

Incorrect solution - ICollection<object> should also be acceptable (since you can Add(Foo) to it), but your solution does not allow for it. It should allow for ICollection of any type that is a base type of Foo (but should not allow for collection of any unrelated type). For comparison, in Java, the same thing looks like this:

 void Add(ICollection<? super Foo> collection)

 {

   collection.Add(new Foo());

 }

and works as intended - you can pass ICollection<FooBase> to it, or ICollection<Object>, but not ICollection<String> - so all typesafe versions are allowed, and all non-typesafe ones are forbidden.

Why is this needed? Well, let's say that we want to write a generic method that sorts an IList<T>, so long as T implements IComparable. First try (I'll use C# for brevity):

 void Sort(IList<T> list) where T:IComparable<T> { ... }

So far it looks good, but now consider this class hierarchy:

 class Base : IComparable<Base>

 {

    void CompareTo(Base other) { ... }

 }

 class Derived : Base { ... }

Note that Derived does not implement IComparable<Derived>; however, it does inherit IComparable<Base> from Base, and therefore you can compare any two instances of Derived (since every Derived is also a Base). It can be a perfectly valid operation, too, if Derived does not add any new fields, and only overrides a couple of methods - a rather common case. But now consider this:

 IList<Derived> list = new List<Derived>();

 Sort(list); // oops

Sort(list) is actually Sort<Derived>(list), so T=Derived here, and the constraint on T is that it must implement IComparable<T> - so we require that Derived implements IComparable<Derived> - and it doesn't! Note that this shouldn't really be a problem, because any two Derived objects can still be compared in a typesafe manner without any casts - it's just that we have overconstrained our method. Unfortunately, the only way to fix this is to use contravariance. In Java, the correct version would be:

 <T extends IComparable<? super T>> void Sort(IList<T>);

So we want an IList of T, where T has CompareTo() which takes an argument of type T, or any of the base classes of T. Now this will actually cover all valid cases. But, unfortunately, there is no way to write it in C# or VB.NET, and declaration-site contravariance won't be of any help here, either.

# re: Generic Variance Part1 : Do you really need it ?

Monday, August 11, 2008 9:16 AM by bill

Actually, you can write that various way in VB and in C# today, e.g:

<T extends IComparable<? super T>> void Sort(IList<T>);

can be written as :

  Sub Sort(Of T As TBase, TBase As IComparable(Of TBase))(ByVal list As IList(Of T))

or:

   void Sort<T, TBase>(IList<T> list)

        where T:TBase

        where TBase:IComparable<TBase>  

It's not as pretty but is the same thing.  today VB.NET and C# can't infer the generic parameters for that though.  That of course may cause problems in some situations when you don't know what actually implements the IComparable(Of t)

In reality though, (apart from the fact List has Sort already), if you want to sort an IList(Of T), I'd expect an overlaod that allows a Comparer(Of T), and you'd call that passing it a Function such as Function(x,y) x.CompareTo(y)

eg:

 Sub Sort(Of T)(ByVal list As IList(Of T), ByVal comparer As Comparison(Of T))

and call that using:

Sort(list, Function(x, y) x.CompareTo(y))

That'd be a more functional approach that would allow for greater flexibility.

That being said, you are right in regards to the ICollection(Of T).Add.  In fact the code I posted in the comment above doesn't work at all.  I think that highlights how this isn't a usual requirement.  And as you noted, having the variance specified on the type defintion won't address that either

# re: Generic Variance Part1 : Do you really need it ?

Monday, August 11, 2008 10:02 AM by int19h

> It's not as pretty but is the same thing.  today VB.NET and C# can't infer the generic parameters for that though.

Yes, which pretty much kills the approach on the spot.

> In reality though, (apart from the fact List has Sort already)

List does, but IList doesn't (and there are plenty collections out there which are not the former, but which do implement the latter).

> if you want to sort an IList(Of T), I'd expect an overlaod that allows a Comparer(Of T), and you'd call that passing it a Function such as Function(x,y) x.CompareTo(y)

I agree, but I would also expect an overload which would use the built-in comparison capability of the type itself so long as it is available.

Anyway, it was intended as a more real-world example of where variance is useful, not a specific problem to solve. I'm sure there are more similar cases that can be thought of with some effort.

> I think that highlights how this isn't a usual requirement.

I would dare say that it is not a usual requirement because people aren't trained to think of it as such - but in pursuit of more type safety (and less failure-prone explicit casts), it is a requirement nonetheless.