Chapter 4. C# 3.0 Technical Overview
LINQ is built on a set of language features included in C# 3.0 and C# 2.0. Each feature was carefully crafted to fulfill a vision. The purpose of this chapter is to describe all these key features and to show exactly how they align to make LINQ possible.
LINQ to Objects can be used to query the collections found in the System.Collections.Generic namespace. These include List<T>, Stack<T>, LinkedList<T>, Queue<T>, HashSet<T>, and Dictionary<TKey, Value>. One particular C# type, IEnumerable<T>, is implemented by all these classes and plays an especially important role in LINQ to Objects. One of the purposes of this chapter is to explain how IEnumerable<T> and iterators contribute to the LINQ architecture.
Although LINQ to Objects has pride of place in this chapter, the lessons you learn also apply to LINQ to SQL and LINQ to XML. In truth, the changes you can run on IEnumerable<T> and the other features covered in this chapter apply to any version of LINQ.
Toward the end of the chapter, I relax the focus a bit and allow the text to zoom out far enough to encompass LINQ to SQL and expression trees. With the inclusion of this final subject, this chapter can stand on its own as a complete description of the LINQ architecture.
C# 2.0 and 3.0 Features Related to LINQ
The following technologies are covered in this chapter:
• Partial methods
• Automatically implemented properties
• Collection initializers
• Object initializers
• Type inference
• Anonymous types
• Generic methods, delegates, and lambda expressions
• Extension methods
• Scoping issues
• IEnumerable<T> and iterator blocks
• Deferred execution
• Overriding LINQ operators
• Expression trees
The first four features are only tangentially related to LINQ, but they are new to C# 3.0 and are used throughout this book and in much of the LINQ code you encounter. Because they are easy to explain and easy to understand, I’ve decided to include a brief description of them in this chapter for the sake of completeness. These features help you write code that is both concise and easy to understand.
Partial Methods
Partial methods are a C# 3.0 feature that help developers modify autogenerated code without fearing that their changes will be overwritten if the code is regenerated. In Visual Studio 2008, they are used by the Object Relational Designer and SqlMetal, two tools that play an important role in LINQ to SQL development. Although code generation is the primary scenario for partial methods, they are now a standard feature of the C# language, and developers can use them when and where they want.
Partial methods allow developers to reserve a name for a method that can optionally be implemented by consumers of their code. They are declared inside partial classes, as shown in Listing 4.1.
Listing 4.1. A Simple Example of a Partial Method
using System;
using System.IO;
namespace AbstractMethod
{
public partial class MyPartialClass
{
partial void MyPartialMethod();
public void WriteFile(string fileName, string contents)
{
using (TextWriter textWriter = new StreamWriter(fileName))
{
textWriter.Write(contents);
}
MyPartialMethod();
}
}
public partial class MyPartialClass
{
partial void MyPartialMethod()
{
Console.WriteLine("File written");
}
}
class Program
{
static void Main(string[] args)
{
MyPartialClass m = new MyPartialClass();
m.WriteFile(@".data.txt", "passaddhi");
}
}
}
Notice that MyPartialClass is declared as partial, as is MyPartialMethod:
partial void MyPartialMethod();
In the first declaration of MyPartialClass, MyPartialMethod appears as a header and as a call in the method called WriteFile. Note, however, that MyPartialMethod is not implemented in this first declaration for MyPartialClass. In effect, this is an invitation to the developer to implement this method if desired in a second declaration for MyPartialClass. In our case, the invitation provides consumers of this class with the opportunity to extend the method called WriteFile. The invitation is called a defining partial method declaration.
If the developer accepts the invitation and creates the second half of MyPartialClass and includes an implementation of MyPartialMethod, the implementation is compiled into the code. At runtime, it is called by the WriteFile method in the first part of this partial class. The implementation of the method is called an implementing partial method declaration.
If the developer decides to decline the invitation, the declaration of MyPartialMethod and the code to call it are optimized out of the program by the compiler, causing all traces of MyPartialMethod to disappear. This ensures that no unnecessary overhead results when partial methods are used.
Suppose the first of the two partial classes shown in Listing 4.1 were autogenerated. The developer would be free to rerun the designer that created the first part of MyPartialClass without fear that this action would overwrite the code in the developers’ implementation of the second half of MyPartialClass. It also allows the developer to work with a relatively small implementation of MyPartialClass that contains only a few methods, without needing to wrestle with the potentially long and complex listings that are often found in autogenerated code.
Although partial methods are easy to use, a number of rules govern their use. Partial methods
• Must be declared inside a partial class.
• Must not return a type. Their declarations contain the keyword partial followed by the keyword void. partial is a contextual keyword and can be used as a regular variable if it is not followed by void.
• Cannot be marked as extern.
• Can be marked static or unsafe.
• Can be generic.
• Can have ref parameters, but not out parameters.
• Cannot be referenced as a delegate until they are implemented.
• Cannot have access modifiers such as public, private, or internal. Partial methods are implicitly marked as private. This means that they cannot be called from outside the partial class and cannot be declared as virtual.
• Can be implemented in the same half of a partial class in which it is defined, although this is not a common practice.
Although partial methods are primarily designed as a tool for use with autogenerated code, there may be occasions when you would want to use this technology in your own code, giving consumers of your objects a place where they can hook into events in your class. For instance, in Listing 4.1 the WriteText method uses a partial method as a means of broadcasting a notification that a text file is being written. Although there are other ways to perform this same task, this is a useful technique whether or not code is autogenerated.
Automatically Implemented Properties
Automatic properties were touched on briefly in Chapter 2, “Getting Started.” Here the subject is explored in more depth.
Automatically implemented properties are a convenience. They are valuable because their syntax is concise. Consider the simple class shown in Listing 4.2, which contains two properties declared with the new syntax.
Listing 4.2. Using the C# 3.0 Feature Called Automatic Properties
class Operator
{
public int OperatorId { get; set; }
public string OperatorName { get; set; }
}
Both OperatorId and OperatorName are automatic properties. They are a shorthand way of telling the compiler that you want it to automatically generate the most obvious, default implementation for your property. Notice that their getters and setters have no explicit implementation. When you declare properties in this manner, the C# compiler automatically generates backing fields and fully implemented accessors behind the scenes. You never see the getters and setters, and you cannot see or access the backing fields.
You can use the prop snippet to help you quickly declare an automatic property. Just type prop and then press Tab twice.
The Operator class just shown is roughly semantically equivalent to the C# 2.0 code shown in Listing 4.3. Automatic properties are an alternative to the C# 2.0 syntax; they do not eclipse or replace it.
Listing 4.3. C# 2.0-Style Properties Have Fully Implemented Getters and Setters and an Explicitly Declared Backing Field
class Operator
{
private int operatorId;
private string operatorName;
public int OperatorId
{
get
{
return operatorId;
}
set
{
operatorId = value;
}
}
public string OperatorName
{
get
{
return operatorName;
}
set
{
operatorName = value;
}
}
}
The patterns followed in Listing 4.3 are repeated often in production C# code. This syntax is valuable because it allows developers to add validation code, or side effects, to their getters and setters. Nevertheless, they frequently use the default implementation shown a moment ago. Automatic properties are simply a shorthand means of writing the default implementation. They make your code more concise and, hence, easier to read and maintain.
To get a deeper understanding of automatic properties, focus for a moment on just the declaration for OperatorId:
public int OperatorId { get; set; }
Reflector shows that the compiler generates the code shown in Listing 4.4 behind the scenes when you create the OperatorId property.
Reflector is a free third-party tool you can download from http://www.aisto.com/roeder/dotnet/. It can sometimes be used to translate IL into standard C# code, thus giving you a peek behind the scenes in a C# program.
Listing 4.4. The Code Generated by Reflector for an Automatic Property
[CompilerGenerated]
private int <OperatorId>k__BackingField;
public int OperatorId
{
[CompilerGenerated]
get
{
return this.<OperatorId>k__BackingField;
}
[CompilerGenerated]
set
{
this.<OperatorId>k__BackingField = value;
}
}
This code is similar to a C# 2.0-style property. The big difference is the presence of the [CompilerGenerated] attribute and the funny-looking name of the backing field: <OperatorId>k__BackingField. This name is not a valid C# identifier, but it is a valid CLR identifier. Because these are not valid C# names, you are unable to access these fields in your own C# code. This was an intentional decision, but it is not inconceivable that the team may provide access to these backing fields in some future version of C#.
About the Code Generated by Reflector
The [CompilerGenerated] attribute simply marks code so that certain tools can choose to ignore it.
The use of invalid C# identifiers for variable names is a theme that will recur throughout this chapter. I’ll show you the Reflector code for them in only this one case, but that tool can be useful when working with the code seen in several sections of this chapter.
You must keep in mind a few caveats when working with automatic properties:
• You must declare both a getter and setter.
• Because you do not have access to the backing field, read-only and write-only properties would not be useful, so they are not allowed. You can, however, place the public or private modifiers before one of the two accessors.
• You should not use automatic properties as an excuse not to include validation code or other safety checks in your program. If you need getters and setters, you should implement them.
Here is an example of placing the modifier private before your setter:
public int Data { get; private set; }
Technically there is a difference between having a private setter and creating a read-only property, but in practice the difference is not significant.
The following code will not compile because both accessors have modifiers:
public int Data { protected get; private set; }
This code will not compile because it does not contain both a setter and a getter:
public int Data { get; }
The following property would be a poor candidate for an automatic property because it contains validation code that could not be easily implemented with automatic properties:
private int data;
public int Data
{
get
{
if (data <= -5)
{
throw new Exception("Data has an invalid range");
}
return data;
}
set
{
data = value;
}
}
In general, automatic properties are a simple feature, designed to help you get more work done with less code. Use them with care, but use them.
Initializers
C# 3.0 includes two new ways to initialize the elements of a collection or the fields and properties of an object. These techniques, called collection initializers and object initializers, are designed to help you write a more declarative style of code that is more succinct, easier to read, and easier to maintain. Again, you were introduced to these topics earlier in the book, but they are covered in more depth here. Later in this chapter, you will read about anonymous types, which use a technology closely related to object initializers.
Collection Initializers
Collection initializers save typing and make code more readable. They provide a means of quickly initializing any collection that implements System.Collections.IEnumerable and includes an Add method. Consider this code fragment that creates and initializes a simple collection:
List<string> list = new List<string>();
list.Add("LINQ");
list.Add("query");
list.Add("adventure");
Because List<T> implements IEnumerable and has an Add method, you can use collection initializers to condense these four lines into one:
List<string> list = new List<string> { "LINQ", "query", "adventure" };
The same simple technique can be used to initialize an array of integers:
List<int> list1 = new List<int> { 1, 2, 3, 4 };
In either case, you can optionally include parentheses for a call to the default constructor:
List<int> list2 = new List<int>() { 1, 2, 3, 4 };
Of course, other types have elements that can be initialized with this syntax. Here is how to use collection initializers with the Dictionary class:
var myDictionary = new Dictionary<string, string>()
{
{ "var", "type inference" },
{ "range variable", "Found in query expression after the word from" }
};
if (myDictionary.ContainsKey("range variable"))
{
Console.WriteLine(myDictionary["range variable"]);
}
A SortedList works almost exactly the same way. Only the name of the object to be created differs:
SortedList<string, string> sortedList = new SortedList<string, string>();
The rest of the code is identical.
Here is how to initialize and use HashSets:
HashSet<int> hash1 = new HashSet<int> { 1, 2, 3 };
HashSet<int> hash2 = new HashSet<int> { 3, 4, 5 };
hash1.IntersectWith(hash2);
foreach (var item in hash1)
{
Console.WriteLine(item); // Write the number 3
}
You would not be able to use collection initializers with a Queue<T>, LinkedList<T>, or Stack<T>, because they have no Add methods. Here, for instance, is an attempt to use collection initializers with a Stack:
Stack<int> stack = new Stack<int>() { 1, 2, 3 };
This code fails with the following error:
System.Collections.Generic.Stack<int>' does not contain a definition
for 'Add.'
The important case of initializing a collection with a set of objects is shown in the next section.
In general, collection initializers are useful, easy to implement, and without significant drawbacks. It is recommended that you use them whenever possible.
Object Initializers
C# 3.0 also provides a concise way to initialize one or more of the properties or fields of an object. Consider the Operator class declared in the section called Automatically Implemented Properties:
class Operator
{
public int OperatorId { get; set; }
public string OperatorName { get; set; }
}
Regardless of whether you used automatic properties, you can now initialize an instance of the Operator class with this simple syntax:
Operator o = new Operator() { OperatorId = 1, OperatorName = "Where" };
Compare this with the old style of object initialization:
Operator o = new Operator();
o.OperatorId = 1;
o.OperatorName = "Where";
Clearly the new style is more succinct.
You may combine object and collection initializers in a single statement:
private List<Operator> OperatorList;
private void CreateLists()
{
// Collection initializer
OperatorList = new List<Operator>
{
new Operator() { OperatorId = 1, OperatorName = "Where" },
new Operator() { OperatorId = 2, OperatorName = "Select" },
new Operator() { OperatorId = 3, OperatorName = "SelectMany" }
};
Console.WriteLine(OperatorList[1].OperatorName);
}
This code folds three object initializers inside a collection initializer. Declarative syntax of this kind is both orderly and concise.
You can pass in parameters to the constructor of an object when using object initializers, and you can omit any properties you don’t want to initialize:
class Operator
{
public Operator() { }
public Operator(int i) { OperatorId = i; }
public int OperatorId { get; set; }
public string OperatorName { get; set; }
public override string ToString()
{
return (string.Format("Id = {0}, Op = {1}",
OperatorId, OperatorName));
}
}
class Program
{
static void Main(string[] args)
{
Operator o = new Operator(1) { OperatorName = "Where" };
System.Console.WriteLine(o);
}
}
The initialization code in the Main method explicitly uses the OperatorName property. The same line of code calls a constructor of class Operator that takes the integer value 1 to initialize the OperatorId. I’ve also added an optional ToString method that is used in the call to WriteLine. I’ve added it simply in the hopes that it will better help those who type in the code to understand what is happening. Try changing the call to the constructor to pass in the number 2, and then check the result:
Operator o = new Operator(2) { OperatorName = "Where" };
Types in C# 3.0
C# 3.0 introduced two major changes to the type system. One is type inference, which allows the compiler to automatically infer the type of a variable. The other is anonymous types, which allows you to declare a new type without explicitly giving it a name. Both of these features play a significant role in LINQ.
Type Inference
The var keyword tells the compiler to use type inference to determine the type of a variable. The developer never explicitly states the type of these variables; instead, it is up to the compiler to infer their type based on their context.
Consider the following simple statements:
var i = 2;
i = "LINQ is strongly typed."; // An error is generated by this line.
The first line uses type inference to determine the type of the variable i. The literal value 2 is of type System.Int32, so the compiler infers that i is an integer.
C# has always been a strongly typed language, and type inference does nothing to change this state of affairs. The second line of code shown here illustrates this fact. In the first line, the compiler infers that the type of i must be an int. C# does not allow assigning a string to an int. As a result, the second line of code creates a compile-time error stating that the compiler cannot implicitly convert type string to int. The lesson: Inferred types are strongly typed.
Do not use type inference unless you have a need for it, or if a developer reading the code could not possibly be confused about its type. As you will see later in this chapter, LINQ query expressions are one place where type inference is needed. However, on other occasions you can safely choose to use it. Consider the following code:
List<int> list = new List<int> { 1, 2, 3 };
This code repeats the declaration for List<string>. Use type inference to remove the repetition:
var list = new List<int> { 1, 2, 3 };
This code is arguably cleaner and easier to read.
The following code compiles cleanly but is probably not a good candidate for type inference:
public static List<int> GetList()
{
return new List<int> {1, 2, 3};
}
static void Main(string[] args)
{
var list = GetList();
}
The compiler will have no problem determining that list is of type List<int>, but a developer browsing the code might become confused, particularly in a large, complex program. As a result, it is probably best to explicitly declare the type of the list returned by the call to GetList:
List<int> list = GetList();
You cannot use type inference in the parameters of a method or in the return type of a method:
public var MyMethod(var myParameter) // generates two errors
{
}
In the cases shown here, the compiler complains, stating:
The contextual keyword 'var' may only appear within a local variable
declaration.
Because var is a contextual keyword, the following compiles cleanly, and the word var is treated as a standard identifier, not as a keyword:
string var = "Sam";
Console.WriteLine(var);
The subjects of type inference and anonymous types are interrelated. As a result, you will read more about type inference in the next section. In particular, you will see that in the case of anonymous types, type inference is not just useful, but a necessity.
Anonymous Types
Anonymous types provide a shorthand means of creating read-only classes with a few simple properties. They are both a new type and a form of initializer. Anonymous types play an important role in LINQ.
Consider the following statement, which declares and initializes an anonymous type:
var mountain = new { Name = "Rainier", Height = 4392, State = "WA" };
This statement has three parts:
• On the right is an object initializer.
• In the middle is the keyword new.
• On the left, type inference is used to determine the type of the identifier mountain.
Note that there is no type declaration between the word new and the opening curly brace:
var mountain = new [No Type Name Appears Here]{ Name = ... };
Anonymous types get their name because they are never explicitly named.
In the preceding section, you saw cases when type inference is useful. Here is a case when it is a necessity. It is not possible to declare the variable mountain without using type inference, because we do not, and cannot, know or write the name of its type at compile time. From the point of view of a C# developer, anonymous types have no name, just as we cannot know the name of a backing field for an automatic property. In the background, a “funny-looking” name is generated like those we saw in the backing fields for automatic properties. But this name is not valid C# code and cannot be known by C# developers at design time.
You can, however, learn the name of an anonymous class by calling getType at runtime:
foreach (var CityAndContact in query)
{
Console.WriteLine(CityAndContact.GetType().ToString());
}
You can also view the type name in Reflector. However, very little can be gained by learning the name, because it is not valid C# code. It is primarily of academic interest.
When it creates an anonymous class like the one shown here, the C# compiler fully and properly implements the ToString(), Equals(), GetHashCode(), and GetType() methods. You will never see this class, but the pseudocode in Listing 4.5 gives you a very general sense of what it looks like. (You can use Reflector to learn more details.)
Listing 4.5. The Compiler Generates Code for Your Anonymous Classes That Looks Something Like the Pseudocode Shown in This Listing
class SomeUnknownFunnyLookingNameNotValidInCSharp
{
public string Name { get;}
public int Height { get; }
public string State { get; }
public override string ToString()...
public int GetHashCode() ...
public Type GetType() ...
bool Equals(object obj) ...
}
Note that the properties are read-only. I include GetType in this pseudocode because it is properly implemented even though it is not really overridden. Finally, remember that you can’t use var in the parameter list or the return type of a method, so you can use this class only within the scope of the current method. There is usually no way to pass it to another method or give it broader scope.
In his review of this text, Nick Paldino found exceptions to the rule I just stated. His comments on the subject are clear, so I’ll include them almost exactly as he presented them to me: You can pass an anonymous type out of a method by passing it as type Object, and Reflection will be able to parse it. Anders Hejlsberg gave a presentation at the MVP summit in 2007 that bound the output of an anonymous type to a DataGridView; he could do that because the DataGridView uses reflection to get the information on the type. Also, the extension methods that LINQ uses actually are outside of the method. When anonymous types are used, they are passed to the Select<T> extension method on the Enumerable class. Technically, that is a means of passing an anonymous type out of a method.
Anonymous types are also used in LINQ queries. Consider this LINQ to Objects code fragment borrowed from one of the samples in Chapter 2:
var query = from c in Customers
where c.City == "London"
select new { c.City, c.CompanyName };
The select clause contains an anonymous type. You could create your own type and use it instead, but it is a common and useful practice to write code like that shown here.
Because this LINQ query uses an anonymous type, developers must use type inference to declare its return type. In the section “Composable” in the preceding chapter, you learned that query expressions both return and operate on instances of IEnumerable<T>. In this case T is some anonymous type with two fields of type string. This means that again we must use type inference to declare the identifier query. Without type inference, code of this type would not be possible.
Consider this code fragment, which operates on the variable returned from the query we are studying:
foreach (var x in query)
{
Console.WriteLine(x);
}
In the current context, x is an anonymous type, so again it would be impossible to declare it explicitly. This is yet another case where we could not go forward if type inference did not exist.
Even if we could explicitly declare the type used in this foreach statement, it would probably cause us more trouble than it would be worth. The problem is that the type of x could easily change if we made small changes to the query expression from which it is derived. In complex LINQ queries, especially those that use composability, this could cause a cascading series of changes. All of this is avoided by using the keyword var and type inference.
In this section you have learned about anonymous types and type inference. You have seen that these subjects are inextricably linked, because only rarely can you make use of anonymous types without also needing to use type inference.
Generic Methods, Delegates, and Lambdas
Lambdas are important both as a stand-alone C# 3.0 feature and as a significant part of the LINQ architecture. The C# 2.0 technologies called delegates and generic methods serve as stepping-stones and building blocks for lambdas. Thus, I will cover them first and then focus on lambdas. I will also briefly mention a C# 2.0 technology called anonymous methods that has been eclipsed by lambdas.
Delegates
Delegates provide a means of declaring a variable that references an individual method. Developers can invoke the delegate, and the delegate, in turn, calls the method it references. Because the delegate is just a variable, you can pass it to other methods and perform similar tricks with it that would otherwise be impossible.
In many other languages, delegates are called and implemented as function pointers. In C#, however, a delegate is implemented as a class, rather than as a pointer. The advantage of this system is that you can fully type-check a class, whereas a pointer is less type-safe.
Consider the code shown in Listing 4.6. It shows a simple delegate type called MyDelegate, used to reference the Add method.
Listing 4.6. A Simple Delegate
using System;
namespace SimpleLambda
{
class Program
{
public delegate int MyDelegate(int a, int b);
public static int Add(int a, int b)
{
return a + b;
}
public static void CallDelegate(MyDelegate func)
{
Console.WriteLine(func(272, 153));
}
static void Main(string[] args)
{
MyDelegate myDelegate = Add;
Console.WriteLine(myDelegate(271, 152));
CallDelegate(myDelegate);
}
}
}
Before we examine this code in depth, let’s take a moment to simply describe what it does. The code defines a delegate type that has the same signature as the Add method. An instance of this delegate type is used to call the Add method. The same instance is then passed to another method that, in turn, calls the Add method.
Now let’s step back and examine the code in more depth. We first need to declare a type that is compatible with the Add method:
public delegate int MyDelegate(int a, int b);
Notice that this type has the same signature as the Add method:
public static int Add(int a, int b)
Both declarations are for a type that takes two integers and returns an integer. This is why it is possible to assign the Add method to an instance of MyDelegate:
MyDelegate myDelegate = Add;
After this assignment is made, a call to the myDelegate variable translates into a call to the Add method. For instance, the following call returns the sum of 271 and 152, which is 423:
myDelegate(271, 152);
The code I’ve shown here is valid shorthand for the following syntax, which is actually generated behind the scenes:
MyDelegate myDelegate = new MyDelegate(Add);
I believe, however, that it is easier to read and understand delegates if you use the shorthand without calling new.
To pass around delegate instances, we must first declare a method that takes our delegate as a parameter:
public static void CallDelegate(MyDelegate myDelegate)
{
myDelegate(272, 153);
}
As you would expect, calls to the MyDelegate instance resolve to calls to the Add method and thus return the value 425 in this case. Here is how you call this method:
MyDelegate myDelegate = Add;
CallDelegate(myDelegate);
We will use delegates in LINQ, but you should understand that they existed before LINQ and have value in their own right. In particular, a commonly used pattern for sorting data uses delegates. When implementing this pattern, consumers of a hypothetical sort routine pass in a delegate, which a user defines to compare two items and decide which is “larger”:
public void Sort<T>(CompareDelegate compare, List<T> items);
Users of this method define their own implementation of compare, which, in turn, is called by the Sort routine. Please recall that I’m providing this example simply to illustrate that delegates have practical uses outside of LINQ. It is not really that important that you understand the particular example I show here.
In this section you saw that delegates consist of two parts—a delegate type and a delegate instance. You learned how to declare delegates and how to use them to call a method and pass a reference to a method. This is just enough information to ensure that you can understand the role they will play in LINQ. I have not, however, covered other aspects of delegates, such as their role in C#’s event processing.
Generic Delegates
Before we cover lambdas, you need to understand one other C# 2.0 technology. Generic methods are one of the most powerful features of the C# language, and they play a key role in LINQ. Let’s take a moment to be sure you know how they work.
As things stand, our MyDelegate type can work with any routine that takes two integers and returns an integer:
public delegate int MyDelegate(int a, int b);
This delegate would be considerably more flexible if it worked with all routines that took two parameters of any type and returned a parameter of any type. If we had that ability, this delegate would no longer be confined to use with methods that accepted and returned integers. It could, for instance, be used with methods that accepted and returned doubles, or that accepted integers and returned a long.
Here is how to declare a generic delegate that does exactly that:
public delegate TResult MyDelegate<T1, T2, TResult>(T1 a, T2 b);
To understand this code, we need to break it into two parts. Look at the following pseudo-declaration, and you will see that it still has the same general signature as the Add method: it takes two parameters and returns a parameter:
public delegate TResult MyDelegate(T1 a, T2 b);
The problem here is that we don’t know the type of T1, T2, and TResult. C# solves that problem by providing a place where you can declare the types of the parameters used by this delegate:
public delegate TResult MyDelegate<T1, T2, TResult>(T1 a, T2 b);
Notice the funny-looking syntax after the word MyDelegate: <T1, T2, TResult>. This is a place where you can pass in type parameters that define what types you want to work with when you declare an instance of this type:
MyDelegate<int, int, int> myDelegate = Add;
This declaration declares the types of T1, T2, and TResult as integers, thus resolving the ambiguity that is inherent in the generic declaration of MyDelegate. In particular, it states that T1 maps to an integer, T2 to an integer, and TResult to an integer. In effect, it transforms, through substitution, our generic declaration for MyDelegate back into a standard method declaration. We start with this declaration:
public delegate TResult MyDelegate<T1, T2, TResult>(T1 a, T2 b);
T1, T2, and TResult are mapped to the type int, and somewhere behind the scenes we end up with this declaration:
public delegate int MyDelegate(int a, int b);
A delegate of this type is compatible with our Add method.
Let me show a second example to help further illustrate how this works. Instead of working with integers, we could have used doubles:
public static double AddDoubles(double a, double b)
{
return a + b;
}
MyDelegate<double, double, double> myDelegate = AddDoubles();
In this case the delegate would be transformed behind the scenes as follows:
public delegate double MyDelegate(double a, double b);
These substitutions take place at compile time and have no effect on the runtime performance of your code. Note also that I had to create a new standard method called AddDoubles that was compatible with our new delegate.
A generic declaration for a delegate is so flexible that you can easily imagine a small set of such declarations that would cover nearly every function any reasonable developer would be likely to declare. This is an excellent opportunity to employ the 80 percent rule: Most functions that return a value take between zero and four parameters. Stick with those five cases, and safely ignore the rare method that takes more than four parameters. Or rather, you can leave it for the developer to declare any such declaration should he or she need it.
The developers of C# have done exactly that—they have declared two sets of delegates in the System namespace. One set called Func returns a value, and another set called Action does not. Here are the ones that do return a value:
public delegate TResult Func<TResult>();
public delegate TResult Func<T, TResult>(T a);
public delegate TResult Func<T1, T2, TResult>(T1 a, T2 b);
public delegate TResult Func<T1, T2, T3, TResult>(T1 a, T2 b, T3 c);
public delegate TResult Func<T1, T2, T3, T4, TResult>(T1 a, T2 b, T3 c,
T4 d);
Here are the declarations for the type that do not return a value:
public delegate void Action();
public delegate void Action<T>(T a);
public delegate void Action<T1, T2>(T1 a, T2 b);
public delegate void Action<T1, T2, T3>(T1 a, T2 b, T3 c);
public delegate void Action<T1, T2, T3, T4>(T1 a, T2 b, T3 c, T4 d);
Given the presence of these declarations in the System namespace, we can modify our program as shown in Listing 4.7.
Listing 4.7. Using the Predeclared Func Delegates
using System;
namespace SimpleLambda
{
class Program
{
public static int Add(int a, int b)
{
return a + b;
}
public static void CallDelegate(Func<int, int, int> func)
{
Console.WriteLine(func(271, 152));
}
static void Main(string[] args)
{
Func<int, int, int> myDelegate = Add;
Console.WriteLine(myDelegate(271, 152));
CallDelegate(myDelegate);
}
}
}
The declaration of our delegate has been deleted and replaced with the Func<T1, T2, TResult> declaration from the System namespace. Otherwise, the code is the same as that found in Listing 4.7.
The last two sections have focused only on the features of generic methods and generic delegates that are directly applicable to LINQ. More could be said about this subject, but that information would be outside the scope of this book.
Lambdas
Lambdas are a simple technology with an intimidating name. They sound like they will be difficult to understand, but in practice they are relatively trivial.
For reasons that will become clear later in this chapter, LINQ has an almost inordinate need for its users to declare a large number of small, simple delegates. The architects of C# decided that forcing the users of LINQ to declare delegates using the syntax shown in the previous two sections was too verbose. They wanted to find a shorter, more concise way to accomplish the same task.
The syntax they settled on looks like this:
Func<int, int, int> myLambda = (a, b) => (a + b);
This is a shorthand way of writing code that is roughly semantically equivalent to the following:
public static int Add(int a, int b)
{
return a + b;
}
Func<int, int, int> myDelegate = Add;
In the next few paragraphs I will compare these two ways of creating a delegate instance and explain how they map back and forth.
It is obvious that the left sides of the following two code fragments have the same meaning:
Func<int, int, int> myLambda = (a, b) => (a + b);
Func<int, int, int> myDelegate = Add;
But how can the right sides be the same?
The expression on the right side of the first statement is a shorthand way of writing a method that is semantically equivalent to the Add method. Just to be clear, a lambda is not a reference to the Add method; it is second method that does the same thing as the Add method.
Here is the lambda:
(a, b) => (a + b);
And here is the Add method:
public static int Add(int a, int b)
{
return a + b;
}
Here is the place in the Add method where we define the parameters it will take:
(int a, int b)
Here is the place in the lambda where we define the parameters it will take:
(a, b)
Here is the place in the Add method where we define what it will return:
return a + b;
Here is the place in the lambda where we define what it will return:
(a + b)
As you can see, a lambda and a method do the same thing: They define a set of parameters and an executable body of code.
The type declarations for a lambda are resolved using a technique very similar to the one we employ for generic methods and generic delegates. To see how this works, look again at the full declaration for the lambda:
Func<int, int, int> myLambda = (a, b) => (a + b);
The generic delegate Func says that the method being implemented takes two integers as parameters and returns an integer. The compiler takes this information and applies it to the lambda. Behind the scenes it resolves (a, b) to (int a, int b) and defines the function such that the body of the lambda (a + b) returns an integer. Thus, we give the compiler enough information to convert our lambda into a method that performs the same action as the Add method.
The => symbol is called a lambda operator and is usually pronounced “goes to.” Thus, the lambda just shown can be read as “a comma b goes to a plus b” or “a and b goes to a plus b.”
Although you will rarely need to do so, you can explicitly declare the type of parameters to a lambda expression:
Func<int, int, int> f = (int a, int b) => (a + b);
For void functions that do not return a value, just use an empty set of parentheses:
() => Console.WriteLine();
Lambdas have access to local variables:
public static void UseLocal()
{
int n;
Func<int> func = () => { n = 6; return n; };
n = func();
Console.WriteLine(n); // Outputs the number 6
}
You might be familiar with anonymous methods from C# 2.0. Semantically, anonymous methods and lambdas are identical, but the lambda syntax is easier to use. As a result, there is probably no reason for you to use anonymous methods in the future unless you find that their syntax makes your code pleasing or easier to read. Here are a lambda and anonymous method side by side:
Func<int, int, int> myLambda = (a, b) => (a + b);
Func<int, int, int> myAnonMethod = delegate(int a, int b)
{
return a + b;
};
Both methods take two integers, add them together, and return the result. Commenting further on anonymous methods at this point would serve no purpose, because lambdas create the same result with less work.
You saw earlier that the compiler generates “funny-looking” names that we never see for the backing fields of automatic properties, and for the classes created when we declare an anonymous type. A similar process is employed for lambdas. Behind the scenes, the compiler generates code that looks much like the Add method, but it gives the method a “funny-looking” name that is valid in the CLR but illegal—hence, by necessity, invisible—to the C# programmer.
Exercises
In the beginning of this section, I said that lambdas are easy to understand. To help reinforce that point, I’ve included a few quick exercises. When you have had an “aha!” moment when the idea behind lambdas becomes clear, you should find these exercises, and lambdas in general, very simple. Appendix A contains the answers.
1. As you have seen, the following lambda and method are semantically equivalent:
(a, b) => (a + b);
public int Add(int a, int b)
{
return a + b;
}
Given that this is the case, what is the lambda equivalent of the following method?
public int Subtract(int a, int b)
{
return a - b;
}
2. What lambda is semantically equivalent to this method?
public int Multiply(int a)
{
return a * 5;
}
3. What lambda is semantically equivalent to this method?
public void Display(string value)
{
Console.WriteLine(value);
}
4. What is the lambda equivalent of this method?
public void DisplayWarning()
{
Console.WriteLine("Warning");
}
5. What is the lambda equivalent of this method?
public decimal SimpleMath(int a, int b, int c)
{
return (a + b) / c;
}
6. What lambda is equivalent to this method?
public static long Add(int a, int b)
{
return a + (long)b;
}
Here is the declaration for a lambda and a statement that calls it:
Func<string, int, int, string> showMe =
(a, b, c) => string.Format(a, b, c, (b + c));
Console.WriteLine(showMe("{0} + {1} = {2}", 3, 5));
Lambdas provide you with a concise syntax for writing a method. They are valuable in large part because they are so short. This concision helps make possible the functional style of programming used in LINQ query expressions, where each expression is composed into a single, discreet entity with no external references. If this latter point does not yet make sense to you, simply focus on the fact that lambdas are useful because they are concise and short.
Extension Methods
Extension methods allow you to add optional functionality to an existing class or interface without modifying the class itself. Added in C# 3.0, extension methods appear to be instance methods of an object, but they are actually declared as static methods in a separate class.
Suppose you have an easy-to-use class with three methods. Much of the time, those three methods would provide all the power a developer needs from your class. But under certain circumstances, you might want the class to have more functionality. Before extension methods, there were three ways to solve this problem, each with its own drawbacks:
• Add the new methods to the existing class.
• Use inheritance to add the methods in a derived class.
• Use static methods.
Suppose you are working on a program that needs to test whether strings are valid abbreviations for a state. In this case, you can’t use option 1 for two reasons:
• You don’t have access to the source of class string.
• Even if you did have access to it, you might not want to add the weight and overhead of this feature to all strings—only to a subset of all strings.
Option 2, inheritance, might also be a bad choice:
• It would force developers who wanted your added functionality to use your type instead of normal strings.
• Even if they were willing to do that, it is not possible, because class string is sealed.
Because options 1 and 2 are unavailable, this leaves only option 3, which I have implemented in Listing 4.8.
Listing 4.8. Using a Static Method to Add the Functionality of the string Class
using System;
namespace ConsoleApplication1
{
public static class SpecialString
{
public static bool IsState(string source)
{
string[] stateCodes =
{"AL","AK","AZ","AR","CA","CO","CT","DE","DC",
"FL","GA","HI","ID","IL","IN","IA","KS","KY",
"LA","ME","MD","MA","MI","MN","MS","MO","MT",
"NE","NV","NH","NJ","NM","NY","NC","ND","OH",
"OK","OR","PA","RI","SC","SD","TN","TX","UT",
"VT","VA","WA","WV","WI","WY"};
if (source == null) return false;
source = source.ToUpper();
foreach (var item in stateCodes)
{
if (source == item)
{
return true;
}
}
return false;
}
}
class Program
{
public static void ShowTest(string state)
{
string format = "You entered: {0}. It is a state: {1}";
Console.WriteLine(format, state,
SpecialString.IsState(state));
}
static void Main(string[] args)
{
ShowTest("co");
ShowTest("WA");
ShowTest("AW");
ShowTest("AL");
ShowTest("NV");
ShowTest("NB");
ShowTest("MI");
}
}
}
The class SpecialString implements a static method named IsState. We access that class and our new method in the following line:
Console.WriteLine(format, state, SpecialString.IsState(state));
This is not such a bad solution, but it could be improved if we could write the following:
Console.WriteLine(format, state, state.IsState());
When placed side by side, it should be obvious that the second solution is more succinct than the first:
SpecialString.IsState(state)
state.IsState()
To enable the second syntax in C# 3.0, you need to make only one small change to your code. Here is the original declaration for the IsState method:
public static bool IsState(string source)
And here is the same code converted into an extension method:
public static bool IsState(this string source)
Simply add the keyword this to the method declaration to make the IsState method an extension of the string class. You can now write myString.IsState(). It’s that simple.
You can use IntelliSense to discover the IsState method, just as if it were a real instance method of SpecialString, as shown in Figure 4.1.
Figure 4.1. The variable state, which is of type string, appears to the developer to support an instance method called IsState.
It should come as no surprise to learn that behind the scenes the compiler converts the call into a static method call: SpecialString.IsState(myString). From the developer’s perspective, it appears to be like an instance method of type string, but behind the scenes it is a static method call. This is another place where the compiler takes code that you write and transforms it behind the scenes.
The SpecialString class has several traits that must be true if you want to use extension methods:
• The class must be declared to be static.
• The extension method must also be static.
• The first parameter of an extension method must include the this modifier, and it cannot be a pointer type.
• Extension methods cannot appear in generic classes.
Follow these guidelines, and you will find it easy to create extension methods.
Scoping Issues
You must keep in mind a few scoping rules when using extension methods. Problems with scoping and extension methods are rare, but when you encounter them, they are quite vexing.
An instance method is always called before an extension method. The compiler looks first for an instance method. If it finds an instance method with the right name and signature, it executes it and never looks for your extension method. The following code illustrates this problem:
using System;
namespace ConsoleApplication1
{
public class MyClass
{
public void DoThis()
{
Console.WriteLine("MyClass.DoThis");
}
}
public static class MyExtensions01
{
// Can never be called as if it were an instance method
// of MyClass.
public static void DoThis(this MyClass myClass)
{
Console.WriteLine("MyExtensions01.DoThis");
}
}
class Program
{
static void Main(string[] args)
{
MyClass myClass = new MyClass();
myClass.DoThis(); // Calls MyClass.DoThis
MyExtensions01.DoThis(myClass); // Calls
// MyExtensions01.DoThis
}
}
}
MyExtensions01.DoThis is a valid extension method for MyClass. However, it will never be called, because MyClass.DoThis always takes precedence over it unless you explicitly call it as a static method of MyExtensions01.
In cases where you have two extension methods with the same name, an extension method in the current namespace wins out over one in another namespace. Ambiguity becomes an issue, however, when you try to call two extension methods with the same name and signature in the same namespace, or in two different namespaces that are both used by the current namespace. Listing 4.9 gives an example of this problem.
Listing 4.9. This Code Does Not Compile Because the Compiler Finds the Call to DoThat Ambiguous
using System;
using System.Collections.Generic;
using System.Linq;
namespace ExtensionScope
{
public class MyClass
{
public void DoThis()
{
Console.WriteLine("Do this");
}
}
}
namespace Extensions01
{
using ExtensionScope;
public static class MyExtensions01
{
// Can never be called
public static void DoThis(this MyClass myClass)
{
Console.WriteLine("Do this");
}
public static void DoThat(this MyClass myClass)
{
Console.WriteLine("Do bop");
}
}
}
namespace Extensions02
{
using ExtensionScope;
public static class MyExtensions02
{
// Can never be called
public static void DoThis(this MyClass myClass)
{
Console.WriteLine("Do this");
}
public static void DoThat(this MyClass myClass)
{
Console.WriteLine("Do bang");
}
}
}
namespace ExtensionScope
{
using Extensions01;
using Extensions02;
class Program
{
static void Main(string[] args)
{
MyClass m = new MyClass();
m.DoThat();
}
}
}
This program throws a compile-time error because the compiler does not know if you want MyExtensions01.DoThat() or MyExtensions02.DoThat(). There are three ways to resolve this error:
• You could remove the using directive for either Extensions01 or Extensions02. In this case, that would be a fine resolution. But if there were other methods or classes in both Extensions01 and Extensions02 that you wanted to use, this could become a painful, or even unacceptable, choice.
• You could explicitly state which method you want to call using standard static syntax: MyExtensions01.DoThat(m).
• You could move either MyExtensions02 or MyExtensions01 into the ExtensionScope namespace:
namespace ExtensionScope
{
public static class MyExtensions02
{
public static void DoThat(this MyClass myClass)
{
Console.WriteLine("MyExtensions02.DoThat");
}
}
}
This solution works so long as you have access to the source.
It should be clear that some of the issues discussed here can lead to trouble if you are not careful. In particular, you don’t want to end up in a situation where forcing someone to remove a namespace results in his losing access to important functionality. Nor do you want to force him to choose between functionality he wants and using your extensions.
It can also be a serious nuisance if you muddy a namespace with what many developers might consider superfluous methods. If you added 50 extension methods to the C# string class, developers who just want to access the base functionality of that object would always have to contend with your methods, particularly when using IntelliSense.
To avoid or at least mitigate the seriousness of these problems, you should always place your extension methods in a unique namespace separate from the rest of your code. That way, you can easily include the extension methods in or exclude them from a program. Listings 4.10 and 4.11 illustrate this technique.
Listing 4.10. Place Your Extensions in a Separate File, and Give Them a Unique Namespace
namespace MyCode
{
... Code omitted here
}
namespace MyCode.Extensions
{
public static class SpecialString
{
private static string[] stateCodes =
{"AL","AK","AZ","AR","CA","CO","CT","DE","FL",
"GA","HI","ID","IL","IN","IA","KS","KY","LA",
"ME","MD","MA","MI","MN","MS","MO","MT","NE",
"NV","NH","NJ","NM","NY","NC","ND","OH","OK",
"OR","PA","RI","SC","SD","TN","TX","UT","VT",
"VA","WA","WV","WI","WY"};
public static bool IsState01(this string source)
{
if (source == null) return false;
source = source.ToUpper();
foreach (var item in stateCodes)
{
if (source == item)
{
return true;
}
}
return false;
}
}
}
Listing 4.11. Accessing Extension Methods in a Namespace
using System;
using MyCode;
using MyCode.Extensions;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
MyCode myCode = new MyCode();
... // Use My Code here.
string test = "WA";
if (test.IsState())
{
Console.WriteLine("{0} is a state", test);
}
}
}
}
In Listing 4.11 your extension method is available, and the code compiles. If you were to comment out the third using directive, your extension method would be unavailable, and the code would not compile. The developer would, however, still have access to the functionality found in the MyCode namespace. You could perhaps improve this technology by putting your extensions in their own assembly with its own namespace. You could then be sure that developers could choose to include or exclude the extra weight of your extension methods when they ship their code.
Listing 4.10 shows you two alternative ways to implement the IsState extension method. The second, which uses the LINQ Contains operator, is probably easier to maintain. The Contains operator is discussed in the next chapter.
The primary reason for the inclusion of extension methods in C# 3.0 is to enable LINQ. It is unlikely that this feature would have been added to the language had LINQ not existed. They are, however, now a part of the language, and, if used with caution, they can be useful. Placing them in their own namespace is a best practice that should help you get the most from this feature. Near the end of this chapter we will revisit extension methods, and you will see the crucial role they play in LINQ development.
IEnumerable<T>
As mentioned at the beginning of this chapter, each of the collections in the System.Collections.Generic namespace supports the IEnumerable<T> interface. For instance, here is part of the declaration for List<T>:
public class List<T> : IList<T>, ICollection<T>, IEnumerable<T> ...
As you can see, the List<T> class supports IEnumerable<T>. This fact, and this fact alone, makes it possible to write a LINQ to Objects query against this variable, or any variable of this type.
As you learned in the preceding chapter in the section “Composable,” LINQ to Objects queries always interrogate and usually return an instance of IEnumerable<T>. Consider the following code fragment:
List<int> list = new List<int> { 1, 3, 2 };
var query = from num in list
where num < 3
select num;
foreach (var item in query)
{
Console.WriteLine(item);
}
The type IEnumerable<T> plays two key roles in this code:
• The query expression has a data source called list that implements IEnumerable<T>. The data source produces a sequence of elements.
• The query expression returns an instance of a type that implements IEnumerable<T>.
Every LINQ to Objects query expression, including the one just shown, begins with a line of this type:
var w = from x in y
In each case, the data source represented by the variable y must support the IEnumerable<T> interface, and the variable w usually supports it. As you have already seen, the list of integers shown in this example supports that interface.
The same query shown here could also be written as follows:
IEnumerable<int> query = from num in list
where num < 3
select num;
This code makes explicit the type of the variable returned by this query.
In practice, you will find that most LINQ to Objects queries return IEnumerable<T>, for some type T. The only exceptions are those that call a LINQ query operator that returns a simple type, such as Count():
int number = (from num in list
where num < 3
select num).Count();
In this case the query returns an integer specifying the number of items in the list created by this query. LINQ queries that return a simple type like this are an exception to the rule that LINQ to Objects queries operate on classes that implement IEnumerable<T> and return an instance that supports IEnumerable<T>.
Although it might not be immediately obvious, simple arrays in C# 3.0 implement IEnumerable<T>. As a result, the following code compiles and runs as expected:
int[] array = new int[] { 1, 2, 3 };
var query = from i in array
where i < 3
select i;
foreach (var item in query)
{
Console.WriteLine(item);
}
Differences Between LINQ to Objects and LINQ to SQL
LINQ to SQL queries both operate on and return types that implement an interface called IQueryable<T>. It, in turn, implements the IEnumerable<T> interface. As a result, LINQ to SQL queries still provide the functionality found in LINQ to Objects, plus they use features of IQueryable<T> to enable the generation of SQL strings and calls to a SQL server. Exactly how this works is covered in section “Expression Trees” and is explained in more depth in Chapters 7 through 10.
Understanding Sequences
The IEnumerable<T> interface gives developers access to a sequence of items. For instance, a collection contains a sequence of some instances of type T arranged in a particular order. Here, for instance, is a sequence of integers that could be stored in a List<int>:
1, 3, 2
It is important to understand the differences between a sequence and a set:
• In a set, order is not important, and there is always a finite number of items.
• In a sequence, order is important, and there is not always a limit on the number of items.
• Re-enumeration is not built into sequences. If you ask to enumerate the values returned by a LINQ query a second time, it is not guaranteed that this will yield the same sequence of items in the same order.
It is important to understand that the data source found in the from clause at the beginning of a query expression provides a sequence of elements. A sequence has no defined limit. For instance, there is no limit on the number of items in the Fibonacci sequence, and it’s possible to use such a sequence as the data source for a LINQ query. That sort of sequence may not be a typical LINQ data source, but it is nonetheless a possible data source. The next two sections help explain the theory behind that type of query and provide an example of a data source that produces an infinite sequence. I should add that set theory also encompasses the idea of infinite sets. For instance, the set of all integers is infinite. You will see, however, that implementing an infinite sequence in LINQ is fairly trivial, whereas implementing an infinite set in computer programming is rare.
Enumeration
All generic collections provide the ability to ask for the first item in the sequence, and then for the next item, and the next item, until either the sequence or the need for new elements is exhausted. This is called enumerating over a sequence of elements, and it is an ability granted to us by the IEnumerable<T> interface.
The IEnumerable<T> interface looks like this:
public interface IEnumerable<T> : IEnumerable
{
IEnumerator<T> GetEnumerator();
}
The GetEnumerator method returns an implementation of the IEnumertor<T> interface, which, in turn, supports the following interface, called IEnumerator:
public interface IEnumerator
{
object Current { get; }
bool MoveNext();
void Reset();
}
You can use this interface to iterate over a collection, as shown in Listing 4.12.
Listing 4.12. Enumerating the Items in a List with the IEnumerator<T> Interface
using System;
using System.Collections.Generic;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
var list = new List<int> { 1, 2, 3 };
IEnumerator<int> e = list.GetEnumerator();
while (e.MoveNext())
{
Console.WriteLine(e.Current);
}
}
}
}
The code in Listing 4.12 uses MoveNext() and Current from IEnumerator to enumerate the values in a list. It is worth pointing out that because we are working with generic types, e.Current is strongly typed. In this case, for instance, Current is of type int. This means that you do not need to worry about typecasts.
As you know, the same effect can be achieved by writing the following code:
foreach (var item in list)
{
Console.WriteLine(item);
}
The C# foreach syntax is just a shorthand way of writing out the enumeration code shown in Listing 4.12. This syntax exists only because it is easier and cleaner for you to write. Behind the scenes the compiler actually executes a while loop on the MoveNext() method.
Iterators
Because a foreach loop is a shorthand way to use the IEnumerator interface, it should not be a surprise to learn that there is a shorthand way to implement it. Rather than forcing you to create a class that explicitly implements MoveNext(), Current, and Reset(), C# 2.0 lets you implement that interface by using yield return. Listing 4.13 shows how this works.
Listing 4.13. Using the Power of yield return to Implement IEnumerable<T>
using System;
using System.Collections.Generic;
namespace IteratorTests
{
class Program
{
public static IEnumerable<int> GetList()
{
var length = 3;
for (int i = 1; i <= length; i++)
{
yield return i;
}
}
static void Main(string[] args)
{
var list = GetList();
// Iterate over a list with an Enumerator
IEnumerator<int> e = list.GetEnumerator();
while (e.MoveNext())
{
Console.WriteLine(e.Current);
}
// Now do the same thing with foreach
foreach (var item in list)
{
Console.WriteLine(item);
}
}
}
}
Listing 4.13 is much like Listing 4.12, except that the implementation of a list is now found in a method that returns IEnumerable<T> rather than in a simple List<T>. But as you can see, both sets of code work the same way.
The call to yield return sets in motion quite a bit of hand waving and compiler magic. Behind the scenes the code we write is changed almost beyond recognition. Nevertheless, the end result is as follows:
1. The first time you call GetList(), it returns the first item produced by the for loop, which it implements.
2. The second time you call GetList(), it returns the second item from the for loop, and so on.
3. The process ends when it runs out of items to iterate over.
The compiler actually transforms our simple call to yield return into an autogenerated class that contains a state machine for keeping track of the items yielded up to the user. The series of case statements and calls to goto that populate this autogenerated class are perhaps more utilitarian than elegant. Nevertheless, something is compelling about these kinds of transformations. If you are curious to learn more, I recommend Raymond Chen’s summation of the subject, because it is relatively succinct:
http://blogs.msdn.com/oldnewthing/archive/2008/08/12/8849519.aspx
One interesting implication of this system is that you could use a technique like this to implement an endless loop that never stopped returning values. Consider the following implementation of IEnumerable<T>:
public static IEnumerable<int> GetList()
{
int i = 2;
while (true)
{
i = i * 2;
if ((i <= 0) || (i > int.MaxValue))
{
i = 2;
Console.WriteLine("Enter to continue, CTRL-C to break.");
Console.ReadLine();
}
else
{
yield return i;
}
}
}
The preceding code, plugged into the code shown in Listing 4.13, produces the following sequence in an endless loop:
4
8
16
32
64
128
256
512
1,024
2,048
4,096
8,192
16,384
32,768
65,536
131,072
262,144
524,288
1,048,576
2,097,152
4,194,304
8,388,608
16,777,216
33,554,432
67,108,864
134,217,728
268,435,456
536,870,912
1,073,741,824
4
8
16
Etc...
Deferred Execution
For newcomers to LINQ, deferred execution is a mysterious feature. But now that you understand iterators and yield return, deferred execution should be easy to understand, even immediately intuitive. Consider the code shown in Listing 4.14.
Listing 4.14. A Simple LINQ Query with a Sequence Provided by an Iterator
using System;
using System.Collections.Generic;
using System.Linq;
namespace DeferredTests
{
class Program
{
public static IEnumerable<int> GetSequence()
{
var length = 3;
for (int i = 1; i <= length; i++)
{
yield return i;
}
}
static void Main(string[] args)
{
var list = GetSequence();
var query = from num in list
where num < 3
select num;
foreach (var item in query)
{
Console.WriteLine(item);
}
}
}
}
Listing 4.14 is very much like Listing 4.13, only it uses the System.Linq namespace and includes a simple LINQ query expression.
If you stepped through the code in Listing 4.14 with a debugger, it would be natural to assume that you would see the LINQ query execute when the debugger stepped over this statement:
var query = from num in list
where num < 3
select num;
To the surprise of nearly every newcomer to LINQ, this is not what happens. The query actually executes when you reach the foreach statement.
Use the Debugger to Help You Understand LINQ
If you have the tools available, consider running this program in Visual Studio and stepping through it with the debugger. It will help drive home this point if you see it for yourself. The C# and Debugger teams worked very hard to integrate LINQ and the Debugger. I’ve found it instructive to allow the Debugger to illuminate my LINQ code. Alternatively, try inserting a WriteLine statement into the for loop found in the call to GetSequence(), as shown in the sample program (available on this book’s web site) called DeferredExecution.
Execution of a query expression is deferred until the moment when you ask for the first item in the result sequence. Until that time, the value returned from a query expression is simply a computation; it is not a result set. As you learned in the section “Composable” in the preceding chapter, you can use these computations in additional queries, but even then execution is deferred until something forces LINQ to ask for the first element in the result sequence.
I’ll provide two different explanations of what happens when the foreach code executes. My first explanation will be entirely utilitarian; it will explain the practical, visible results of a call to foreach. I will then revisit the subject and explain what is happening behind the scenes. The difference between the explanations is somewhat like the difference between saying that the sun rises in the east, and explaining what really happens when you know that the Earth is a spinning ball revolving around the sun. There is nothing misleading or dangerous about thinking that the sun rises in the east. In fact, the sun doesn’t rise at all: the Earth spins. Nevertheless, you can make reliable plans based on the assumption that the sun rises in the east. From the point of view of an observer out in space, that is an incorrect explanation of what happens. But practically speaking, from the point of view of a person on Earth, the sun rises in the east.
So I will explain this business from two points of view—one utilitarian, and the other more theoretical. The theoretical explanation will be more rigorously correct, but when you are writing code, you can easily make do with the more practical explanation. In fact, you might find it preferable to use the practical explanation, just as we find it simpler to state that the sun rises in the east.
When thinking about the solar system, we say that from a practical perspective, it appears that the sun rises in the east. When thinking about the code in Listing 4.14, we can make the practical observation that a method called GetSequence yields a series of values. When you loop through foreach the first time, it appears that GetSequence is called and yields the value 1. This is the first number produced by the for loop found inside GetSequence. (Step through the code with the debugger, and you will see what I mean.) After this value is retrieved, then the LINQ query is executed. The where clause in the query expression tests if 1 is smaller than 3, and if it is, it returns the value, which is printed to the console. Now we are back up at the top of the foreach loop, and GetSequence is “called” a second time. This time it returns the number 2, which is again passed through the Where clause in the query expression and returned for printing to the console. The foreach loop begins again, and this time the number 3 is retrieved. The Where clause tests if 3 is smaller than 3. It is not, so the query expression does not return this value, and nothing is printed to the console. The loop requests the next number from the sequence, and GetSequence returns false, so the loop ends and the program exits. For all practical purposes, that is what happens. You will never go astray by living with this interpretation of events, just as you will never go astray believing that the sun rises in the east.
However, in a book of this kind, I need to dig beneath the surface and explain what is really happening. Behind the scenes, the method called GetSequence is called only once. It does not really return values one at a time. Instead, it returns an instance of an autogenerated object with a name such as GetListEnumerator that implements a state machine. Again, this is a case where the compiler radically transforms your code into something very different from what you originally wrote.
I’ve worked with a developer on the C# team named Eric Lippert to produce the following code, which approximates the code produced by the compiler when it sees our call to GetSequence:
public static IEnumerable<int> GetSequence()
{
return new GetListEnumerable();
}
private class GetListEnumerable : IEnumerable<int>
{
public IEnumerator<int> GetEnumerator()
{
return new GetListEnumerator();
}
}
private class GetListEnumerator : IEnumerator<int>
{
public int Current { get; private set; }
private int i;
private int length;
private int state = 0;
public bool MoveNext()
{
if (state == 0) goto State0;
if (state == 1) goto State1;
if (state == 2) goto State2;
State0:
this.length = 3;
for (this.i = 1; this.i <= this.length; this.i++)
{
this.State = 1;
this.Current = this.i;
return true;
State1:
}
State2:
this.state = 2;
return false;
}
}
Ultimately, the call to GetSequence yields a class that we call GetListEnumerator, which contains a single method called MoveNext. A state machine is implemented in the class such that calls to MoveNext mimic what would happen if we called the simple for loop in the original GetSequence method. The difference is that the results from the for loop are retrieved one at a time, so that the first call to MoveNext returns the first value from the loop, the next call to MoveNext returns the next value, and so on, until the items generated by the loop are exhausted.
The actual location of the MoveNext loop can differ, depending on the type of query you write. In our case, it is actually called from inside the implementation of Where, as shown in the next section.
Deferred execution ensures that LINQ never wastes time performing calculations you don’t actually need. This is made possible by LINQ’s reliance on sequences of numbers that are retrieved from a class that implements the IEnumerator interface. This is true even if we declare a list like this:
var list = new List<int> { 1, 2, 3 };
Even with a seemingly static list like this, behind the scenes the C# compiler uses the IEnumerator pattern and pulls the numbers from a MoveNext() loop, grabbing each current item one at a time.
Consider the following variation of the code from Listing 4.14:
static void Main(string[] args)
{
var list = GetList();
int bound = 3;
var query = from num in list
where num < bound
select num;
bound = 4;
foreach (var item in query)
{
Console.WriteLine(item);
}
}
A newcomer to LINQ might suppose that this method prints the numbers 1 and 2, because bound is equal to 3 when the query expression is “executed.” However, the code actually prints the values 1, 2, and 3. The variable bound is equal to 4 when the code reaches the foreach loop, and that is when the query expression is executed.
Why is execution of the query deferred? A primary reason is because it enables composition to work as expected. You can link two, three, four, or more queries using the compositional style of development, and none of the queries will execute until you begin to iterate over the results. This means that each query can be combined into a single “computation” that is executed only once.
When you are using query expression syntax, execution is always deferred. Only operators that must be called using query method syntax might execute immediately. For instance, when you call First() or ToList(), execution is immediate:
var query = (from m in typeof(Enumerable).GetMethods()
orderby method.Name
where m.DeclaringType == typeof(Enumerable)
select m).First();
The orderby, where, and select methods are all called using query expression syntax and are all deferred. The First operator is called using query method syntax and is not deferred.
Overriding LINQ Operators
We are now deep inside the implementation of LINQ to Objects and near the end of our journey. Just one piece is missing: How are LINQ operators, such as where, actually implemented?
This chapter has told you several times that code that appears to say one thing is actually translated by the compiler into something else. The compiler translates automatic properties into standard properties with funny names. Anonymous types are translated into real classes that have funny names. Behind the scenes foreach loops actually call the IEnumerator interface with its MoveNext() method. Most surprising of all, the compiler translates yield iterators into classes that implement the IEnumerator interface.
Given this background, it should come as no surprise that the compiler translates query expressions into something else. Consider the following query, which you have seen several times:
var query = from num in list
where num < value
select num;
Behind the scenes, at compile time, this query is translated into the following code:
var query = list
.Where<int>(num => num < value)
.Select<int, int>(num => num);
Or if you prefer, the compiler is smart enough to work with this shortened version of the statement:
var query = list.Where<int>(num => num < value);
These three statements are semantically quite similar, even if they differ syntactically. The second and third statements are valid C# code and can be used in lieu of the first implementation. They are said to use query method syntax, whereas the first statement is a query expression.
Why are query expressions translated into query methods? Why didn’t the developers of LINQ ask developers to write query methods?
The original implementation of LINQ had no such thing as a query expression. You could use only query method syntax. The team ran a series of usability tests on this syntax and found that many developers found it confusing, especially as queries grew more complex. This feedback forced them to return to the whiteboard, where they scratched their heads for a bit before inventing query expressions. This proved a more viable solution, because developers picked it up with relative ease.
You are now in a position to appreciate the role that lambdas play in query expressions. Of the three examples just shown, it is obvious that the second and third contain lambdas. It is less obvious, however, that the first example, the query expression, also contains a shortened form of a lambda. The where clause contains the body of a lambda. The designers of LINQ decided that it was not necessary for developers to include a complete lambda expression, because the type of the variable num is inferred in the first line, where it appears as a range variable.
We can now see that the Where and Select operators appear to be normal methods. In fact, a little experimentation will reveal that they are methods that can be called on any implementation of IEnumerable<T>. This fact is actually a bit puzzling when you consider that the implementation for IEnumerable<T> looks like this:
public interface IEnumerable<T> : IEnumerable
{
IEnumerator<T> GetEnumerator();
}
This simple interface has no place for an implementation of the Where and Select methods, nor for any of the approximately 50 other operators supported by LINQ and their numerous overloads.
By now you have probably guessed that Where, Select, and all the other LINQ operators are really extension methods. It turns out that they are declared in the System.Linq namespace, in a class called Enumerable, which is a variation on the SpecialString class shown earlier. In other words, it is a static class that contains a long list of extension methods, one for each of the LINQ operators, plus numerous overloads of these methods.
IEnumerable<T> Supports All the LINQ Operators
IEnumerable<T> is a lightweight interface with one method, which you can implement with a simple yield iterator. This means that it is easy for you to support IEnumerable<T> on any list-like structure you create. If you then add a System.Linq directive, you can query your list using LINQ and its broad range of operators. Nothing else needs to be done. The other two options that the C# team could have used to provide this functionality would have been to force you to inherit your list from a class that implemented all the extensions methods that support the LINQ operators, or to put all 50 operators and their numerous overloads in the IEnumerable<T> interface and force you to implement them. Neither option is very appealing. The fact that IEnumerable<T> can use extensions methods to support all the LINQ operators is a very nice trick that makes your life as a developer much simpler.
Let’s create our own version of the Where method. By placing it nearer in scope to our code than the Where method that ships with LINQ, we will be able to watch it execute and get some insight into how LINQ works. To get started, take a look at Listing 4.15.
Listing 4.15. Implementing the Where Operator to See How It Works
using System;
using System.Collections.Generic;
using System.Linq;
namespace WhereTests
{
public static class MyExtensions
{
public static IEnumerable<T> Where<T>(this IEnumerable<T> source,
Func<T, bool> predicate)
{
foreach (var item in source)
{
if (predicate(item))
{
yield return item;
}
}
}
}
class Program
{
public static IEnumerable<int> GetList()
{
var length = 6;
for (int i = 1; i <= length; i++)
{
yield return i;
}
}
static void Main(string[] args)
{
var list = GetList();
var query = list.Where(num => num < 3).Select(num => num);
foreach (var item in query)
{
Console.WriteLine(item);
}
}
}
}
This code differs from our previous implementations of this query only in the fact that we can explicitly see the implementation of the Where operator. The header for the Where method shows that it is an extension method that works with the IEnumerable<T> interface. It is also passed a simple delegate that takes a value of type T and returns a bool:
static IEnumerable<T> Where<T>(this IEnumerable<T> source,
Func<T, bool> predicate)
Finding the Where Metadata Declaration
Our Where method has the same declaration as the Where method in the LINQ source code. To see that declaration, type in a query with a Where operator. Use query method syntax, as shown in Listing 4.15. Place the mouse cursor over the word Where, right-click, and select Go to definition. You are taken to the declaration for Where, and you also see the declaration for all the other LINQ operators.
Looking at our query, we see that the delegate is passed the following lambda expression:
num => num < 3
The loop in the Where method iterates over our collection of numbers, pulling them out one at a time, just as we showed in the section “Deferred Execution.” It pulls the number 1 first and passes it to the predicate:
foreach (var item in source)
{
if (predicate(item))
{
yield return item;
}
}
The predicate compares the number 1 to the number 3, sees that it is smaller, and returns true. The code in the Where method then yield returns this value, and it is printed to the Console in the foreach loop found in the Main method. Then Where is called again, and this time the number 2 is pulled from our GetList() method. It is run through the predicate, returns true, is passed back to the foreach loop and printed to the screen, and so on. Each item is passed to the predicate, and, if true is returned, the item is yield returned. Otherwise, the foreach loop simply iterates the next item until the last item in source has been tested through predicate, just as before. You are now seeing the entire scope of the LINQ query, witnessing exactly how each portion of it is implemented.
At this stage, you know almost everything there is to know about LINQ to Objects. You have seen how extension methods, lambdas, and iterators come together to form a query language that works with collections. This background knowledge will act as a foundation on which you can build a deep understanding of LINQ to Objects.
Expression Trees
After getting a close look at LINQ to Objects, you might think that this tour through the LINQ architecture would be complete. Yet one more key feature is left to explore. This feature is not part of LINQ to Objects, but it does play a key role in other technologies, such as LINQ to SQL.
In LINQ to Objects, the data that is being queried is local and is stored in objects that support the IEnumerable<T> interface. That is not the case, however, in LINQ to SQL. In that scenario, the data is stored in a different process, which is likely to be running on a different machine. And, of course, the data structures in a relational database know nothing about IEnumerable<T>.
The technology for calling a database from a C# program already exists, so at least that part of the problem is solved. Two issues, however, still need to be resolved:
• How do we translate a query expression into a SQL statement that can be sent to a server?
• How do we convert the data we get back from the SQL server into objects that LINQ can query?
The answer to the second question is covered later in this book, in Chapters 7 through 10. The first question, however, is one that you need to come to terms with if you want to understand the LINQ architecture.
Expression trees allow you to convert code into data. In particular, they make it possible to convert a query expression into a data structure. A LINQ provider can then parse that data structure, determine what data the developer wants, and then retrieve it. For instance, an expression tree can convert a LINQ to SQL query expression into a data structure, parse that data structure, and compose a SQL statement based on its contents. It can then use conventional techniques to execute that SQL statement and return the results to the developer. In this chapter, I’ll explain the basics of this process, and then in Chapter 17, “LINQ Everywhere,” you will be introduced to providers that parse entire expression trees and convert them into useful code.
Let’s begin by creating a simple expression tree based on a lambda. As you can see from Listing 4.16, the first step is to use the System.Linq.Expressions namespace. After you have included the namespace, you can create an expression.
Listing 4.16. Creating an Expression Tree Based on a Lambda
using System;
using System.Linq.Expressions;
namespace SimpleExpressions
{
class Program
{
static void Main(string[] args)
{
Expression<Func<int, int, int>> expression = (a, b) =>
(a + b);
}
}
}
Each expression is of a particular type. In this case, the type is our old friend: a delegate that takes two integers and returns an integer. By setting an instance of this type equal to a lambda expression, we are creating not code that can be executed, but a data structure that can be parsed. Here is another way to think about what is happening: The Expression type is a generic type parameterized by the type of the delegate that it is supposed to wrap. Our old friend Func fits perfectly for this job. In this particular example, the lambda takes two integers’ parameters and returns an integer.
Listing 4.17 shows how to parse this data structure to discover a few basic facts about it. Listing 4.18 shows the output.
Listing 4.17. Code to Perform Basic Parsing Operations on an Expression Tree
Expression<Func<int, int, int>> expression = (a, b) => (a + b);
Console.WriteLine("Expression Type: {0}", expression.NodeType);
foreach (var item in expression.Parameters)
{
Console.WriteLine("Parameter: {0}; Type: {1}", item, item.Type);
}
BinaryExpression body = (BinaryExpression)expression.Body;
ParameterExpression left = (ParameterExpression)body.Left;
ParameterExpression right = (ParameterExpression)body.Right;
ExpressionType nodeType = body.NodeType;
Console.WriteLine("Body: {0} = Analysis of body: {1} {2} {3}",
body, left, nodeType, right);
Listing 4.18. The Output from Listing 4.17
Expression Type: Lambda
Parameter: a; Type: System.Int32
Parameter: b; Type: System.Int32
Body: (a + b) = Analysis of body: a Add b
The code in Listing 4.17 begins by discovering the type of the expression, which is a lambda:
Console.WriteLine("Expression Type: {0}", expression.NodeType);
It then looks at the parameters to the lambda and discovers that they are called a and b and are of type Int32:
foreach (var item in expression.Parameters)
{
Console.WriteLine("Parameter: {0}; Type: {1}", item, item.Type);
}
The next step is to examine the body of the lambda. We look at the expression on the left and see that it is our friend a, and the expression on the right and see that it is b. The NodeType of the expression is Add:
BinaryExpression body = (BinaryExpression)expression.Body;
ParameterExpression left = (ParameterExpression)body.Left;
ParameterExpression right = (ParameterExpression)body.Right;
ExpressionType nodeType = body.NodeType;
Console.WriteLine("Body: {0} = Analysis of body: {1} {2} {3}",
body, left, nodeType, right);
Although there is considerably more information in the expression tree, we have harvested enough information to see that our lambda takes two parameters of type integer and adds them together.
There is, of course, a difference between parsing a simple lambda like this and parsing a complex query expression. Nevertheless, you should now understand enough to grasp the basic principles involved. To help drive home the point, let’s use a tool called the Expression Tree Visualizer that ships with the Visual CSharp samples.
The Expression Tree Visualizer is an add-on that lets Visual Studio display an expression tree. To use it, first you need to obtain a copy of the sample. You can do this by choosing Help, Samples from Visual Studio. You are taken to an HTML page, where you find a set of instructions for downloading the CSharp samples. After you have unzipped the samples, open the ExpressionTreeVisualizer project and build it. Go to following directory, and locate the file called ExpressionTreeVisualizer.dll:
...ExpressionTreeVisualizerExpressionTreeVisualizerinDebug
Copy the DLL into a directory called Visualizers that is located at the root of the Visual Studio 2008 folder in your Documents directory. If the Visualizers directory does not already exist, create it. Create a default console application, and type in and run the program found in Listing 4.17, or open the SimpleExpression project sample that accompanies this book. Set a break point after this line:
Expression<Func<int, int, int>> expression = (a, b) => (a + b);
Right-click the word expression. A ToolTip pops up with a magnifying class icon, as shown in Figure 4.2. Click the down arrow next to the magnifying glass, and then click the popup menu to open the Expression Tree Visualizer. You see a window like the one shown in Figure 4.3.
Figure 4.2. Opening the Expression Tree Visualizer.
Figure 4.3. Parsing the expression for a simple lambda with the Expression Tree Visualizer.
Looking at Figure 4.3, you can see the four main nodes of the expression tree:
• Body
• Parameters
• NodeType
• Type
The parameters are called a and b, are of type Int32, and are of NodeType parameter. The body also has two parameters and a NodeType of Add. The return type of the body is Int32, and so on. All the information you need to work with this expression is available to you. Studying the code for the Expression Tree Visualizer would obviously be a good way to learn more about parsing these objects.
You can also use the Expression Tree Visualizer to parse the code from the LINQ to SQL program. The tree generated from that query is too long to show here, but the principles involved are similar to those shown in parsing the simple lambda just shown.
To get started, open the sample run to a point right after the query expression:
var query = from c in db.Customers
where c.City == "London"
select c;
At runtime, hold the mouse cursor over the variable query to bring up the Data tip window. Click the plus symbol to open the Data Tip, and explore the Non-Public members. Look for the field called queryExpression. This is the variable containing the expression tree that represents your query. Notice that on the right is a magnifying glass, as shown in Figure 4.4. Click the down arrow next to it, which brings up the Expression Tree Visualizer. You see a completely parsed image of the tree for your program.
Figure 4.4. The popup menu item for the Expression Tree Visualizer in an IntelliSense fly-by window.
In this section you have seen that expressions allow you to convert code into data. If you parse that data, you can extract the semantic meaning of that code, and use that information to call into another process. This is the only way that LINQ can execute a query expression when it needs to work with a data source that does not implement IEnumerable<T>. In general, LINQ must use expression trees if it wants to query a data source that resides in another process.
Summary
This chapter has covered all the major features of C# 2.0 and C# 3.0 that make LINQ possible. The text began by covering general-purpose features such as collection and object initializers. The middle portions of the chapter covered type inference, lambdas, and extension methods, all of which play key roles in the LINQ syntax. Near the end of the chapter you learned about the type IEnumerable<T>, the central axis around which LINQ to SQL revolves. Finally, at the end of the chapter you learned about expression trees, a feature that is very important to developers who want to create providers.
The interesting thing about the LINQ syntax is that it is built from a set of fairly simple features. Lambdas, extension methods, and iterators are all quite simple ideas. When brought together in LINQ, however, they form a very powerful query syntax that can change how developers write code. In the next chapter, you will learn more about the power of query expressions, and you’ll finally get a chance to begin exploring the ways to use this syntax in real programs.