Good heavens, this just keeps on happening to me.

If you're interested in what we're musing about for future versions of C#, check out this video of Anders Hejlsberg, Scott Wiltamuth, Paul Vick, Mads Torgersen, Matt Warren, Jim Hugunin and, off in one corner, me.

Working with this caliber of people every day is a huge part of what makes this the best job ever.

http://channel9.msdn.com/posts/Charles/C-40-Meet-the-Design-Team/

I want to start this by discussing the purpose of method type inference, and clearing up some potential misunderstandings about type inference errors.

First off though, a brief note on nomenclature. Throughout this series when I say "type inference" I mean "method type inference", not any of the other forms of type inference we have in C# 3.0. (Implicitly typed locals, implicitly typed arrays, and so on.)

The purpose of type inference is to allow generic methods to be called without explicitly specifying the generic types. For example, if you have a generic method

then it would be nice to be able to say

without having to say redundant information:

This was useful in C# 2.0, but with the advent of extension methods and query comprehensions in C# 3.0, it is downright vital. If we made Largest into an extension method then clearly you want to be able to say

and not have to insert this ugly mechanism information into your lovely semantic query:

When you call a method without an explicit argument list, overload resolution must figure out which method you meant to call. The way type inference works with overload resolution is that all methods of that name are put into a pool called the candidate set. If any of them are generic, we run a type inference algorithm to see if the generic type arguments can be inferred for the method. If they can, then the constructed generic method stays in the candidate set; if inference fails then it is removed. Then all methods which are inapplicable -- that is, the arguments cannot be converted to the parameter types -- are removed. Of the remaining applicable candidates, either a unique best candidate is chosen. If a unique best candidate cannot be identified then overload resolution fails.

Note that type inference failure is not actually an error in of itself. However, type inference failure (or success!) might cause real errors downstream in a number of ways. For example:

• if type inference fails and the candidate set becomes empty as a result, then overload resolution fails
• if type inference fails when the user intended the generic method to be the chosen one, and the remaining candidates have no unique best member, then overload resolution fails
• if type inference succeeds when it wasn't expected to then there might be more methods in the candidate set than expected. If the inferred method ties for "bestness" with another candidate then overload resolution fails. (The tiebreaker rules in overload resolution are designed to avoid this scenario, but it is still possible in contrived situations.)

This then brings up the question of what error message to display when overload resolution fails. In C# 2.0 we have a heuristic which tries to detect when overload resolution failed because of the first case (which is the most common of the three cases.) In those cases it gives an error message that says "type inference failed" rather than "overload resolution failed". Even though the actual error as far as the language specification is concerned is that the candidate set contained no unique best applicable member, the user typically thinks of the cause of the error as being type inference failure in many cases, so we try to do a good job of reporting that.

It works pretty well in C# 2.0, but we struggled with this a lot in C# 3.0. Suppose you end up in a situation where you have a query:

Oops. That is going to be translated into customers.Select(c=>c.FristName). There are no methods named "Select" on IEnumerable<Customer>, we look for extension methods and find Enumerable.Select<T, R>(this IEnumerable<T> list, Func<T, R> selector). Type inference infers T as Customer, but cannot figure out what R is because Customer does not have a property FristName. Therefore type inference fails, and therefore overload resolution fails, and therefore our heuristic takes over and gives the error that type inference failed on Select.

I think you would agree that the user does not think of the error in this program as being a failure of overload resolution or type inference; they think that the failure is that there's a typo in one clause of the query. Wes did quite a bit of work on the heuristics to go back one step further, and report why type inference failed; because the body of the lambda could not be successfully bound.

So that's one change to type inference between C# 2.0 and C# 3.0, but I seem to have gotten ahead of myself somewhat. Next time we'll take a closer look at how the mechanism of type inference works in C# 2.0.

Back in November I wrote a bit about a corner case in method type inference which does not work as expected or as specified in C# 3.0. A number of people made blog comments, sent me mail, and entered "Connect" issues with additional problems and ideas for how we could improve this algorithm. (Particular thanks to nikov for his many fascinating and detailed Connect reports.) As a result, as soon as I had time I embarked upon a detailed review of the method type inference specification and the implementation.

The good news is that this resulted in a complete overhaul of both the implementation and the specification; they are now consistent with each other and to the best of my knowledge, correct. Furthermore, the principle concern of commenters on my earlier article has been dealt with: return type inference from a method group to the return type of a delegate type will be legal, but only when the delegate type's input parameters are all completely known. This eliminates the "chicken and egg" problem I discussed in November, whereby overload resolution on the method group must consume the very same unfixed formal parameter types that it is attempting to infer.

