Nested Generics: Why can't the compiler infer

Question

I was playing around with a hobby project when I came across a type-inference error I didn't understand. I have simplified it to the following trivial example.

I have the following classes and functions:

class Foo { }
class Bar { }
class Baz { }

static T2 F<T1, T2>(Func<T1, T2> f) { return default(T2); }
static T3 G<T1, T2, T3>(Func<T1, Func<T2, T3>> f) { return default(T3); }

Now consider the following examples:

// 1. F with explicit type arguments - Fine
F<Foo, Bar>(x => new Bar());

// 2. F with implicit type arguments - Also fine, compiler infers <Foo, Bar>
F((Foo x) => new Bar());

// 3. G with explicit type arguments - Still fine...
G<Foo, Bar, Baz>(x => y => new Baz());

// 4. G with implicit type arguments - Bang!
// Compiler error: Type arguments cannot be inferred from usage
G((Foo x) => (Bar y) => new Baz());

The last example produces a compiler error, but it seems to me that it should be able to infer the type arguments without any problems.

QUESTION: Why can't the compiler infer <Foo, Bar, Baz> in this case?

UPDATE: I have discovered that simply wrapping the second lambda in an identity function will cause the compiler to infer all the types correctly:

static Func<T1, T2> I<T1, T2>(Func<T1, T2> f) { return f; }

// Infers G<Foo, Bar, Baz> and I<Bar, Baz>
G((Foo x) => I((Bar y) => new Baz()));

Why can it do all the individual steps perfectly, but not the whole inference at once? Is there some subtlety in the order that the compiler analyses implicit lambda types and implicit generic types?

Answer 1

The lambda cannot be inferred what it's return type is since it is not assigned and cannot be determined by the compiler. Check out this link on how lambdas return types are determined by the compiler. If you would have haved:

Func<Bar, Baz> f = (Bar y) => new Baz();
G((Foo x) => f);

then the compiler would have been able to calculate the return type of the lambda based on what it is assigned to, but since now it is not assigned to anything the compiler struggles to determine what the return type for (Bar y) => new Baz(); would be.

Answer 2

For the compiler, a lambda function is distinct from a Func, i.e. using a lambda function for a Func implies a type conversion. The compiler does not do "nested" type conversions when specializing generics. That, however, would be required in your example:

Type of (Foo x) => (Bar y) => new Baz () is lambda (Foo, lambda (Bar, Baz)), but Func (T1, Func (T2, T3)) would be required, i.e. two conversions, which are nested.

Answer 3

Because the algorithm as described in the C# specification doesn’t succeed in this case. Let’s look at the specification in order to see why this is.

The algorithm description is long and complicated, so I’ll heavily abbreviate this.

The relevant types mentioned in the algorithm have the following values for you:

• Eᵢ = the anonymous lambda (Foo x) => (Bar y) => new Baz()
• Tᵢ = the parameter type (Func<T1, Func<T2, T3>>)
• Xᵢ = the three generic type parameters (T1, T2, T3)

Firstly, there’s the first phase, which in your case does only one thing:

7.5.2.1 The first phase

For each of the method arguments Eᵢ (in your case, there’s only one, the lambda):

• If Eᵢ is an anonymous function [it is], an explicit parameter type inference (§7.5.2.7) is made from Eᵢ to Tᵢ
• Otherwise, [not relevant]
• Otherwise, [not relevant]
• Otherwise, no inference is made for this argument.

I’ll skip the details of the explicit parameter type inference here; it suffices to say that for the call G((Foo x) => (Bar y) => new Baz()), it infers that T1 = Foo.

Then comes the second phase, which is effectively a loop that tries to narrow down the type of each generic type parameter until it either finds all of them or gives up. The one important bullet point is the last one:

7.5.2.2 The second phase

The second phase proceeds as follows:

• [...]
• Otherwise, for all arguments Eᵢ with corresponding parameter type Tᵢ where the output types (§7.5.2.4) contain unfixed type variables Xj but the input types (§7.5.2.3) do not, an output type inference (§7.5.2.6) is made from Eᵢ to Tᵢ. Then the second phase is repeated.

[Translated and applied to your case, this means:

• Otherwise, if the return type of the delegate (i.e. Func<T2,T3>) contains an as yet undetermined type variable (it does) but its parameter types (i.e. T1) do not (they do not, we already know that T1 = Foo), an output type inference (§7.5.2.6) is made.]

The output type inference now proceeds as follows; again, only one bullet point is relevant, this time it’s the first one:

7.5.2.6 Output type inferences

An output type inference is made from an expression E to a type T in the following way:

• If E is an anonymous function [it is] with inferred return type U (§7.5.2.12) and T is a delegate type or expression tree type with return type Tb, then a lower-bound inference (§7.5.2.9) is made from U to Tb.
• Otherwise, [rest snipped]

The “inferred return type” U is the anonymous lambda (Bar y) => new Baz() and Tb is Func<T2,T3>. Cue lower-bound inference.

I don’t think I need to quote the entire lower-bound inference algorithm now (it’s long); it is enough to say that it doesn’t mention anonymous functions. It takes care of inheritance relationships, interface implementations, array covariance, interface and delegate co-/contravariance, ... but not lambdas. Therefore, its last bullet point applies:

• Otherwise, no inferences are made.

Then we come back to the second phase, which gives up because no inferences have been made for T2 and T3.

Moral of the story: the type inference algorithm is not recursive with lambdas. It can only infer types from the parameter and return types of the outer lambda, not lambdas nested inside of it. Only lower-bound inference is recursive (so that it can take nested generic constructions like List<Tuple<List<T1>, T2>> apart) but neither output type inferences (§7.5.2.6) nor explicit parameter type inferences (§7.5.2.7) are recursive and are never applied to inner lambdas.

Addendum

When you add a call to that identify function I:

• G((Foo x) => I((Bar y) => new Baz()));

then type inference is first applied to the call to I, which results in I’s return type being inferred as Func<Bar, Baz>. Then the “inferred return type” U of the outer lambda is the delegate type Func<Bar, Baz> and Tb is Func<T2, T3>. Thus lower-bound inference will succeed because it will be faced with two explicit delegate types (Func<Bar, Baz> and Func<T2, T3>) but no anonymous functions/lambdas. This is why the identify function makes it succeed.