Covariance and Contravariance in C# Part Seven: Why Do We Need A Syntax At All?

Covariance and Contravariance in C# Part Seven: Why Do We Need A Syntax At All?

Rate This
  • Comments 21

Suppose we were to implement generic interface and delegate variance in a hypothetical future version of C#. What, hypothetically, would the syntax look like? There are a bunch of options that we could hypothetically consider.

Before I get into options though, let’s be bold. What about “no syntax at all”? That is why not just infer variance on behalf of the user such that everything magically just works?

Unfortunately this doesn’t fly, for several reasons.

First, it seems to me that variance ought to be something that you deliberately design into your interface or delegate. Making it just start happening with no control by the user works against that goal, and also can introduce breaking changes. (More on those in a later post!)

Doing so automagically also means that as the development process goes on and methods are added to interfaces, the variance of the interface may change unexpectedly. This could introduce unexpected and far-reaching changes elsewhere in the program.

Second, attempting to do so introduces a new kind of cycle to the language analysis. We already have to detect things like cycles in base classes, cycles in base interfaces and cycles in generic type constraints, so this is in theory nothing new. But in practice, there are some issues.

In my previous post I did not discuss what additional restrictions we’d need to put on variant interfaces; one important restriction is that a variant interface which inherits from another variant interface must do so in a manner which does not introduce problems in the type system. Basically, all the rules for when a type parameter can be covariant or contravariant need to "flow through" to base interfaces. (This is vague, I know. I have a precise formal definition of what all the rules are which I may post at a later date. The exact rules are not important for the purposes of this discussion.)

For example, suppose the compiler was trying to deduce variance in this program:

interface IFrob<T> : IBlah<T> { }
interface IBlah<U> {
  IFrob<U> Frob();
}

We might ask ourselves “is it legal for T to be variant in IFrob<T>?” To answer that question, we need to determine whether it is legal for U to be variant in IBlah. To answer that question we need to know whether it is legal for U to be variant in output type IFrob<U>, and hey, we’re back where we started!

I would rather the compiler not go into an infinite loop when given this program. But clearly this is a perfectly legal program. When we detect a cycle in base classes, we can throw up our hands and say "you've got an illegal program". We cannot do that here. That complicates matters.

Third, even if we could figure out a way to solve the cycle problem, we would still have a problem with the case above. Namely, there are three possible logically consistent answers: “both invariant”, “+T, +U” and “-T, -U” all produce programs which would be typesafe. How would we choose?

We could get into even worse situations:

interface IRezrov<V, W> {
  IRezrov<V, W> Rezrov(IRezrov<W, V> x);
}

In this crazy interface we can deduce that “both invariant”, “ <+V, -W> and <-V, +W> are all possibilities. Again, how to choose?

And fourth, even if we could solve all those problems, I suspect that the performance of such an algorithm would be potentially very bad. This has “exponential growth” written all over it. We have other exponential algorithms in the compiler, but I'd rather not add any more if we can avoid it.