The bad news is that these changes to the implementation will not make it in to the service release of C# 3.0; they will have to wait for a later revision of the compiler. (It is not yet clear to me whether or not the changes to the specification will make it into the next edition of the published specification.)

This is one of the most complex areas of the specification and implementation; I'd like to spend some time in this blog going over the specification in detail and explaining where we got things subtly wrong, and how we intend to fix it.

In this series I want to hit on the following points:

• What did method type inference look like in C# 2.0? Why was it inadequate for LINQ?
• How did we attempt to modify and ultimately rewrite the specification for C# 3.0?
• Where did we go subtly wrong in the specification and the implementation?

Next time, we'll get started with a look back at C# 2.0.

Here's some back-and-forth from an email conversation I had with a user a while back.

Why should one avoid method hiding? 

If there were no advantages and only disadvantages then we would not have added it to the language in the first place. C# implements hiding because hiding is frequently useful. 
 
I therefore deny the premise of the question. One should not avoid method hiding if it is the right thing to do.

But I find method hiding confusing. It lets derived types appear to break the contracts of base types. If a derived type D hides a method M on base class B because D.M does something different than B.M, shouldn't it have a different name?

That sounds remarkably like a good answer to your original question.

However, method hiding is for exactly those times when you need to have two things to have the same name but different behaviour.
 
Obviously that is not a pleasant situation to be in. I agree with you that it is almost always preferable to have different things have different names. However, I can think of a few situations in which it's desirable. Consider this real-world example:
 
interface IEnumerable<T> : IEnumerable {
  new IEnumerator<T> GetEnumerator();
}
 
Is there a better name than GetEnumerator? That's what it does: it gets an enumerator. And in this case, you want to suppress the usage of the base type's non-generic GetEnumerator as much as possible; this version is intended to fully replace the non-generic version.

Of course, if C# had method return type covariance, this would not have to be a new method. That gives us a larger good reason for method hiding; it allows for something like return type covariance in a language that does not have such a feature.

I suppose that makes sense. Could you give some other examples of valid usage?

Sure, but I will have to digress in a prolix manner first.

We want to write computer programs which solve real-world problems, and therefore we want to design languages which enable developers to model their real-world problems in natural, flexible and intuitive ways. We want to take problem solving techniques which work well in the non-computer realm and enable developers to use the real-world intuitions and skills they’ve learned in their program.

One of the techniques that we developed millennia ago to solve problems is organization of objects into hierarchies. Hierarchies are often imperfect – there are the occasional platypuses which crop up and resist easy classification. But hierarchies are such a powerful and useful tool that we use them, despite their flaws, to help organize the world’s data and solve real problems.

Thus, it should be clear that class-based inheritance exists in programming languages because we wish to enable developers to naturally and easily write programs which model problems solved by hierarchies.

So here’s the rub: in a world where objects fit into a hierarchy, who gets to decide how to manipulate that object based on its position in the hierarchy?  Does the object get to decide (at runtime), or does the code doing the manipulation get to decide (at compile time)? 

The former is called “virtual dispatch”, the latter “non-virtual dispatch”.  Which you choose to use depends entirely upon the problem being modeled. It’s not like one of them is absolutely morally better than the other. The better one is the one which models the real-world problem better.

Many problems – probably the majority of problems in this space – are best modeled by letting the object decide how it is to be treated.  When you call Feed on an instance of Animal, let the instance decide what happens based on whether the instance is a Squid or a Zebra. Do a virtual dispatch at runtime. But it would be an error to say that because most problems are modeled this way, that the language ought not to allow modeling the problem any other way. Sometimes it is best for the caller to decide how the object is treated, because the caller has more information.

For example, when I was a teenager my father owned a restaurant. This was at the time that the Conservative government in Canada introduced a highly unpopular value-added sales tax on goods and services called, unimaginatively enough, the Goods and Services Tax.  The GST rules were roundly criticized as being insanely complicated. No government wants to be known as “the government that increased the price of food for poor people”, so grocery items were exempted from the GST. But what qualified as a “grocery item”? That had a whole other complex set of rules.

A cake sold in a grocery store, no GST. The exact same cake, sliced and plated in my father’s restaurant, GST. The exact same cake, NOT sliced, sold whole in the restaurant, no GST. A muffin in a grocery store, no GST. The same muffin in my father’s restaurant, GST. A box of six muffins sold in the restaurant, no GST.

I gather that in the last twenty years the tax has been rationalized somewhat. That’s not my point. My point is that this is a case where what the object is (virtual dispatch) is only one factor in how it behaves with respect to taxes. An equally important factor is how the object is being classified right now (non-virtual dispatch).

How might we model this in a programming language? There are lots of ways, and we could certainly argue about which is best. C# allows you the flexibility to come up with a variety of different designs and decide for yourself which models your problem best. One way in which we could reasonably model this problem would be to have a hierarchy:

