LINQ as Declarative Programming

Introduction

The tip is aimed to show how to utilize the potential of LINQ. It also helps to understand the difference between imperative and declarative programming approaches.

Background

Assume that you're familiarized with the basics of OOP, Imperative Programming Paradigm, Declarative Programming Paradigm, C#, LINQ, Extension Methods, Expression Trees.

Issue

Consider the simple task:

Given the integers {1, ..., 1000}. Find numbers that are divisible by 29.

Let's be up to date and solve that by using the following LINQ query syntax:

from i in Enumerable.Range(1, 1000)
where i % 29 == 0
select i;  

Wow, that sounds almost like the original question! It is very readable and so declarative, isn't it? However, more experienced developer will probably automatically translate that declaration into its imperative counterpart:

foreach (var i in Enumerable.Range(1, 1000)
    if (i % 29 == 0)
        yield return i; 

The truth is that the default implementation of LINQ operators, acts in such way. While the programmer is analysing his translated imperative version of the query he points out, that the implementation is inefficient. The better solution will be as follows:

for (var i = 29; i <= 1000; i += 29)
    yield return i;  

What does he do next, for the sake of the performance? He rids off the LINQ query, writes a custom, imperative, illegible implementation and... that is the pattern, that this tip attempts to change!

Concept

To make a change, we need 3 .NET tools:

• Extension Methods
• Method Overloading
• Expression Trees

LINQ beyond query syntax also has an equivalent method syntax. We might prescribe our original query to the following form:

Enumerable.Range(1, 1000).Where(i => i % 29 == 0); 

It is not as beautiful as the former, but is only aimed to facilitate further considerations. Notice that Where statement is nothing more than method invocation. An extension method Enumerable.Where is more specific. We are free to overload that method by a more concrete version that will capture our invocation:

static IEnumerable<int> Where(this IEnumerable<int> source, Func<int, bool> predicate) 

We could put the boosted algorithm here:

static IEnumerable<int> Where(this IEnumerable<int> source, Func<int, bool> predicate)
{  
    for (var i = 29; i <= 1000; i += 29)
        yield return i;
} 

But that is a one off, inflexible solution. We have ignored the predicate. Fortunately, there is a solution - Expression Trees. Look at the declaration below:

static IEnumerable<int> Where(
    this IEnumerable<int> source,
    Expression<Func<int, bool>> predicate) 

That also works well as the previous one, but gives additional advantages. It allows to explore the internals of given function. Probably the most shocking thing is that the function may never be invoked! Below is the simplified implementation of our custom Where method:

static IEnumerable<int> Where(
    this IEnumerable<int> source,
    Expression<Func<int, bool>> predicate)
{
    var body = predicate.Body as BinaryExpression;
    var bodyLeft = body.Left as BinaryExpression;
    var moduloRight = bodyLeft.Right as ConstantExpression;
    var rightValue = (int) moduloRight.Value;
 
    for (var i = rightValue; i < source.Count(); i += rightValue)
        yield return i;
}    

If something went wrong, then use standard Where method:

if (bodyLeft.NodeType != ExpressionType.Modulo)
    return Enumerable.Where(source, predicate.Compile());  

That's it! Now, we can use our original LINQ query syntax to solve the issue in a readable and also efficient way.

Declarative vs Imperative

Notice that the expression i % 29 == 0 have never been invoked! In imperative programming, you tell: Do i % 29 == 0 for each element. In declarative programming, you tell: Do what you wish, but the result must be equivalent to as you do i % 29 == 0 for each element.

Thus, LINQ may solve your task in a different manner than you can think. Keep that in mind. Free your mind from imperative and extend the usage of your LINQ.