The problem of understanding C # type inference as described in the language specification

Question

The C # language specification describes type inference in §7.5.2. It has details that I do not understand. Consider the following case:

// declaration void Method<T>(T obj, Func<string, T> func); // call Method("obj", s => (object) s); 

Microsoft and Mono C # compilers correctly conclude T = object , but my understanding of the algorithm in the specification will give T = string , and then crash. Here is how I understand it:

First phase

• If Ei is an anonymous function, then the conclusion about the explicit type of parameters (§7.5.2.7) is made from Ei to Ti

  ⇒ not valid because the lambda expression has no explicit parameter types. Right?

• Otherwise, if Ei is of type U and xi is a value parameter, then output with a lower boundary is made from U to Ti.

  ⇒ The first parameter is of the static type string , so it adds string to the lower bounds for T , right?

Second phase

• All uncommitted variables of type Xi that are independent of (Section 7.5.5.5) are fixed (X7.2.2.10).

  ⇒ T fixed; T is independent of anything ... so T needs to be fixed, right?

§7.5.2.11 Fixation

• The set of candidate types Uj begins as the set of all types in the set of ratings for Xi.

  ⇒ { string (lower bound)}

• Then we consider each estimate for Xi in turn: [...] For each lower boundary U of the set Xi, all types Uj to which there is no implicit conversion from U are removed from the set of candidates. [...]

  ⇒ Does not remove any of the candidate sets, right?

• If among the other types of candidates Uj there is a unique type V, from which an implicit conversion to all other types of candidates occurs, then Xi is fixed to V.

  ⇒ Since there is only one candidate type, this is an empty value, so Xi is fixed to string . Right?

---

So where am I mistaken?

Answer 1

UPDATE: My initial investigation into the bus this morning was incomplete and incorrect. The specification text for the first phase is correct. The implementation is correct.

The specification is incorrect in that the second order of events is incorrect. We must indicate that we are outputting the output type before correcting the independent parameters.

Man, this stuff is complicated. I have rewritten this section of the specification more times than I remember.

I have seen this problem before, and I clearly recall creating revisions, so the incorrect term "type variable" is everywhere replaced by "type parameter". (Type parameters are not storage locations whose contents may vary, so it makes no sense to call them variables.) I think at the same time I noticed that the order was incorrect. It probably happened that we accidentally sent an older version of the specification on the Internet. A lot of apologies.

I will work with Mads to update the specification in accordance with the implementation. I think that the correct formulation of the second phase should look something like this:

• If there are no parameters of an uncommitted type, then type inference succeeds.
• Otherwise, if there is one or more arguments Ei with the corresponding parameter type Ti such that the output type Ei with type Ti contains at least one uncommitted type of parameter Xj and none of the input types Ei with type Ti contains any uncommitted type of the parameter Xj, then the output of the output type is made from all such Ei in Ti.

Regardless of whether the previous step really concluded, we must now correct at least one type parameter, as shown below:

• If there is one or more parameters of type Xi such that Xi is not fixed and Xi has a nonempty set of estimates and Xi is independent of any Xj, then each such Xi is fixed. If any commit operation is not performed, type inference is not performed.
• Otherwise, if there is one or more parameters of type Xi such that Xi is unfixed and Xi has a nonempty set of estimates and there is at least one parameter of type Xj depending on Xi, then each such Xi is fixed. If any commit operation is not performed, type inference is not performed.
• Otherwise, we will not be able to make progress and uncommitted parameters. Type input error.

If type inference fails or fails, repeat the second phase.

The idea here is that we want to make sure that the algorithm never goes into an infinite loop. With each repetition of the second phase, he either succeeds, or fails, or makes progress. It cannot loop more than once there are type parameters for type correction.

Thank you for bringing this to my attention.