And so on. We could continue to complexify this to model the tax rules better. Now when I have a variable of type Cake, it’s tax rate is 7%. When I have the same cake stuck into a variable of type Grocery, its tax rate is 0%. That is, what the object “really” is at runtime is less relevant to the problem at hand then how I am presently classifying it.

One might make the argument that this is a violation of the Single Responsibility Principle, that the tax logic should be in a class of its own, that groceryness should be a flag and not a part of the type system, that really what we need is both a Food and a TransactionContext hierarchy, blah blah blah. I am sure that we could come up with a completely different hierarchy of objects which did not require hiding, and that other hierarchy might even be “better” in some ways. We seem to be badly conflating mechanism with policy here, which is worrisome.

But that's not my point. My point is that in C# we want to give you the flexibility to model problems this way if you choose to, if you believe that this is the best way to model them. And I think that’s a good thing.

I wrote a couple of articles about how we designed this same feature into JScript .NET. It is a language greatly complicated by its dynamic nature, so the design decisions became correspondingly harder. See

http://blogs.msdn.com/ericlippert/archive/2004/06/07/150367.aspx
http://blogs.msdn.com/ericlippert/archive/2004/06/08/151209.aspx

The comments are particularly useful in these articles as well.

In my youth I once attended a lecture given by Brian Kernighan on the subject of code quality, which was very influential on my attitudes towards writing legible code. One of the things that Kernighan recommended was to endeavour write code that was so clear that it could be easily read over the phone and understood. Most people find code much easier to comprehend when read than when heard; if you can make it clear enough to be understood when heard, it's probably pretty clear code.

I was reminded of this when I got the following question from a colleague by email:

First off, I told my colleague that there are no stupid questions, only stupid people. No stupid people work here, so don't stress about it. This is a perfectly sensible question.

As far as I know, we do not have an "official" line on how to read this operator over the phone. In the absense of any other context, I personally would say c=>c+1 as "see goes to see plus one". Some variations that I've heard:

For a projection, (Customer c)=>c.Name: "customer see becomes see dot name"

For a predicate, (Customer c)=>c.Age > 21: "customer see such that see dot age is greater than twenty-one"

