B# .NET Blog : C# 3.0, LINQ

Taming Your Sequence’s Side-Effects Through IEnumerable.Let

bart — Sat, 12 Sep 2009 11:56:42 GMT

Introduction

Side-effects don’t fit together very well with functional-style delayed computation, as observed in LINQ. Having such constructs embedded in an otherwise eagerly evaluated imperative language like C# can cause quite some confusion from time to time. A few samples (due to Erik Meijer) of such “mishaps” are shown below:

//
// When does it throw?
//
IEnumerable<double> res = null;
try
{
    res = from x in Enumerable.Range(0, 10)
          select 1.0 / x;
}
catch (DivideByZeroException) {}

foreach (var rcp in res)
    Console.WriteLine(rcp);

//
// What does it print?
//
Func<int, bool> div2 = i => { Console.WriteLine(“Div2 test “ + i); return i % 2 == 0; };
Func<int, bool> div3 = i => { Console.WriteLine(“Div3 test “ + i); return i % 3 == 0; };
var res = from x in Enumerable.Range(0, 10)
          where div2(x)
          where div3(x)
          select x;

foreach (var sxt in res)
    Console.WriteLine(sxt);

The side-effects in the samples above are of various kinds: exceptions and output operations all hurt in a functional setting. In pure “fundamentalist” functional programming languages, those effects are made explicit by means of the type system (in particular, the IO monad). When looking at a .NET “function” signature, types are lying at us:

class Random
{
public int Next();
}

Sure, Next returns an Int32 numeric value when being called. But that’s only part of the story: every time you call it, it may return something else. In other words, we can’t simplify the following program:

var rand = new Random();
var fems = new Pair(rand.Next(), rand.Next());

into

var rand = new Random();
var __rn = rand.Next();
var fems = new Pair(__rn, __rn);

The main reason is simply because we don’t know enough about the behavior, i.e. the side-effects, the Next function exposes. Or to state it in another manner, Next is not a (pure) function but a method. In Haskell, types tell us a side-effect is going on:

randomIO :: (Random a) => IO a

Roughly speaking, Random a stands for Random<T> and IO a stands for T, “tagged” with the fact it has a side-effect through the IO monad (not the same as IO<T> as the CLR’s type system doesn’t support the higher kinding required to realize the typing required for monads).

Multiplication of side-effects

Being aware of the presence of side-effects is one thing, having them amplified or multiplied (almost) invisibly through the use of query combinators and such is even more painful. Consider the following iterator:

static class RandomExtensions
{
    public static IEnumerable<int> GetNumbers(this Random rand, int max)
    {
        while (true)
            yield return rand.Next(max);
    }
}

which can be called like:

var rand = new Random();
foreach (var x in rand.GetNumbers(100).Take(10))
Console.WriteLine(x);

All is good and well so far, we’ll get 10 random numbers printed to the screen. Now assume we’re already in .NET 4 (just to make illustration a little easier, the general topic of “taming side effects” is version-independent and platform(-excluding-Haskell)-independent) and have Zip method available. Let’s write the following:

var rand = new Random();
var res = rand.GetNumbers(100).Take(10).Zip(rand.GetNumbers(100).Take(10), (l, r) => l + r).All(x => x % 2 == 0);

What do you think res should be? Clearly, the sum of a number and itself is always even. In bold, we have a common subexpression: on the face of it, you may think it’d produce the same results for both “sides” of Zip, hence the conclusion the zipped sums should always be even. Nothing is further away from the truth: GetNumbers propagates the side-effect of the underlying IO operation (reading form a random number generator) and the two calls create separate iterator instances, each merrily ticking along. A simple Print operator can help to illustrate this:

static class Enumerable
{
    public static IEnumerable<T> Print<T>(this IEnumerable<T> source, string formatMessage)
    {
        foreach (var item in source)
        {
            Console.WriteLine(formatMessage, item);
            yield return item;
        }
    }
}

Yes, even more side-effects added to the melting pot. Now we can write the following to illustrate the mishap:

var rand = new Random();
var res = rand.GetNumbers(100).Take(10).Print(“SRC1: {0}”).Zip(rand.GetNumbers(100).Take(10).Print(“SRC2: {0}”), (l, r) => l + r).All(x => x % 2 == 0);

One run on the author’s machine produced:

SRC1: 82
SRC2: 86
SRC1: 17
SRC2: 91
SRC1: 48
SRC2: 15

Clearly, both sources are out of sync. Now we go and knock on the door of a fellow programmer and ask to solve this issue. Well, clearly you’re calling GetNumbers twice – that’s your problem right there. Not so much… Let’s see what a proposed fix would look like:

var rand = new Random();
var src = rand.GetNumbers(100).Take(10);
var res = src.Print(“SRC1: {0}”).Zip(src.Print(“SRC2: {0}”), (l, r) => l + r).All(x => x % 2 == 0);

And here’s the result:

SRC1: 89
SRC2: 39
SRC1: 22
SRC2: 15

What’s happening here? Although we’ve reduced the number of calls to GetNumbers to just a single one, its execution is still lazily evaluated as we’re using an iterator. It’s not until we start iterating that computation is triggered. Moreover, the iterator returns an IEnumerable<int> which merely provides the potential to enumerate though the IEnumerator<int> objects it hands out. In effect, Zip will call GetEnumerator twice, resulting in two instances of the iterator (simplified code below):

public static IEnumerable<R> Zip<T1, T2, R>(this IEnumerable<T1> left, IEnumerable<T2> right, Func<T1, T2, R> zip)
{
    var leftE = left.GetEnumerator();
    var rightE = right.GetEnumerator();
    while (leftE.MoveNext() && rightE.MoveNext())
        yield return zip(leftE.Current, rightE.Current);
}

In our case, left and right are pretty much the same (ignore Print which acts as an all-pass filter iterator), namely src:

src.Zip(src, …)

Two calls to GetEnumerator result, each querying the same random generator instance that happily continues on its side-effecting mission. The iterator we wrote for GetNumbers is semantically equivalent to the following, illustrating this issue more clearly for those who are not familiar with the way iterators are compiled (simplified presentation):

static class RandomExtensions
{
    public static IEnumerable<int> GetNumbers(this Random rand, int max)
    {
        return new GetNumbersIterator(rand, max);
    }
}

class GetNumbersIterator : IEnumerable<int>
{
    private Random _rand;
    private int _max;

    public GetNumbersIterator(Random rand, int max)
    {
        _rand = rand;
        _max = max;
    }

    public IEnumerator<int> GetEnumerator()
    {
        return new GetNumbersIteratorEnumerator(this);
    }

    class GetNumbersIteratorEnumerator : IEnumerator<int>
    {
        private GetNumbersIterator _iter;
        private int _curr;

        public GetNumbersIteratorEnumerator(GetNumbersIterator iter)
        {
            _iter = iter;
        }

        public bool MoveNext()
        {
            _curr = _iter._rand.Next(_iter._max);
            return true;
        }

        public int Current
        {
            get { return _curr; }
        }
    }
}

In fact, you could say the side-effect that’s killing us now is the instantiation of GetNumbersIteratorEnumerator inside the GetEnumerator method. Observing that, the innocent unenlightened developer may say: what if we eliminate that additional object instantiation? Let’s “desugar” the iterator by writing it as the thing above (quite a bit of work, but the innocent developer is willing to go great lengths to get his code working As The Natural Numbers Intended) and eliminating the construction of a new GetNumbersIteratorEnumerator all the time.

class GetNumbersIterator : IEnumerable<int>
{
    private Random _rand;
    private int _max;
    private GetNumbersIteratorEnumerator _curr;

    public GetNumbersIterator(Random rand, int max)
    {
        _rand = rand;
        _max = max;
        _curr = new GetNumbersIteratorEnumerator(this);
    }

