Take the 2-minute tour ×

Just curious: sure, we all know that the general case of type inference for generics is undecidable. And so C# won't do any kind of subtyping at all: if Foo<T> is a generic, Foo<int> isn't a subtype of Foo<T>, or Foo<Object> or of anything else you might cook up. And sure, we all hack around this with ugly interface or abstract class definitions.

But... if you can't beat the general problem, why not just limit the solution to cases that are easy. For example, in my list above, it is OBVIOUS that Foo<int> is a subtype of Foo<T> and it would be trivial to check. Same for checking against Foo<Object>.

So is there some other deep horror that would creep forth from the abyss if they were to just say, aw shucks, we'll do what we can? Or is this just some sort of religious purity on the part of the language guys at Microsoft?

share|improve this question
That was painful. Use backtick ` not a backslash. –  Hans Passant Dec 21 '10 at 20:33
This question is extremely confusing. Can you clarify the question? Start by carefully defining precisely what you mean by "subtype" because it is not at all clear to me what you mean by it. A simple, realistic example of the sort of conversion you believe should be legal and "trivial to check" would help. –  Eric Lippert Dec 21 '10 at 23:25
For example: Foo<T> has a method Bar: public T Bar(T value){/*...*/}. For Foo<object> foo = new Foo<object>();, this would be legal: object result = foo.Bar(0);. So would this: object result = foo.Bar("XYZ"); However, for Foo<object> foo = new Foo<int>(); only the first would be legal. –  phoog Dec 22 '10 at 0:13
Sorry Hans; took a minute to figure out the escape sequence. –  Ken Birman Dec 22 '10 at 1:36
Eric, what I'm trying to do is to create a List of objects, each of which specializes a generic that I define but with different types. Then I want to be able to call methods in these objects. For example: my generic requires the user to provide an Aggregate(KeyType key, ValueType value) method, and I plan to call it with objects of the appropriate type (obtained from the user). My code is a fairly elaborate distributed protocol; think of it as MapReduce. They specialize my logic. –  Ken Birman Dec 22 '10 at 1:38
add comment

6 Answers

up vote 6 down vote accepted

They already have solved it for many of the "easy" cases: C# 4.0 supports covariance and contravariance for generic type parameters in interfaces and delegates. But not classes unfortunately.

It's fairly easy to workaround this limitation:

List<Foo> foos = bars.Select(bar => (Foo)bar).ToList();
share|improve this answer
+1 For pointing out contra/covariance terms and providing a link. –  user166390 Dec 21 '10 at 20:43
I'm aware of the covariance and contravariance additions. Tres cool, but not such a good fit to my intended use, unfortunately. –  Ken Birman Dec 22 '10 at 1:36
add comment


To you maybe, but not to me.

To me, the huge hole this rips into the type system is simply not acceptable. If you want to throw type-safety out the window like that, I'd much rather use a dynamically typed language that was actually designed for this stuff.

The fact that arrays are covariant, even though this is known to break type-safety, is bad enough, now you want to break it for everything?

This goes to the very heart of what a type system is about. All a type system does is reject programs. And because of Rice's Theorem, those rejected program include perfectly well-typed, type-safe programs.

That is a huge cost. Taking away expressivity, preventing me from writing useful programs. In order to justify that cost, the type system better pay be back big time. It has basically two ways of doing that: giving back expressivity at the type-level it took away at the program-level and type-safety.

The former is out, simply because C#'s type system isn't powerful enough to let me express anything even remotely interesting. This leaves only the latter, and it is already on pretty shaky ground because of null, covariant arrays, unrestricted side-effects, unsafe and so on. By making generic types automatically covariant, you more or less completely take away the last shred of type-safety that is left.

There are only very few cases where S <: T ⇒ G<S> <: G<T> is actually type-safe. (IEnumerable is one such example.) And there are probably equally many cases where only S <: T ⇒ G<T> <: G<S> is type-safe. (IObservable, IComparer, IComparable, IEqualityComparer.) Generally, neither G<S> <: G<T> nor G<T> <: G<S> are type-safe.

share|improve this answer
Don't buy your assertion that there are few interesting cases where a simple mechanism could suffice and be useful. I think there are probably lots of cases where the inference can be done easily and is type safe too. I have such cases; topic is the number one FAQ for generics here on the C# threads and on Java too. Because the obvious things feel broken. No issue with the complex cases not working: C# could just say "unable to prove subtype relation" if it can't do the safety inference in a few ms, isn't sure and wants to give a nice error message.... –  Ken Birman Dec 22 '10 at 1:43
@Ken Birman: I am not sure what you mean. I was specifically responding to your claim that it is " obvious " that Foo<int> is a subtype of Foo<object>, and I gave four examples of cases where it is not only not obvious but plain simply not true. –  Jörg W Mittag Dec 22 '10 at 2:57
Jorg, your examples aren't tangential. I don't disagree that type inference for generics is an undecidable question; I pointed that out myself in posing my question. You are failing to understand my point, which is that sometimes there exist simple subsets of these problems that can be solved even if the general case is not solvable. The instances I suggested are obvious because the types are directly derived from the ones they subtype from, and hence any tiny amount of history at all would reveal the exact match and hence the subtype relationship, even if an inference algorithm were hard. –  Ken Birman Dec 22 '10 at 13:54
One way to think of this: many problems are NP complete. Yet today we solve such problems all the time because we often find that the world is producing a biased set of instances that have some sort of quirk rendering those instances "easy" despite the difficulty of the general case. I have several examples from my area of distributed systems; a good one involves optimal assignment of IP multicast resources in cloud computing subject to constraints. So I'm suggesting a rethinking of undecidability for generic subtype relationship inferences, aimed at the same insight. –  Ken Birman Dec 22 '10 at 13:57
... which is, specifically, the insight that some hard problems have easy yet useful subcases. Solving those is valuable even if you leave the most general problem instance open -- even if it will never be solved. –  Ken Birman Dec 22 '10 at 13:58
add comment

The point is that you can't do it for all cases, so you don't do it for any. Where do you draw the line is the problem. If you don't do it for any than everyone who uses C# knows that it doesn't do that. If you do it part of the time, that is when it gets complicated. It can become a guessing game as to how your code will behave. It's all the edge cases on what is easy and what is not that become complex to the programmers and can cause errors in code.

Here is a scenario that would absolutely cause havoc. Let's say that you can infer boo is bar in scenario A. Someone else comes and changes part of the base type and this no longer holds true. By making it either always apply, or never apply, you don't run into this situation, ever. In a complex environment, tracking down a problem like this can be an absolute nightmare, especially when you factor in this may not be catchable during the compile time (reflection, the DLR etc.). It's so much easier to write code to manually handle the conversion up front, than assume that it will work in your scenario when the possibility that sometime down the line it just won't (not counting upgrading to a new version).

C# 4.0 does fix some of this as they allowed inference on what they felt is "safe" for the programmers.

share|improve this answer
Yes, I realize that. The general case is not solvable. But many useful special cases would be easily solvable. Maybe all useful cases. –  Ken Birman Dec 21 '10 at 20:34
add comment

A really good real life example of a language that is muddied and made more complex than necessary by special cases is English. In a programming language things like "i before e except after c" make the language harder to use and as such, less useful.

share|improve this answer
Not asking for anything remotely as fancy as that. Just want to declare an Isis Aggregator<KeyType,ValueType> generic; my user creates an IntAggregator: IsisAggregator<int,int> and the C# compiler realizes that an IntAggregator is an IsisAggregator hence lets me call some methods without wierd, hand-coded reflection. Which yes, I do understand how to write, and yes, does represent one possible work-around. –  Ken Birman Dec 22 '10 at 1:45
add comment

Since instances of generic classes have different method signatures I don't belive it would make any sence to consider specific classes to be inherited from base classes.

class Base<T> 
 public T Method() { return default(T);}

If you suggest that Base and Base than both of them have "Method" with the same signature (coming from base class) and it can be called by using reference to base class. Can you please explain what obvious return value "Method" will have in your system if one points to Base<int> or Base<string> object by pointing to base class?

share|improve this answer
I would cast it to object, so would end up with a default object in this case of type T. Later might pass that INTO some other method in the same, user-defined, derived class. My particular use is focused on Aggregator classes that take some type of input (say ints, or doubles) and compute some aggregation operation (say max, or min). They have standard methods but specialized for the types used (or defined) by the programmer using my scalable distributed aggregation library (think of this as a variation on MapReduce, for cloud computing). –  Ken Birman Dec 22 '10 at 14:01
add comment

So, I found an elegant work-around for my real problem (although I do find that C# is overly constraining).

As you've gathered, my main goal is to write code that can register a callback to a method that you'll write later (in 2011, for example) and that was defined externally with generic type parameters that don't exist today, hence aren't available to me at the time I wrote my library (today).

For example I need to make a list of objects you'll define next year, and iterate over the elements of the list, calling back to each object's "Aggregate<KeyType, ValueType>" method. My frustration was that while you can certainly register your class, or an object in your class, C# type checking wasn't letting me call the methods because I don't know the types (I can get the types via GetType() but can't use those as types in expressions). So I was starting to use reflection to hand-compile the desired behavior, which is ugly and can violate type safety.

And the answer is... anonymous classes. Since an anonymous class is like a closure, I can define my callbacks inside the "register" routine (which has access to the types: you can pass them in when you register your objects). I'll create a little anonymous callback method, right inline, and save a delegate to it. The callback method can call your aggregator since C# considers it to "know" the parameter types. And yet my list can list methods with known type signatures at the time I compile my library, namely tomorrow.

Very clean and C# doesn't end up driving me insane. Still, C# really doesn't try hard enough to infer subtype relationships (sorry Eric: "what should be subtype relationship"). Generics aren't macros in C. Yet C# is much too close to treating them as if they were!

And that answers my own (real) question.

share|improve this answer
add comment

Your Answer


