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

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

Answer 2

Read this article:

Learn how to create custom LINQ providers

Answer 3

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 4

Perhaps my LINQ for R6RS Scheme will provide some insights.

It is 100% semantically, and almost 100% syntactically the same as LINQ, with the noted exception of additional sort parameters using 'then' instead of ','.

Some rules/assumptions:

• Only dealing with lists, no query providers.
• Not lazy, but eager comprehension.
• No static types, as Scheme does not use them.

My implementation depends on a few core procedures:

• map - used for 'Select'
• filter - used for 'Where'
• flatten - used for 'SelectMany'
• sort - a multi-key sorting procedure
• groupby - for grouping constructs

The rest of the structure is all built up using a macro.

Bindings are stored in a list that is tagged with bound identifiers to ensure hygiene. The binding are extracted and rebound locally where ever an expression occurs.

I did track the progress on my blog, that may provide some insight to possible issues.

Answer 5

Matt Warren's blog has all the answers (and a sample IQueryable provider implementation to give you a headstart):

http://blogs.msdn.com/mattwar/

Answer 6

For design ideas, take a look at c omega, the research project that birthed Linq. Linq is a more pragmatic or watered down version of c omega, depending on your perspective.