An unfortunate conflation is that the => operator looks a lot like ⇒, the "implies" operator in mathematics. Since => does not have the same semantics as ⇒, it is probably a bad idea to read => as "implies". (x⇒y would have the semantics of !x|y in C#.)

Incidentally, it is a little known fact that VB6 and VBScript implemented the ⇒ operator with the Imp keyword and the ⇔ operator with the Eqv keyword. They disappeared in VB.NET. Where did they go? It is a mystery!

OK, computers aren't entirely dumb when it comes to LINQ. Here's an example of a place where we're a bit smarter.

Consider the following query:

Does this get transformed by the compiler into

or

?

This question caused tremendous debate amongst the members of the C# design and implementation teams. I am quite happy with the compromise we achieved.

The sections of the C# specification which cover this topic are sections 7.15.2.3, and 7.15.2.5:

***

***

It might sound like the second statement contradicts the first. The first statement says that the “.Select(x=>v)” is omitted when “v” is “x”, and the second statement says that no, the “.Select(x=>x)” is in fact generated.

The spec is not particularly clear on this point, I agree, though the explanatory text about “degenerate query expressions” does help clear it up somewhat. Basically what we are saying here is that the optimization to remove degenerate selects is only performed on the result of an earlier query translation.

Some examples will help.

If you have from n in number_array orderby n select n then this is first translated into from n in (number_array).OrderBy(n=>n) select n and then, since the selector is the same as the range variable, this is translated into ((number_array).OrderBy(n=>n)).

We optimize away the Select(n=>n) because from n in (number_array).OrderBy(n=>n) select n is the intermediate result of an earlier query translation.

If you had from n in number_array select n then this would be considered a degenerate query expression requiring a Select. We cannot simply translate it into (number_array) because then you could assign that to a variable and have referential identity with the collection. The result of the query should not “leak” information about the collection out; it should just be an enumerable object of the appropriate type, and not have an identity relationship. Therefore, we take the performance hit and protect the identity of the collection by emitting a degenerate query translation (number_array).Select(n=>n).

This is important because the collection might be a mutable collection. One does not expect that the result of a query over that collection could be used to mutate the collection! The query results should be read-only.

We do not need to append the degenerate Select(n=>n) when you have an “orderby” in there because the OrderBy(n=>n) call already protects the identity of the original collection. This saves on the performance cost of the no-op Select.

I think we’ve made a reasonable compromise in the case of degenerate queries. If you are crazy enough to write “from x in xs select x” when you mean “(xs)”, then you’ll have to live with the decreased performance. But if you are introducing a degenerate select at the end of a meaningful query, then it will be optimized away.

UPDATE: Andrew Kennedy, author of the paper I reference below, was good enough to point out some corrections and omissions, which I have addressed. Thanks Andrew!

As I've discussed at length in this space, we are considering adding covariance and contravariance on delegate and interface types parameterized with reference types to a hypothetical future version of C#. (See my earlier articles in this series for an explanation of the proposed feature.)

Variance is highly useful in mainstream cases, but exposes a really irksome problem in certain bizarre corner cases. Here's just one example.

Consider a "normal" interface contravariant in its sole generic type parameter, and a "crazy" invariant interface which extends the normal interface in a strange way:

This is a bit weird, but certainly legal.

Before I go on, I want to digress and talk a bit about why this is legal. Most people when they first see such a beast immediately say "but an interface cannot inherit from itself, that's an illegal circularity in the inheritance chain!"

First off, no, that is not correct. Nowhere does the C# specification make this kind of inheritance illegal, and in fact, a weak form of it must be legal. You want to be able to say:

that is, you want to be able to express that one of the guarantees of the INumber<X> contract is that you can always compare one number with another one. Therefore, it must be legal to use a type's name in a type argument of a generic base type.

However, all is not rosy. This particularly gross kind of inheritance that I give as an example is in fact illegal in the CLR, even though it is not illegal in C#. This means that it is possible to have the C# compiler generate an interface type which then cannot be loaded by the CLR. This unfortunate mismatch is troubling, and I hope in a future version of C# to make the type definition rules of C# as strict or stricter than those of the CLR. Until then, if it hurts when you do that, don't do it.

Second, unfortunately, the C# compiler presently has numerous bugs in its cycle detector such that sometimes things which kinda look like cycles but are in fact not cycles are flagged as cycle errors. This just makes it all the more difficult for people to understand what is a legal cycle and what isn't. For example, the compiler today will incorrectly report that this is an illegal base class cycle, even though it clearly is not:

I have devised a new (and I believe correct!) cycle detection algorithm implementation, but unfortunately it will not make it into the service release of the C# 3 compiler. It will have to wait for a hypothetical future release. I hope to address the problem of bringing the legal type checker into line with the CLR at the same time.

Anyway, back to the subject at hand: crazy variance. We have the interfaces defined as above, and then give the compiler a little puzzle to solve:

In Part Two I asked a couple of follow-up questions, the first of which was:

Suppose you were a hostile third party and you wanted to mess up the parenting invariant. Clearly, if you are sufficiently trusted, you can always use private reflection or unsafe code to muck around with the state directly, so that's not a very interesting attack. Any other bright ideas come to mind for ways that this code is vulnerable to tampering?

Before I get into some ideas for attacks, I want to re-emphasize the bit in the middle there: attacks which presuppose that the attacker is already an administrator on your machine are not interesting attacks. A number of people came up with attacks involving the attacker being able to run debuggers or even replace the entire CLR with a custom-built runtime.

Since there is no point in protecting code from hostile code which is already stronger than the security system itself, it's not very interesting to consider such attacks. The interesting question is how to protect yourself against hostile code which is weaker than the code you are attempting to protect. That's what attackers want to do -- they want to leverage vulnerabilities in your strong code to turn their weak code into strong code. If they already have strong code, they don't need to lure your code into doing something, they can just do it directly.

Anyway, that said, there are a number of flaws in my proposed implementation from a security perspective:

• Eamon Nerbonne pointed out the implementation is not in the slightest thread-safe; hostile code which wished to mess up the parenting invariant could run adds and removes on the same objects on multiple threads at once, and when the smoke clears, pretty much any weird parenting arrangement you care to name could be the case.
• Matt pointed out that the implementation relies upon a correct implementation of hashing/equality. If a hostile or buggy object provides an implementation of hashing which is inconsistent with its implementation of equality, it is possible to put stuff into a hash set and never get it back out again. The parenting invariant in this implementation relies upon being able to use hash sets correctly.
• Jon Skeet pointed out that the implementation has no protections against parenting relationships which are locally sensible but not globally sensible, like a box containing itself.

All of these vulnerabilities could of course be mitigated without too much difficulty; the trick is in remembering to look for the vulnerability in the first place!

Getting the parenting relationship consistently acyclic is an interesting algorithmic problem. There are numerous ways to do it. Two sketches for your consideration:

1) Every time you add an item to a container, search the parent list of the container for the item. Hopefully containment relationships are shallow and this is not too expensive. 

2) Only allow adding an item to a container if the item and the container are different but are themselves in the same immediate container. If you have a box in a bag, and you want to put a ball in the box, first put it in the bag, and then in the box. 

Next time, some thoughts on immutability and parenting relationships.