    public IEnumerator<int> GetEnumerator()
    {
        return _curr;
    }

Guess what? Here’s the result:

SRC1: 15
SRC2: 97
SRC1: 31
SRC2: 57
SRC1: 21
SRC2: 57
SRC1: 63
SRC2: 94

Bummer. We’re just pushing the problem in front of us. Though we have the same enumerator object inside the Zip method now, we’re still calling MoveNext twice:

public static IEnumerable<R> Zip<T1, T2, R>(this IEnumerable<T1> left, IEnumerable<T2> right, Func<T1, T2, R> zip)
{
    var leftE = left.GetEnumerator();
    var rightE = right.GetEnumerator();
    Debug.Assert(leftE == rightE);
    while (leftE.MoveNext() && rightE.MoveNext())
        yield return zip(leftE.Current, rightE.Current);
}

What would the desperate developer’s next suggestion be? Let’s not go there – clearly there’s something bigger the matter here. Everything you try at this level of decomposing iterator objects and knowing precisely how query operators work is a very very ugly band-aid trying to cover up for the bigger problem of side-effect replication here.

One way to tackle the problem from the outside is to break laziness:

var rand = new Random();
var src = rand.GetNumbers(100).Take(10).ToArray();
var res = src.Print(“SRC1: {0}”).Zip(src.Print(“SRC2: {0}”), (l, r) => l + r).All(x => x % 2 == 0);

Operators like ToArray and ToList drain the left-hand side sequence on the spot, persisting the retrieved elements in-memory. Iterators versus persisted data sequences aren’t differentiated on the type level: both are “enumerable”. Great from a generalization point of view, less so to understand the runtime behavior of dealing with those objects. Either way, the above works and prints:

SRC1: 44
SRC2: 44
SRC1: 6
SRC2: 6
SRC1: 81
SRC2: 81
SRC1: 14
SRC2: 14
SRC1: 65
SRC2: 65
SRC1: 1
SRC2: 1
SRC1: 9
SRC2: 9
SRC1: 67
SRC2: 67
SRC1: 65
SRC2: 65
SRC1: 75
SRC2: 75

For the first time we reached the end of the zipped sequence. Wonderful. But we’ve made a big sacrifice, something I accounted for right from the start of the post by using Take(10). The above doesn’t work if we’re dealing with infinite sequences. Obviously you should never try to drain those as the program will get stuck (which in fact can be formalized as well, maybe stuff to cover another time), yet infinite sequences are great to provide the user with the potential to compute as many results as desired. Having to break laziness to make query operator composition, e.g. for Zip in our sample, work spoils this whole idea of lazy computation.

By now it should be clear that side-effects are have far-stretching implications, but we should not ignore the fact they’re useful at times. What we need to make our “consistent consumption of side-effectful sequences” is some kind of let construct.

What’s let anyway?

Functional programming languages typically provide a “let” construct, e.g. as seen in ML-style languages like F#. One form is to use the following syntax:

let id = expr1 in expr2

The above is shorthand for abstraction and application carried out right after one another:

(fun id –> expr2) expr1

Consider the next sample:

let x = 1 in (x, x)

where (…, …) is the tupling operator. Semantically the above is equivalent to:

(fun x –> (x, x)) 1

In a call-by-value setting this effectively avoids re-evaluating the expr1 expression. Of course in the sample above, there’s not much work required to “re-evaluate” the rather minimalistic expression “1”. However, when evaluating this expression causes side-effects, we’re eliminating duplicate evaluation. This is shown in the sample below where we use the Stopwatch type to retrieve the timestamp, based on a high-resolution performance counter (see MSDN documentation for information and potential caveats).

Of course we can loop in our Random type sample as well:

You get the idea. How does this apply to our side-effecting iterators? Well, what we really want is a mechanism by which we can expose the same iterator to multiple consumers without re-evaluating the side-effects that get triggered by calls to IEnumerator.MoveNext (where the iterator’s code lives in one form or another). In addition to this functional requirement, we can’t drain the whole iterator as we’d break our teeth on infinite (computed) sequences.

IEnumerable.Let – Signature and use

First, let’s have a look at the contract for the IEnumerable.Let operator we’re after here. Obviously we want to keep the order as natural as possible and what better to use than an extension method to make syntax as natural as possible:

… Let<T>(this IEnumerable<T> source, …)

That’s a good start: we can take in an IEnumerable<T> as the expr1 for the let construct. Looking back at the F# equivalent for a moment:

(fun id –> expr2) expr1

It’s clear we need to have a function that exposes the one-time evaluated (read: enumerated) to a block of code where the user can party on the exposed sequence without having to worry about duplicating side-effects. The input of such a function clearly is IEnumerable<T>, leading to:

… Let<T>(this IEnumerable<T> source, Func<IEnumerable<T>, …

So, “id” from the F# code sample above will be identified to the input of the Func delegate. Finally, what’s the output meant to be? Obviously just the output of the expr2 evaluation after feeding in expr1 through the parameter. As we’re talking about sequence operators, a natural choice is to make the output an IEnumerable as well, and to allow projections and such to happen inside we choose another generic parameter:

… Let<T, U>(this IEnumerable<T> source, Func<IEnumerable<T>, IEnumerable<U>> function)

You can guess where the output of the source is meant to go to: the output of the Let construct by itself:

IEnumerable<U> Let<T, U>(this IEnumerable<T> source, Func<IEnumerable<T>, IEnumerable<U>> function)

Makes sense? For example, for our fancy Zip over random sequence we want to be able to write the following:

var rand = new Random();
var res = rand.GetNumbers(100).Take(10).Let(nums => nums.Zip(nums, (l, r) => l + r)).All(x => x % 2 == 0);

See what’s happening here? The left-hand side to Let becomes the source, which internally is exposed as “nums”. Zip produces its output, which becomes the output of the Let construct that’s subsequently fed into All. In fact, the above could be read as:

var res = (let nums = rand.GetNumbers(100).Take(10) in
nums.Zip(nums, (l, r) => l + r))
.All(x => x % 2 == 0);

Now on to the question of the night, how to realize this?

Implementing IEnumerable.Let

Before we start implementing the let construct for LINQ to Objects, we need to make sure we fully understand the problem. Let me rephrase it one more time:

Given an IEnumerable<T> source, we need to expose it to a function is such a way that multiple consumers can only trigger a single enumerator to be active on the source. This ensures that the side-effects occurring as part of the enumeration (using MoveNext/Current) over the enumerator are not replicated.

Since many consumers can be active inside the “let body” (the function parameter in the signature), we can expect those to move at different paces. Here’s an example:

nums.Skip(5).Zip(nums, …)

In here, the Skip operator readily advances the iteration over the source 5 positions ahead. Then Zip consumes this input as well as the raw source starting from position 0. Given a sequence of { 1, 2, 3, 4, 5, 6, 7, 8, 9 }, the inputs to Zip are skewed over a distance 5, combining (6, 1), (7, 2), etc. This forces us to memorize the first 5 elements that have already been consumed by Skip, as they still have to be observed through Zip’s second input (and obviously we can’t recompute them as that’s what we’re trying to eliminate!).

For one thing, we need to keep track of elements that have been consumed from the Let-source so that consumers inside the body can get access to those computed values. An immediate question becomes whether or not we can optimize this: wouldn’t it be possible to scavenge the computed values if we are sure no single consumer inside the body can still consume it? Sounds reasonable, but there’s a deep problem here: the number of consumers can be dynamic. A good sample is SelectMany:

from x in nums
from y in nums
select x + y

This translates into the following:

nums.SelectMany(x => nums, (x, y) => x + y)

SelectMany is conceptually similar to nested loops used to enumerate a collection and for each of its elements retrieve associated objects (e.g. for each product, and each order for that product, do …). In the sample above we use nums twice, so assuming the source looks like { 1, … , 9 }, we will see the following pairs being fed to the projection function parameter:

(1, 1), (1, 2), …, (1, 9), (2, 1), …, (9, 1), (9, 2), …, (9, 9)

For the 9 elements in the left-hand side source, we’ll enumerate all of the elements in the corresponding source found by evaluating x => nums (where, in this degenerate case, we disregard the parameter x and simply return ourselves). How many times will we trigger enumeration on nums here? Well, one time for the input to SelectMany as the left-hand side, and for each element one more time for the nested enumeration. So, with 9 elements, the total will be 9 + 1 = 10. There’s no way for us to know upfront how many subscriptions will happen, so we can’t make assumptions when we can discard elements we’ve retrieved from the source.

All of those observations give rise to the introduction of a “memoized enumerator”. A what? Memoization is a technique used in functional programming to cache the result of evaluating a function knowing that function is pure, i.e. given the same inputs it always gives back the same output. A typical example is recursive Fibonacci:

Func<uint, uint> fib = null;
fib = n => n <= 1 ? 1 : fib(n - 2) + fib(n - 1);
for (uint i = 0; i < 50; i++)
Console.WriteLine(fib(i));

Good luck running this code – it will take forever to compute fib(50) (ignore the fact it doesn’t fit in a uint) due to the explosion of recursive steps and re-evaluations incurred. A generic memoization function will cache results:

static Func<T, R> Memoize<T, R>(Func<T, R> f)
{
    var cache = new Dictionary<T, R>();

    return t =>
    {
        R res;
        if (cache.TryGetValue(t, out res))
            return res;
        return cache[t] = f(t);
    };
}

This memoizer is a higher-order function that transparently (in terms of the function signature) maps a function onto one that caches evaluation results. As a result, for a given function input “t”, the function “f” can be evaluated at most once (for subsequent function calls given the same input, the dictionary will be consulted). It should be pretty clear this is precisely what we want for our Let-enumerator as well, but instead of keying off the avoidance for multiple evaluations from the function input, we’ll need to avoid it based on the position of an enumerator. Let’s discuss this.

Assume you have two consumers of the Let-input sequence: one skips ahead 5 positions, the other starts from the beginning, just as we saw before:

src.Let(nums => nums.Skip(5).Zip(nums, (l, r) => l + r))

Let’s decompose the interactions here. Zip is pulling both its left-hand side followed by its first parameter, at an equal pace. First, the end-result:

I hope the above diagram makes sense, if not look at the more conceptual diagram below:

Now we loop bottom-up: if something pulls at Zip, what does it start pulling at by itself? First it calls MoveNext on its left-hand side, which is the Skip(5) block. Skip starts by fetching the first 5 + 1 items from its input, which is the Let block, in order to yield the 6th item back to the consumer. This leads to the following situation:

The read arrows indicate the active “channels” of enumeration. Reading bottom-up, Zip requested one element from Skip(5), which on its drew 6 items through its upstream channel connected to Let. Since Let hasn’t received calls to retrieve elements from the source at positions 0 through 5, it pulled on its source to get those items, causing potential side-effects (indicated by the bombs). But beside just yielding them back to the Skip(5) caller, it also “memoizes” them in an indexed collection. The “@5” annotation on the outgoing Let arrows – representing enumerators – indicate the cursor position in the source sequence, of the element that was last yielded through the channel.

Now that Zip has an element from its left-hand side source, it needs to fetch an element from its right-hand side source, in order for the two elements to be combined by the zipper function (in our case numerical +). This looks as follows:

Notice the red channel doesn’t extend all the way to the source – we already have received the element at position 0, so we can consult the memoization store to retrieve the value from there. No observable source-induced side-effects are triggered by doing so. The cursor position for the active Let-consumer is moved to 0.

Essentially, whenever a channel queries for an element below the high-water mark of the memoization store, the element are retrieved from the store instead of pulling from the source. On to the code now. We’ll start by looking at a memoizing enumerable as we’ll use that as the building block for the Let construct. First, the IEnumerable<T> implementation:

class MemoizeEnumerable<T> : IEnumerable<T>, IDisposable
{
    private readonly IEnumerable<T> _source;
    private IList<T> _data;
    private IEnumerator<T> _enumSource;
    private bool _disposed;
    private bool _reachedEnd;

    public MemoizeEnumerable(IEnumerable<T> source)
    {
        _source = source;
    }

    public IEnumerator<T> GetEnumerator()
    {
        if (_disposed)
            throw new ObjectDisposedException("LetIterator");

        if (_enumSource == null && !_reachedEnd)
        {
            _enumSource = _source.GetEnumerator();
            _data = new List<T>();
        }

        return new MemoizeEnumerator<T>(this);
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    private bool TryMoveNext(int cursor, out T value)
    {
        Debug.Assert(cursor <= _data.Count);

        if (_disposed)
            throw new ObjectDisposedException("LetIterator");

        if (cursor < _data.Count)
        {
            value = _data[cursor];
            return true;
        }
        else
        {
            if (_reachedEnd)
            {
                value = default(T);
                return false;
            }

            if (_enumSource.MoveNext())
            {
                value = _enumSource.Current;
                _data.Add(value);
                return true;
            }
            else
            {
                // When we reach the end, no reason to delay the disposal of the source
                // any longer. Now we should avoid calls to MoveNext further on, so we
                // set a _reachedEnd flag to detect this case.
                _enumSource.Dispose();
                _enumSource = null;
                _reachedEnd = true;

                value = default(T);
                return false;
            }
        }
    }

    public void Dispose()
    {
        // Facilitates deterministic disposal of the underlying store. We can't rely
        // on Dispose calls on the enumerator object as we don't know the number of
        // consumers we're dealing with.
        if (!_reachedEnd)
        {
            _enumSource.Dispose();
            _enumSource = null;
        }

        _disposed = true;
        _data.Clear();
    }

    class MemoizeEnumerator<T_> : IEnumerator<T_>
    {
        …
    }
}

A MemoizeEnumerable<T> encapsulates an underlying IEnumerable<T> that represents the source. The GetEnumerator method for consumers to call in order to establish an enumerator triggers the MemoizeEnumerable to start consuming the input source unless it’s already doing so. This is the key to avoiding multiple source-consumers, which would lead to duplication of side-effects. The memoization store is simply a List<T>, which is indexable. What the MemoizeEnumerator<T> looks like will be shown soon.

Skipping over TryMoveNext for just a second, we look at Dispose first. As we’ve seen before, the number of enumerators over the exposed memoized data structure is something we can’t know upfront or infer from context. So, the disposal of enumerator objects doesn’t mean we can dispose the enumerator we established on the (memoized) source. We need a hint from the outside to say: it’s fine to let go the source (which could be holding on to, say, a network connection underneath). This will correspond to “scoped usage” of the Let construct as we shall see later.

Now on to TryMoveNext. Here the fetching of the underlying source happens, based on a passed-in cursor. We enforce linear progression, which is expected for MoveNext calls: the consuming enumerators should at most take one step forward at a time. If the cursor falls within the range of the memoization store, we simply retrieve the cached value from there. Otherwise, we fetch the next element from the underlying source (causing a potential side-effect once and for all for that element) and keep it in the store. If there are no further elements to be fetched as signaled by the source’s MoveNext call’s return value, we can dispose the enumerator over the source. To avoid subsequent calls on the disposed object, we keep a flag to signal we’ve reached the end. Notice we’re not dealing with multi-threaded consumers here – such worries are left as an exercise for the reader.

Finally, we should have a look at the MemoizeEnumerator inner class which obviously will call TryMoveNext in order to make progress over the shared source enumerator and memoization store. This type is fairly trivial:

class MemoizeEnumerator<T_> : IEnumerator<T_>
{
    private readonly MemoizeEnumerable<T_> _source;
    private int _cursor;
    private T_ _lastValue;

    public MemoizeEnumerator(MemoizeEnumerable<T_> source)
    {
        _source = source;
        _cursor = 0;
    }

    public T_ Current
    {
        get { return _lastValue; }
    }

    object System.Collections.IEnumerator.Current
    {
        get { return Current; }
    }

    public bool MoveNext()
    {
        return _source.TryMoveNext(_cursor++, out _lastValue);
    }

    public void Reset()
    {
        _cursor = 0;
    }

    public void Dispose()
    {
        // No disposal here - the enumerable object does the bookkeeping of the
        // underlying enumerator object. Here we're essentially just dealing with
        // a cursor into the underlying sequence.
    }
}

All there is to a memoizing enumerator is to keep its cursor, communicate it to TryMoveNext, and increment it. Notice the assert in TryMoveNext will trigger when an ill-behaved consumer continues to call MoveNext on the enumerator after it has returned false. One could pimp this case a little bit by either keeping a _reachedEnd state inside the enumerator (not to bother the enumerable object anymore in such a case) or by keeping the _cursor value in its final position as opposed to incrementing it.

Notice the enumerator’s Dispose method is not implemented for reasons explained earlier. The only thing one could do as a meaningful implementation is a _disposed flag to throw an ObjectDisposedException if the object is used beyond its disposal state. We leave this as a trivial exercise for the reader as well.

Ultimately we’ve reached a state where we can give away the entry-point to IEnumerable.Let:

public static IEnumerable<U> Let<T, U>(this IEnumerable<T> source, Func<IEnumerable<T>, IEnumerable<U>> function)
{
    using (var mem = new MemoizeEnumerable<T>(source))
    {
        foreach (var item in function(mem))
            yield return item;
    }
}

The most important thing here is obviously the memoization of the source which is fed to the function for the let-body to party on. The use of a using-block inside an iterator causes that iterator’s Dispose method to call the Dispose method on the resource in use. In other words, if one foreach’es over the result of a Let-call, exiting the loop will trigger a call to Dispose which on its turn disposes the memoized enumerable, again on its turn disposing the underlying source’s singleton enumerator. This means re-executing the Let resulting sequence itself will cause re-iteration over the underlying source. This makes sense as we only protect against duplication of side-effects inside the let-body. If you want to avoid re-execution of the Let-operator to cause duplication of side-effects by itself, wrap it in yet another Let-call.

A few samples

Time for some samples to conclude this journey. We go for two source iterators that are only of interest for their side-effects:

static IEnumerable<int> GetNums(int n)
{
    try
    {
        for (int i = 0; i <= n; i++)
        {
            Console.ForegroundColor = ConsoleColor.Red;
            Console.Write(i + "   ");
            Console.ResetColor();
            yield return i;
        }
    }
    finally
    {
        Console.ForegroundColor = ConsoleColor.Green;
        Console.WriteLine("Disposed");
        Console.ResetColor();
    }
}

static Random rand = new Random();

static IEnumerable<int> Lotto()
{
    try
    {
        for (int i = 0; i < 6; i++)
        {
            var n = rand.Next(100);
            Console.ForegroundColor = ConsoleColor.Red;
            Console.WriteLine(n);
            Console.ResetColor();
            yield return n;
        }
    }
    finally
    {
        Console.ForegroundColor = ConsoleColor.Green;
        Console.WriteLine("Disposed");
        Console.ResetColor();
    }
}

We log produced values to the console to visualize how many times the iterator is enumerated over. Obviously we write those in red as they are bloody side-effects. We’re also interested to see proper disposal, so we log that event too. A first example using SelectMany without Let shows how bad things get as we replicate side-effects:

Console.WriteLine("Without let");
{
    var source = GetNums(10);

    var res = from x in source
              from y in source
              select x + y;

    foreach (var i in res)
        ;
}
Console.WriteLine();

The result is as follows, no less than 11 iterations over the source sequence:

Next, we eliminate the common sub-expression “source” by lifting it into a Let block. Source becomes the input to Let, and inside the let-body we represent the source with the “src” identifier:

Console.WriteLine("With let");
{
    var source = GetNums(10);

    var res = source.Let(src =>
                from x in src
                from y in src
                select x + y);

    foreach (var i in res)
        ;
}
Console.WriteLine();

Now things look much better:

Obviously the computed results will be the same (not visualized here – we’re just showing the side-effects), but we got rid of the excessive side-effect replication. This said, consuming a Let’s output multiple times doesn’t prevent the source from being consulted more than once: only inside the Let-block, consumers are shielded from side-effect duplication, but outside, consumers of the Let-block itself don’t get protection:

Console.WriteLine("With let (twice)");
{
    var source = GetNums(10);

    var res = source.Let(src =>
    {
        Console.WriteLine("Let!");
        return from x in src
               from y in src
               select x + y;
    });

    foreach (var i in res)
        ;

    foreach (var i in res)
        ;
}
Console.WriteLine();

We enumerate twice over the output of Let, hence we see the side-effects twice (and not 22 times as would be the case if we left Let out of the picture altogether):

However, nothing prevents us from putting a Let over the Let we already have: let’s eliminate the common subexpression res in both foreach-statements as follows:

Console.WriteLine("With let (nested)");
{
    var source = GetNums(10);

    var res = source.Let(src =>
        {
            Console.WriteLine("Let!");
            return from x in src
                   from y in src
                   select x + y;
        });

    res.Let(src =>
    {
        foreach (var i in src)
            ;

        foreach (var i in src)
            ;

        return new int[] { }; // doesn't matter, we want an "imperative let"
    }).ToArray(); // forces evaluation
}
Console.WriteLine();

Sure enough, we’re back to the minimum amount of side-effects:

And finally, some direct uses of Memoize, assuming the following exposition on IEnumerable<T> is present:

public static MemoizeEnumerable<T> Memoize<T>(this IEnumerable<T> source)
{
    return new MemoizeEnumerable<T>(source);
}

Now we use our lottery iterator as a source and show that the sequences are not equal without memoization as they are enumerated multiple times and hence different random numbers are picked for two uses of the source:

Console.WriteLine("Without memoize");
{
    var src = Lotto();
    Console.WriteLine(src.SequenceEqual(src));
}
Console.WriteLine();

Console.WriteLine("With memoize");
{
    using (var src = Lotto().Memoize())
        Console.WriteLine(src.SequenceEqual(src));
}
Console.WriteLine();

With the Memoization in use, obviously the two sequences ought to be the same all the time:

One more thing to illustrate is the use of infinite streams by means of a Repeat operator:

public static IEnumerable<T> Repeat<T>(T value)
{
    while (true)
        yield return value;
}

public static IEnumerable<T> Repeat<T>(IEnumerable<T> source)
{
    while (true)
        foreach (var item in source)
            yield return item;
}

It should be clear that the use of eagerly evaluated operators like ToArray and ToList won’t work as a side-effect-avoiding technique in such a setting. However, with Memoize one can eliminate side-effects without getting stuck:

Console.WriteLine("Memoize prevents _|_ out");
{
    using (var mem = Enumerable.Repeat(1).Memoize())
        Console.WriteLine(mem.Take(10).Count());
}
Console.WriteLine();

Console.WriteLine("ToList may _|_ out");
{
    Console.WriteLine(Enumerable.Repeat(1).ToList().Take(10).Count());
}
Console.WriteLine();

The samples above are not of interest for side-effects (though one can easily come up with samples), but rather for their infinite character. Use of ToList will exhaust the managed heap quickly, while Memoize just fills memory for the objects that are ever requested downstream (in the case above “Take 10”).

Wonder about the _|_ notation? This is the “bottom type”, one way to type non-termination. “Entre parentheses”, we don’t have such a thing in the world of .NET, which is a pity. For example, if you have an exception throwing helper method:

static void ThrowAlways()
{
throw new MyException(/* localization fluff */);
}

and you call the above from a function to signal an exception:

static int Bar()
{
    if (cond)
        …
    else
        ThrowAlways();
}

the compiler will complain that “not all code paths return a value”. Void is not the same as bottom, flow analysis cannot know the method won’t every return. With a bottom type, e.g. using keyword “never” (or more juicy ones like “blackhole”, “getstuck”, “goodbye”, “farewell”), one could say:

static never ThrowAlways()
{
throw new MyException(/* localization fluff */);
}

Now the compiler would check statically that ThrowAlways can never reach its end (either by throwing an exception, looping infinitely or calling other “never”-returning methods). At the call-site, the compiler would be happy with Bar’s definition as well since it knows ThrowAlways never returns, hence there’s no need to be worried about not having a return value for the enclosing method. And of course, if we also had union types, we could (or maybe should, depending on how pesky the compiler would be made) warn the user that Bar may never return:

static (never | int) Bar()
{
    if (cond)
        …
    else
        ThrowAlways();
}

But all of this deserves its own discussion another time.

Conclusion

If you don’t want to tame your side-effects, you should at least have good notions about where they happen and how they may get replicated by mixing lazy and eager evaluation in languages like C#. Enumerable.Let shows one approach to taming side-effects in the context of LINQ queries with side-effecting computed sequences (iterators).

If you can’t get enough of this stuff, check out Erik Meijer’s talks on Fundamentalist Functional Programming. Credits where credits are due, the Enumerable.Let exercise shown in here presents the dual of the IObservable’s Let operator (from the Reactive LINQ framework Erik and his team have been working on lately), which I’ll talk about another time.

Left as a challenge for the reader: can you think of a way to port let’s brother “letrec” to the world of IEnumerable<T> as well? Let completeness be your source of inspiration :-).

ExceLINQ – Not Your Typical LINQ Provider

bart — Sun, 29 Mar 2009 00:16:00 GMT

Introduction

On my last trip I had the opportunity to talk on the subject of LINQ once more. Geeky as we are, this time’s session title was “LINQ in breadth”, an orthogonal view on LINQ compared to my last year’s LINQ in depth talk.

But what makes LINQ have a certain breadth? The simple answer: its spectrum of possible LINQ “provider” implementations. Far too often people think LINQ is only extensible by means of the IQueryable<T> interface which makes you opt-in to every imaginable query operator. That’s one useful side of the LINQ spectrum (albeit most of the time an overkill approach). The totally opposite end of the spectrum is ironically IEnumerable<T>. I say ironically because theoretically both interfaces are identical (I should really go into monads once more, but let’s suppress that urge). It’s just that making something LINQable is trivial if one can expose the data as an IEnumerable<T> because from that point on one can fall back to LINQ to Objects (and that’s precisely what LINQ to XML does).

The rest of the breadth comes from all intermediate implementations that are possible. I’ve mentioned before that, from a language perspective, LINQ is a tiny syntactical layer on top of the rest of the language. To be convinced about that, look at my C# 3.0 Query Expression Translation Cheat Sheet. All you’re seeing there is some kind of fixpoint algorithm that gradually compiles away the C# 3.0 language’s knowledge of query comprehension syntax till nothing but methods and operands remain.

All of this means we can party along on the syntactical sugar that LINQ provides us, as shown in my “Who ever said LINQ predicates need to be Boolean-valued?” post. It turns out I’ve talked about this spectrum theory over there too. All of this can be used for samples that are only of technical value, like LINQ to Simpsons (see below), but also to create useful stuff.

(Exercise for the reader: what’s the type of x in the fragment above?)

The genesis of ExceLINQ

So, while preparing for my demos, I was thinking about potential samples of non-obvious but nevertheless useful LINQ implementations. Rather by accident I came up with bridging Excel to LINQ. Maybe a short story on how that idea came along. One evening (night according to the post’s publication time) I was writing up a blog entry on “The M Programming Language – Part 0 – Intellipad, MrEPL, VS2008 project support and Excel integration” (more posts on that topic to follow soon). As I’m not the kind of guy that spontaneously opens Excel – which doesn’t mean I don’t like the product, I just don’t have a job that requires overdoses of spreadsheet interaction on a day-to-day basis – I took the opportunity to browse a bit more through the product in its current form. The last screenshot is where the fascination kicked in:

Clicking the little arrows on the column headers reveals a whole new world (I admit I was exposed to it in a distant past, but it was a pleasant deja-vu as you can tell, otherwise this post wouldn’t exist):

Query operators, anyone? As I already had a C# project open to prepare C# 4.0 demos on improved COM interop (posts on that to follow too), I decided to explore the Excel automation APIs a bit more. Here are a few of the interesting methods I came across:

Range.AutoFilter – filters based on one or more predicates
SortFields.Add – and much more plumbing to do sorting
_Application.Union – usable for simple column projections; a COM interop beauty with no less than 30 parameters, 28 of which are optional (luckily C# 4.0 will help out here – yes, you can say “finally” if you want)

Great, lots of stuff that’s applicable to querying. But let’s not settle for the obvious: creating a LINQ binding that results in yet another IEnumerable<T> where T is an entity type representing a set of strongly-typed columns (with an ExcelMetal.exe export tool, sounds familiar doesn’t it?). To illustrate the flexibility of LINQ I wanted the query to return something non-obvious. What about an Excel chart? In preparing my C# 4.0 talk I’d been exposed to Office interop code to create a chart in Excel, so that was certainly doable too.

Ah beautiful – it was the first time I didn’t curse myself for going on a speaking tour with 7 distinct talks. After all my M talk led me to dive into Excel, link it to C# 4.0 COM interop to end up with something applicable for my LINQ talk. And obviously I added PowerShell to the ingredients by showing off LINQ through PowerShell during that talk too :-).

The mission statement for ExceLINQ

Another great distinction between developers and managers: the latter need to open up Word to come up with a mission statement, while the former group opens up their favorite IDE to cook up a prototype. So in the true sense of “say it with code”, here’s what I want to accomplish:

using (var src = new ExcelSource<Proc>(_file))
{
    var res = from proc in src
              where proc.WorkingSet > 20 * 1024 * 1024
              where proc.Name.StartsWith("D")
              orderby proc.WorkingSet
              select new Column[] { proc.Name, proc.WorkingSet };
    pictureBox1.Image = res.ToChart(XlChartType.xlColumnClustered);
}

Or more graphically, a press of the button results in a chart being rendered:

We could go even further and allow any IEnumerable<T> to be imported into Excel transparently in order to create a chart, but in the sample above I’m simply using an existing Excel file (which I populated manually using Excel interop code). But hey, it’s a proof-of-concept.

The construction of ExceLINQ

There’s a magical touch to ExceLINQ. The query shown above does look like a regular LINQ query, yet there’s a bunch of stuff going on even in just declaring the query. What if I told you that the > operator in the first where clause is not the one you’d expect? And what if I told you that none of the query operators you’re seeing is defined in the same spot (like Enumerable or Queryable)? Indeed, everything is custom in ExceLINQ: a la carte cuisine, no microwave food.

Regular readers of this blog will be bored by what follows in this paragraph (hopefully not by the things coming in the subsequent ones), but the query fragment above translates into:

src.Where(proc => proc.WorkingSet > 20 * 1024 * 1024).Where(proc => proc.Name.StartsWith(“D”)).OrderBy(proc => proc.WorkingSet).Select(proc => new Column[] { proc.Name, proc.WorkingSet })

I kept everything on one line deliberately to emphasize the fluent interface LINQ is. At this point there’s no query comprehension syntax left and the compiler falls back to the well-known rules for method overload resolution, processing from the left to the right (duh). In other words: given src which is of type ExcelSource<Proc>, can we find a method called Where that takes one argument with type …:

src.Where(proc => proc.WorkingSet > 20 * 1024 * 1024)

Right, but what’s the type of the argument? We can only tell once we know what the type of proc is, so we can compute the type of the lambda body. One thing’s sure: the “shape” of the argument is required to be a Func<A, B>, a function from some type to another type (type theorists will see a relationship to the concept of kinds).

All we need to see from this discussion is that we can provide our own Where method (possibly an instance method, or an extension method but there’s no reason to choose for the latter option in this case) and as long as it has the right shape of signature, the compiler will be happy. Let’s reveal its signature now:

public Query<T> Where(Func<T, Filter> filter)

We see the generic parameter T comes from the surrounding type, ExcelSource<T>. Obviously T is meant to be substituted for an entity type, a strongly-typed representation of the columns in the worksheet. This mapping is nothing fancy:

[Sheet("Sheet1")]
class Proc
{
    [Column("A")]
    public StringColumn Name { get; private set; }

    [Column("B")]
    public IntColumn WorkingSet { get; private set; }
}

Ignore the custom attributes for now, those are true details required for the interop plumbing to correlate entity types to sheets and properties to columns in that sheet. Trivial stuff to define and to use. What’s more important is the typing we’re looking at. Name is not a string, it’s a StringColumn. Similarly WorkingSet isn’t an int, but rather it’s an IntColumn.

So, looking back at our Where method, “proc” ought to be an instance of Proc, hence the lambda body should be the type of:

proc.WorkingSet > 20 * 1024 * 1024

We know WorkingSet is of type IntColumn, so the > comparison operator can only come from an operator overload defined on that type:

class IntColumn : Column
{
    public static Filter operator >(IntColumn column, int value)
    {
        return new Filter(column, FilterType.GreaterThan, value);
    }

    …
}

As you can see, the return type of this operator is Filter, so the entire lambda expression is assignable to the Func<T, Filter> and the call to Where is working out fine:

src.Where(proc => proc.WorkingSet > 20 * 1024 * 1024)

returns a Query<T> instance as seen from the Where method signature. Next in the chain of method calls, we find another call to Where:

src.Where(proc => proc.WorkingSet > 20 * 1024 * 1024).Where(proc => proc.Name.StartsWith(“D”))

So Query<T> should again have a Where method defined, an indeed it does:

public Query<T> Where(Func<T, Filter> filter)

Now proc.Name is of type StringColumn, so the StartsWith method should be the guy returning the Filter instance required to make the Where method happy:

class StringColumn : Column
{
    public Filter StartsWith(string value)
    {
        return new Filter(this, FilterType.StartsWith, value);
    }
    …
}

You get the idea. In a very similar way the OrderBy method is defined on Query<T>. This time it doesn’t take in a lambda producing a Filter (as ordering is not filtering, right?), but rather a lambda that produces a Column. After all the function required to carry out an ordering is a so-called key extractor (and we don’t bother about things like composite keys here):

public Query<T> OrderBy(Func<T, Column> column)

As both properties on Proc are typed to be *Column, each of which derives from the Column base class, the OrderBy call succeeds:

src.Where(proc => proc.WorkingSet > 20 * 1024 * 1024).Where(proc => proc.Name.StartsWith(“D”)).OrderBy(proc => proc.WorkingSet)

The final call is a Select call, which is typed as follows:

public Result<T> Select(Func<T, Column[]> project)

Notice two things here:

The return type of the projection lambda is not generic (as in other LINQ implementations, where the projection function would be a Func<T, R> where R can be anything, e.g. an anonymous type). This way we make sure the user just returns a set of columns with no fancy decoration over it (like new { Bar = x.Foo } which results in an anonymous type).
The return type of the whole Select query operator is of type Result<T>, no longer Query<T>. This means we can’t continue our query beyond the Select call (assuming we don’t provide methods like Where, OrderBy, Select on Result<T>, which we don’t). By doing this, we can rest assured the user doesn’t “keep going on” and our query is terminated properly.

The last point is quite important. In fact we’ve created a state machine of types. Starting from an ExcelSource<T>, we transitioned into Query<T> to end up with Result<T>. You could go much further in controlling the order of operators and the number of operator calls that are allowed (e.g. a maximum of two Where calls) but creating much more types:

Finally we have a Result<T>, which has a method to turn the result into a chart:

public Image ToChart(XlChartType chartType)

where Image is the built-in System.Drawing.Image class from the .NET Framework.

The plumbing of ExceLINQ

We’re done with the conceptual part of our mission. The user can write queries that result in calls being made to our own methods on types like Query<T>. Even more, we gained control over the lambda expressions that are passed to those query operators too. So we have all the information about the query the user intended to write, meaning we can turn it into execution.

That’s where the plumbing part comes in. The implementation of our query operator methods needs to collect all the information about the query. Once we have aggregated all of this knowledge into a Result<T> object, we need to turn it into instructions that Excel understands. And finally, we ask Excel to generate the graph upon calling Result<T>.ToChart, producing an Image instance somehow. All of this is quite irrelevant to the LINQ topic in this post.

I’ll omit all of the COM interop magic as it doesn’t contribute much to the core idea, but there’s one thing I should dive into a bit more here. We’ve seen that purely based on the type information available through ExcelSource<T>, more particularly because of the T part in there, we can write strongly typed queries over some entity type like the one below:

[Sheet("Sheet1")]
class Proc
{
    [Column("A")]
    public StringColumn Name { get; private set; }

    [Column("B")]
    public IntColumn WorkingSet { get; private set; }
}

We’ve also seen that we defined operators like Where based on such an entity type, e.g. taking in a Func<T, Filter> where T is substituted for the particular entity type we’re dealing with:

where proc.WorkingSet > 20 * 1024 * 1024

The reason we did that is to be able to call the (in this case predicate-valued) delegate to get the corresponding filter object (i.e. the runtime representation of the > condition applied in the predicate) without further runtime hoops. Those hoops would come from the IQueryable style of query provider implementation where the predicate would not be a Func<T, Filter> but an Expression<Func<T, bool>>, hence the user could write all sorts of expressions that ultimately produce a Boolean value, and although the compiler would be fine with that, we might give up at runtime because the generated expression tree is too complex (e.g. when the user wrote something like “where CallGreenManOnMars(proc).Replied(“Okay”)”, which doesn’t make sense but type-checks fine). In some sense, we pushed down the Expression<…> part into the function signature to constrain the lambda body to something of type Filter, which is our mini (domain-specific) expression tree.

There’s something missing though: in order to get the result of the predicate delegate, we need to feed it an instance of the entity type T, in this case a Proc instance. Moreover, we need to make sure all properties are properly instantiated because we’re about to call into them during the execution of the lambda body, e.g. by doing “proc.WorkingSet”.

The way we accomplish this is by new’ing up the entity type at runtime and filling in the properties dynamically:

internal static T CreateInstance<T>()
{
    T res = Activator.CreateInstance<T>();

    var mappings = from prop in typeof(T).GetProperties()
                   select new { Property = prop, Attribute = prop.GetCustomAttributes(typeof(ColumnAttribute), false).Cast<ColumnAttribute>().Single() };

    var columns = mappings.OrderBy(column => column.Attribute.Column);
    var first = columns.First().Attribute.Column[0];

    foreach (var col in columns)
    {
        object colObj = col.Property.PropertyType.GetConstructor(BindingFlags.Instance | BindingFlags.NonPublic, null, new [] { typeof(string), typeof(int) }, null)
            .Invoke(new object[] { col.Attribute.Column, (int)(1 + col.Attribute.Column[0] - first) });
        col.Property.SetValue(res, colObj, null);
    }

    return res;
}

Let’s step through this a bit. On the first line we create an instance of T, nothing fancy (an alternative would have been to have a generic parameter constraint for a default constructor, it just turned out this way for no particularly good reason and, hey, this is just a sample). Next we use LINQ to Objects (don’t you love it?) to get all the properties and their ColumnAttribute mapping. I’m using the Single operator here, so foreign properties (which don’t have a mapping attribute) will cause our CreateInstance method to fail. I could be more polite and ignore those properties or define my own exception type here (which I should really have done) but you get the idea.

Finally, the loop going over the columns is required to instantiate each individual property. Again, we’re a bit lazy here and expect the properties to be of a Column-derived type we know about, as we assume a two-parameter private constructor is available to new that up. To make this code production quality you’d obviously go for more thorough checking code with proper exception types being used to signal failures. The bit of tricky code here is to order the columns, so that we can determine the column index in the spreadsheet, required for other COM plumbing code where we select Excel ranges. This is just an implementation detail and could be eliminated with some more careful study of the Office automation libraries (but I’m not an Office programming expert at all). Here’s a sample column type with the constructor used:

class Column
{
    protected Column(string name, int index)
    {
        Name = name;
        Index = index;
    }

    public string Name { get; private set; }
    public int Index { get; private set; }
}

class StringColumn : Column
{
    internal StringColumn(string name, int index)
       : base(name, index)
    {
    }
    …
}

The state of ExceLINQ

As mentioned repeatedly during my post write-up, ExceLINQ is more of a conceptual rapidly-prototyped piece of demo code, so there’s lots of room for improvement left to be made:

General code clean-up, proper error handling and use of C# 4.0 dynamic to reduce COM interop plumbing.
Query<T> mutates its own state on every query operator call; it would be better to return new instances on every call as queries might act as the base for other queries (a common pattern).
A better design would be to go for the “type state machine approach” as outlined in this post, to restrict the order and multiplicity of query operators.

Anyway, if you’re curious to see how all of this works, I’ve uploaded the prototype over here. Usual warnings about sample code apply. Below is a nice scenery of ExceLINQ stepping through:

Now pressing F10 applies the first Where clause, causing the filter to be applied in Excel instantaneously.

Notice the filtering icon in the first row now. This live filtering makes ExceLINQ an ideal visualization of query execution, which was a big appealing factor to use it for my “LINQ in Breadth” demo. Next we apply ordering:

and again, continuing execution causes immediate filtering application (notice the little sorting arrow in cell B1):

Enjoy!

Help! Drowning in Expression Trees, What Now?

bart — Thu, 12 Feb 2009 11:50:00 GMT

Introduction

Once more I found myself in LINQ providers land recently for a project yet unannounced. Given the relative poverty of the query language we’re targeting in that particular provider, a very common question came up: what about complex expressions in predicates? Let me give you an example:

from p in products where p.Price > 100 select p

is a pretty innocent query, right? But what about:

from p in products where EnterUnknownTerritory(p.Price * Math.PI / 4) == 26 select p

That’s the totally opposite side of the spectrum, where we can’t translate the query anymore because the “EnterUnknownTerritory” method is definitely not known in the target language. So, take a look at something “in the center”, not quite trivial but by no means impossible:

from p in products where p.Price > minPrice select p

where minPrice is a variable. You might say this is as innocent as the original query, but in fact quite some stuff is going on here. Remember that LINQ queries are composed of chains of method calls each of which represent a query operator. In the sample above that boils down to:

products.Where(p => p.Price > minPrice)

The argument to the Where method is a lambda expression that captures an outer variable, so you end up with a closure and minPrice becomes a field access on the closure class. Here’s an illustration of this behavior:

So, MemberExpressions are lurking around every corner, sometime a little unexpectedly. Another sample of user-induced complication of expression trees (most likely well-intentioned anyway) is the following:

from p in products where p.Price > 100 && someThingLocal.Equals(alsoLocal) select p

where whole parts of the expression tree can be evaluated locally, meaning the above query can be simplified by applying the rules of Boolean logic after partial evaluation of the local portions.

Approach #1 – Foreign nodes

So, how to tackle this “issue”? As part of any expression tree translator (whether it’s LINQ or something else) you’ll turn the source tree into some target tree, resembling the abstract syntax of the target domain. Typically this is carried out by some kind of expression tree visitor that recursively “visits” the tree, translating nodes and putting them together. For example, you might recognize a BinaryExpression with NodeType set to ExpressionType.AndAlso and turn it into an AndPredicate:

public BinaryPredicate VisitAndAlso(BinaryExpression andAlso)
{
return Predicate.AndAlso(Visit(andAlso.Left), Visit(andAlso.Right));
}

Here Visit is the top-level method that can take in an arbitrary (System.Linq-based) expression, and we’re turning everything into Predicate objects, our destination universe. The top-level method will look much like:

public Predicate Visit(Expression ex)
{
    switch (ex.NodeType)
    {
        case ExpressionType.AndAlso:
            return VisitAndAlso((BinaryExpression)ex);
        …
    }
}

Obviously you’ll add much more cases to the Visit method, and likely you’ll merge implementations for various binary operations that share a common implementation (recurse, construct, return). That said, at some point you’ll end up with things you don’t know about. Let’s use method calls as a sample. Maybe a method call itself is still of interest (in a sense it can be turned into a target-side equivalent), like:

p.Name.Equals(“Chai”)
String.Equals(p.Name, “Chai”)
p.Price.CompareTo(100)

but at some level, inevitably, you’ll end up with lots of unknowns, like (assuming the methods invoked below don’t have a target-side equivalent):

EnterUnknownTerritory(p.Price * Math.PI / 4)
p.Name.Normalize()

Outside the domain of method calls, similar unknowns can exist. Maybe the target language can’t cope with a Boolean Not, or with a simple numerical addition. Either way, you’re drowning in expression trees at that point, and the subtree you’re stuck at becomes an “unknown” to you.

Now two things can happen: either the unknown expression tree node has a dependency on a target-side thing (brought in scope through abstraction, i.e. lambda parameters), or it’s completely defined source-side (in the C#/VB local execution domain). The samples above fall under the former category because of the occurrence of “p” in the expression subtree.

During the first visit over the tree, you could (and maybe should) decide not to investigate the unknown territory yet, and invent some pseudo-node in the target domain AST that represents something “Foreign”:

return Predicate.Foreign(ex);

On a subsequent phase in the compiler, you’d decide whether or not you can evaluate the expression (some kind of partial evaluation of the entire expression) locally. If so, it gets substituted by a constant node (containing the result of source-side evaluation); if not, an exception occurs (like NotSupportedException). How to figure out whether you can do local evaluation or not? Detect whether or not foreign expression contains (again recursively by some visitor) references to the lambda parameter representing the input to the predicate clause (i.e. representing the target-side entity, e.g. a database row or entity).

The evaluation itself can be done in two ways:

A complete expression tree interpreter: quite a bit of work.
Some trick, like wrapping the remaining expression in a lambda expression, using the Compile method on it and invoke the resulting delegate, like this:

object result = Expression.Lambda(foreignEx).Compile().DynamicInvoke();

Note this could actually be used to figure out the foreign expression is lambda parameter free, because an InvalidOperationException will result from the Compile method if this is not the case. (Question for the reader: is the premise of requiring a foreign expression to be completely lambda-parameter-free valid?)

Approach #2 – Avoid the problem altogether

How’s that for a solution? If the target domain is sufficiently poor with a relatively little number of operators and such, you could try to avoid general expression trees altogether. But how? Let’s stick with query predicates (the where clause body) for our discussion to simplify matters a bit. Remember my post titled Who ever said LINQ predicates need to be Boolean-valued? from last year? That’s precisely the thing we’re going to leverage here. Instead of assigning the predicate lambda to an Expression<Func<T, bool>>, let’s “assign it” to a Func<T, Predicate>. Sounds awkward? Not really, if the way to build up the Predicate instance (which is already in a pretty good shape to be turned into the final destination language, as it reflects the AST of the target language quite accurately already) is user-friendly enough.

What do I mean with that? Well, you most certainly don’t want the user to write the following:

from p in products where Predicate.AndAlso(Predicate.LessThan(p.Price, 100), …) select p

but it would just work fine (for reasons outlined in my Who ever said LINQ predicates need to be Boolean-valued? post). However, let’s look at the problem step-by-step, inside-out. What’s up with that p.Price thing? How can we still know all the metadata about that guy? Remember, what we’re defining above in a hidden way is a simple lambda expression of type Func<Product, Predicate>:

p => Predicate.AndAlso(Predicate.LessThan(p.Price, 100), …)

That is, give it a Product instance and it will give you back a Predicate instance. But we won’t have Product instances till we’ve executed the query, and to execute the query we need to have the predicate first. Err, something’s not quite right yet as we’re turning in circles. The crux is in the use of p.Price somewhere deep inside the lambda expression (in fact, every reference to p is where the snake bites its own tail). We clearly want to have IntelliSense on every p. (“p dot”) showing all the properties on the entity we can use in our predicate. But on the other hand, executing the lambda with some Product instance, we don’t want to traverse the “dot” into the Price property above, as we need to capture the fact we’re putting a condition on the price of the product.

Columns and values

So, that’s where things get a little tricky. What about making the Price property something that behaves just like a decimal (assuming that’s the type we want) – well, possibly in a restricted way, see further – but still knows its own identity (i.e. it’s a representation of an underlying field/column/attribute/… with the name “Price”). Actually, here we already have an opportunity to control what the user can do with the field. Maybe the target-side doesn’t support, say, addition. So, we want to disallow that (statically). It should be clear by now that p.Price should have a type different from a “raw” decimal. It represents a column, that carries an identity, and can be instantiated at some time to become a value. Let’s ignore the latter part for now and just focus on the “column has a name” part (enough to formulate a query expression). Here’s a proposal:

class Column
{
    internal Column(string name)
    {
        Name = name;
    }

    public string Name { get; private set; }

    public NullCheck HasValue
    {
        get
        {
            return new NullCheck(this, false);
        }
    }

    public override string ToString()
    {
        return "[" + Name + "]";
    }
}

The class above acts as the base class for any column. As our target domain is “nullable” regardless of the data type (i.e. not discrepancies in nullability based on reference or value type taxonomies), we also provide a HasValue property here, which returns something that acts like a Boolean but captures semantics for use in query translation. Let’s come back to that in a few moments, but dive into the Column subclass for decimal columns first:

sealed class Number : Column
{
    internal Number(string name)
        : base(name)
    {
    }

    public Comparison Equals(NumberValue value)
    {
        return Comparison.Equal(this, value);
    }

    public static Comparison operator <(Number a, NumberValue b)
    {
        return Comparison.LessThan(a, b);
    }

    public static Comparison operator <(NumberValue a, Number b)
    {
        return Comparison.GreaterThan(b, a);
    }

    …
}

Again, here we have an opportunity to be different. In the above, I’m mimicking the target domain already in that I’m stepping away from the CLR types into target types. For example, here we talk about Number instead of Decimal (maybe because the target domain only has one numerical format). But notice how the operator overloads (I’ve omitted the opposite ones, which are identical in nature) don’t return Booleans but Comparison objects. Again, wait a moment for a peek at the Comparison type. First we need to talk about the difference between Number and NumberValue. NumberValue is the source-side representation of a constant number, e.g. in our sample query the “100” we’re comparing to would be a NumberValue. That’s where the two worlds meet: in writing a query, you simply use literals in your source language of choice, but NumberValue allows us to transition to the target domain smoothly:

sealed class NumberValue : Value
{
    private NumberValue(decimal value)
    {
        Value = value;
    }

    internal decimal Value { get; private set; }

    public override string ToString()
    {
        return Value.ToString();
    }

    public static implicit operator NumberValue(decimal x)
    {
        return new NumberValue(x);
    }

    …
}

Value is a trivial empty base class (just to have a base class in places where we need it to make our code as generic as possible). The only way to construct a NumberValue is by an implicit operator that (and that’s where things are seamless) “lifts” the CLR value into our domain-specific representation. Notice you could perfectly have additional such conversions that allow you to take in other numerical types, causing them to be normalized to the common type the target language knows about.

Comparisons

Now we know about the leaf nodes of the predicate trees, namely columns and values, we can turn to their parents. Predicates are based on conditions, that can be of various kind. Relational operators, null checks, string matching, etc are a few samples of such possibilities. What about the LessThan comparison?

class Comparison : Predicate
{
    internal Comparison(PredicateType type, Column column, Value value)
        : base(type)
    {
        Column = column;
        Value = value;
    }

    internal Column Column { get; private set; }
    internal Value Value { get; private set; }

    public override string ToString()
    {
        string op = null;

        switch (Type)
        {
            case PredicateType.LessThan:
                op = "<";
                break;
            …
        }

        return Column.ToString() + " " + op + " " + (Value == null ? "null" : Value.ToString());
    }

    public static Comparison LessThan(Column column, Value value)
    {
        if (column == null)
            throw new ArgumentNullException("column");

        if (value == null)
            throw new NotSupportedException("Cannot apply comparison operator with a null value argument.");

        return new Comparison(PredicateType.LessThan, column, value);
    }

    …
}

Obviously, you can envision much more such factory methods. The key here is that all of those comparisons represent (part of) a predicate (see further) but are purely a representation instead of something executable locally. I.e. writing p.Price > 100 will result in a Comparison object with Column set to the Number(Column) pointing a the “Price” column, and Value set to a NumberValue carrying the decimal value of 100. We’ve just created a domain-specific representation of the essential building blocks of predicates.

Our NullCheck we met earlier is built in a very similar way, although it only refers to a column (it’s a unary operator so to speak):

class NullCheck : Comparison
{
    internal NullCheck(Column column, bool isNull)
        : base(isNull ? PredicateType.IsNull : PredicateType.IsNotNull, column, null)
    {
        IsNull = isNull;
    }

    internal bool IsNull { get; private set; }

    public static NullCheck operator !(NullCheck check)
    {
        return new NullCheck(check.Column, !check.IsNull);
    }

    public override string ToString()
    {
        return base.ToString();
    }
}

Notice we just play the rules of Booleans, and you can negate a null-check to get a not-null—check. Dead easy.

Actually there’s a special type of column that needs special treatment: Boolean columns (like p.IsInStock) can be used as a condition straight away (i.e. leaving off the == true comparison). That means a Boolean column should be implicitly convertible into a Condition:

sealed class Boolean : Column
{
    internal Boolean(string name)
        : base(name)
    {
    }

    public static Comparison operator !(Boolean a)
    {
        return Comparison.Equal(a, new BooleanValue(false));
    }

    public static implicit operator Comparison(Boolean a)
    {
        return Comparison.Equal(a, new BooleanValue(true));
    }

    …
}

Again I’ve omitted a bunch of operator overloads (like ==, !=) that are quite predictable.

Predicates

Finally the predicates themselves. Comparisons already are predicates, hence their base class being Predicate. However, predicates need to be combinable using Boolean operators, so we need a bit of plumbing there as well:

class Predicate
{
    internal Predicate(PredicateType type)
    {
        Type = type;
    }

    public PredicateType Type { get; private set; }

    public static Predicate operator &(Predicate a, Predicate b)
    {
        return new BinaryPredicate(PredicateType.And, a, b);
    }

    public static Predicate operator |(Predicate a, Predicate b)
    {
        return new BinaryPredicate(PredicateType.Or, a, b);
    }

    public static Predicate operator !(Predicate a)
    {
        return new UnaryPredicate(PredicateType.Not, a);
    }

    public static bool operator false(Predicate a)
    {
        // Used by operator && (7.11.2)
        // x && y --> T.false(x) ? x : T.&(x,y)
        return false;
    }

    public static bool operator true(Predicate a)
    {
        // Used by operator || (7.11.2)
        // x || y --> T.true(x) ? x : T.|(x,y)
        return false;
    }
}

The interesting thing here is that the operators && and || are not overloadable by themselves. The C# specification, section 7.11, details how short-circuiting operators && and || are defined in terms of more basic building blocks: &, |, true and false. So, we play a trick above: by defining operator overloads for true and false (you can think of those as “has value true” and “has value false” checks), we can force the overloads for & and | to be called at all times, eliminating short-circuiting behavior. Here’s a sample:

p.Name == “Chai” && p.Price < 100

Both sides of the && are Comparison objects, which have an overload for the & operator, in addition to the false operator (the || case is defined symmetrically in terms of | and true), so the expression above turns into:

Comparison left = p.Name == “Chai”;
Predicate.false(left) ? left : left & (p.Price < 100);

By returns “false” from the “false” call (I know, it gets abstract), we always end up in the bold part of the conditional expression above, forcing the & operator overload to be called (so, we’re in control again). And actually, it’s not much of a trick after all: by returning “false” from both the “false” and “true” operators, we actually say: “we don’t know yet whether this thing is true or false, please be pessimistic and don’t try to short-circuit this evaluation” (in a sneaky way mumbling to ourselves: “and we’ll do the rest, as you’ll blindly call us on either & or |”).

Now it should be clear that Boolean operators “just work” based on the operator overloads above. The UnaryPredicate returned from ! is straightforward, and so is the BinaryPredicate on & and |, so let’s show just one of the two:

class BinaryPredicate : Predicate
{
    public BinaryPredicate(PredicateType type, Predicate left, Predicate right)
        : base(type)
    {
        Left = left;
        Right = right;
    }

    internal Predicate Left { get; private set; }
    internal Predicate Right { get; private set; }

    public override string ToString()
    {
        string op = null;

        switch (Type)
        {
            case PredicateType.And:
                op = "and";
                break;
            case PredicateType.Or:
                op = "or";
                break;
        }

        return "(" + Left.ToString() + " " + op + " " + Right.ToString() + ")";
    }
}

No surprises here. So ultimately, the expression p.Name == “Chai” && p.Price < 100 results in a Predicate instance that carries all the semantics of the predicate and that can be translated (by means of a visitor over our AST representation) into the target domain. Here’s the PredicateType enum that illustrates the breadth of the predicate expressiveness:

enum PredicateType
{
    LessThan,
    LessThanOrEqual,
    GreaterThan,
    GreaterThanOrEqual,
    Equal,
    NotEqual,
    IsNull,
    IsNotNull,
    StartsWith,
    EndsWith,
    Contains,
    Matches,
    And,
    Or,
    Not,
}

Entities

We have all the materials to be successful in building up a Predicate given an entity object, like Person. Remaining question is how to write such an entity type in a straightforward way, given that the properties need to be subtypes of the Column class (like Number, (our own) Boolean, etc). Here’s a naive attempt:

class Product
{
    public String Name { get { return new String("productName"); } }
    public Number Price { get { return new Number("unitPrice"); } }
}

Brr, that’s by no means a nice representation. We’re stating the obvious a number of times: Name is a String (again, one of our subclasses of Column, maybe it should be called StringColumn after all, oh well), referring to a column with name “productName”. Same deal for Price. Lots of boilerplate here just to be able to write queries against a container of such objects. Ideally, we’d be able to write something like:

class Product
{
    [Column("productName")]
    public String Name { get; private set; } }

    [Column("unitPrice")]
    public Number Price { get; private set; } }
}

Question is how we can magically populate those properties. There are lots of tricks to do this; I’ll illustrate one below. But first, the model above doesn’t allow us to use the same type for the results of the query (we have no place to stick values). In the typical LINQ providers world, that’s a problem. In more exotic scenarios, we might just want to use LINQ to formulate a query, send it to a server and get some kind of visualization of the results back other than raw data. If the latter is the case (as it turned out to be for the problem this blog post is inspired by), this restriction is not a problem. However, even if we’d have to write a “classic” LINQ provider that allows users to return data, you could hack up a solution that looks like this. Maybe I’ll cover that another time as it’s quite an elegant approach to the problem.

Back to reality: being able to formulate the query requires us to populate the entity object instance with “good” values for its column properties. How did we get here? Well, we don’t have a mechanism anymore that can capture things like p.Name (without causing client-side evaluation). I say “anymore” because we’ve given up expression trees which exactly have that power. In order to populate the properties on the entity type, we could sacrifice the inheritance hierarchy and require the user to derive from some base class called Entity. Again, if we’re just interested in formulating a query, the entity object doesn’t have to do much more than act as a client-side metadata-container in the local type system, so this restriction shouldn’t be a stumble block:

class Product : Entity
{
    [Column("productName")]
    public String Name { get { return new String("Name"); } }

    [Column("unitPrice")]
    public Number Price { get { return new Number("Price"); } }
}

Now, what does the ColumnAttribute (used for mapping purposes) look like?

[AttributeUsage(AttributeTargets.Property, Inherited = false, AllowMultiple = false)]
sealed class ColumnAttribute : Attribute
{
    readonly string name;

    public ColumnAttribute(string name)
    {
        this.name = name;
    }

    public string Name
    {
        get { return name; }
    }
}

Given this, the role of the Entity base class will be to reflect upon the entity object itself, resolve the mapping attributes, new up column objects (like Number, String, etc), carrying the column they refer to:

sealed class Number : Column
{
    internal Number(string name)
        : base(name)
    {
    }

Here’s a possible simple implementation of the Entity constructor:

class Entity
{
    public Entity()
    {
        foreach (var prop in this.GetType().GetProperties())
        {
            var mapping = prop.GetCustomAttributes(typeof(ColumnAttribute), false).Cast<ColumnAttribute>().SingleOrDefault();
            if (mapping != null)
            {
                var column = prop.PropertyType.GetConstructor(BindingFlags.Instance | BindingFlags.NonPublic, null, new Type[] { typeof(string) }, null).Invoke(new object[] { mapping.Name });
                prop.SetValue(this, column, null);
            }
        }
    }
}

Nothing more than some reflection voodoo to find all the properties, corresponding mappings, private property setters and invoke the constructor for the column type required, passing in the column mapping value. “Cooperative instantiation” if you really want to hear a fancy word that summarizes it all :-).

The result

Let’s write a query and see how all of this works in concert. To be able to write such a query I’m going to provide a dummy implementation of a Source<T>, in order to allow the query expression pattern to work:

class Source<T> where T : new()
{
    private Predicate _predicate;

    public Source<T> Where(Func<T, Predicate> where)
    {
        _predicate = where(new T());
        return this;
    }
}

Now we can target this source with a LINQ query as follows:

var res = from p in new Source<Product>() where p.Price > 100 && p.Name == "Chai" select p;

Notice how all the operator overloads do their thing:

The user can’t tell the difference with a regular query (i.e. against CLR types) but can’t fall off the ship either now: no exotic methods will be allowed in the expression if they don’t participate in the typing for the Predicate, Comparison, etc. Obviously, you can still substitute parts of the expression by local values (that can be retrieved by doing whatever you wish) but the other way around – trying to use the entity column references like p.Price and p.Name – won’t work:

From an operation point of view, how did we manage to get the Predicate instance that represents the whole where clause? Take a look at the Where method definition:

public Source<T> Where(Func<T, Predicate> where)
{
    _predicate = where(new T());
    return this;
}

The only thing to realize here is that T, which is substituted for Product in the sample, is not a concrete instance of the entity type, but merely a metadata container as discussed before. In a bottom-up fashion, our query above translates into a Predicate as follows:

new T() gives us a new Product object, where the base constructor takes care of resolving the column mappings
calling the “where” delegate (which refers to the lambda expression from the query expression) will evaluate like this:

p.Price becomes a Number, as instantiated by the constructor trick above and pointing at the unitPrice column;
p.Price > 100 causes the 100 to become a NumberValue (through the implicit conversion), and the comparison becomes a Comparison through the > operator overload;
similar things happen for p.Name == “Chai”;
the two Comparison objects are combined through the & operator overload (together with the “false” operator trick), this produces a Predicate instance;
we’re done…

Under the debugger, the result looks like this (thanks to the ToString implementation):

Ah, I like it!

Download

You can find the code of this blog post here. All usual warnings apply: no quality assurance was carried out, use at your own risk, and blahblah.

Cheers!

LINQ and The Matrix – Introducing MLinq

bart — Tue, 10 Feb 2009 18:46:55 GMT

Today we’ll take a look at project “MLinq”, a very simple way to perform symbolic matrix calculations based on LINQ expression trees.

Introduction

But first, why would you even want to do this? Let me tell you I’m a big believer of the power of mathematical notation. Say you’ve been asked to write a piece of code that will carry out rotation of points in an n-dimensional space. To simplify matters, just consider two dimensions. Lots of readers will know this isn’t that hard using matrices:

So far so good, but now you need to know matrix multiplication in order to concretize the formula for both coordinates. Not a big deal for this particular case, but composability suffers: next you want to take the output of this rotation and feed it in to a transposition, another rotation, and so on. Wouldn’t it be nice just to write the formula as-is and let the system figure out how to turn it into execution? Obviously matrices are just the tip of the iceberg, arbitrary mathematical expressions can be represented in a symbolic format and turned to execution somehow. However, we don’t intend to write a whole symbolic math framework as part of the journey, as others have done this before (Maple, Matlab, Mathematica, to name a few)...

Let’s go back to our sample of matrix multiplication. What we’re after is something along those lines:

var t = MathExpression.Symbol<double>("t");
var p = MathExpression.Symbol<Point>("p");

MatrixExpression<double> rotate = new Expression[2, 2] { { MathExpression.Cos(t), -MathExpression.Sin(t) },
                                                         { MathExpression.Sin(t),  MathExpression.Cos(t) } };

MatrixExpression<double> point  = new Expression[2, 1] { { p.X() },
                                                         { p.Y() } };

var rot = (rotate * point).Compile<Func<Point, double, Point>>(p, t);

Console.WriteLine(rot(new Point(1, 0), Math.PI / 4));

First we define two symbolic constants, t and p. The first symbol, t, stands for the rotation angle (theta) in radians; the second symbol, p, stands for the point to rotate. Next, we define two matrices: one for the rotation matrix (using factory methods for the symbolic representation of cos(theta) and sin(theta)), and another one for the components of the point (actually the X and Y over there could benefit from some dynamic typing features, see further, as the empty method call parentheses pairs are aesthetically unpleasing). Where the magic happens is in the line below:

var rot = (rotate * point).Compile<Func<Point, double, Point>>(p, t);

Here we do a bit too much all at once, but it should still be comprehendible enough. First we multiply the two matrices in a “natural” way (you can already smell operator overloading everywhere, don’t ya?), and friendly ask the resulting expression to compile itself into a delegate that given a point and a rotation angle carries out the rotation, returning the resulting point.

Once we have all of this, we have a compiled piece of code at our service to rotate as much points as we see fit to. The sample above prints the following to the screen, rotating point (1,0) over an angle of 45° (counter-clockwise that is):

(0.707106781186548,0.707106781186547)

… something every self-respecting math-aware programmer should have predicted almost instantaneously.

Matrix expressions

The first piece of glue we need to get this to work is a way to express matrices. Core question becomes what makes up a matrix. The answer is: cells. What do we want those cells to contain? Answer: expressions. So we end up with an array of cells (let’s stick with two dimensions as we’re talking about matrices and not a higher-order construct like tensors).

Next, what can we do with a single matrix by itself? It makes sense to be able to retrieve an arbitrary cell’s “value”, i.e. the expression that lives in the cell with indices i and j. Notice this “value” isn’t actually a value, it’s an expression representing the cell’s contents in a symbolic way (e.g. x + y, where x and y come from somewhere, maybe as a result of adding together two matrices of the same dimensions).

Now that we know our intent with individual matrices, what about operations on one or more matrices, like negation, addition, subtraction, multiplication, and more matrix-specific operations like transposition and calculating the determinant of a matrix? An obvious choice here is to leverage the power of operator overloading. Say we want to add up two matrices, what will the result look like? Assuming the dimensions of both arrays match up (a requirement to add two matrices together), each cell will consist of an expression that is the sum of the corresponding expressions in both the input matrices. In other words, we do cell-by-cell addition. Operations like multiplication are a bit more involved though.

An important question in this whole discussion is whether we want to build up the individual cell expressions at the time a matrix operation is carried out (like addition), or we just want to keep around the fact we applied an operation between different matrices, without building up the expressions for individual cells. In some sense, the former approach is eager while the latter is lazy. And actually, the lazy approach makes sense as the user might just be interested in retrieving the contents of cell (123, 654) after carrying out a bunch of operations on 1024x1024 matrices. It would clearly be a waste of effort to build up expression trees for all other cells. This said, it should be possible to forcefully build up the resulting (symbolic) matrix expression if the user thinks that’s the thing to do (maybe because all cell values are needed). So we’ll go with the lazy variant as the foundation.

Enough about design, let’s go into implementation. Or wait, one more thing: we’ll treat expressions as immutable for very good reasons and stay in a functional world as much as possible. This said, here’s the class with factory methods for matrices (omitted null checks and such for clarity):

public static class MatrixExpression
{
    public static NewMatrixExpression<T> New<T>(Expression[,] elements)
    {
        return new NewMatrixExpression<T>(elements);
    }

    public static BinaryMatrixExpression<T> Sum<T>(MatrixExpression<T> left, MatrixExpression<T> right)
    {
        return new SumMatrixExpression<T>(left, right);
    }

    public static BinaryMatrixExpression<T> Product<T>(MatrixExpression<T> left, MatrixExpression<T> right)
    {
        return new ProductMatrixExpression<T>(left, right);
    }

    public static UnaryMatrixExpression<T> Negate<T>(MatrixExpression<T> operand)
    {
        return new NegateMatrixExpression<T>(operand);
    }

    public static UnaryMatrixExpression<T> Transpose<T>(MatrixExpression<T> operand)
    {
        return new TransposeMatrixExpression<T>(operand);
    }

    public static Expression Determinant<T>(MatrixExpression<T> operand)
    {
        throw new NotImplementedException("Left as an exercise for the reader.");
    }
}

For instance, to get into matrix world, we have to start by calling MatrixExpression.New<T> at some point. This takes in a two-dimensional array of LINQ expression trees that represent, symbolically, the contents of the matrix’s cells. I didn’t want to call this guy a “constant expression” because of its possibly parameterized nature (containing x’s and y’s). The other operators are quite easy to grasp I guess: most of them build up new matrix expressions based on existing ones, with the exception of Determinant that returns to LINQ expression tree land (and is left as a fun exercise for the reader :-)). In essence all of those play the role of constructors, which will become more convenient once we have operator overloads in place (see further).

So, what does a matrix expression by itself look like?

public abstract class MatrixExpression<T>
{
    internal MatrixExpression(MatrixExpressionType type)
    {
        NodeType = type;
    }

