Variance and Generalized Constraints for C# Generics

Variance and Generalized Constraints for C# Generics. Burak Emir, Andrew J. Kennedy, Claudio Russo, Dachuan Yu. July 2006

Generic types in C# behave invariantly with respect to sub-typing. We propose a system of type-safe variance for C# that supports the declaration of covariant and contravariant type parameters on generic types. To support more widespread application of variance we also generalize the existing constraint mechanism with arbitrary subtype assertions on classes and methods. This extension is useful even in the absence of variance, and subsumes equational constraints proposed for Generalized Algebraic Data Types (GADTs). We formalize the subtype relation in both declarative and syntax-directed style, and describe and prove the correctness of algorithms for constraint closure and subtyping. Finally, we formalize and prove a type safety theorem for a featherweight language with variant classes and generalized constraints.

Discussion of previous C# GADT paper on LtU.

I am unsure about use-site versus definition-site variance declerations. It would be interesting to hear what others think.

Also check out the LtU discussion on wildcards in Java.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Comments, anyone?

Comments, anyone?

Although I think it's great work,,,

...my only criticism is at the syntactical (and somewhat superficial) level. I really think that overloading + and - with yet another semantic meaning, is not the route I would have chosen. But then, this is probably more a call for introducing more symbols into the PL world, or at least using a more verbose syntax.

Java almost used +/-

The papers and (I believe) early prototypes for generics in Java used +/- symbols. Though I liked them, there were people who didn't and so it was eventually changed to the ridiculously verbose (? extends X). I suppose the verbosity would be less of a problem if Java had local type inference...

Scala uses +/- and I think it's pretty easy to get used to.

Or typedefs

"I suppose the verbosity would be less of a problem if Java had local type inference..."

Typedefs would be enough.

OCaml uses +/- as well for

OCaml uses +/- as well for variance notations.

Interesting.

I guess variance and constraints are important for library writers: it allows them to finetune their libraries so as that type violations are minimal. From a user's perspective, I doubt it will make much of a difference. Maybe catching a few bugs here and there.

I also agree with Chris Rathman about the usage of symbols + and -. It would have been better if they used a keyword.

It seems like C#, Java, and to a lesser extent C++ (when it gets constraints), will converge at some point to the same language.

Language Convergence

Although I'd agree that this is perhaps more important from a library design standpoint, I think that ultimately cleaner libraries are in the best interest of all users. I also happen think that most users are designers of ad hoc libraries, so it will help them as well, though perhaps not as dramatically. I do notice that I've been using the current offering in generics more and more in C# and that it does make my life easier - the more I use them, the more I like them. So my personal opinion would be that although these sorts of things seem esoteric at first, they slowly creep into your toolbox and become second nature. (Of course, the dynamic PL crowd will tell us that generics is a symptom of static typing - but that's a different issue).

As for convergence, well C# and Java started as basically the same language, so it wouldn't be that surprising if they are on parallel projectories. From a language design standpoint, I think that Java and C# are somewhat good for each other - though there's friction between the communities based on competing interests.

[Edit Note] Probably obvious, but I meant this in reply to Achilleas.

Tension

Excellent work from the authors, as always. There is much tension in exposing variance specifiers in a language that assumes mutability everywhere and has no means of specifying constant references and constant operations. The use of "where" constraints further implies complex nonlocal reasoning both in typechecking and on the human side when we read the code and try to understand why it works. These extensions stretch the C language family to an impressive new local optima, but at some point the world is going to have to move away from this imperative-everywhere, broken-const model of programming.

