How does Linq work (behind the scenes)?

Question

I was thinking about making something like Linq for Lua, and I have a general idea how Linq works, but was wondering if there was a good article or if someone could explain how C# makes Linq possible

Note: I mean behind the scenes, like how it generates code bindings and all that, not end user syntax.

Answer 1

It's hard to answer the question because LINQ is so many different things. For instance, sticking to C#, the following things are involved:

• Query expressions are "pre-processed" into "C# without query expressions" which is then compiled normally. The query expression part of the spec is really short - it's basically a mechanical translation which doesn't assume anything about the real meaning of the query, beyond "order by is translated into OrderBy/ThenBy/etc".
• Delegates are used to represent arbitrary actions with a particular signature, as executable code.
• Expression trees are used to represent the same thing, but as data (which can be examined and translated into a different form, e.g. SQL)
• Lambda expressions are used to convert source code into either delegates or expression trees.
• Extension methods are used by most LINQ providers to chain together static method calls. This allows a simple interface (e.g. IEnumerable<T>) to effectively gain a lot more power.
• Anonymous types are used for projections - where you have some disparate collection of data, and you want bits of each of the aspects of that data, an anonymous type allows you to gather them together.
• Implicitly typed local variables (var) are used primarily when working with anonymous types, to maintain a statically typed language where you may not be able to "speak" the name of the type explicitly.
• Iterator blocks are usually used to implement in-process querying, e.g. for LINQ to Objects.
• Type inference is used to make the whole thing a lot smoother - there are a lot of generic methods in LINQ, and without type inference it would be really painful.
• Code generation is used to turn a model (e.g. DBML) into code
• Partial types are used to provide extensibility to generated code
• Attributes are used to provide metadata to LINQ providers

Obviously a lot of these aren't only used by LINQ, but different LINQ technologies will depend on them.

If you can give more indication of what aspects you're interested in, we may be able to provide more detail.

If you're interested in effectively implementing LINQ to Objects, you might be interested in a talk I gave at DDD in Reading a couple of weeks ago - basically implementing as much of LINQ to Objects as possible in an hour. We were far from complete by the end of it, but it should give a pretty good idea of the kind of thing you need to do (and buffering/streaming, iterator blocks, query expression translation etc). The videos aren't up yet (and I haven't put the code up for download yet) but if you're interested, drop me a mail at [email protected] and I'll let you know when they're up. (I'll probably blog about it too.)

Answer 2

Mono (partially?) implements LINQ, and is opensource. Maybe you could look into their implementation?