    public Expression this[int i, int j]
    {
        get
        {
            if (i < 0 || i >= Rows)
                throw new ArgumentOutOfRangeException("i");



            if (j < 0 || j >= Columns)
                throw new ArgumentOutOfRangeException("j");

            return Retrieve(i, j);
        }
    }

    public MatrixExpressionType NodeType { get; private set; }

    public int Rows { get; internal set; }
    public int Columns { get; internal set; }

    internal abstract Expression Retrieve(int i, int j);

    public Expression ToBLOCKED EXPRESSION
    {
        // See further.
    }

    public override string ToString()
    {
        // See further.
    }

    public R Compile<R>(params ParameterExpression[] parameters)
    {
        // See further.
    }

    public static BinaryMatrixExpression<T> operator +(MatrixExpression<T> left, MatrixExpression<T> right)
    {
        return MatrixExpression.Sum(left, right);
    }

    public static BinaryMatrixExpression<T> operator *(MatrixExpression<T> left, MatrixExpression<T> right)
    {
        return MatrixExpression.Product(left, right);
    }

    public static UnaryMatrixExpression<T> operator -(MatrixExpression<T> operand)
    {
        return MatrixExpression.Negate(operand);
    }

    public static UnaryMatrixExpression<T> operator ~(MatrixExpression<T> operand)
    {
        return MatrixExpression.Transpose(operand);
    }