why is it necessary (apart

why is it necessary (apart from backwards compatability) to require annotation in these cases? why not make all generic parameters covariant and all return values contravariant? or, at least, make that the default - if one wants to limit a generic expression to be exactly equal to the class then require extra syntax. this seems to work fine with ordinary methods, classes, etc.

i assume i've got something mixed up - do you end up with something inconsistent?

Ergonomics?

I guess it's the same reason you have to mark a class 'abstract' instead of relying on the fact that a single abstract method forces the class to be abstract.

The requirement for covariance in a type parameter (that it appears in a covariant position in every place it is used) is not totally trivial and so it's nice to be able to have the compiler tell you when your declared variance conflicts with the way you're using it.

For type functions

Variance annotations are not for value arguments but for type arguments. For example, when you define a generic type

List[+A] = ...

then it says that List[A]<List[B] if A<B. Of course, this requires the definition of List to conform, i.e. its generic type argument may only ever appear in covariant position on the RHS (that's why mutability almost always precludes variance).

Where the definition is known, variance can in fact be inferred. OCaml does this, for instance. But in interface specifications, where no definition might be given, it cannot. C# however does no such inference, neither does Scala, AFAIK.

that's why mutability almost

that's why mutability almost always precludes variance

ah, ok, i get it now. yes, of course. hence tim's comment which had confused me.

ok, so next question along the road - wouldn't it have been better add some kind of const statement (and then make this implicit)? i guess the arguments is (1) that's hard to enforce (i can imagine you end up with a whole new language if you follow it through; which again is probably what tim was implying (as i type this i can't see his comment so am going by memory)) and (2) this is more general (in that you can do consistent changes, although off the top of my head it's hard to think of non-trivial ones in java, but - another penny drops - perhaps this where c# lower bound comes in).

thanks again - that made thing a lot clearer (i think!).

Prerequisite, not replacement

I believe what Tim alluded to is the fact that variance hardly ever applies to mutable types. In other words, some form of "constness" is a *prerequisite* for variance to be useful. But because you cannot always infer variance, constness is no *replacement*.

Code Generation Tool

It is about 3 years that I am programming in C#. I have done 3 or 4 Windows Application/Web Application in C# 2.0. Does anyone tried to see what is the type of a generic object? (i.e. a list). According to my experiences in using C# generics and some additional studies I tell you C# generics are just a code generation tool that is integrated to .NET 2.0 SDK. They are not real types. There is no inheritance and there is no base class for a generic type!!! What the hell is that? I told : just a coge generation tool that Microsoft just named it as "Generics"! You can try it and you will see it is a shame to ship such thing as a language feature! See Java 5.0 generics in comparission to find out what is missed. And about that dynamic functions and closures; they cause easily many bugs i.e. for GC to collect objects. I had seen this in (especially) ASP.NET. I am forced to use microsoft for my job but I know all these are fake. (Maybe you say it works after all. Yes because microsoft provide other tools to make these failures correct and continue to make product oriented languages)

Why is java better?

Not familiar enough with Java generics, but there has been some grumbling about the Type Erasure among other things.

As for C#, if I do something like:

   List<string> stringList = new List<string>();
   Console.WriteLine(stringList.GetType());
   Console.WriteLine(stringList.GetType() == typeof(List<string>));
   Console.WriteLine(stringList.GetType() == typeof(List<int>));

I get back:

   System.Collections.Generic.List`1[System.String]
   True
   False

Playing a little further, arrays of generics like the following are said not to work in Java:

    Pair<Integer,Integer>[] intPairArr = new Pair<Integer,Integer>[10]; // illegal

Whereas the following should work in C#:

    class Pair
    {
        public T1 First;
        public T2 Second;
    }

   Pair<string, string>[] intPairArr = new Pair<string, string>[10];
   Console.WriteLine(intPairArr.GetType());
   // output: Pair`2[System.String,System.String][]

Finally, C# and Java share the property that List<Object> is not a supertype of List<String>

Just to finish up the thought...

The following Java code will return true in the runtime comparison:

ArrayList<String> stringList = new ArrayList<String>();
ArrayList<Integer> intList = new ArrayList<Integer>();
System.out.println(stringList.getClass() == intList.getClass());

whereas the following C# code will return false

List<string> stringList = new List<string>();
List<int> intList = new List<int>();
Console.WriteLine(stringList.GetType() == intList.GetType());