Thus, if we do add interface and delegate variance in some hypothetical future version of C#, we will provide a syntax for it. Next time, some ideas on what that syntax could look like. (If you have bright ideas yourself, feel free to post them in comments!)

  • I see the logical issues involved with inference.

    The token is an explicit statement of intent which greatly reduces the scope of the problem - now you can tell the developer that their program is illegal.

    Also, I like the variance token as a suffix; it reads like a property of the type parameter instead of an operator.

  • I would prefer a suffix as well, though that does present a minor problem, as "interface IFoo<T->" would be lexed as INTERFACE ID LEFTANGLE ID ARROW.  We'd have to do some minor surgery to the lexical grammar to make it work out.

  • How about a syntax like:

    interface I<:U, V:> {

     U f(V);

    }

    Here, :T means covariant (a visual reminder of 'is derived from T'), and T: means contravariant (a visual reminder of 'derives from T'). It's not perfect, because derivation isn't the relationship we're capturing, but given:

    class A {}

    class B : A {}

    interface I<:U, V:> { U f(V); }

    It seems reasonable that this is OK:

    class C : I<A, B> { B f(A); }

  • Indeed, that is one of the syntaxes I will discuss next time, and the downside of it is exactly as you state.  I would rather not further overburden the notion of "derivation". But it is a nice visual. (We were thinking of *:T, U:*, which is even more visually striking.)

  • I occasionally use variance at the IL level and am rather accustomed to the +- notation.

    I think it would do just as well in C#.

  • Is it a bad idea to allow variance where deduceable and disallow it where it's ambiguous? Perhaps it means that changing an interface would make the new version incompatible with the old version.

  • instead of an operator why not an attribute.

    [Variance(V=covariant,W=contravariant)]

    interface M<V, W> {

    }

    i've got to be honest in that i find this whole thing quite confusing. (compilable examples obviously help...) but i think that an attribute-based system will be more readable.

    it also seems a little more appropriate, imho.

    also, it obviously trivialises the job to integrate this into the 'hypothetical' language.

  • The attribute idea is an interesting one. I do prefer the more verbose syntax such things provide (You read and edit a class/interface many many more times than you write one) but appreciate it might make life harder for the compiler.

    It also brings up the question of how such variance is expressed within the reflection system...

    Making the attribute handle each iof the generic types could require some nasty hacks or etxtual code which could be messy. An alternate is to extend attribute locations to allow them to be placed on each generic type

    e.g.

    class Foo< [Variance(Variances.Covariant)] U, [Variance(Variances.Contravariant)] V>

    {

    }

    I don't like how needlessly verbose this is though. Perhaps

    class Foo< [Covariant] U, [Contravariant] V>

    {

    }

    Which is two attributes but rather more readable (if a type is both add both).

    Of course what happens if you apply the attributes within a language which doesn't support it :(

  • > Is it a bad idea to allow variance where deduceable and disallow it where it's ambiguous?

    If we disallow it when it is ambiguous then what do we do for the customer who wants variance, knows what variance they want, and has an ambiguous interface?  That will be a very common case since ambiguities are easy to make. We have to provide a syntax for that case so that the user can disambiguate explicitly.  

    We would also want to provide a syntax for "no variance" that differed from "deduce variance".

    Both facts speak to the need for variance to be always explicit, never inferred.

  • > how such variance is expressed within the reflection system

    That's easy to answer. See http://msdn2.microsoft.com/en-us/library/system.reflection.genericparameterattributes.aspx for details.

  • > what happens if you apply the attributes within a language which doesn't support it

    Then that language probably ignores the attributes as it always has.

    Remember, variance as I am characterising it here is an extension to the assignability rules. A language implementer may choose to implement whatever assignability rules they want. C# 3.0 presently ignores the variance bits in Reflection; the feature I am proposing in this series would make some future C# start paying attention to those bits and allowing certain assignments which are presently illegal.

  • How about extending the existing generic constraint syntax?

    class Foo<T> where T: class, covariant, IBar

    {

    ...

    }

  • Welcome to the thirty-fifth edition of Community Convergence. We have an interesting and controversial

  • What do you mean by cycles?

    Like here: "When we detect a cycle in base classes, we can throw..."

    I am brazillian and dont undestand very well...

    I can say that I'm your fan, and I think the articles of the blog incredible.  I would like your permission to translate them, we do not have anything like that in Portuguese, would be of great help to the community

  • By "cycles in base classes" I mean a situation such as:

    class A : B {}  

    class B : C {}

    class C : D {}

    class D : A {}

    That's not a legal class hierarchy. There is no way to eventually get to object as the base type.

    Similarly, it's not legal to have

    class C<T, U>

    where T : U

    where U : T

    And similarly with interface "inheritance".

    Glad you like the blog!

Page 1 of 2 (21 items) 12