    public static implicit operator MatrixExpression<T>(Expression[,] ex)
    {
        return MatrixExpression.New<T>(ex);
    }
}

The operator overloads at the bottom shouldn’t be too strange (I’ve omitted a few for simplicity), but maybe the last one deserves some more attention. It’s nothing more but an implicit conversion operator between a two-dimensional array of expressions into a matrix expression, allowing you to write things like:

MatrixExpression<double> rotate = new Expression[2, 2] { { MathExpression.Cos(t), -MathExpression.Sin(t) },
                                                         { MathExpression.Sin(t),  MathExpression.Cos(t) } };

As you can see, a matrix expression by itself is quite an abstract beast (at least on the instance level). It knows how much rows and columns it has, what its node-type is (just to reduce type casts) and how to retrieve elements (the abstract method will be implemented by the various subclasses and omits bounds checking, we control the bounds of the indices that come in through the indexer and trust implementers to provide a meaningful implementation for indices that are within range). There’s some common functionality though, like pretty printing (ToString). Let’s show that one first:

public override string ToString()
{
    StringBuilder sb = new StringBuilder();

    sb.Append("{ ");
    for (int i = 0; i < Rows; i++)
    {
        sb.Append("{ ");
        for (int j = 0; j < Columns; j++)
        {
            sb.Append(Retrieve(i, j).ToString());
            if (j != Columns - 1)
                sb.Append(", ");
        }
        sb.Append(" }");

        if (i != Rows - 1)
            sb.Append(", ");
    }
    sb.Append(" }");

    return sb.ToString();
}

No surprises here, just calling into ToString on the individual expressions for the cells retrieved through the Retrieve method. So, in essence, ToString forces the cells to be “computed” in a symbolic fashion (e.g. ToString invoked on a summation matrix expression will yield cell-left + cell-right in a symbolic fashion, e.g. x + y).

Printing isn’t the most exciting thing though, but we’ll defer the discussion of ToExpression and Compile for a little while longer, and show how to implement concrete matrix expressions first.

Implementing sum and product

So, how does a concrete matrix expression implementation look like? Let’s start by taking a quick look at the NewMatrixExpression, which will act as a leaf node in matrix expression trees:

public sealed class NewMatrixExpression<T> : MatrixExpression<T>
{
    private Expression[,] _elements;

    internal NewMatrixExpression(Expression[,] elements)
        : base(MatrixExpressionType.New)
    {
        _elements = elements;

        Rows = elements.GetLength(0);
        Columns = elements.GetLength(1);
    }

    internal override Expression Retrieve(int i, int j)
    {
        return _elements[i, j];
    }
}

This thing does nothing more but storing a reference to the array of expressions (representing each individual cell), with a trivial implementation of Retrieve on top of it. All we’ve done is abstracted the concept of a two-dimensional array a bit further. (Notice we don’t have true immutability here as we pass in a reference to an existing array of expressions, modifying that will have effects on the whole matrix expression tree defined on top of it…).

Enough trivialities, let’s turn to the real stuff by taking a glimpse of the SumMatrixExpression:

public sealed class SumMatrixExpression<T> : BinaryMatrixExpression<T>
{
    internal SumMatrixExpression(MatrixExpression<T> left, MatrixExpression<T> right)
        : base(MatrixExpressionType.Sum, left, right)
    {
        if (left.Rows != right.Rows || left.Columns != right.Columns)
            throw new InvalidOperationException("Dimensions do not match.");

        Rows = left.Rows;
        Columns = left.Columns;
    }

    internal override Expression Retrieve(int i, int j)
    {
        return Expression.Add(Left.Retrieve(i, j), Right.Retrieve(i, j));
    }
}

Still we’re fairly minimalistic in the implementation. We do a little checking of the incoming matrices to make sure the dimensions match, and call into our base class constructor to create a “binary matrix expression” (nothing more than a container for a two MatrixExpression instances, of the same generic parameter T, named Left and Right). The interesting part is Retrieve, which locates the requested cell in both matrices and returns a new expression tree representing the sum of the cells. So, internally matrix expressions perform their operations based on the underlying LINQ expression trees.

Cool, so how does a product matrix look like? A bit more complicated due to the less trivial mathematical definition, but again relatively straightforward and without boilerplate code:

public sealed class ProductMatrixExpression<T> : BinaryMatrixExpression<T>
{
    private int _k;

    internal ProductMatrixExpression(MatrixExpression<T> left, MatrixExpression<T> right)
        : base(MatrixExpressionType.Product, left, right)
    {
        if (left.Columns != right.Rows)
            throw new InvalidOperationException("Dimensions do not line up.");

        Rows = left.Rows;
        Columns = right.Columns;

        _k = left.Columns;
    }

    internal override Expression Retrieve(int i, int j)
    {
        var res = Expression.Multiply(Left.Retrieve(i, 0), Right.Retrieve(0, j));

        for (int k = 1; k < _k; k++)
            res = Expression.Add(res, Expression.Multiply(Left.Retrieve(i, k), Right.Retrieve(k, j)));

        return res;
    }
}

If you can’t remember how to multiply matrices, open up your favorite search engine to find the answer. You’ll see we’re simply encoding that algorithm above by means of a single for-loop, building up an expression tree that’s a sum of products of cells.

I’ll leave the implementation of Transpose (rows become columns and vice versa) and Negate (negate every cell) to the reader.

Preparing for evaluation

Next we need to take a look at how to evaluate a matrix expression, i.e. how to yield concrete values when supplying substitutions for the symbols. But wait a minute, where to those symbols come from? Say, we’re creating a new matrix and want to stick x and y in some cells, what precisely are x and y? The answer is: ParameterExpression, one of the node types of LINQ expression trees. That by itself is simple enough, but on the surface we might want to abstract that a little to make things more general and more aesthetically pleasing. (Actually, I’m deviating a little here into the world of OMMLinq, where MatrixExpressions are a subset of MathExpressions.) Here’s the glue we want to add:

public class MathExpression
{
    private Expression _ex;

    internal MathExpression(Expression ex)
    {
        _ex = ex;
    }

    public static MathExpression operator -(MathExpression op)
    {
        return new MathExpression(Expression.Negate(op._ex));
    }

    public static MathExpression Cos(MathExpression arg)
    {
        return new MathExpression(Expression.Call(typeof(Math).GetMethod("Cos"), arg._ex));
    }
    
    public static MathExpression Sin(MathExpression arg)
    {
        return new MathExpression(Expression.Call(typeof(Math).GetMethod("Sin"), arg._ex));
    }

    public static SymbolMathExpression Symbol<T>(string name)
    {
        return new SymbolMathExpression(Expression.Parameter(typeof(T), name));
    }

    public static implicit operator MathExpression(Expression ex)
    {
        return new MathExpression(ex);
    }

    public static implicit operator Expression(MathExpression ex)
    {
        return ex._ex;
    }
}

public class SymbolMathExpression : MathExpression
{
    private ParameterExpression _ex;

    internal SymbolMathExpression(ParameterExpression ex) : base(ex)
    {
        _ex = ex;
    }

