This will be my last post before I head off for my annual vacation in Canada; see you again in September for more Fabulous Adventures in Coding!

Last time on FAIC I suggested a rule for translating nested “from” query expressions into a much simpler form than the C# specification requires. Why does the C# specification not use my simplified form?

In fact what I showed yesterday is pretty close to what the LINQ translation rules for SelectMany queries looked like shortly before shipping C# 3.0. The problem with it becomes apparent when you consider the following:

from q in items
from r in a(q)
from s in b(q, r)
from t in c(q, r, s)
from v in d(q, r, s, t)
select e(q, r, s, t, v)

How is this translated in the scheme I laid out last time? We apply the SelectMany rule four times and the Select rule once to obtain:

items.SelectMany(
  q => a(q).SelectMany(
    r => b(q, r).SelectMany(
      s => c(q, r, s).SelectMany(
        t => d(q, r, s, t).Select(
          v => e(q, r, s, t, v))))))

The range variables are all in scope exactly where they need to be and this query has the desired semantics so we’re good on that front. But now consider the problem that overload resolution has to solve. Go back and read my 2007 article on overload resolution problems for nested lambdas. I’ll wait.

Welcome back. Now you know that since there are in fact four SelectMany overloads and two Select overloads we have to consider all 4 x 4 x 4 x 4 x 2 possibilities, which is only 512; that’s totally doable. But now suppose that we wanted a query like this nested ten or fifteen deep: the number of possibilities that have to be evaluated grows exponentially. Also, even if we limited the number of overloads in LINQ-to-objects, there might be many overloads in other LINQ pattern implementations.

The C# testing and development team quickly discovered that even simple, realistic queries that had a lot of nested from clauses could cause the IDE to bog down or the compiler to run out of memory.

This was the problem we faced before C# 3.0 shipped. Let’s take a step back here, and remember the problem we’re trying to solve. We need to have all those range variables in scope in the right places, but now we want to do so without nesting any lambdas. Therefore we need a new scoping mechanism. Transparent identifiers are that mechanism! In a world where we have transparent identifiers, we do the translation as follows:

from q in items
from r in a(q)
from s in b(q, r)
from t in c(q, r, s)
from v in d(q, r, s, t)
select e(q, r, s, t, v)

first becomes

from * in items.
  SelectMany(
    q => a(q), 
    (q, r) => new {q, r})
from s in b(q, r)
from t in c(q, r, s)
from v in d(q, r, s, t)
select e(q, r, s, t, v)

which becomes

from ** in items.
  SelectMany(
    q => a(q), 
    (q, r) => new {q, r}).
  SelectMany(
    * => b(q, r), 
    (*, s) => {new {*, s}))
from t in c(q, r, s)
from v in d(q, r, s, t)
select e(q, r, s, t, v)

I’ll skip a few steps; you see how this goes. We end up with:

items.
  SelectMany(
    q => a(q), 
    (q, r) => new {q, r}).
  SelectMany(
    * => b(q, r), 
    (*, s)=>{new {*, s})).
  SelectMany(
    ** => c(q, r, s), 
    (**, t) => new {**, t})).
  SelectMany(
    *** => d(q, r, s, t), 
    (***, v) => e(q, r, s, t, v))

And now we desugar all the transparent identifiers:

items.
  SelectMany(
    q => a(q), 
    (q, r) => new {q, r}).
  SelectMany(
    d1 => b(d1.q, d1.r),
   (d1, s) => {new {d1, s})).
  SelectMany(
    d2 => c(d2.d1.q, d2.d1.r, d2.s),
   (d2, t) => new {d2, t})).
  SelectMany(
    d3 => d(d3.d2.d1.q, d3.d2.d1.r, d3.d2.s, d3.t), 
    (d3, v) => e(d3.d2.d1.q, d3.d2.d1.r, d3.d2.s, d3.t, v))

And hey presto, no nested lambdas, so this can be resolved very quickly with overload resolution.

This same technique was then applied to let and join clauses which introduce new range variables, to ensure that they did not also cause big blowups in the amount of lambda nesting during translations.