How does the compiler/runtime determine a lambda expression's type?

Question

I was wondering how the the compiler/runtime determines a lambda expression's type?

For example, the following System.Linq Select extension method (not select query)

//var recordIds = new List<int>(records.Select(r => r?.RecordId ?? 0));
//var recordIds = new List<int>(records.Where(r => r != null).Select(r => r.RecordId));
var recordIds = new List<int>(records.Select(r => r.RecordId));

is defined as

Enumerable.Select<TSource, TResult> Method (IEnumerable<TSource>, Func<TSource, TResult>)

and so takes the lambda r => r.RecordId as a Func<TSource, TResult>.

How is the lambda's type determined, and once it is, is it simply cast to that type?

Answer 1

I was wondering how the the compiler/runtime determines a lambda expression's type?

It is rather complicated. Implementing this feature was the "long pole" for the version of Visual Studio that shipped C# 3 -- so every day that I was over schedule on this was a day that VS would slip! -- and the feature has only gotten more complicated with the introduction of covariance and contravariance in C# 4.

As others have noted, consult the specification for exact details. You might also read the various articles I've written about it over the years.

I can give you a quick overview though. Suppose we have

records.Select(r => r.RecordId)

where records is of type IEnumerable<Record> and RecordId is of type int.

The first question is "does IEnumerable<Record> have any applicable method called Select? No, it does not. We therefore go to the extension method round.

The second question then is: "is there any static type with an accessible extension method that is applicable to this call?"

SomeType.Select(records, r => r.RecordId)

Let's suppose that Enumerable is the only such type. It has two versions of Select, and one of them takes a lambda that takes two parameters. We can automatically discard that one. That leaves us with, as you note:

static IEnumerable<R> Select<A, R>(IEnumerable<A>, Func<A, R>)

Third question: Can we deduce the type arguments corresponding to type parameters A and R?

In the first round of type inference we consider all the non-lambda arguments. We only have one. We deduce that A could be Record. However, IEnumerable<T> is covariant, so we make a note that it could be a type more general than Record as well. It cannot be a type that is more specific than Record though.

Now we ask "are we done?" No. We still don't know R.

"Are there any inferences left to make?" Yes. We haven't checked the lambda yet.

"Are there any contradictions or additional facts to know about A?" Nope.

We therefore "fix" A to Record and move on. What do we know so far? We have:

static IEnumerable<R> Select<Record, R>(IEnumerable<Record>, Func<Record, R>)

We then say OK, the argument must be (Record r) => r.RecordId. Can we infer the return type of this lambda knowing that? Plainly yes, it is int. So we put a note on R saying that it could be int.

Are we done? Yes. Is there anything else we can make a deduction about? No. Did we infer all the type parameters? Yes. So we "fix" R to int, and we're done.

Now we do a final round that checks to make sure that Select<Record, int> does not produce any errors; for example, if Select had a generic constraint that was violated by <Record, int> we would reject it at this point.

We've deduced that records.Select(r=>r.RecordId) means the same thing as Enumerable.Select<Record, int>(records, (Record r) => { return (int)r.RecordId; } ) and that's a legal call to that method, so we're done.

Things get rather more complicated when you introduce multiple bounds. See if you can figure out how something like a Join works where there are four type parameters to infer.

Answer 2

I think the best place to look for such information is the language spec:

Section 7.15

An anonymous function is an expression that represents an “in-line” method definition. An anonymous function does not have a value or type in and of itself, but is convertible to a compatible delegate or expression tree type. The evaluation of an anonymous function conversion depends on the target type of the conversion: If it is a delegate type, the conversion evaluates to a delegate value referencing the method which the anonymous function defines. If it is an expression tree type, the conversion evaluates to an expression tree which represents the structure of the method as an object structure.

The above explains the nature of lambda expressions, basically that they have no types by themselves, unlike say, an int literal 5. Another point to note here is that the lambda expression is not casted to the delegate type like you said. It is evaluated, just like how 3 + 5 is evaluated to be of int type.

Exactly how these types are figured out (type inference) is described in section 7.5.2.

...assume that the generic method has the following signature:

T_r M<X₁…X_n>(T₁ x₁ … T_m x_m)

With a method call of the form M(E₁ …E_m) the task of type inference is to find unique type arguments S₁…S_n for each of the type parameters X₁…X_n so that the call M1…S_n>(E₁…E_m)becomes valid.

The whole algorithm is quite well documented but it's kind of long to post it here. So here's a link to download the language spec.

https://msdn.microsoft.com/en-us/library/ms228593(v=vs.120).aspx