    public static implicit operator ParameterExpression(SymbolMathExpression ex)
    {
        return ex._ex;
    }
}

I’ve omitted a bunch of operators (trigonometry functions, exponentials and logarithms, combinatorials, etc), to reduce the concept of MathExpression to the bare minimum needed for our rotation sample. The key thing here is to see how implicit conversions allow us to go back and forth between LINQ expression trees and math expressions. It’s a bit unfortunate the LINQ expression trees form a closed world (but for a very good reason), so you don’t get to extend that library, ending up with a common base type for all expression tree nodes, so we cook our own. But in essence, once we’re in the world of MathExpression, operations are defined to apply operators and such, without leaking the LINQ expression tree implementation to the outside as part of those operations (unless the raw expression tree is needed, it stays within the walls of this domain-specific expression tree format).

From the above, you can see how we’ve introduce syntactical sugar for a ParameterExpression in the form of MathExpression.Symbol<T>:

var t = MathExpression.Symbol<double>("t");
var p = MathExpression.Symbol<Point>("p");

This feels much more natural and domain-specific than a raw ParameterExpression from LINQ. What Point is defined like shouldn’t be too much of a surprise: two double-valued properties X and Y (and again, immutable).

Given all of this, you can see how (with additional operators on MathExpression if required) larger and more complex math expressions are built: simply by using the constructor factory methods on MathExpression. That’s how we end up with the definition of the rotation and point matrices:

MatrixExpression<double> rotate = new Expression[2, 2] { { MathExpression.Cos(t), -MathExpression.Sin(t) },
                                                         { MathExpression.Sin(t),  MathExpression.Cos(t) } };

MatrixExpression<double> point  = new Expression[2, 1] { { p.X() },
                                                         { p.Y() } };

A few things should stand out here. First, why did I decide to make MatrixExpression “compatible with” a two-dimensional array of LINQ expressions, as opposed to MathExpression objects? The sole reason right now is because of simplification in the implementation of matrices; more specifically, Expression.Add (and its brothers) can’t do operator overload resolution by themselves. For instance, if you’d have two matrices of complex numbers and the ComplexNumber class has an operator overload for +, Expression.Add on two such terms won’t be able to find that operator overload by itself. To avoid distraction on implementing overload resolution rules, I’ve omitted this kind of plumbing (although you can still make it crash by using “unconventional” matrices, e.g. of string elements, which do not have a built-in + operator either).

The second observation is the use of methods on p to retrieve the point’s coordinates. As I wanted to show the point’s coordinates explicitly (as opposed to multiplying the rotation matrix, which is 2 x 2, with a point, that would look like 1 x 1), I needed a way to extract the coordinates. Simply calling the properties for X and Y doesn’t help, as those return the double values directly. Rather, we need some kind of indirection: a symbolic representation of “take the X coordinate of point p”. I’ve hacked this up using a couple of extension methods:

static class PointExtensions
{
    public static MathExpression X(this MathExpression ex)
    {
        // Could be generalized using C# 4.0 "dynamic".
        return new MathExpression(Expression.MakeMemberAccess(ex, ((Expression)ex).Type.GetProperty("X")));
    }

    public static MathExpression Y(this MathExpression ex)
    {
        // Could be generalized using C# 4.0 "dynamic".
        return new MathExpression(Expression.MakeMemberAccess(ex, ((Expression)ex).Type.GetProperty("Y")));
    }
}

Essentially, those build up math expressions based on expression trees that refer to the respective properties. We can’t make this happen automatically while still having somewhat nice syntax. Expression trees can be created for lambda expressions in C#, like – with a closure capturing outer variable p – () => p.X, but not for “stand-alone” expressions. Even if we’d go with the lambda syntax, using p.X won’t work as p is of type SymbolMathExpression and that doesn’t have an X property by itself (the thing it refers to might have though, as is the case in our sample). That’s where “dynamic” in expression trees would come in handy.

Evaluation

So, how do we want to go about evaluating the result of a symbolic computation using those matrix expressions? The answer is, we need to be able to turn cells or the whole matrix into code that can compute values, given the substitutions for the symbols. For example, if we multiply rotate by point and want to know the topmost, leftmost cell’s value, we still need to supply values for the point and the rotation angle, because the cell’s computation might depend on those. So, ultimately we need to turn the cell into the body of a lambda expression that’s parameterized in the symbols.

Let’s start by looking at the plumbing to evaluate a single cell:

MatrixExpression<double> res = rotate * point;
Expression cell00 = res[0, 0];
Console.WriteLine(cell00);

LambdaExpression fCell00 = Expression.Lambda(cell00, p, t);
var f = (Func<Point, double, double>)fCell00.Compile();
double xNew = f(new Point(1, 0), Math.PI / 4);
Console.WriteLine(xNew);

Step-by-step now. The first line is obvious, we take our two matrices and multiply them, giving us back a new matrix containing double-valued (though symbol) cells. Next, we call into the public indexer to retrieve the expression tree for the topmost, leftmost cell. Again, that’s symbolic. You should be able to predicate the third line therefore prints (modulo precise knowledge of Expression.ToString):

((Cos(t) * p.X) + (-Sin(t) * p.Y))

As you can see, this contains ingredients from different cells in the original matrices, but composed through LINQ expression tree operations like product and sum. Next, we want to evaluate this, which means we need to get rid of the symbolic representation of p (the pont) and t (the rotation angle). So, we wrap this in a lambda expression that has p and t as parameters. This is what fCell00 is all about. If you’d printf that one, you’d see something like:

(p, t) => ((Cos(t) * p.X) + (-Sin(t) * p.Y))

We know the type of p and t, as well as the result (a cell of the matrix is of type double), so we can provide a signature for the to-be-compiled lambda: Point –> double –> double, or in C# style: Func<Point, double, double>. That’s what gets stored in f. And finally, we can call through the delegate, applying our function to a point (x = 1, y = 0) and with a rotation angle of 45° (Pi/4 in radians).

Quite some boilerplate code to get this to work, but if you want you could compactify the whole thing quite a bit:

var f = (Func<Point, double, double>)Expression.Lambda((rotate * point)[0,0], p, t).Compile();

and indeed, this kind of logic would rightfully belong inside MatrixExpression, returning a delegate given cell indices and a (symbols) parameter order.

Now that we got an idea about how to evaluate a single cell, what about evaluating a whole matrix? What would the result of that be? Clearly, a two-dimensional array of concrete values that are computed based on substitution values for the symbols. That’s exactly what the ToExpression method on MatrixExpression is meant for:

public Expression ToBLOCKED EXPRESSION
{
    var res =
        Expression.NewArrayInit(typeof(T[]), Enumerable.Range(0, Rows).Select(i =>
            Expression.NewArrayInit(typeof(T), Enumerable.Range(0, Columns).Select(j =>
                Retrieve(i, j)
            ))).Cast<Expression>() // Missing generic variance (C# 4.0).
        );

    return res;
}

This might look quite dense, but uses the power of LINQ to build up (the expression tree for) an array of symbolic computations, based on the Retrieve method for each individual cell. Insert a few curly braces and it starts to look like nested foreach loops:

public Expression ToBLOCKED EXPRESSION
{
    var res =
        Expression.NewArrayInit(typeof(T[]), Enumerable.Range(0, Rows).Select(i =>
        {
            Expression.NewArrayInit(typeof(T), Enumerable.Range(0, Columns).Select(j =>
            {
                Retrieve(i, j);
            });
        })).Cast<Expression>() // Missing generic variance (C# 4.0).
    );

    return res;
}

What this creates is an expression tree to create an instance of a T[][] array. Notice I’m using jagged arrays because expression trees do not support the creation of multi-dimensional arrays at the time of writing. The use of the Cast<Expression> is interesting. If you emit this, you’ll get a compile error saying: cannot convert an IEnumerable<NewArrayExpression> into an IEnumerable<Expression>. Clearly this is valid because of covariance (IEnumerable<Elephant> should be assignable to IEnumerable<Animal>), but we don’t have this feature at our service for the moment (but C# 4.0 will, yippie, hence my comment in the code).

Anyway, let’s try the following:

MatrixExpression<double> res = rotate * point;
Expression matrix = res.ToBLOCKED EXPRESSION;
Console.WriteLine(matrix);

LambdaExpression fMatrix = Expression.Lambda(matrix, p, t);
var f = (Func<Point, double, double[][]>)fMatrix.Compile();
double[][] pNew = f(new Point(1, 0), Math.PI / 4);
pNew.Print();

Notice the parallels with the code to evaluate a single cell. Now the first Console.WriteLine prints:

new [] {new [] {((Cos(t) * p.X) + (-Sin(t) * p.Y))}, new [] {((Sin(t) * p.X) + (Cos(t) * p.Y))}}

or, with some manual touch-ups,

new [] {
new [] {((Cos(t) * p.X) + (-Sin(t) * p.Y))},
new [] {((Sin(t) * p.X) + ( Cos(t) * p.Y))}
}

Clearly the formula we expected for both coordinates, in a LINQ expression tree format. Again, the compilation code is fairly similar, but notice how the return type of the delegate is degraded to a double[][] instead of a Point. We’ll do something about this in a minute, but first the output of the call to Print():

{ { 0.707106781186548 }, { 0.707106781186547 } }

What’s Print anyway? Just a plain extension method on jagged arrays:

static class Extensions
{
    public static void Print<T>(this T[][] array)
    {
        StringBuilder sb = new StringBuilder();

        sb.Append("{ ");
        int m = array.Length;
        for (int i = 0; i < m; i++)
        {
            int n = array[i].Length;
            sb.Append("{ ");
            for (int j = 0; j < n; j++)
            {
                sb.Append(array[i][j].ToString());
                if (j != n - 1)
                    sb.Append(", ");
            }
            sb.Append(" }");

            if (i != m - 1)
                sb.Append(", ");
        }
        sb.Append(" }");

        Console.WriteLine(sb);
    }
}

So, what about that broken return type in our delegate (also some kind of covariance, although a double[][] is not really to be treated as a Point in the general case)? Can we do better? With a little hack we can. Say we can trust the user to call Compile on a MatrixExpression, passing in a compatible delegate for the result, like this:

var rot = (rotate * point).Compile<Func<Point, double, Point>>(p, t);

(Notice this trust relationship is of a kind that we can still throw exceptions in the abuser’s face :-).) It’s clear we can take a look at the generic parameter passed in to Compile, make sure it’s a Func<…>, an extract the return type from it (the last generic parameter). Once we have that, we can emit a LINQ expression tree that wraps the result of a ToExpression call in a Convert expression tree node that makes the return value of the desired type (Expression.Convert is smart enough to find such conversions):

public R Compile<R>(params ParameterExpression[] parameters)
{
    var t = typeof(R);
    if (!t.IsGenericType || !t.GetGenericTypeDefinition().Name.StartsWith("Func"))
        throw new Exception("Not a Func<...>.");

    var a = t.GetGenericArguments();
    var r = a[a.Length - 1];

    return Expression.Lambda<R>(Expression.Convert(this.ToBLOCKED EXPRESSION, r), parameters).Compile();
}

Isn’t that beautiful? We just need to have a conversion available from double[][] to Point, obviously one that checks – omitted below – the input dimensions to be conform with expectations for a point’s dimensions (1 x n, with n = 2 in our case, thus a vector):

public static implicit operator Point(double[][] point)
{
    return new Point(point[0][0], point[1][0]);
}

This will do the trick for now, but notice how this makes the intermediate array allocation totally redundant. Can we eliminate that inefficiency? Sure, we have all the materials in the room to do so. We just shouldn’t apply the "Point conversion” from the outside, but extract the two relevant cells from the resulting matrix and feed them in to the Point constructor straight away. Adding this intelligence to our little engine isn’t that hard, even in a somewhat generic way (i.e. “intelligent conversions” as expression tree rewriters), but let’s keep that for another time when we talk about optimizing techniques (tip: try this at home with sparse matrices, i.e. lots of zero-valued cells, and watch the output of simple matrix calculations…).

Just for the record, here are the results for rotating 10,000,000 (randomly chosen) points with a direct (but naive, i.e. equivalent to the generated expressions from the matrix multiplication, without extracting common subexpressions for sine and cosine calculation) implementation versus our symbolic one (excluding the initial compilation of the lambda):

Symbolic: 00:00:05.2810564
Classic: 00:00:03.0292995

Applying the optimization for Point-conversion I’m hinting at above puts them on par actually (we even did a little better, but that’s just a test noise artifact):

Symbolic: 00:00:03.1099769
Classic: 00:00:03.2106196

and if we’d go all the way in the optimizer, we could even eliminate common subexpressions (a bit tricky though, but doable), at the cost of additional compile and analysis time upfront (and getting into territory where LINQ expression trees do not longer help as we need to generate multiple statements now, welcome DLR!).

Did I tell you I’m a big believer of the power of mathematical notation? Yielding control to the runtime might sound frightening to some, but it has its merits as you can see…

Have fun!

Dude, Where’s My LINQ DML?

bart — Sat, 22 Nov 2008 21:53:00 GMT

Introduction

On last week’s TechEd EMEA Developers 2008 conference in Spain I redelivered my talk on writing custom LINQ providers, showing off implementations of LINQ to AD and LINQ to SharePoint. One of the questions I received afterwards went along the lines of this blog post’s title: “Dude, where’s my LINQ DML statement support?”. The stock answer to this kind of question points out that it’s up to individual LINQ providers to provide reasonable support for updating data source entries based on the O/whatever mapping they establish. The typical way this is done is through change tracking of entity objects that have been new’ed up by the provider upon execution of the query through LINQ.

However, there are cases where this kind of updating is unsatisfactory, especially when dealing with batch updates that don’t require client-side input or computation. For example, when dealing with interactive users, the change tracking driven solution works great, but when updating a set op records based on a certain update pattern (e.g. increase the price of each product with 5%) there’s no need to suck in all entity objects from the data source only to send them back with updates that could well be executed by the target database. Obviously it all depends on the richness of the underlying database’s DML statements, but assuming it’s flexible enough, how to deal with this in the context of LINQ?

Updateable LINQ to Objects

In order to set the scene, let’s investigate what it would take to make LINQ to Objects update-capable. In other words, we want to be able to execute a query and update the retrieved objects in a declarative fashion, i.e. without manual iteration over the query results. To tackle this problem, we can rely on extension methods over IEnumerable<T> in order to provide a method that can apply a certain update-action to each individual object in the sequence. Here’s a possible implementation.

public static void Update<T>(this IEnumerable<T> source, params Action<T>[] updates)
{
    if (source == null)
        throw new ArgumentNullException("source");

    if (updates == null)
        throw new ArgumentNullException("updates");

    foreach (T item in source)
    {
        foreach (Action<T> update in updates)
        {
            update(item);
        }
    }
}

This particular implementation will break the IEnumerable<T> chain as the method is void-returning, but it’s not hard to make it an iterator, yield returning the original sequence elements from the outer loop after the updates have taken place. However, using an iterator in this case might not be the best idea, as the update won’t go through till you start iterating over the resulting sequence because of the lazy nature iterators have. So, let’s stick with void. Next, you might wonder why I chose to pass in an array of update actions instead of a just a single update action. It turns out this doesn’t really matter that much for the in-memory LINQ to Objects case (and indeed, if you just specify a single update action, it will just work fine) but as we’ll see further on, having more manageable individual update actions is a good idea to remote the DML statement. However, in this particular case there’s no way to have more control over the nature of updates, as an Action<T> can be used to point at any procedure, e.g. specified using a statement lambda. Below, I’m illustrating the use of the Update method with more granular update actions:

List<Product> products = new List<Product>() {
    new Product { Name = "Chai", Price = 123m },
    new Product { Name = "Chang", Price = 234m },
};

(from p in products
 where p.Price > 100
 select p).Update(
    p => p.Price *= 0.95,
    p => p.Name = p.Name.ToUpper()
);

foreach (var p in products)
    Console.WriteLine(p.Name + " - " + p.Price);

Notice how other LINQ to Objects operators are used indirectly through query comprehension syntax, more specifically we filter out the items to be updated using a where clause first. As Update performs eager evaluation, enumerating over the source sequence straight away, the results will be visible immediately when iterating over the (now updated) source sequence after the Update invocation. But let’s take a closer look at how we’re specifying the updates above:

p => p.Price *= 0.95

Here we’re using lambda syntax but notice how the specified lambda doesn’t have a statement body. We’re simply leveraging the fact any value can be ‘converted’ to void, so the lambda above which is of type Product –> decimal can be assigned to an Action<T> where T is Product or, in functional signature syntax, a Product –> void. But there’s nothing that keeps us from writing a far more complex statement body:

p => {
   decimal oldPrice = p.Price;
   string oldName = p.Name;
   p.Price = oldPrice * 0.95;
   p.Name = oldName.ToUpper();
}

Just let your imagination work. Why is this a relevant fact? Our original set of update actions are far more “comprehensible” at runtime for introspection (well, if we turn them in something else than Action<T> which doesn’t produce just plain old IL code) because of their declarative nature.

There are still quite a few things lacking from our simplistic LINQ to Objects update support mechanism, such as transactional integrity (e.g. assume one of the update actions blows up, how to roll back previous applied updates?) but you get the overall idea.

Updateable remotable LINQ

Now, let’s turn the scene and focus on remotable kinds of LINQ, where we want to send off the DML statement to a remote component, e.g. a DBMS system, to execute the update statement. In order to accomplish this goal, we need a way to represent the update statement in some form that we can inspect at runtime to cross-translate it into the remote DML language, e.g. SQL. Luckily we have such a capability in the framework today, with expression trees.

But what’s in a name? Yes, expression trees. So, we don’t have the ability to represent arbitrary pieces of procedural statement-driven code like we have above with Action<T>:

Action<int> a = i => { Console.WriteLine(i); }; // works
Expression<Action<int>> e = i => { Console.WriteLine(i); } // fails to compile

On the one hand, this is a pity as it limits our expressiveness, but on the other hand it’s a good thing as analyzing arbitrary statement trees would significantly boost the complexity of the translator we’re about to write. However, there’s one significant limitation imposed by this: our update ‘actions’ cannot contain an assignment operator as this can’t be expressed by an expression tree:

Expression<…> e = p => p.Price *= 0.95;

So, even if we’d find a way to specify expression trees to build up a DML statement (see further), we can’t make assignments which obviously is a pretty basic piece of functionality when dealing with updates. So, how to work around this? What about the following? Instead of representing an update ‘action’ as one function, we could represent it as two functions: one that acts as a “update target selector” denoting which entity property to update (e.g. p => p.Price) and one that calculates the new value (e.g. p => p.Price * 0.95). Together these two carry enough information to express the intent of the update:

Expression<Func<Product, decimal>> extract = p => p.Price;
Expression<Func<Product, decimal>> update = p => p.Price * 0.95;

This is a little unfortunate and although there are alternatives (e.g. cooking up some “Updater” object that carries both extractor and updater) most of these yield syntactical clutter, so the bets of having a signature as easy as the following are off:

public static void Update<T>(this IEnumerable<T> source, params Expression<Action<T>>[] updates)

Using an Updater object, we’d end up with:

public static void Update<T, R>(this IEnumerable<T> source, params Updater<T, R>[] updates)

but calling it would be cumbersome:

Update(
new Updater<Product, decimal>(p => p.Price, p => p.Price * 0.95),
new Updater<Product, string>(p => p.Name, p => p.Name.ToUpper())
)

where Update has a constructor taking in:

class Updater<T, R>
{
public Updater(Expression<Func<T,R>> extract, Expression<Func<T,R>> update)

Ideally, we’d have a way to use tuples to keep the two function expression trees together at all times, also being able to use them in a params:

public static void Update<T, R>(this IEnumerable<T> source, params Tuple<Expression<Func<T, R>> /* extract */, Expression<Func<T, R>> /* update */>[] updates)

and hence the ability to call them easily using some hypothetical call-site syntax:

Update(
(p => p.Price, p => p.Price * 0.95),
(p => p.Name, p => p.Name.ToUpper())
)

or even without the additional parentheses pairs (at this time I’m even not thinking about disambiguation, overload resolution, betterness rules, and all this goodness). Or, we could lift the common Expression part out of the tuples, ending up with:

public static void Update<T, R>(this IEnumerable<T> source, params Expression<Func<T, Tuple<R /* extract */, R /* update */>>>[] updates)

Internally, the Update method could now inspect the way the Tuple<R,R> is instantiated, extracting the expression trees for the extract and update parts. However, we’re not all too pleased with the calling syntax that would need to new up tuple objects, obfuscating the intent of the code.

Let’s go over our needs and observations one more time before we settle on some design:

We’re bound to the limitations of expression trees; hence:
- we cannot express an individual update action as one expression (no assignment operation supported);
- so, an update action needs to be split into an extract and update phase;
- and, by extension, an update action can only target one value on the entity object at a time.
It should be possible to specify multiple update actions at a time to execute them as one unit:
- this supports transactional updates;
- we need a way to batch up update actions.

Introducing IUpdateable<T>

By now, we all know about the mysterious IQueryable<T> interface of LINQ. I’ve blogged about it several times, but here’s the key take-away: IQueryable<T> represents a query, wrapping an expression tree denoting the semantics of the intended query, and providing iteration facilities by means of its IEnumerable<T> parent. This, however, only tells half of the story, namely the “IQuery” part. The other half, the “able” part, is not visible on the interface per se, and allows users to extend the query by applying additional query operators that are supplied by means of the extension method in the Queryable class, each of which represents a query operator, like Where, Select, OrderBy, etc. This design allows the implementer of the interface to focus on the query execution part rather than the query construction part which is totally done on behalf of the implementer by means of the extension methods.

One way to think about IQueryable<T> in general is as a giant state machine. Most of the IQueryable<T> extension methods return an IQueryable<T>, so applying the method (i.e. some query operator) puts us back in the domain of a (new) IQueryable<T>. However, there are other methods like AsEnumerable that allow us to switch to another world, the one of IEnumerable<T>, where we have similar extension methods. To provide update support, we can play a similar trick:

Users write the base query (typically only using filtering) to extract the records that need to be updated – this happens in the IQueryable<T> domain.
Next, we transition out of the IQueryable<T> into the IUpdateable<T> domain to provide update support.
In IUpdateable<T>, updates can be batched up by calls to a Set method, specifying individual update actions, returning a new IUpdateable<T>.
Once all update actions have been specified, an Update method can be called to execute the batch of updates.

A few questions and remarks:

Why starting for IQueryable<T>? In quite some cases, users will want to filter records before applying updates. Right, so what about just having a Where method on IUpdateable<T>? Well, it turns out other operators might be useful as well, such as ordering in case the update would be used to number items based on their ordering (left to the reader as an exercise to think about ways to provide this capability in IUpdateable<T>). Similarly, things like Take could be translated into TOP clauses to apply the update only to the first number of items. And so on. In the end, providing all IQueryable<T> operators first, allowing the user to transition into IUpdateable<T> seems beneficial although some operators likely don’t make much sense (like Select, which would result in updating a projection…).
How to iterate over the resulting records, after the update has been applied? This kind of combined approach seems attractive too, but we won’t go there in the scope of the blog post. However, providing this feature shouldn’t be too hard, by means of an AsQueryable method, or by making IUpdateable<T> also IEnumerable<T>, where an iteration triggers execution of the update followed by iteration over the original query that got captured by AsUpdateable originally. This too is left as an exercise for the reader.

Time to present our new interface:

interface IUpdateable<T>
{
    Expression Expression { get; }
    IUpdateProvider Provider { get; }
}

It pretty much follows the design of IQueryable<T> where the Expression property captures the expression tree for the update so far, and the Provider property is used by the extension methods to gain access to a factory method to new up new IUpdateable<T> objects:

interface IUpdateProvider
{
    IUpdateable<T> CreateUpdate<T>(Expression expression);
    int Update(Expression expression);
}

In addition, the provider supplies an Update method that will take in the constructed updateable object’s expression tree, carrying out the update and returning the number of affected records. This one can be compared to the Execute method on IQueryProvider. So, how to use those two interfaces now? All of the direct uses will be provided by means of extension methods:

public static class Updateable
{
    public static IUpdateable<T> AsUpdateable<T>(this IQueryable<T> source)
    {
        IUpdateProvider updateProvider = source.Provider as IUpdateProvider;
        if (updateProvider == null)
            throw new InvalidOperationException("Update operations not supported by this query provider.");

        return updateProvider.CreateUpdate<T>(
            Expression.Call(
                null,
                ((MethodInfo)MethodBase.GetCurrentMethod()).MakeGenericMethod(typeof(T)),
                new Expression[] { source.Expression }
            )
        );
    }

    public static IUpdateable<T> Set<T, R>(this IUpdateable<T> source, Expression<Func<T, R>> extract, Expression<Func<T, R>> update)
    {
        return source.Provider.CreateUpdate<T>(
            Expression.Call(
                null,
                ((MethodInfo)MethodBase.GetCurrentMethod()).MakeGenericMethod(typeof(T), typeof(R)),
                new Expression[] { source.Expression, extract, update }
            )
        );
    }

    public static int Update<T>(this IUpdateable<T> updateable)
    {
        return updateable.Provider.Update(updateable.Expression);
    }
}

Here the first method, AsUpdateable, captures an existing IQueryable<T> and checks whether its provider (of type IQueryProvider) supports updates. This piggybacking on top of the existing provider infrastructure is a good thing in general as implementers of an update-capable provider will need to talk to the query provider in order to translate the query portion of the update statement (e.g. a WHERE clause). Being the flip side of it, this means it’s not really possible to sprinkle update support on top of an existing query provider without modifying that provider. You could imagine an additional overload to AsUpdateable that takes in an IUpdateProvider object, and though this would work you’d end up implementing some of the query operators yourself again (e.g. to support filtering). If you know the original query provider’s concrete class and you know it exposes a way to take in an expression tree representing a query, getting back the translated query, there might be a way to avoid duplication (provided the target query language is compositional in nature):

var provider = (SomeSqlQueryProvider)source.Provider;
string sql = provider.GetSqlStatement(source);
…
string update = “UPDATE “ + … + “ FROM (“ + sql + “)”; // pseudo-SQL

But let’s ignore this for now. Other than this, AsUpdateable is straightforward, it takes the original expression tree and wraps it in a MethodCallExpression for the current method. Just like IQueryable<T> does this, the original expression tree gets extended with information about the applied operators represented as method calls.

The Set method, representing an individual update action, is completely similar. More interesting is its signature: besides of an IUpdateable<T> object, it takes in both the extract and update functions as expression trees, using the principle we talked about earlier.

Finally, Update is just syntactical sugar on top of an IUpdateable<T> to call into the underlying provider to carry out the update, allowing for a fluent interface design. Ultimately, all of this can be used as follows:

(from p in new Table<Product>()
 where p.Price > 100
 select p).AsUpdateable()
    .Set(p => p.Price, p => p.Price * 0.95)
    .Set(p => p.Name, p => p.Name.ToUpper())
 .Update();

Going out in the woods we could start dreaming about integrated syntax that looks like this:

from p in new Table<Product>()
where p.Price > 100
update p.Price *= 0.95,
p.Name = p.Name.ToUpper();

which might automatically become eager, i.e. the Update call is implicit, or stays lazy (which would mean one can reuse the query/update comprehension expression). VB syntax could be very similar, optionally using the With keyword (Update p With …).

Enough dreaming for now, this whole expression (more specifically everything before the .Update() part) translates into an expression tree, constructed at runtime with the aid of the Queryable query operators and Updateable update operators, that can be represented as follows using ToString notation:

expression = {value(Table`1[Product]).Where(p => (p.Price > 100)).AsUpdateable().Set(p => p.Price, p => p.Price * 0.95).Set(p => p.Name, p => p.Name.ToUpper())}

Now the update provider can go ahead and cross-translate this expression tree into a statement the target data source understands, e.g. a SQL DML statement for UPDATE (I’m not a SQL language expert, so treat the following as conceptual code):

UPDATE Products WHERE Price > 100 SET Price *= 0.95, Name = TOUPPER(Name)

I’ll leave a concrete implementation of an update provider to the inspired reader; a basic prototype for SQL (only allowing columns to be updated with constant string or integer values) worked like a charm. In addition, the reader should feel free to think about how it would be possible (if desirable at all, something to think about as well) to make the “LINQ to Objects with update support” case similar to the remotable case, in terms of used operators (i.e. our current LINQ to Object implementation in the first paragraph doesn’t use Set method calls and isn’t lazy at all).

Enjoy!

C# 4.0 Feature Focus - Part 3 - Intermezzo: LINQ's new Zip operator

bart — Tue, 04 Nov 2008 07:11:43 GMT

After named parameters and optional parameters, we'll take a little breadth and deviate a bit from the language specifics to present a new LINQ operator: Zip. Just like a zipper zips two streams of materials together, LINQ's Zip operator can zip together two sequences. Here's the signature of the new method:

public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func);

Sample

Given two sequences and a function that combines two elements from both sequences, a sequence of zipped pairs is produced. Here's a sample:

string[] names = { "Bart", "John" };
int[] ages = { 25, 60 };

names.Zip(ages, (name, age) => name + " is " + age + " years old.");

This produces a sequence with the sentences "Bart is 25 years old." and "John is 60 years old.". The lambda syntax for the passed-in function should speak for itself, and notice we're using extension method invocation here, so names is propagated to become the left-hand side of the method call.

How Zip works

Previously I've implemented the Standard Query Operators for reference purposes on the Codeplex site at http://www.codeplex.com/LINQSQO. I won't update that sample library just yet, but here's an illustration on how easy Zip is to implement, ignoring exception handling (which is more subtle than you might think, see further):

static class Enumerable
{
    public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func)
    {
        var ie1 = first.GetEnumerator();
        var ie2 = second.GetEnumerator();

        while (ie1.MoveNext() && ie2.MoveNext())
            yield return func(ie1.Current, ie2.Current);
    }
}

The Zip operation is implemented using iterators inside ("yield return") and stops as soon as one of the sequences runs out of juice (the case of the asymmetric zipper).

Zip without Zip?

As a curiosity, is it actually possible to build Zip out of existing LINQ operators, ignoring performance worries? Unsurprisingly, it turns out this is the case. Here's how:

static class Enumerable
{
    public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func)
    {
        return first.Select((x, i) => new { X = x, I = i }).Join(second.Select((x, i) => new { X = x, I = i }), o => o.I, i => i.I, (o, i) => func(o.X, i.X));
    }
}

(Exercise for the reader: think of more alternatives.) How does this work? To explain this we need a bit of vocabulary, so let's refer to Wikipedia for a second and apply an isomorphism between textile sciences and computer sciences (something in me screams "zip, zipper, zippest"):

The ~~bulk~~ signature of a ~~zipper~~ Zip consists of two ~~strips~~ sequences of ~~fabric~~ element taypes, each affixed to one of the two ~~pieces~~ sequence instances to be joined, carrying tens or hundreds or anything below OutOfMemoryException conditions of ~~specially~~ regularly ~~shaped~~ allocated ~~metal~~ reference- or ~~plastic~~ value-typed ~~teeth~~ elements. (...) The ~~slider~~ Func<TFirst, TSecond, TResult> delegate, operated by ~~hand~~ executing Zip, moves along the ~~rows~~ sequences of ~~teeth~~ elements. Inside the ~~slider~~ Func<TFirst, TSecond, TResult> delegate is a ~~Y-shaped~~ strongly-typed ~~channel~~ function that meshes together ~~or separates~~ the opposing ~~rows~~ sequences of ~~teeth~~ elements, ~~depending on the direction of its movement~~. The ~~friction~~ binding and ~~vibration~~ application of the ~~slider~~ Func<TFirst, TSecond, TResult> delegate ~~against~~ on the ~~teeth~~ elements causes a characteristic ~~buzzing~~ callvirt'ing noise, which is probably not the origin of the name zipper. The name also may have originated in the greater speed and ease with which the two sides of a ~~zipper~~ Zip can be joined, compared to the time needed for ~~fastening~~ executing ~~laces or buttons~~ the method above.

Well, that's exactly what happens: opposing ~~rows~~ sequences of ~~teeth~~ elements are combined by a ~~Y-shaped~~ strongly-typed ~~channel~~ function. How to determine opposing sequence elements? Using Select's overload that provides (besides the element itself) an index denoting the element's position in the original sequence. Matching the opposing elements is a matter of joining both sequences, extracting the keys (marked as I in the anonymous type) and combining the selected pairs of elements from both sequences (marked as X in the anonymous type) by feeding them in to the ~~slider~~ Func<TFirst, TSecond, TResult> delegate. I told you the explanation was straightforward, or did I?

Iterators and exceptions

Most of the LINQ operators are implemented using iterators. You might wonder this this is relevant at all. Obviously we need it as LINQ operators need to be lazy. Only when you start fetching results by iterating of the sequence, the internal machinery should kick in. Declaring a query doesn't cause any execution whatsoever. Internally iterators are implemented as state machines. Every state can do on "yield", after which the state machine is suspended till the consumer asks for the next element in the sequence being produced by calling MoveNext on the IEnumerator<T> object.

Our Zip implementation above is turned into an equivalent piece of code (slightly simplified for illustrative purposes):

public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func)
{
    return new ZipIterator<TFirst, TSecond, TResult>(first, second, func);
}

private sealed class ZipIterator<TFirst, TSecond, TResult> : IEnumerable<TResult>, IEnumerator<TResult>
{
    //
    // Captured iterator method parameters.
    //
    private IEnumerable<TFirst> _first;
    private Func<TFirst, TSecond, TResult> _func;
    private IEnumerable<TSecond> _second;

    //
    // Iterator's enumerator state and thread affinity.
    //
    private State _state;
    private int _initialThreadId;

    //
    // Value currently yielded by the iterator's enumerator.
    //
    private TResult _current;

    //
    // Local variables used by the iterator's enumerator.
    //
    private IEnumerator<TFirst> _ieFirst;
    private IEnumerator<TSecond> _ieSecond;

    //
    // Captured iterator method parameters used by enumerator.
    //
    private IEnumerable<TFirst> first;
    private Func<TFirst, TSecond, TResult> func;
    private IEnumerable<TSecond> second;

    //
    // Public constructor to create an iterator in the initial ready state.
    //
    public ZipIterator(IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func)
        : this()
    {
        this._first = first;
        this._second = second;
        this._func = func;
    }

    //
    // Private constructor to set state and thread affinity.
    //
    private ZipIterator()
    {
        this._state = State.Before;
        this._initialThreadId = Thread.CurrentThread.ManagedThreadId;
    }

    //
    // Gets a new enumerator over the iterator.
    //
    IEnumerator<TResult> IEnumerable<TResult>.GetEnumerator()
    {
        ZipIterator<TFirst, TSecond, TResult> iterator;

        //
        // Can reuse the current enumerator if thread affinity and state permit it.
        //
        if (Thread.CurrentThread.ManagedThreadId == _initialThreadId && _state == State.Before)
        {
            iterator = this;
        }
        else
        {
            iterator = new ZipIterator<TFirst, TSecond, TResult>();
        }

        iterator.first = this._first;
        iterator.second = this._second;
        iterator.func = this._func;

        return iterator;
    }

    //
    // Gets a new enumerator over the iterator.
    //
    IEnumerator IEnumerable.GetEnumerator()
    {
        return ((IEnumerable<TResult>)this).GetEnumerator();
    }

    //
    // Advances the iterator one yield return at a time.
    //
    bool IEnumerator.MoveNext()
    {
        switch (this._state)
        {
            case State.Before:
                this._ieFirst = this.first.GetEnumerator();
                this._ieSecond = this.second.GetEnumerator();
                goto case State.Suspended;

            case State.Suspended:
                if (this._ieFirst.MoveNext() && this._ieSecond.MoveNext())
                {
                    this._current = this.func(this._ieFirst.Current, this._ieSecond.Current);
                    this._state = State.Suspended;
                    return true;
                }
                break;
        }

        this._state = State.After;
        return false;
    }

    //
    // Retting the iterator enumerator is not supported; create a new one instead by calling GetEnumerator.
    // The foreach statement does this anyway.
    //
    void IEnumerator.Reset()
    {
        throw new NotSupportedException();
    }

    //
    // Gets the value currently yielded from the iterator.
    //
    TResult IEnumerator<TResult>.Current
    {
        get
        {
            return _current;
        }
    }

    //
    // Gets the value currently yielded from the iterator.
    //
    object IEnumerator.Current
    {
        get
        {
            return _current;
        }
    }

    //
    // IDisposable implementation.
    //
    void IDisposable.Dispose()
    {
    }

    //
    // Internal iterator enumerator states.
    //
    private enum State
    {
        Before,
        Running,
        Suspended,
        After
    }
}

Notice that the code above holds the middle between the specification (paragraph 10.14 of the C# 3.0 specification) and the actual implementation in the Visual C# 2008 compiler. More specifically, I've made the discrete states (which are internally represented as integers) match the ones in the specification, but haven't gone all the way in matching the code up with the

Of all this machinery, the MoveNext method is the most interesting one from the iterator's point of view. Here a state machine is built, rewriting the original iterator block by splitting it into discrete blocks. To perform this transformation, yield return statements are replaced as follows:

yield a;

becomes

this._current = a;
this._state = State.Suspended;
return true;

Similar rewrites happen for yield break statements, but that's not relevant here. Furthermore all the iterator block code is placed in a MoveNext method, switching on the current state. The specification only mentions the four states I've implemented above, but we're lucky the number of states for our sample matches up with the number of states that's specified. In cases where there are more yield statements, more states are needed to suspend the machine and resume at the same point during the next MoveNext call. Other transformations needed include rewriting of loops (things like while don't really play well with suspension points and need to be rewritten in terms of if/goto, where gotos require additional states). Applying all those tricks gives us:

bool IEnumerator.MoveNext()
{
Begin:
    switch (this._state)
    {
        case State.Before:
            this._ieFirst = this.first.GetEnumerator();
            this._ieSecond = this.second.GetEnumerator();
            this._state = State.Running;
            goto Begin;

        case State.Running:
        case State.Suspended:
            if (this._ieFirst.MoveNext() && this._ieSecond.MoveNext())
            {
                this._current = this.func(this._ieFirst.Current, this._ieSecond.Current);
                this._state = State.Suspended;
                return true;
            }
            break;
    }

    this._state = State.After;
    return false;
}

Here the local variables used in the iterator block are captured in the initial pass through MoveNext, when state is still set to Before. Strictly speaking we move from Before to Running all the way to the first point where the code gets suspended, but in our case states can be merged quite a bit. In fact the code really produced by the compiler looks like this:

bool IEnumerator.MoveNext()
{
    switch (this._state)
    {
        case 0:
            this._state = -1;
            this._ieFirst = this.first.GetEnumerator();
            this._ieSecond = this.second.GetEnumerator();
            while (this._ieFirst.MoveNext() && this._ieSecond.MoveNext())
            {
                this.current = this.func(this._ieFirst.Current, this._ieSecond.Current);
                this._state = 1;
                return true;
            Resume:
                this._state = -1;
            }
            break;
        case 1:
            goto Resume;
    }
    return false;
}

But why am I telling you all this? Because it's fascinating? Yes, for that reason too. But I promised to tell you something about exceptions, right? Let me quote from the C# 3.0 specification paragraph 10.14.4.1 first:

(...) The precise action performed by MoveNext depends on the state of the enumerator object when MoveNext is invoked:

If the state of the enumerator object is 'before', invoking MoveNext:
- Changes the state to 'running'.
- Initializes the parameters (including this) of the iterator block to the argument values and instance value saved when the enumerator object was initialized.
- Executes the iterator block from the beginning until execution is interrupted (as described below).

(...)

The red line is what's of interest to us, and you should read it in reverse:

The code from the beginning of the iterator block till the place where execution is interrupted (i.e. a yield occurs) is executed by MoveNext when transitioning from 'before' to 'running'.

What if that code contains exception throwing statements?

static class Enumerable
{
    public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func)
    {
        if (first == null)
            throw new ArgumentNullException("first");

        if (second == null)
            throw new ArgumentNullException("second");

        var ie1 = first.GetEnumerator();
        var ie2 = second.GetEnumerator();
        while (ie1.MoveNext() && ie2.MoveNext())
            yield return func(ie1.Current, ie2.Current);
    }
}

As you can guess, this code won't get executed till the very first passage through the iterator's enumerator object's MoveNext method. Recall what foreach corresponds to:

foreach (V v in x) embedded-statement

becomes (with C the collection type, E the enumerator type, V the local variable type and T the element type)

{
    E e = ((C)(x)).GetEnumerator();
    try {
        V v;
        while (e.MoveNext()) {
            v = (V)(T)e.Current;
            embedded-statement
        }
    }
    finally {
        ...
    }
}

So just calling the iterator does nothing that can cause the exceptions to be thrown, until a call is made to MoveNext, e.g. by using a foreach loop. As we want the exception to be thrown straight away when calling Zip with invalid arguments, the right way to implement our Zip method is:

static class Enumerable
{
    public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func)
    {
        if (first == null)
            throw new ArgumentNullException("first");

        if (second == null)
            throw new ArgumentNullException("second");

        return ZipInternal(first, second, func);
    }

    private static IEnumerable<TResult> ZipInternal<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func)
    {
        var ie1 = first.GetEnumerator();
        var ie2 = second.GetEnumerator();
        while (ie1.MoveNext() && ie2.MoveNext())
            yield return func(ie1.Current, ie2.Current);
    }
}

Conclusion

The addition of Zip to LINQ is a nice one, but not a mind-blower. So I hope you'll accept my apologies for using this as a lame excuse to nag about the implementation of iterators and their subtle impact on exceptions. Next time: generics co- and contra-variance in C# 4.0.

Who ever said LINQ predicates need to be Boolean-valued?

bart — Sun, 14 Sep 2008 19:23:00 GMT

Note for purists: This post only speaks for “LINQ predicates”, not – although closely related to - the mathematic concept of a predicate as defined by

Weisstein, Eric W. "Predicate." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Predicate.html

An operator in logic which returns either true or false.

The LINQ provider spectrum

Back in the wonderful world of LINQ. This time I’d like to highlight one of the most important properties of LINQ: its flexibility. On various occasions I’ve already stated that the potential of LINQ is infinity², the reason for it being the infinite fan-in (LINQ though C#, VB, F#, PowerShell, various transport mechanisms, etc) multiplied by the infinite fan-out (LINQ to SQL, Entities, XML, Objects, DataSets, SharePoint, Active Directory, Amazon, etc). In this post we forget about the former infinity factor and move on to the latter, where we have a whole spectrum of query provider implementations. The spectrum is bordered by two extremes:

Completely local, through IEnumerable<T> (some will debate whether this is a query provider). LINQ to Objects and XML fit in this bucket. The cost to implement this is virtually zero, you just need to make sure your API speaks in terms of IEnumerable<T> (e.g. in LINQ to XML we have methods like Descendants that return sequences of XML nodes). On the flip side though, you can’t delegate execution of the query to another execution engine, e.g. by “remoting” the query to SQL.
Completely remotable, through IQueryable<T>. LINQ to SQL, SharePoint, Active Directory, Amazon, etc fall under this umbrella. Implementation cost is higher for this type of providers as the expression tree produced by the IQueryable extension methods needs to be turned into whatever domain-specific language you want to target, e.g. SQL, CAML, LDAP, web service calls, etc. However, the potential to control and delegate execution is huge.

Notice the italics for the word remotable in the latter category: the provider shouldn’t necessarily remote (in the broadest sense of the word, from cross-process to cross-machine) the execution, instead it can be a transformer that rewrites expression trees to optimize or decompose them, etc. Similarly, the provider could be intelligent about distribution of the query execution: maybe it can divide-and-conquer, splitting the work across servers or doing part of the work locally. I’m not a huge fan of the latter “intelligence” (because it becomes too “smart”) as such providers tend to be dishonest about where executes what:

var res = (from p in products where p.Price > 100 select new { Name = p.ProductName }).Take(5);

Maybe the provider executes the where-predicate locally, meaning we’d suck in too many rows. Or it might not know how to do a projection remotely, causing us to suck in too many columns. Similarly, the Take operation might not translate well in the target domain causing similar data transmission overhead worries. Personally I prefer explicit transitioning markers using AsEnumerable to clearly delimit the borders of local versus remote execution. Obviously, when remote and local are relatively close to each other (e.g. cross-process) this type of “smartness” might be well-justified (e.g. LINQ to MSI queries a local file; or LINQ to SharePoint might run in an ASP.NET application on the same machine as WSS; or LINQ to SQL could potentially and hypothetically run inside the database relational engine itself). Back to where we were though…

LINQ as a language pattern

In between those two extremes there’s a whole range of possibilities because of the way LINQ really works: as a front-end language pattern, just like foreach, lock, using, etc are patterns on top of other stuff (IEnumerable, Monitor, IDisposable, etc). What does that imply? The compiler just knows about LINQ as a set of keywords that can be turned into specific method calls, which happen to reflect query operators. To provide some context, refer to my earlier post on “C# 3.0 Query Expression Translation Cheat Sheet” where you’ll see translation rules like:

from x in e where f …

becomes

from x in (e).Where(x => f) …

That’s just it, and nothing more. Keeping the title of this post in mind, do you see any types whatsoever being expressed here? No, the only requirement for the Where method (when invoked like an instance method on whatever e’s type is) is to take in something with a type compatible with “x => f” where f’s type can be inferred of course because f is an expression. Notice how I said “like an instance method”: the method call just follows the rules of method (overload) resolution, including – but not limited to – C# 3.0 extension methods when everything else fails. The only thing defined here is the type of f: the type of x can be anything (in most typical cases though it corresponds to the entity type from the fed in query expression in e) and the same holds for the return type of Where.

Similarly, translation rules like:

from x in e select v

becomes

(e).Select(x => v)

are equally flexible with regards to typing. From this point of view we could (and should) see LINQ as just another language pattern around certain methods, not necessarily related to a specific interface type (therefore establishing a sort of limited duck typing), just like foreach only needs a “compatible GetEnumerator method” (see §8.8.4 of the C# 3.0 language specification, second step of the determination process during foreach-compilation). Noteworthy is a counter-example where an interface type is required to use a specific language feature: the using statement requires an IDisposable object to operate on. The key takeaway though is that LINQ falls in the former category and just needs the right methods to translate away the query expression keywords.

A different view on predicates

Let’s zoom in and investigate just one query operator: where. As we saw before it maps onto a Where method that takes in a lambda of the form x => f. In here, x can be seen as an input element in the source sequence being processed, while f acts as the body of the predicate, establishing a filter condition. Although one could misuse the where operator to implement totally different semantics, we’ll assume we’re dealing with filtering capabilities, i.e. an operator that restricts the returned elements from a given sequence based on some condition also known as a predicate. As we discussed before, f shouldn’t necessarily be Boolean-typed, although the two common implementations – IEnumerable and IQueryable – define it as such:

IEnumerable<T> Where<T>(this IEnumerable<T> source, Func<T, bool> predicate)
IQueryable<T> Where<T>(this IQueryable<T> source, Expression<Func<T, bool>> predicate)

This means when using sources e of any of the above types (ignoring a little caveat I’ll discuss below), the translation for the where operator:

from x in (e).Where(x => f) …

will bind x to T and f to bool, which gets enforced at compile-time (remember co- and contravariance rules for delegates, Func<T, bool> is just one of those). What’s the caveat I was hinting at? Well, first of all (incredibly obvious, I admit) is that this will only work if the Where extension method is brought in scope by means of the using keyword. LINQ doesn’t care about extension methods at all, but when the front-end language compiler rewrites the query expressions into chains of methods call, method resolution kicks in where extension methods are the fallback plan. That brings us to the real caveat: extension methods are only “fallbacks” and instance methods take precedence. Therefore instance methods have the capacity to “hide” extension methods with the same name and signature:

class MyList<T> : IEnumerable<T>
{
    public IEnumerable<T> Where(Func<T, bool> predicate)
    {
        …
    }

    public IEnumerator<T> GetEnumerator()
    {
        …
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        …
    }
}

When using this class – even with System.Linq (and therefore the extension methods in System.Linq.Enumerable) in scope – you’ll see that our self-defined Where operator takes precedence:

while another overload is still available through the extension methods:

This simple fact is easy to overlook but it’s incredibly important to leverage the full spectrum of possible LINQ provider implementations. Maybe you want all of the LINQ to Objects stuff to “just work” except for a few operators you want to implement yourself. Equally you could override IQueryable behavior when you wish to do so. Needless to say, the above just works fine with the where keyword too. To prove this point, let’s use a simple breakpoint:

As you can see, while iterating over the resulting query, the highlighted lambda is being hit while being called from the MyList<string>.Where method. Quiz: Would setting a breakpoint on “x” in Select reveal something in this particular case? Why (not)?

In contrast, the projection lambda in select will be called by an extension method on IEnumerable<T>. To illustrate this, I’ve tweaked the query a bit (why?) and disabled the “Just my code” feature in Visual Studio:

So how can we do even more creative stuff using this technique? What about doing this:

class MyList<T> : IEnumerable<T>
{
    public IEnumerable<T> Where(Func<T, Regex> filter)
    {
        foreach (T item in this)
            if (filter(item).Match(item.ToString()).Success)
                yield return item;
    }

    public IEnumerator<T> GetEnumerator()
    {
        …
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        …
    }
}

Does this work? You bet :-). Actually we don’t even need to be IEnumerable<T>, but let’s keep that for later. Here’s how you can use it:

var res = from x in new MyList<string>() { "abba", "baab" } where new Regex("^a.*a$") select x;

foreach (var x in res)
    ;

This will only return abba in the foreach loop. Notice we’re actually doing nothing with the input of the “filter” function argument, but we could by referring to x in the where clause. In this case, most likely we only want to process strings (as a regular expression operates on strings) and the regular expression won’t be variant based on the input. To make it a bit more concrete, here’s a sample of a dictionary:

class Dictionary : IEnumerable<string>
{
    private List<string> _lst = new List<string>();

    public IEnumerable<string> Where(Func<object, Regex> filter)
    {
        Regex predicate = filter(null);
        foreach (string word in _lst)
            if (predicate.Match(word).Success)
                yield return word;
    }

    public IEnumerator<string> GetEnumerator()
    {
        return _lst.GetEnumerator();
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return _lst.GetEnumerator();
    }

    public void Add(string word)
    {
        _lst.Add(word);
    }
}

Because we derive from IEnumerable<T>, we get all the LINQ to Objects operators for free, including the other Where overloads:

So now we can query our dictionary using a “regular” Boolean-valued predicate (with two distinct overloads: Func<string, bool> and Func<string, int, bool> where int represents the position in the original sequence), but also using a regular expression based predicate.

Taking it across the border: IQueryable (or something like it)

What' we’ve done before was just relying on local execution using IEnumerable’s LINQ to Objects extensions and some of our overrides and/or “query operator” overloads. In an equally simple manner we can make this work with remotable queries using IQueryable; the only difference would be in the signature of the Where operator. To scale things down a bit and avoid the burden of IQueryable’s “gang of three” properties, we’ll cook our own little query model that conforms with the LINQ query operators:

class DictionaryService
{
    public DictionaryQuery Where(Expression<Func<object, Regex>> filter)
    {
        return new DictionaryQuery(filter.Body);
    }
}

The DictionaryService class acts as an entry-point to our service that’s capable of retrieving words based on regular expressions. It only supports a filtering operator, which will make it work together with LINQ. Notice we’re using an Expression<…> for the predicate so that we’ll get expression trees we can parse at runtime in order to perform some kind of remote execution. We’ll cook our own Regex class for reasons to be explained further on:

class Regex
{
    private string _regex;

    public Regex(string regex)
    {
        _regex = regex;
    }

    public static Regex operator&(Regex regex1, Regex regex2)
    {
        //
        // Just making the expression API happy to use Expression.And.
        //
        throw new NotSupportedException("Only for use in expression trees.");
    }
}

Now we can turn our attention to the remaining DictionaryQuery class. The start is fairly simple:

class DictionaryQuery
{
    private Expression _filter;

    internal DictionaryQuery(Expression filter)
    {
        _filter = filter;
    }

    public DictionaryQuery Where(Expression<Func<object, Regex>> filter)
    {
        return new DictionaryQuery(Expression.And(_filter, filter.Body));
    }

    public IEnumerator<string> GetEnumerator()
    {
        string[] filters = Compile();
        string[] results = GetWords(filters);
        return results.AsEnumerable().GetEnumerator();
    }

Basically, a query consists of a filter that represents the aggregation of where filter clauses. This is stored in _filter. To allow for the user to specify multiple conditions, we have a Where operator available on the query object itself as well. All this operator does in this case is creating a new filter clause that “ands” together the original filter and the new filter. To do this, we just grab the passed in new filter’s body and hook it up with the original filter in a BinaryExpression of node type And. Notice we’re a bit lazy here and ideally we’d walk the tree of the passed in filter’s body to make sure it’s lambda parameter free (left as an exercise, tip: use a visitor). Expression.And will (statically) verify whether there’s an “And” (& in C# speak) operator available for use with the two specified arguments, hence we need our operator overload on Regex:

public static Regex operator&(Regex regex1, Regex regex2)
{
    //
    // Just making the expression API happy to use Expression.And.
    //
    throw new NotSupportedException("Only for use in expression trees.");
}

Notice this one is solely meant to be used in expression trees and doesn’t do anything useful. As a little exercise for the reader, what would it take to implement the && operator (corresponds to AndAlso in expression trees)? What would be the implications concerning the semantics and the evaluation strategy on the target service? Can we map the semantics nicely and if so, how?

The more important thing here though is the fact we’re implementing a GetEnumerator method. This will allow the user to iterate over the query results, which means we must translate the _filter into some service call to fetch results. This happens in a couple of stages: first we compile _filter into something the service understands (in this case just an array of strings) and next we send the compiled result (which we could cache if we want, so that subsequent iterations won’t trigger compilation again) to a service to process the request, getting the results back to iterate over. Question for the reader: why don’t we implement IEnumerable<string> here? Would it be desirable? Explain the pros and cons.

Question remains how the compilation happens. Here it is:

private string[] Compile()
{
    return Compile(_filter).ToArray();
}

private IEnumerable<string> Compile(Expression filter)
{
    switch (filter.NodeType)
    {
        case ExpressionType.And:
            {
                BinaryExpression binEx = (BinaryExpression)filter;
                foreach (string regex in Compile(binEx.Left).Concat(Compile(binEx.Right)))
                    yield return regex;
            }
            break;
        case ExpressionType.New:
            {
                NewExpression newEx = (NewExpression)filter;
                if (newEx.Type != typeof(Regex))
                    throw new NotSupportedException("Invalid leaf node type in query: " + newEx.Type);

                //
                // Only one constructor is public.
                //
                Expression arg = newEx.Arguments[0];
                if (arg.NodeType != ExpressionType.Constant)
                    throw new NotSupportedException("Regex constructor uses in query should have a constant argument value.");

                ConstantExpression constEx = (ConstantExpression)arg;
                string value = (string)constEx.Value;
                if (value == null)
                    yield break;
                else
                    yield return value;
            }
            break;
        default:
            throw new NotSupportedException("Invalid expression type in query: " + filter.NodeType);
    }                
}

This is fairly straightforward as well. We just expect two types of nodes: BinaryExpression nodes of type And used as the query composition operator, and NewExpression nodes for the leaf nodes (although leaf isn’t strictly true, why?) representing the atoms of the query predicate. Most code is boilerplate error checking but the points of interest are:

The use of iterators to produce a stream of strings representing the individual regular expressions. Notice the use of recursion in the And case (unfortunately we don’t have a yield foreach construct yet).
How we get the the value of the regular expression on the leaf nodes, through the first argument on the constructor. Actually, we don’t even need the private field in Regex in this case as we’re purely using it for expression trees and we can get to it through the constructor’s first argument in the expression tree.

To show what the tree looks like so far, consider the following query:

var dict = new DictionaryService();
var res = from word in dict
          where new Regex("^A.*a$")
          where new Regex(".*m.*")
          select word;

foreach (var x in res)
    ;

Setting a breakpoint on Compile allows us to inspect the filter:

Here we just see the ToString representation but when clicking the magnifier glass (assuming the Expression Tree Visualizer sample is installed), we get to see the entire tree:

Notice where our information of interest lives and how our expression tree compiler extracts it carefully from the tree. Another little quiz for the reader: is the query below equivalent to the one above (watch out for details)? Why (not)?

var dict = new DictionaryService();
var res = from word in dict
          where new Regex("^A.*a$") && new Regex(".*m.*")
          select word;

Last but not least we should take a look at our service itself. Obviously you could imagine any real service technology being used, such as WCF, but let’s stick with some simple fake local execution:

private string[] GetWords(string[] regexs)
{
    //
    // This acts as an imaginary remote service.
    //
    var conditions = new List<System.Text.RegularExpressions.Regex>();
    foreach (string regex in regexs)
        conditions.Add(new System.Text.RegularExpressions.Regex(regex));

    var res = from a in AppDomain.CurrentDomain.GetAssemblies()
              from t in a.GetTypes()
              from m in t.GetMethods()
              let word = m.Name
              where conditions.All(r => r.Match(word).Success)
              select word;

    return res.ToArray();
}

The biggest source of in-memory data is without doubt reflection, so let’s use it :-). Here we’re using real regular expressions (Questions: Why did we wrap them in the first place? Could we use some serialization mechanism? Explain!) to do the matching as part of a LINQ query (regular LINQ to Objects this time – it would be interesting to use our “LINQ-by-Regex” implementation recursively :-)). Notice how we return an array which has implications for the laziness when consuming data. Depending on the transport protocol the implementation could be streaming data to the client, so that the client can terminate the request at any point in time (when breaking from the foreach loop for instance). Or we could implement some kind of paging to retrieve the results in batches.

On my computer the following query:

var dict = new DictionaryService();
var res = from word in dict
          where new Regex("^A.*a$")
          where new Regex(".*m.*")
          select word;

returns

"AutoIncrementCannotSetIfHasData"
"AddSchema"

when running it in the context of a Windows Forms application created with Visual Studio 2008.

Exercise: Think of ways to simplify this regular-expression based (remote!) querying capability, especially with regards to the end-user writing queries targeting it. Can we get rid of the “Regex” word in there? Why (not)? How could we compile other Boolean operators to compose more complex queries and send them across to the server (tip: *fix).

Staged migration of query languages

By now you might wonder where we can use this “Frankenstein” LINQ flavor where we party on the existing language integration but extend it with our own predicate types, or projection types (remember the return type of Select can be anything as well), or … types. As illustrated above, in some cases you could imagine other predicate-like types like regular expressions to be applicable and we can glue them in with the where keyword in a fairly straightforward manner. However, there are other cases where this becomes extremely useful as well: dealing with “(old) dragon” query languages that either do not map nicely on LINQ operators or that are loaded with huge existing investments from users in terms of existing query definitions and/or models.

Let’s start by exploring the former. A typical sample of mismatches especially (when dealing with predicates) occurs for “exotic operators” or operators that have very specific semantics in a target language that are not available in VB or C#. A few samples:

LDAP has an “approximately equal to” ~= operator.
CAML has a DateRangesOverlap method to operate on calendars and such.
SQL has various date/time operators that are not in the BCL with identical enough semantics.

To address this, one typically creates static helper methods to act as “legacy predicate islands” in a LINQ query. For example, LINQ to SQL has the SqlMethods class:

which contains a “Like” operator that allows people to re-use their existing “LIKE” operator clauses from SQL directly in LINQ to SQL:

Attempting to cross-compile .NET regular expressions to an equivalent SQL predicate would be fairly interesting to say the least :-), so escape valves like those are ideal to address this mismatch. Methods like those simply act as stubs for use in expression tree translation and can’t be used on the client:

The nice thing about this is that you can still get some decent degree of type-verification when writing LINQ queries: Like takes in two strings and the compiler will enforce this. Of course, what’s inside the “pattern” parameter won’t be subject to checking as it’s impossible and undesirable to extend the front-end language compilers with query domain-specific knowledge to interpret “LIKE” strings and such (much like “printf” strings, although some compilers allow to verify those, but that’s a different topic of discussion).

Another place where the use of customized LINQ operators can be handy is when dealing with old APIs to allow to do querying while you want to put some LINQ sugar on top of it. For example, you might have a widely-used API to model queries for your specific data store. E.g. CAML.NET provides an object model to write CAML predicates (and more). What if people have already invested in such an API and have written huge queries encoded in terms of such an API? Or maybe you need such an object model because there’s no nice O/<whatever DSQL> mapping available. Well, first of all the question becomes where you still want to use LINQ. If there’s no benefit at all (such as strong typing all the way through or a nice object mapping) the advantages are slim. However, when an object mapping (and hence some degree of strong typing) is still possible but certain parts of a query already have specialized APIs (e.g. a predicate API) LINQ might still be of interest. Let’s give a sample with CAML.NET:

var res = from product in ctx.Products
          where CAML.And(
                    CAML.Gt(
                        CAML.FieldRef("UnitPrice"),
                        CAML.Value(123)
                    ),
                    CAML.BeginsWith(
                        CAML.FieldRef("ProductName"),
                        CAML.Value("C")
                    )
                )
          select new { Name = product.ProductName, Price = p.UnitPrice };

The reader is invited to infer the signature of the Where method used here. Similarly, the same could be expressed in terms of plain XML:

var res = from product in ctx.Products
          where new XElement("And",
                    new XElement("Gt",      
                        new XElement("FieldRef", new XAttribute("Name", "UnitPrice")),
                        new XElement("Value", new XAttribute("Type", "Integer"), 123)
                    ),
                    new XElement("BeginsWith",      
                        new XElement("FieldRef", new XAttribute("Name", "ProductName")),
                        new XElement("Value", new XAttribute("Type", "String"), "C")
                    )
                )
          select new { Name = product.ProductName, Price = p.UnitPrice };

or even better in VB:

Dim res = From product In ctx.Products _
          Where (<And>
                     <Gt>
                         <FieldRef Name="UnitPrice"/>
                         <Value Type="Integer">123</Value>
                     </Gt>
                     <BeginsWith>
                         <FieldRef Name="ProductName"/>
                         <Value Type="String">C</Value>
                     </BeginsWith>
                 </And>) _
          Select New With {.Name = product.ProductName, .Price = product.UnitPrice }

Notice we still have the richness of the projection in terms of object construction, so there’s still a benefit although the Where part is a black hole without compile-time type checking. However, given the context and the generated mappings the expression compiler that would need to be implemented could do some more intelligent analysis of the query before attempting to execute it remotely. Also notice it’s perfectly possible to combine approaches: you could have various overloads to support different mechanisms to express the same predicate (or projection, or sorting, or grouping, or …). There could even be a mixed approach within a clause:

var res = from product in ctx.Products
          where product.UnitPrice > 123
                && ???(new XElement("BeginsWith",      
                        new XElement("FieldRef", new XAttribute("Name", "ProductName")),
                        new XElement("Value", new XAttribute("Type", "String"), "S")
                   ))
          select product.Name;

I’ll leave it to the creative reader to fill out the ???(…) part in here and to explain why this mysterious thing would be required.

Conclusion

LINQ is an incredibly extensible and flexible beast. Writing APIs that are LINQ-aware can be done in a whole spectrum of styles, of which I’m just listing a few discrete flavors below:

Do nothing – The simplest approach, just use LINQ to Objects and such. Maybe your API can be expressed in terms of IEnumerable<T> and you’re done with it.
Stand in the shadow of giants – LINQ to Objects is a giant – it knows of all the standard query operators, and making your API work with IEnumerable<T> is the only thing it takes to leverage LINQ to Objects. That’s exactly what LINQ to XML does in terms of exposing XML in more intelligent fashion than “imperative-style" DOM programming. Other samples of this approach include the use of LINQ to SQL when your target database has a “SQL bridge” provider (e.g. an OLE DB provider for AD), although LINQ to SQL is intrinsically aware about Microsoft SQL Server 2000/2005.
Follow the troups – The other extreme, do what lots of people do for fun and profit: implement your own IQueryable<T>. This might be overkill in quite some cases as you buy in to all of the query operators and most likely the query language being targeted does not support even half of them. There’s no magic threshold indicating when to consider IQueryable<T> but if you only want to do Where and Select most likely this approach doesn’t scale all that well.
Embrace and extend – You’re happy with LINQ to objects, your object is IEnumerable<T> but you’d like another way to filter/project/order/group/join stuff. To solve this equation, you can add overloads for the query operators as instance level methods on your class. It will just work with the built-in LINQ syntax. This technique can also be used if you’ve implemented a full IQueryable<T> and did not run out of juice yet, so you want to add even more query operators (for which you obviously won’t get any LIN in LINQ).
Override and overrule – Hijack the existing LINQ implementation by “overriding” or “hiding” existing LINQ extension methods. The only thing you need to do is provide an instance level method with the same signature as the operator you want to override.
Cook it yourself – This is the most creative approach I’m often referring to as “LINQ to Simpsons”. As soon as you provide the right set of methods, the VB and C# compilers will be perfectly happy to translate the query expressions into underlying method calls for you. To illustrate this: guess the type of the query below. More information can be found in my Q: Is IQueryable the Right Choice for Me? post as well.

var res = (from x in new Homer() where x.HasSkateboard select x.Sister).Father

where

class Homer
{
public Marge Where(Func<Bart, bool> p) { … }
}

class Marge
{
public Homer Select(Func<Maggie, Lisa> p) { … }
}

Enjoy!

C# 3.0 Query Expression Translation Cheat Sheet

bart — Sat, 30 Aug 2008 08:29:05 GMT

As a reference for some planned and unplanned future posts, I wanted to share out my “cheat sheet” for the C# 3.0 translation carried out for query expressions. Obviously it’s based on the C# 3.0 Language Specification more specially section 7.15.2. A few remarks that deserve more attention when reading the specification:

Words in bold are contextual keywords; these are not reserved keywords as the language doesn’t introduce new reserved keywords to ensure forward compatibility for programs written in previous language versions (e.g. “from” could be used as a variable name).
Method names indicated in red are the query operators known by the compiler as compilation targets for the corresponding query syntax contextual keywords. Where these methods come from is purely a question answered by method resolution rules, obviously including extension methods from C# 3.0 on.
The ‘*’ in the translations below stands for the transparent identifier, more of an implementation aspect of the compiler to “carry forward” the range variables captured in the anonymous type produced by a query operation (e.g. in SelectMany). This illustrates that anonymous types (as well as lambda BLOCKED EXPRESSION are essential pieces of glue to make LINQ work (although alternatives based on a hypothetical “tuple type” runtime feature would work too).
For the orderby operator, corresponding flavors with descending order have been omitted. Essentially all of the ordering clauses can optionally have the descending keyword, resulting in an OrderByDescending or ThenByDescending call in the corresponding translation.
All the rules are mutually recursive: starting with a query expression, the translation will gradually “compile away” certain parts of the query expression syntax into method call driven equivalent expressions. Notice all rules without an ellipsis … on the left-hand side don’t have any query expression keywords left on the right-hand side – these are the terminal “closed” expressions that are entirely expressible in C# 3.0 \ { LINQ }. It’s like peeling off the LINQ layer from the C# 3.0 onion.
The first two rules for Select seem redundant, i.e. when substituting v for x in the second rule one gets the first rule. The reason they are spelled out each individually is because the first rule covers degenerate expressions (covered in another post of mine) and rules should be evaluated from top to bottom. The Select ( x => x ) is kept based on the conditions spelled out in section 7.15.2.3.

So here’s my cheat sheet:

Feel free to redistribute it in any form but I’d appreciate at least a reference to the official C# 3.0 Language Specification with it as that’s the ultimate resource for the detailed language specifics. A pointer to my blog would be much appreciated as well of course :-).

What Do VB 9.0 Error “BC36593: Expression of type ‘X’ is not queryable.” And C# 3.0 Error “CS1936: Could not find an implementation of the query pattern for source type ‘X’.” Really Mean?

bart — Thu, 21 Aug 2008 03:04:00 GMT

While preparing for another one of my posts, soon to be published, I received the following:

What can one do when observing such a message? Since watching a grown man cry is both a pathetic and embarrassing situation, downloading the language specification is a good start. Here are my findings. Section 11.21 on Query Expressions says:

A query expression is an expression that applies a series of query operators to the elements of a queryable collection.

Query operators are what I’m playing with – as will become apparent later on – but what’s supposed to be a “queryable collection”? Somewhere further, in paragraph 11.21.2 on Queryable Types the following is said:

Query expressions are implemented by translating the expression into calls to well-known methods on a collection type. These well-defined methods define the element type of the queryable collection as well as the result types of query operators executed on the collection. Each query operator specifies the method or methods that the query operator is generally translated into, although the specific translation is implementation dependent.

Right, but what makes up a “queryable collection”? Where not getting closer yet but somewhere further in the same paragraph one can make a little jump in the air to express a joyful mood:

A queryable collection type must satisfy one of the following conditions, in order of preference:

It must define a conforming Select method.

It must have have one of the following methods

Function AsEnumerable() As CT
Function AsQueryable() As CT

which can be called to obtain a queryable collection. If both methods are provided, AsQueryable is preferred over AsEnumerable.

It must have a method

Function Cast(Of T)() As CT

which can be called with the type of the range variable to produce a queryable collection.

In here CT stands for a (queryable) collection with elements of type T. The definition is actually recursive: one of the three bullets needs to be satisfied in order for something to be “queryable CT”. It’s clear that the latter two act as (the recursive case) escape valves to turn something “non-queryable” into something queryable because their result type is denoted as CT. So, all the power lies ultimately in the first bullet (the base case) on a “conforming Select method”. A bit further in the paragraph we read:

It is not necessary for a collection object to implement all of the methods needed by all the query operators, although every collection object must at least support the Select query operator.

Why this restriction? The VB 9.0 spec doesn’t really tell but actually C# does have a similar rule, which is more explanatory. In the C# 3.0 Specification there’s a paragraph 7.15.2.3 on so-called “Degenerate query expressions”:

A degenerate query expression is one that trivially selects the elements of the source. (…) It is important (…) to ensure that the result of a query expression is never the source object itself, as that would reveal the type and identity of the source to the client of the query. Therefore this step protected degenerate queries written directly in source code by explicitly calling Select on the source. (…)

In other words, something like

from c in customers select s

translates into

customers.Select(c => c)

which looks as unnecessary (in the end the lambda passed in is the identity function) but it makes sure that a query can never degenerate in its original source, which ensures the source is kept hidden (some form of encapsulation if you want) from the query consumer. Indeed, the paragraph continues:

It is then up to the implementers of Select and other query operators to ensure that these methods never return the source object itself.

Let’s turn it into practice. Assume we have the following class definitions:

class Bar
{
    public Foo Where(Func<object, bool> predicate)
    {
        // …
    }
}

class Foo
{
    // …
}

then the following query would translate fine:

var res = from b in new Bar() where true select b;

which strictly speaking translates into

var res = new Bar().Where(b => true).Select(b => b);

but Where already “hides” the original source, so the degenerate Select can be trimmed away:

var res = new Bar().Where(b => true);

The fact the result of b.Where, an instance of Foo, doesn’t have a Select method won’t bit us in this case (notice that Where(b => true) could be treated as a degenerate case as well; however, the compiler doesn’t treat it that way and leaves the Where call in). However, when the query is the following:

var res = from b in new Bar() select b;

the translation would look like

var res = new Bar().Select(b => b)

Dropping Select would make the result equal to the source, which is a violation of the rules in 7.15.2.3, so the compiler complains about the non-existence of Select on class Bar (trivial question: why not on Foo this time?) in this case:

So, implementing Select is a bare minimum for query provider implementations (that do not go through IQueryable<T> because those already “inherit” a Select implementation). Here’s the resulting code in VB:

Module W
    Sub Main
        Dim res = From b In New Bar Where True
    End Sub
End Module

Class Bar
    Public Function Where(p As Func(Of Object, Boolean)) As Foo
        Return Nothing
    End Function

    Public Function [Select](s As Func(Of Object, Object)) As Bar
        Return Nothing
    End Function
End Class

Class Foo
End Class

that makes the compiler happy. Notice VB doesn’t require you to say “Select b”, a little but handy feature although it makes degenerate queries even more hidden. Why? Tell me what the following means:

Dim res = From b In New Bar

Indeed, the compiler will insert a Select method call for you (hence the reason it needs a Select method in order to be able to do this):

where the referenced lambda is as trivial as you can imagine.

Conclusion: We don’t allow degenerate queries to occur; both compiler errors are manifestations of that rule. Obviously this relies on a trust relationship with query providers to play according to the rules; those should never return the original query source when applying a query on it, even if that query just selects all elements from the source. Why? The source object may contain things such as connection strings that you don’t want to leak across the border established by a query over that source object. Providers like LINQ to Objects (returns an iterator yielding all elements in the input source when presented with a degenerate select), LINQ to SQL (establishes some Query<T> object over a Table<T> even when presented with a degenerate select) and LINQ to XML (which is just LINQ to Objects with a special API powering it) play according to those rules.

The Most Funny Interface Of The Year … IQueryable

bart — Sat, 16 Aug 2008 05:43:08 GMT

Recently I delivered a talk at TechEd South Africa on “Custom LINQ Providers”. This is a very broad topic to cover in barely 60 minutes especially if one has to explain pretty “abstract” pieces of art like IQueryable<T>. Apparently I managed to do so looking at the scores <g>. But why is IQueryable<T> such a special specimen? This post will explain why.

What’s in a name?

Well, not that much: I and Queryable. “I” means there’s work to do if you want to use it – that’s precisely what interfaces are all about (the Imperative form of to Implement). “Queryable” is the promise of the interface – what we’ll get in return for the “I” labor.

So, what would you guess that needs to be implemented to get query capabilities in return? A blind guess would be: every query operator? Looking at all of the query operators we support with all their fancy overloads, that would mean 126 methods. Framework designers are sometimes masochistic but to such a large extent? Nah! There’s a magic threshold for interfaces which I would conservatively set to 10 methods. If you go beyond that threshold, only masochistic framework users will care to (try to) implement your interface. People have come up with brilliant (hmm) ideas to reduce the burden of interface implementation by trading the problem for another set of problems: abstract base classes. Right, we only have 47 distinct query operators and additional overloads can do with a default implementation in quite some cases, but still 47 abstract methods is way too much especially if most implementors will only be interested in a few of them, so you get a sparse minestrone soup with floating NotImplementedExceptions everywhere. And you’re facing the restrictions of the runtime with respect to single inheritance only, which is one of the reasons I don’t believe that much in abstract base classes as extensibility points (although there are cases where these work great).

We need something better. What about the silver bullet (hmm) to all complexity problems: refactoring? Oh yeah, we could have 47 interfaces each with a few methods (all having the same name since they would be overloads) with exciting names like IWhereable, ISelectable, IOrderable, IGroupable, etc. If it doesn’t scale against one axis, what about pivoting the whole problem and make it again not scale against the orthogonal axis? We’ve gained nothing really. Maybe there’s yet a better idea.

Time to step back a little. Remember the original promise of the interface? You implement me and I give you something with “queryable” characteristics in return. However, for ages the typical way of delivering on such a promise was symmetric to the implementation. It was really all about: “I know – but only abstractly – how to use something but only if you concretize that something for me.”. Hence interfaces for say serialization have predictable members like Serialize and Deserialize. And yes, the interface delivers on its promise of marking something that can do serialization as such but in a rather lame and predictable way. So what if we could deliver on the “queryable” promise without putting the burden of implementing all query operators directly on the implementor? This is where interfaces can also be “asymmetric” concerning their promise versus their implementation cost. (If I were in a really philosophical mood, I could start derailing the conversation introducing parallels with concave, convex and regular mirrors. Let’s not do this.) But how…?

An asymmetric interface (IImplement side)

In order to have useful query capabilities we really need two things:

Write a query
Enumerate over the results

From the latter promise we can already infer that IQueryable<T> ought to implement IEnumerable<T>, which makes our outstanding balance for the “implementor frustration threshold” (IFT for acronym lovers) two: a generic and non-generic equivalent of GetEnumerator:

interface IQueryable<T> : IEnumerable<T>
{
}

For the former promise we already came to the conclusion that it would be unreasonable to require 47 methods or so to be implemented (btw, that would also mean that in subsequent releases of LINQ, new query operators would have to go in an IQueryable2<T> interface since interfaces do not scale well on the versioning axis – remember COM?). So what if we could do all the heavy lifting for you, just giving you one piece of information that represents an entire query. That’s what expression trees are capable of doing. Now we end up with one more member to IQueryable<T>:

interface IQueryable<T> : IEnumerable<T>
{
Expression Expression { get; }
}

Conceptually, we could stop here. You have an expression tree that can represent an entire query (but how does it get there?) and you have a method that demands (where lazy becomes eager) you to start iterating over the results. The two query capability requirements have been fulfilled. Oh, and it’s quite predictable how the GetEnumerator would work, right? Take the expression tree, translate it into a Domain Specific Query Language (DSQL if you will), optionally cache it, send it to whatever data store you’re about to query, fetch the results, new up objects and yield them back.

I already raised the question about where the expression tree property’s value comes from. The answer is we need a bit of collaboration from you, the implementor, through a property called QueryProvider:

interface IQueryable<T> : IEnumerable<T>
{
Expression Expression { get; }
IQueryProvider QueryProvider { get; }
}

An IQueryProvider is an object that knows how to create IQueryable objects, much like a factory. However, at certain points in time we’ll want you to do a different thing: instead of creating a new IQueryable, we might want you to execute a query on request (for example when you’re applying the First() query operator, eager evaluation results and we’ll need a way to kindly ask you for the value returned by the query):

interface IQueryProvider
{
IQueryable<T> CreateQuery<T>(Expression ex);
T Execute<T>(Expression ex);
}

How lame you might think: it’s just asking me to create the IQueryable<T> on LINQ’s behalf. Yes, but you can carry out whatever tricks you need (such as propagating some connection information needed to connect to a database) inside the CreateQuery implementation. Oh, and both methods above have non-generic counterparts.

In addition to the two properties and two methods above, there’s one last property I should mention for completeness: ElementType. The idea of this property is to expose the type of the entities being queried. Why do we need this? Is IQueryable<T> not telling enough, namely T? Indeed, there’s even such a remark in the MSDN documentation:

The ElementType property represents the "T" in IQueryable<T> or IQueryable(Of T).

The reason we still have ElementType is for non-generic cases. For example, you might want to target a data store that doesn’t have an extensible schema, so you don’t need a generic parameter ‘T’. Instead, the type of the data returned by the provider is baked in, and ElementType is the way to retrieve that underlying type.

Finally, we end up with the following definition of IQueryable<T>:

interface IQueryable<T> : IEnumerable<T>
{
    Expression Expression { get; }
    IQueryProvider QueryProvider { get; }
    Type ElementType { get; }
}

All of this might still look fancy, so let’s turn to the consumer side to clarify things. That’s were the asymmetry becomes really apparent.

An asymmetric interface (IConsume side)

Let’s assume for a minute we have some Table<T> class that implements IQueryable<T>:

var products = new Table<Product>();

Given our derived interface definition for IQueryable<T> we don’t really get much “query capabilities”, do we? Right, we can ask this instance for things like ElementType (which really will be typeof(T)) and fairly abstract notions of Expression and QueryProvider. But no way we have query operators such a Where and Select available already. However, as you’ll know by know, LINQ relies on such operators. Indeed, take a look at the following query:

var products = new Table<Product>();
var res = from p in products where p.Price > 100 select p.Name;

The way this gets translated by the compiler looks as follows:

Table<Product> products = new Table<Product>();
var res = products.Where(p => p.Price > 100).Select(p => p.Name);

but where’s the Where? The answer lies in extension methods of course. Once we have System.Linq in scope, a (static) class called Queryable is in reach which exposes extension methods for IQueryable<T>. This is precisely why IQueryable<T> deserves the title of “funny interface” since it’s most likely the first interface that has been designed with a split view in mind. On the one hand, there’s the real “interface interface”, i.e. in CLR terms. But on top of that, extension methods provide the really useful interface functionality and act virtually as default method implementations in interfaces. That is, you don’t need to implement a whole bunch of query operator methods to get their functionality.

So, how do those methods work? Before going there, what about refreshing our mind on the LINQ to Objects implementation of those operators, as defined in System.Linq.Enumerable as extension methods on IEnumerable<T>. Just to pick one, consider Where:

static IEnumerable<T> Where<T>(this IEnumerable<T> source, Func<T, bool> predicate)
{
    foreach (T item in source)
        if (predicate(item))
            yield return item;
}

Note: I’ve omitted the (a little tricky to implement – why?) exception throwing code in case source or predicate are null; this is left as an exercise for the reader. Solutions can be found in www.codeplex.com/LINQSQO.

Besides client-side execution using iterators, there are a few important things to notice. First, here we’re extending on IEnumerable<T>. Although IQueryable<T> implements IEnumerable<T>, LINQ to Objects operators won’t be used when applying query operators on an IQueryable<T> data source because the latter type is more specific. If one wants to switch to LINQ to Objects semantics, AsEnumerable<T>() can be called. The second important thing is the type of the second parameter (on the call side this will look like the first and only parameter because we’re looking at an extension method). It’s just a Func<T, bool>, which is a delegate. This triggers the compiler to create an anonymous method:

IEnumerable<Product> products = new List<Product>();
IEnumerable<string> res = products.Where(delegate (Product p) { return p.Price > 100; }).Select(delegate (Product p) { return p.Name; });

Now, switch to the IQueryable<T> counterpart defined in System.Linq.Queryable, ignoring the implementation for a second:

static IQueryable<T> Where<T>(this IQueryable<T> source, Expression<Func<T, bool>> predicate)

Obviously the return type and first parameter type are different, but more importantly is the different type for the predicate parameter. This time it’s an Expression<…> of that same delegate Func<T, bool> type. When the compiler tries to assign a lambda expression to such an Expression<T> it emits code to create an expression tree, representing the lambda’s semantics, at runtime:

IQueryable<Product> products = new Table<Product>();

ParameterExpression p = Expression.Parameter(typeof(Product), “p”);
LambdaExpression <>__predicate = Expression.Lambda(Expression.Greater(Expression.Property(p, “Price”), Expression.Constant(100)), p);
LambdaExpression <>__projection = Expression.Lambda(Expression.Property(p, “Name”), p);

var res = products.Where(<>__predicate).Select(<>__projection);

So, we can already see how a LINQ query ends up as a chain of query operator method calls that are all implemented as extension methods on IQueryable<T> and take in their “function parameter” as an expression tree, so that interpretation and translation can be deferred till runtime. Indeed, an expression tree representing p => p.Price > 100 can easily be translated into a WHERE clause in SQL or whatever equivalent in another DSQL.

The inner workings of the beast

Remaining question is how System.Linq.Queryable.* methods are implemented. Obviously no iterators, there’s nothing that can be done client-side. Instead we want to end up with a giant expression tree representing a query, originating from a chain of query operator method calls:

products.Where(<>__predicate).Select(<>__projection)

The query above contains no less than 5 ingredients:

The query source, i.e. “products”, containing all the relevant information to connect to the data store.
First we want to filter the data using a “Where” clause which
1. takes in a predicate as an expression tree
Next we want to project the results of the previous operator using
1. a projection represented as an expression tree

After executing the line of code above, we get an IQueryable<string> in return (a string because the projection maps the Product objects onto strings using p.Name), one that should contain all of the information outlined above. Breaking this down, products is an IQueryable<Product> and hence it has an Expression property representing point ‘1’ above – data about the query source. When applying Where to this, we take all existing query information (from the “left hand side of the .”) through the Expression property and add the knowledge we’re about to apply Where with a given predicate (point ‘2’ above), resulting in a new IQueryable<Product>. Finally, Select is applied, again taking the original information via the Expression property, extending it with “Select some projection”, resulting in a new IQueryable<string> in this case. To wrap up this sample, the code above creates no less than three distinct IQueryable<T> instances (that is, including “products” in this count).

A picture is worth a thousand words:

Inside the implementation of Where<T>, we:

ask the original source for the expression tree that represents all the information about the query gathered so far (really the left of the ‘.’ when calling Where<T> through extension method syntax);
combine this with the passed in predicate expression tree;
grab the MethodInfo for the currently executing method, i.e. Queryable.Where, which will act as the representation for the query operator in the resulting expression tree;
combine all of the above in a MethodCallExpression;
feed the resulting MethodCallExpression into the IQueryProvider’s CreateQuery<T> method to end up with a new IQueryable<T>.

Subsequent query operator calls, e.g. to Select<T,R>, will continue this process of taking the original query expression and building a new one out of it by extending it with information about the query operator and its arguments (e.g. the projection lambda expression).

Conclusion

Quite often, the recommendation for using extension methods is to use them only to “extend” (sealed) classes with helper methods, if you don’t have a way to extend those yourself. In other words, if you’re the owner of a class, you should consider extending the class’s functionality rather than using extension methods are your primary extension mechanism. This recommendation is absolutely correct. However, when dealing with (what I refer to as) “asymmetric” interfaces, extension methods offer an interesting – albeit advanced – capability to separate the bare minimum extensibility points (the real “CLR interface”) from the offered functionality (brought in scope – or “woven in” – through extension methods via a namespace import) to reduce the tension between interface creator and implementor. In this post, you’ve seen one of the pioneers employing this technique: IQueryable<T>. Before you even consider following this technique, think about all the options you have: pure interfaces (keeping the “implementor frustration threshold” in mind), abstract base classes (keeping the single inheritance restriction in mind) and extension method based interface asymmetry.

Enjoy!