August 2008 - Posts

Introduction

Hi there back again. Hope everyone is already exploiting the power of LINQ on a fairly regular basis. Okay, everyone knows by now how simple LINQ queries with a where and select (and orderby, and Take and Skip and Sum, etc) are translated from a query comprehension into an equivalent expression for further translation:

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

becomes

products.Where(p => p.Price > 100).Select(p => p.Name)

All blue syntax highlighting has gone; the compiler is happy with what remains and takes it from there in a left-to-right fashion (so, it depends on the signature of the found Where method whether or not we take the route of anonymous methods or, in case of an Expression<…> signature, the route of expression trees).

But let’s make things slightly more complicated and abstract:

from i in a
from j in b
where i > j
select i + j

It’s more complicated because we have two from clauses; it’s more abstract because we’re using names with no intrinsic meaning. Let’s assume a and b are IEnumerable<int> sequences in what follows. Actually what the above query means in abstract terms is:

(a X b).Where((i, j) => i > j).Select((i, j) => i + j)

where X is a hypothetical Cartesian product operator, i.e. given a = { 1, 4, 7 } and b = { 2, 5, 8 }, it produces { (1,2), (1,5), (1,8), (4,2), (4,5), (4,8), (7,2), (7,5), (7,8) }, or all the possible pairs with elements from the first sequence combined with an element from the second sequence. For the record, the generalized from of such a pair – having any number of elements – would be a tuple. If we would have this capability, Where would get a sequence of such tuples, and it could identify a tuple in its lambda expression as a set of parameters (i, j). Similarly, Select would do the same and everyone would be happy. You can verify the result would be { 6, 9, 12 }.

Back to reality now: we don’t have the direct equivalent of Cartesian product in a form that produces tuples. In addition to this, the Where operator in LINQ has a signature like this:

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

where the predicate parameter is a function of one – and only one – argument. The lambda (i, j) => i > j isn’t compatible with this since it has two arguments. A similar remark holds for Select. So, how can we get around this restriction? SelectMany is the answer.

 

Demystifying SelectMany

What’s the magic SelectMany all about? Where could we better start our investigation than by looking at one of its signatures?

IEnumerable<TResult> SelectMany<TSource, TCollection, TResult>(
    this IEnumerable<TSource> source,
    Func<TSource, IEnumerable<TCollection>> collectionSelector,
    Func<TSource, TCollection, TResult> resultSelector)

Wow, might be a little overwhelming at first. What does it do? Given a sequence of elements (called source) of type TSource, it asks every such element (using collectionSelector) for a sequence of – in some way related – elements of type TCollection. Next, it combines the currently selected TSource element with all of the TCollection elements in the returned sequence and feed it in to resultSelector to produce a TResult that’s returned. Still not clear? The implementation says it all and is barely three lines:

foreach (TSource item in source)
    foreach (TCollection subItem in collectionSelector(item))
        yield return resultSelector(item, subItem);

This already gives us a tremendous amount of power. Here’s a sample:

products.SelectMany(p => p.Categories, (p, c) => p.Name + “ has category “ + c.Name)

How can we use this construct to translate multiple from clauses you might wonder? Well, there’s no reason the function passed in as the first argument (really the second after rewriting the extension method, i.e. the collectionSelector) uses the TSource argument to determine the IEnumerable<TCollection> result. For example:

products.SelectMany(p => new int[] { 1, 2, 3 }, (p, i) => p.Name + “ with irrelevant number “ + i)

will produce a sequence of strings like “Chai with irrelevant number 1”, “Chai with irrelevant number 2”, “Chai with irrelevant number 3”, and similar for all subsequent products. This sample doesn’t make sense but it illustrates that SelectMany can be used to form a Cartesian product-like sequence. Let’s focus on our initial sample:

var a = new [] { 1, 4, 7 };
var b = new [] { 2, 5, 8 };

from i in a
from j in b
select i + j;

I’ve dropped the where clause for now to simplify things a bit. With our knowledge of SelectMany above we can now translate the LINQ query into:

a.SelectMany(i => b, …)

This means: for every i in a, “extract” the sequence b and feed it into …. What’s the …’s signature? Something from a (i.e. an int) and something from the result of the collectionSelector (i.e. an int from b), is mapped onto some result. Well, in this case we can combine those two values by summing them, therefore translating the select clause in one go:

a.SelectMany(i => b, (i, j) => i + j)

What happens when we introduce a seemingly innocent where clause in between?

from i in a
from j in b
where i > j
select i + j;

The first two lines again look like:

a.SelectMany(i => b, …)

However, going forward from there we’ll need to be able to reference i (from a) and j (from b) in both the where and select clause that follow but both the corresponding Where and Select methods only take in “single values”:

IEnumerable<TSource> Where<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate);
IEnumerable<TResult> Select<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> projection);

So what can we do to combine the value i and j into one single object? Right, use an anonymous type:

a.SelectMany(i => b, (i, j) => new { i = i, j = j })

This produces a sequence of objects that have two public properties “i” and “j” (since it’s anonymous we don’t care much about casing, and indeed the type never bubbles up to the surface in the query above, because of what follows:

a.SelectMany(i => b, (i, j) => new { i = i, j = j }).Where(anon => anon.i > anon.j).Select(anon => anon.i + anon.j)

In other words, all references to i and j in the where and select clauses in the original query expression have been replaced by references to the corresponding properties in the anonymous type spawned by SelectMany.

 

Lost in translation

This whole translation of this little query above puts quite some work on the shoulder of the compiler (assuming a and b are IEnumerable<int> and nothing more, i.e. no IQueryable<int>):

  • The lambda expression i => b captures variable b, hence a closure is needed.
  • That same lambda expression acts as a parameter to SelectMany, so an anonymous method will be created inside the closure class.
  • For new { i = i, j = j } an anonymous type needs to be generated.
  • SelectMany’s second argument, Where’s first argument and Select’s first argument are all lambda expressions that generate anonymous methods as well.

As a little hot summer evening exercise, I wrote all of this plumbing manually to show how much code would be needed in C# 2.0 minus closures and anonymous methods (more or less C# 1.0 plus generics). Here’s where we start from:

class Q
{
    IEnumerable<int> GetData(IEnumerable<int> a, IEnumerable<int> b)
    {
        return from i in a
               from j in b
               where i > j
               select i + j;
    }
}

This translates into:

class Q
{
    IEnumerable<int> GetData(IEnumerable<int> a, IEnumerable<int> b)
    {
        Closure0 __closure = new Closure0();
        __closure.b = b;

        return Enumerable.Select(
            Enumerable.Where(
                Enumerable.SelectMany(
                    a,
                    new Func<int, IEnumerable<int>>(__closure.__selectMany1),
                    new Func<int, int, Anon0<int, int>>(__selectMany2)
                ),
                new Func<Anon0<int, int>, bool>(__where1)
            ),
            new Func<Anon0<int, int>, int>(__select1)
        );
    }

    private class Closure0
    {
        public IEnumerable<int> b;

        public IEnumerable<int> __selectMany1(int i)
        {
            return b;
        }
    }

    private static Anon0<int, int> __selectMany2(int i, int j)
    {
        return new Anon0<int, int>(i, j);
    }

    private static bool __where1(Anon0<int, int> anon)
    {
        return anon.i > anon.j;
    }

    private static int __select1(Anon0<int, int> anon)
    {
        return anon.i + anon.j;
    }
}

private class Anon0<TI, TJ> // generics allow reuse of type for all anonymous types with 2 properties, hence the use of EqualityComparers in the implementation
{
    private readonly TI _i;
    private readonly TJ _j;

    public Anon0(TI i, TJ t2) { _i = i; _j = j; }

    public TI i { get { return _i; } }
    public TJ j { get { return _j; } }

    public override bool Equals(object o)
    {
        Anon0<TI, TJ> anonO = o as Anon0<TI, TJ>;
        return anonO != null && EqualityComparer<TI>.Default.Equals(_i, anonO._i) && EqualityComparer<TJ>.Default.Equals(_j, anonO._j);
    }

    public override int GetHashCode()
    {
        return EqualityComparer<TI>.Default.GetHashCode(_i) ^ EqualityComparer<TJ>.Default.GetHashCode(_j); // lame quick-and-dirty hash code
    }

    public override string ToString()
    {
        return “( i = “ + i + “, j = ” + j + “ }”; // lame without StringBuilder
    }
}

Just a little thought… Would you like to go through this burden to write a query? “Syntactical sugar” might have some bad connotation to some, but it can be oh so sweet baby!

 

Bind in disguise

Fans of “monads”, a term from category theory that has yielded great results in the domain of functional programming as a way to make side-effects explicit through the type system (e.g. the IO monad in Haskell), will recognize SelectMany’s (limited) signature to match the one of bind:

IEnumerable<TResult> SelectMany<TSource, TResult>(
    this IEnumerable<TSource> source,
    Func<TSource, IEnumerable<TResult>> collectionSelector)

corresponds to:

(>>=) :: M x –> (x –> M y) –> M y

Which is Haskell’s bind operator. For those familiar with Haskell, the “do” notation – that allows the visual illusion of embedding semi-colon curly brace style of “imperative programming” in Haskell code – is syntactical sugar on top of this operator, defined (recursively) as follows:

do { e }            = e
do { e; s }         = e >>=  \_ –> do { s }
do { x <- e; s }    = e >>= (\x –> do { s })
do { let x = e; s } = let x = e in do { s }

Rename to SelectMany, replace M x by IEnumerable<x> and assume a non-curried form and you end up with:

SelectMany :: (IEnumerable<x>, x –> IEnumerable<y>) –> IEnumerable<y>

Identifying x with TSource, y with TResult and turning a –> b into Func<a, b> yields:

SelectMany :: Func<IEnumerable<TSource>, Func<TSource, IEnumerable<TResult>>, IEnumerable<TResult>>

and you got identically the same signature as the SelectMany we started from. For the curious, M in the original form acts as a type constructor, something the CLR doesn’t support since it lacks higher-order kinded polymorphism; it’s yet another abstraction one level higher than generics that math freaks love to use in category theory. The idea is that if you can prove laws to be true in some “structure” and you can map that structure onto an another “target structure” by means of some mapping function, corresponding laws will hold true in the “target structure” as well. For instance:

({ even, odd }, +)

and

({ pos, neg }, *)

can be mapped onto each other pairwise and recursively, making it possible to map laws from the first one to the second one, e.g.

even + odd –> odd
pos * neg –> neg

This is a largely simplified sample of course, I’d recommend everyone who’s interested to get a decent book on category theory to get into the gory details.

 

A word of caution

Now that you know how SelectMany works, can you think of a possible implication when selecting from multiple sources? Let me give you a tip: nested foreachs. This is an uninteresting sentence that acts as a placeholder in the time space while you’re thinking about the question. Got it? Indeed, order matters. Writing the following two lines of code produces a different query with a radically different execution pattern:

from i in a from j in b …
from j in b from i in a …

Those roughly correspond to:

foreach (var i in a)
    foreach (var j in b)
        …

versus

foreach (var j in b)
    foreach (var i in a)
        …

But isn’t this much ado about nothing? No, not really. What if iterating over b is much more costly than iterating over a? For example,

from p in localCollectionOfProducts
from c in sqlTableOfCategories

This means that for every product iterated locally, we’ll reach out to the database to iterate over the (retrieved) categories. If both were local, there wouldn’t be a problem of course; if both were remote, the (e.g.) SQL translation would take care of it to keep the heavy work on the remote machine. If you want to see the difference yourself, you can use the following simulation:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading;

class Q
{
    static void Main()
    {
        Stopwatch sw = new Stopwatch();

        Console.WriteLine("Slow first");
        sw.Start();
        foreach (var s in Perf<int,char>(Slow(), Fast()))
            Console.WriteLine(s);
        sw.Stop();
        Console.WriteLine(sw.Elapsed);

        sw.Reset();

        Console.WriteLine("Fast first");
        sw.Start();
        foreach (var s in Perf<char,int>(Fast(), Slow()))
            Console.WriteLine(s);
        sw.Stop();
        Console.WriteLine(sw.Elapsed);
    }

    static IEnumerable<string> Perf<S,T>(IEnumerable<S> a, IEnumerable<T> b)
    {
        return from i in a
               from j in b
               select i + "," + j;
    }

    static IEnumerable<int> Slow()
    {
        Console.Write("Connecting... ");
        Thread.Sleep(2000);
// mimic query overhead (e.g. remote server)
        Console.WriteLine("Done!");
        yield return 1;
        yield return 2;
        yield return 3;
    }

    static IEnumerable<char> Fast()
    {
        return new [] { 'a', 'b', 'c' };
    }
}

This produces:

image

Obviously, it might be the case you’re constructing a query that can only execute by reaching out to the server multiple times, e.g. because order of the result matters (see screenshot above for an illustration of the ordering influence – but some local sorting operation might help too in order to satisfy such a requirement) or because the second query source depends on the first one (from i in a from j in b(i) …). There’s no silver bullet for a solution but knowing what happens underneath the covers certainly provides the necessary insights to come up with scenario-specific solutions.

Happy binding!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Recently I posted a post titled Curry for dummies. I have to admit the article did possibly exceed the dummy level, so here's a little code-based wrap-up before extending upon it:

int Add(int a, int b) { return a + b; }

//
// Without curry support = all or nothing
//

var add = Add; // a delegate (no args applied = nothing)
var addOne = add(1);
// an error (not enough args applied)
var three = add(1, 2); // an int (all args applied = all)

//
// With curry support = allow partial application
//

var add = Add;
// a delegate
var addOne = add(1);
// a function with one more int to go
var three = addOne(2); // an int - all args of Add have been "eaten"

I pointed out there are two ways to make currying work. Actually I'd say there's only one "right" way of doing it (at least from a theoretical point of view), which is formal substitution as specified in lambda calculus. Let's do the last part of the sample above but more formally:

//
// With curry support = allow partial application
//
add = λ a b . a + b
addOne = add 1
       = (λ a b . a + b) 1
       = [a := 1](λ b . a + b)
       = λ b . [a := 1](a + b)
       = λ b . 1 + b
three = addOne 2
      = (λ b . 1 + b) 2
      = [b := 2](1 + b)
      = 1 + 2
      = 3

But we have to keep ourselves honest. This approach only works in a purist functional world. I'll explain why in just a bit. The alternative I've discussed is by wrapping the original function in a new function, reducing the number of arguments (the "InvocationExpression" way):

var add = Add;
var addOne = b => add(1, b);
var three = addOne(1);

But why is this "impure" way preferable in some sense? Side-effects come and bite us if we don't do it this way. Essentially what this approach does is preserving the "call-by-value" semantics of function calls throughout the currying process (which we can't really call curry anymore because we're loosing some of the essential lambda purity, but that's nitpicking). As we don't touch the inner workings of the original function, its behavior isn't changed with respect to calling it. Why this matters becomes apparent in the following sample:

Func<int,int,int> f = (a, b) => (a + b) / a;

I hear my readers already scream the word "simplify" but can we really do that, like this?

Func<int,int,int> f = (a, b) => 1 + b / a;

That's exactly the problem and I want you to think about the assumptions you've made why this would hold true. Just a few questions/hints. Did you make assumptions about the type of the parameters (or: did you really look at the variable type first; if not, what made you believe the distributive law holds)? What about overflowing conditions? Although all of those questions need to be answered, a more important question to raise is on the call semantics. You'll have to admit you just assumed (correctly for this particular language) that call-by-value semantics are in effect. For example, calling f like this:

f(e, 2)

is executed as:

f_arg_0 = e;
f_arg_1 = 2;
f(a := f_arg_0, b := f_arg_1) // using := for parameter binding
{
    return (a + b) / a; // could we optimize here? why? why not? assumptions?
}

What are the implications of this strategy? The expressions that act as the parameter values are evaluated exactly once (I've assumed a left-to-right order but even that might differ from language to language). But maybe the body of f doesn't use the value of the first parameter at all (this behavior might be conditioned on the second argument). So if expression e wouldn't terminate, we're hanging the application for no good reason. To look at it in another way: the parameter evaluation stays outside the function which acts as a black box from the caller's point of view. An alternative is call-by-name where the parameters to the function are "propagated down into" the function's body by a formal substitution mechanism:

f(e, 2)

becomes

return (e + 2) / e;

This time, e is evaluated twice, which is essentially what the substitution implementation in Curry for dummies does. Does this matter? Most people will say: yes, because of performance. While that's true, there's more. Let's assume our compiler is smart and can eliminate common subexpressions, say as a performance optimization trick. Assume e = (some * giant + expression):

return ((some * giant + expression) + 2) / (some * giant + expression);

So, it would have the right to say: hey, this thing is done twice (and that shouldn't necessarily be caused by substitution of parameters), let's just do it only once and reuse the produces values:

var dummy = (some * giant + expression);
return (dummy + 2) / dummy;

But can we really do this? What about side-effects? Here's a sample where such optimization will hurt:

Console.WriteLine("Current time: " + DateTime.Now);
Thread.Sleep(1000);
Console.WriteLine("Current time: " + DateTime.Now);

The compiler will say this:

string dummy = "Current time: " + DateTime.Now;
Console
.WriteLine(dummy);
Thread.Sleep(1000);
Console.WriteLine(dummy);

Does it have the right to do this? No. For what reason? Side-effects are not made explicit in the framework (or in more general terms, in imperative languages). The problem is not with the string concatenation; that's a pure function (is it really?). Instead the problem is in DateTime.Now's type (remember that the property Now is really a call to a "function" called get_Now) being DateTime. From the type we can't know whether or not the result will be a constant, and clearly it isn't. In Haskell the type would be IO DateTime to indicate there's a side-effect involved, meaning this optimization can't be carried out. Because we don't know - and because we don't have the right to gamble - we can't be smart and need to be conservative.

A slightly modified version of call-by-name is called call-by-need where memoization (a specific form of caching) is employed. Again, parameter evaluation is percolated down into the function being called (to avoid evaluating any parameters that are not used on the code path taken inside the function during this particular call) but when the parameter is used multiple times, it's only evaluated the first time it's used:

f(e, 2)

becomes

var cell_a = new Cell<...>(() => e);
var cell_b = new Cell<...>(() => 2);
return (cell_a.Value + cell_b.Value) / cell_a.Value;

The generic Cell<T> introduced above takes in a function producing a value (Func<T>) that's evaluated once at most, when calling the Value property getter for the first time. On subsequent calls, the result is returned straight away without calling the function again. Here's how a Cell<T> implementation could look like:

class Cell<T>
{
    private Func<T> _func;
    private T _value;
    private bool _evaluated;

    public Cell<T>(Func<T> func)
    {
        _func = func;
    }

    public T Value
    {
        if (!_evaluated)
        {
            _value = _func();
            _evaluated = true;
        }

        return _value;
    }
}

Readers looking for a challenge are invited to think about how it would be possible to adapt the original (substitution-driven) Curry for dummies code to work with call-by-need semantics; in other words, how can a lambda expression be applied (the number of arguments provided is not really relevant in this discussion) with arguments that are lazily (one time at most) evaluated? I'll post the answer some time soon.

Exercise: Based on the discussion of these three strategies, point out what the (differences in the) results of the following function call will be when each of the strategies is applied:

twice(DateTime.Now.Ticks, div(1, 0));

where

long twice(long a, long @default)
{
    return a > 0 ? a + a : @default; // a + a != 2 * a
}

long div(long a, long b)
{
    return a / b;
}

For people who want to know more, Philip Wadler's site contains a bunch of interesting papers on calling strategies: http://homepages.inf.ed.ac.uk/wadler/topics/call-by-need.html. How Haskell benefits from call-by-need is something the reader is invited to think about a bit more and if you really want to dig deeper, I strongly recommend Wadler's paper on Monads for functional programming.

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

A few days ago I blogged about Curry for Dummies, outlining one of the typical techniques employed in functional programming. What I didn't say back then is I'm about to reuse the "Curry" function with formal substitution mechanism for this subsequent blog post. Just as a quick refresher:

LambdaExpression Curry(LambdaExpression func, params Expression[] parameters);

used like this:

LambdaExpression add1 = Curry((int a, int b) => Add(a, b), Expression.Constant(1));

produces this:

b => Add(1, b)

But what's up this time? Today we're going to look at a few notable functions from the realm of functional programming: folds. A fold is a higher-order function that knows how to "fold" a given data structure (typically a sequence of elements) into a single return value. There are two sorts of folds, a left fold and a (surprisingly) right fold. The difference is the way the data is "folded", as will become apparent in a minute. Assume you have some sequence of numbers:

source = { 1, 2, 3, 4, 5, 6 }
source :: IEnumerable<TSource>

To be able to do folding one needs a base value, also known as the seed. Let's assume it's 1, thus:

seed = 1
seed :: TAccumulate

Folding proceeds as follows. It takes the seed and combines it with an element from the source to produce a new value in the same value domain as the seed. For instance, it could multiply the two numbers:

fold = (acc, val) => acc * val
fold :: Func<TAccumulate, TSource, TAccumulate>

This function is called repeatedly to combine all the values to come up with a single resulting value in the TAccumulate value domain, e.g.:

fold(fold(fold(fold(fold(fold(1,1),2),3),4),5),6) = 120
                              ^
^ = seed

Actually the statement above is underspecified:

It takes the seed and combines it with an element from the source to produce a new value in the same value domain as the seed.

The sample I gave above is one that does a left fold: the an in the sentence above is determined in a left-to-right fashion. If we define an in a right-to-left order we end up with a right fold:

fold(fold(fold(fold(fold(fold(1,6),5),4),3),2),1) = 120
                              ^
^ = seed

Obviously both calculate factorial but in a different order. In Haskell both uses of the fold look like this:

facl n = foldl (*) 1 [1..n]
facr n = foldr (*) 1 [1..n]

where (*) is the infix multiplication operator and .. is the range operator. In LINQ, we actually do have the left folding operator, named Aggregate. It's defined like this (one of the three overloads):

public static TAccumulate Aggregate<TSource, TAccumulate>(
    this IEnumerable<TSource> source,
    TAccumulate seed,
    Func<TAccumulate, TSource, TAccumulate> func
)
{
    TAccumulate result = seed;
    foreach (var item in source)
        result = func(result, item);
    return result;
}

I didn't care about exception throwing conditions here, feel free to add those yourself. It should be apparent that this definition is a left fold. The fact we iterate over the source "from left to right" and accumulate with the current result value (that's initialized to the seed value initially) reveals this fact.

To test your understanding of folds so far, write a sum function for values 1..n by filling in the ... below:

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        Console.Write("Specify upper limit for sum: ");
        int n = int.Parse(Console.ReadLine());

        Console.WriteLine("Sum = " + Enumerable.Range(1, n).Aggregate(...));
    }
}

Tip: use a lambda expression for the second argument.

 

Playing with folds

Time to make things a little more complex. Would it be possible to express a right fold in terms of a left fold? This is the sort of question that keeps functional programmers awake at night :-). There's a solution to this problem indeed. Let's reason a bit about it.

First, notice we can't change the order in which we iterate over the source sequence, we still have to walk through it from left to right. However, to make things evaluate from right to left we first need to get all the way to the rightmost element in order to combine it with the seed. Once we're there, we can go back all the way to left, accumulating values from right to left.

The question now becomes how we can keep track of all the values we've already seen while walking from left to right so that "on the way back" we can apply the aggregation function? The answer is to use a function as the accumulator value. Why? In a nutshell because a function has the potential of deferring some execution, think about the following:

int one = 1;
int oneIfYouAskForIt = () => 1;
int oneIAskedFor = oneIfYouAskForIt();

What we need to do in this particular case is to build a function that tracks the entire history of sequence numbers, also knowing how to aggregate them, so that ultimately we can ask for the result simply by calling it. This call would put all the machinery inside the function to work, consuming all the tracked data.

Let's analyze the signature of Aggregate a bit further:

public static TAccumulate Aggregate<TSource, TAccumulate>(
    this IEnumerable<TSource> source,
    TAccumulate seed,
    Func<TAccumulate, TSource, TAccumulate> func
);

To concretize this generic function a bit more, let's substitute TSource for int and assume we'll deal with integers:

public static TAccumulate Aggregate<TAccumulate>(
    this IEnumerable<int> source,
    TAccumulate seed,
    Func<TAccumulate, int, TAccumulate> func
);

Now look at the third parameter: we need a function taking in an accumulator value and an integer, returning a new accumulator. Assume TAccumulate is some kind of function "f" and the integer is represented as "c" (for constant), the lambda we'd supply would look like:

(f, c) => ...

where the ellipsis needs to be filled in with something of the same type as f, i.e. a function with the same signature.

To go a little further in our analysis, let's look at the result we want to get. Accumulating a sequence of integers could result in many things, e.g. we could generate a string consisting of the comma-separating list of integers in their string representation. To make things easy though, assume the accumulation value will be an integer too, e.g. the sum or product of the sequence. It would be tempting to say that TAccumulate therefore needs to be an integer too. However, we already said we want TAccumulate to be a function and moreover, it should be one that "if we ask for it" gives us the result, which is an integer, back. So what about:

TAccumulate := Func<..., int>

which means our function will return an integer "if we ask for it". In other words, we can already call Aggregate like this:

int res = Enumerable.Range(1, n).Aggregate(..., (f, c) => ...)(...);

Notice the extra function call at the end. Since Aggregate returns a function type with one argument, we'll have to call through it in order to get the integer result value back. We're still missing a few pieces though. What should be the type of the parameter to our accumulator? Well, what's the real seed we want to use? We already said, for simplification, we were going to aggregate a list of integers to another integer, so it's fairly reasonable to assume the seed value will be an integer too:

fold(fold(fold(fold(fold(fold(1,6),5),4),3),2),1) = 120
                              ^
^ = seed

Based on this it definitely makes sense to define TAccumulate as:

TAccumulate := Func<int, int>

We're coming close now. With the substitution for TAccumulate the Aggregate signature now looks like:

public static Func<int, int> Aggregate<TAccumulate>(
    this IEnumerable<int> source,
    Func<int, int> seed,
    Func<Func<int, int>, int, Func<int, int>> func
);

Aggregate returns some function with this type, hence we need to call the result of Aggregate with some integer argument. The value we'll pass in here is the seed:

int res = Enumerable.Range(1, n).Aggregate(..., (f, c) => ...)(1);

Next is to infer how the function argument should look like. Here's the type:

Func<Func<int, int>, int, Func<int, int>> func

so our lambda is really:

(Func<int, int> f, int c) => ...

where ... is also of type Func<int, int>. A quick analysis:

  • What's the value of c? If you analyze the loop body of Aggregate you'll come to the conclusion it follows the input values from left to right.
  • What's f supposed to be? This is our time-traveling device: it keeps track of all that needs to be calculated before we can process c in our aggregation journey.
  • The result we need to give back is something that "when asked to do so" calls f "aggregating in" c but still being lazy since it has to be a Func<int, int>.

Assuming we want to create a factorial function, our aggregation operator will be *. So we have a Func<int, int> called f, an integer called c and another function * of type Func<int,int,int>. We're missing one integer in order to be able to call our * aggregator: let's call it x. Now we can write:

(Func<int, int> f, int c) => x => f(x * c)

Notice the lambda arrow is right associative, so in reality this is:

(Func<int, int> f, int c) => (x => f(x * c))

Analyzing the type of the result: x * c is an integer, calling f with an integer returns and integer, so f(x * c) is an integer too. Since x is an integer and f(x * c) is an integer, the lambda ought to be a Func<int, int>. Bingo! Almost there:

int res = Enumerable.Range(1, n).Aggregate(..., (f, c) => x => f(x * c))(1);

Remaining is the seed argument to the aggregate call. Again, it needs to be of type Func<int, int>. When and where does it kick in during the evaluation? Looking at the implementation of the Aggregate method:

    Func<int, int> result = seed;
    foreach (var item in source)
        result = func(result, item);
    return result;

The seed is used the first time we call through the function and becomes part of the function's aggregated history for the subsequent iterations. We already are processing all the values of the source sequence, the multiplicative aggregation, so the only function that makes sense here is the identity function:

int res = Enumerable.Range(1, n).Aggregate(x => x, (f, c) => x => f(x * c))(1);

Phew, we're done. But can we figure out how does all this hocus pocus really works now? Let's trace it down a bit, with an input sequence { 1, 2, 3 }. Unfold the loop of the Aggregate implementation:

Func<int, int> result = x => x;
result = ((f, c) => x => f(x * c))(result, 1);
result = ((f, c) => x => f(x * c))(result, 2);
result = ((f, c) => x => f(x * c))(result, 3);
return result;

Here I'm using pseudo-syntax where calling through a lambda is directly supported. It's left as an exercise to the reader to find out whether this works in C# 3.0 and why (not). We already know from the Curry for Dummies post that "calling through a lambda" is beta-reduction which is carried out by means of formal substitution. To make things not mutate state, let's turn to single-assignment form, and to avoid confusing letters let's do an alpha-conversion too (i.e. renaming variables - or refactoring in geeky terms):

Func<int, int> result0 = x => x;
Func<int, int> result1 = ((f, c) => u => f(u * c))(result0, 1);
Func<int, int> result2 = ((g, d) => v => g(v * d))(result1, 2);
Func<int, int> result3 = ((h, e) => w => h(w * e))(result2, 3);
return result3;

Time to do the first substitution:

Func<int, int> result1 = ((f, c) => u => f(u * c))(x => x, 1);
Func<int, int> result1 = u => (x => x)(u * 1);

Next,

Func<int, int> result2 = ((g, d) => v => g(v * d))(u => (x => x)(u * 1), 2);
Func<int, int> result2 = v => (u => (x => x)(u * 1))(v * 2);

And finally:

Func<int, int> result3 = ((h, e) => w => h(w * e))(v => (u => (x => x)(u * 1))(v * 2), 3);
Func<int, int> result3 = w => (v => (u => (x => x)(u * 1))(v * 2))(w * 3);

Now to evaluate, we call result3 with argument 1:

result3(1)
= (w => (v => (u => (x => x)(u * 1))(v * 2))(w * 3))(1)
= (v => (u => (x => x)(u * 1))(v * 2))(1 * 3)
= (u => (x => x)(u * 1))((1 * 3) * 2)
= (x => x)(
((1 * 3) * 2) * 1)
= ((1 * 3) * 2) * 1
= 6

And indeed, the evaluation order is 3 * 2 * 1. Magic! Who ever said lambda calculus and functional programming are boring?

 

Say it with code

To provide all of this works, let's talk LINQ for a bit first:

int n = 5;

//
// Left fold == Aggregate in LINQ.
//

Console.WriteLine("LFOLD");
Console.WriteLine("-----\n");

Console.WriteLine("Value:      " + Enumerable.Range(1, n).Aggregate(1, (a, c) => a * c));

Console.WriteLine();
Console.WriteLine();

//
// Right fold in terms of left fold.
//
Console.WriteLine("RFOLD");
Console.WriteLine("-----\n");

Console.WriteLine("Value:      " + Enumerable.Range(1, n).Aggregate<int,Func<int,int>>(x => x, (f, c) => x => f(x * c))(1));

Not surprisingly this will print 120 twice. But can we go a bit further? What about putting expression trees to work and print how those would look like. As we know by know, lambdas can either represent anonymous methods or expression trees, which are code as data. Leaving the implementation of AggregateE as a trivial exercise to the reader, here's how we're about to call the two folds:

var foldL = Expression.Lambda<Func<int>>(Enumerable.Range(1, n).AggregateE(Expression.Constant(1), (a, c) => Expression.Multiply(a, Expression.Constant(c))));

var foldR = Enumerable.Range(1, n).AggregateE(x => x, (f, c) => {
    var x = Expression.Parameter(typeof(int), "x");
    return Expression.Lambda<Func<int,int>>(Expression.Invoke(f, Expression.Multiply(x, Expression.Constant(c))), x);
});

As you can see, those definitions are identical to the ones used in the previous sample, but expressed in terms of expression trees. The fact we're creating aggregation functions that accumulate expression trees is the ultimate sample of function composition, even more, in a dynamic fashion. What can we do with such expression trees? Both folds above are lambda expressions (actually there are two AggregateE functions in use here, exercise for the reader), so we can dynamically compile them, producing a delegate, through which we can call at runtime to invoke the compiled expression trees:

int n = 5;

var foldL = Expression.Lambda<Func<int>>(Enumerable.Range(1, n).AggregateE(Expression.Constant(1), (a, c) => Expression.Multiply(a, Expression.Constant(c))));

var foldR = Enumerable.Range(1, n).AggregateE(x => x, (f, c) => {
    var x = Expression.Parameter(typeof(int), "x");
    return Expression.Lambda<Func<int,int>>(Expression.Invoke(f, Expression.Multiply(x, Expression.Constant(c))), x);
});

//
// Left fold == Aggregate in LINQ.
//

Console.WriteLine("LFOLD");
Console.WriteLine("-----\n");

Console.WriteLine("Value:      " + Enumerable.Range(1, n).Aggregate(1, (a, c) => a * c));
Console.WriteLine("Expression: " + foldL.Body);
Console.WriteLine("Invocation: " + foldL.Compile().DynamicInvoke());

Console.WriteLine();
Console.WriteLine();

//
// Right fold in terms of left fold.
//
Console.WriteLine("RFOLD");
Console.WriteLine("-----\n");

Console.WriteLine("Value:      " + Enumerable.Range(1, n).Aggregate<int,Func<int,int>>(x => x, (f, c) => x => f(x * c))(1));
Console.WriteLine("Expression: " + foldR);
Console.WriteLine("Invocation: " + foldR.Compile().DynamicInvoke(1));

Again, it will print 120 two more times. What's more interesting though is the ToString output of the expression trees:

image

For the right fold, one can read Invoke(_, args) as the equivalent for _(args). Rewriting the output string based on that makes it a little more "readable":

x => (x => (x => (x => (x => (x => x)(x * 1))(x * 2))(x * 3))(x * 4))(x * 5)

Actually all of the x variables have separate scopes, so we can apply alpha conversion:

a => (b => (c => (d => (e => (f => f)(e * 1))(d * 2))(c * 3))(b * 4))(a * 5)

Let's do the reduction exercise one more time manually:

(a => (b => (c => (d => (e => (f => f)(e * 1))(d * 2))(c * 3))(b * 4))(a * 5))(1)
     
(b => (c => (d => (e => (f => f)(e * 1))(d * 2))(c * 3))(b * 4))(1 * 5)
            (c => (d => (e => (f => f)(e * 1))(d * 2))(c * 3))((1 * 5) * 4)
                  (d => (e => (f => f)(e * 1))(d * 2))(((1 * 5) * 4) * 3)
                        (e => (f => f)(e * 1))((((1 * 5) * 4) * 3) * 2)
                              (f => f)(((((1 * 5) * 4) * 3) * 2) * 1)
                                    (((((1 * 5) * 4) * 3) * 2) * 1)

 

An interpretive-based approach to expression tree evaluation

Did I say we were going to do the reduction only one more time by hand? Smells like a promise you say? Yes. Let's make the computer do the work. In Curry for Dummies I provided a primitive method called Curry that can do (partial) function application. We could really have called this method Beta, it simply applies a function to its arguments, which can be done partially or complete. In this case, we want to evaluate our right fold function completely, which we can do by just passing in a single value, the constant expression for 1 in our case. The Curry method will carry out identically the same substitution as the transition between the first and second line above; to go all the way with the substitution we'll have to continue calling the Curry function till we run out of juice, something screaming for a recursion-driven approach. Here's a Curry wrapper that does this job (code for Curry can be found in Curry for Dummies):

static Expression Evaluate(LambdaExpression ex, params Expression[] parameters)
{
    LambdaExpression l = Curry(ex, parameters);
    Expression res = l;

    if (l.Parameters.Count == 0)
    {
        res = l.Body;
    }

    var invoke = res as InvocationExpression;
    if (invoke != null)
    {
        LambdaExpression l2 = invoke.Expression as LambdaExpression;
        if (l2 != null && l2.Parameters.Count == invoke.Arguments.Count)
        {
            res = Evaluate(l2, invoke.Arguments.ToArray());
        }
    }

    return res;
}

It basically applies the parameters to the current lambda expression, eliminates the remaining empty "() => Body" to Body and continues by "unwrapping" the embedded InvocationExpression (after all, invocation is just a form that can be reduced through beta conversion, hence the recursion). Finally our code looks like:

int n = 5;

var foldL = Expression.Lambda<Func<int>>(Enumerable.Range(1, n).AggregateE(Expression.Constant(1), (a, c) => Expression.Multiply(a, Expression.Constant(c))));

var foldR = Enumerable.Range(1, n).AggregateE(x => x, (f, c) => {
    var x = Expression.Parameter(typeof(int), "x");
    return Expression.Lambda<Func<int,int>>(Expression.Invoke(f, Expression.Multiply(x, Expression.Constant(c))), x);
});

//
// Left fold == Aggregate in LINQ.
//

Console.WriteLine("LFOLD");
Console.WriteLine("-----\n");

Console.WriteLine("Value:      " + Enumerable.Range(1, n).Aggregate(1, (a, c) => a * c));
Console.WriteLine("Expression: " + foldL.Body);
Console.WriteLine("Invocation: " + foldL.Compile().DynamicInvoke());

Console.WriteLine("Reduction:  " + Evaluate(foldL));

Console.WriteLine();
Console.WriteLine();

//
// Right fold in terms of left fold.
//
Console.WriteLine("RFOLD");
Console.WriteLine("-----\n");

Console.WriteLine("Value:      " + Enumerable.Range(1, n).Aggregate<int,Func<int,int>>(x => x, (f, c) => x => f(x * c))(1));
Console.WriteLine("Expression: " + foldR);
Console.WriteLine("Invocation: " + foldR.Compile().DynamicInvoke(1));
Console.WriteLine("Reduction:  " + Evaluate(foldR));

And yes, it works as expected:

image

 

Conclusion

Really just for fun although the left-fold accumulation operator is quite useful in different cases. For samples like factorial, agreed, it's overkill but nevertheless an interesting journey through the wonderful world of functions and their applications. To get our feet back on the ground, our lfold sample really is equivalent to (the generalized case of):

int res = 1;
for (int i = 1; i <= n; i++)
    res *= i;

Have (functional) fun!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

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:

  1. Write a query
  2. 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:

  1. The query source, i.e. “products”, containing all the relevant information to connect to the data store.
  2. First we want to filter the data using a “Where” clause which
    1. takes in a predicate as an expression tree
  3. 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:

image

Inside the implementation of Where<T>, we:

  1. 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);
  2. combine this with the passed in predicate expression tree;
  3. 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;
  4. combine all of the above in a MethodCallExpression;
  5. 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!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Introduction

Functional programming concepts aren’t that hard but sometimes a little abstract. In this post I’ll try to demystify the concept of currying, or - in simple words – partial function application. If you wonder where the name “curry” comes from, it’s named after Haskell Curry, one of the creative minds behind functional programming, and indeed as the name implies it adds quite some spicy taste to functional programming. To be completely honest, currying wasn’t originally invented by Haskell Curry; Haskell himself attributed the technique to Schönfinkel although another mathematician Frege was using it also at that time (in the pre-internet era, it wasn’t so uncommon for different people to have the same idea independently from each other without knowing each other’s work in real-time).

 

Talking beta

So, what’s it all about? In the lambda calculus, one of the basic rules to deal with functions is the so-called beta-conversion. It’s nothing more but a fancy name for function application. Assume you have a function called “add”, looking like:

λ a b . a + b

Every symbol between the λ symbol and the . acts as a parameter to the function while the function’s body is specified to the right of the .. In C# 3.0 syntax this would look like (ignoring the fact the expression above is untyped and assuming int for both parameters):

(int a, int b) => a + b

Beta-conversion allows us to apply the function, like this:

(λ a b . a + b) 1 2

which is left-associative:

(((λ a b . a + b) 1) 2)

and carried out by formal substitution. Evaluating the inner portion first looks like (the parameter “binding” is underlined):

(((λ a b . a + b) 1) 2)

This means we can substitute a for 1 in the body of the function, like this:

((λ b . 1 + b) 2)

What’s left in the inner parentheses now is a new function that takes one remaining argument:

λ b . 1 + b

This is the basic idea behind currying. Going back to C# 3.0 this would mean we’d be able to write something like:

Func<int, int, int> add = (int a, int b) => a + b;
Func<int, int> addOne = add(1);

but we can’t. The compiler would complain about the second line, telling us that the delegate doesn’t take one argument. In other words, the language (as opposed to for example F#) doesn’t support currying. However, I still want to show you how such a feature would work conceptually by lifting our lambda expressions out of the language and switching to expression trees.

 

A simple approach

So how can we achieve building a currying sample in C# 3.0? There are different approaches really. One way to do it would be to take the original lambda function and “invoke” it with the supplied parameters, keeping the remaining parameters in place. In other words, we’re eating certain parameters at the head and leaving the remaining tail parameters there. Let’s assume we’re given a LambdaExpression instance with whatever body you can dream of. To make it concrete, consider this lambda expression:

(int a, int b) => Add(a, b)

Here’s the corresponding code the compiler would generate if you assign the expression above to an Expression<Func<int,int,int>> typed variable (the Expression<T> part here is of enormous importance and tells the compiler to generate an expression tree as opposed to an anonymous method):

ParameterExpression a = Expression.Parameter(typeof(int), “a”);
ParameterExpression b = Expression.Parameter(typeof(int), “b”);
Expression<Func<int, int, int>> e = Expression.Lambda<Func<int, int, int>>(
    Expression.Call(null, typeof(Operators).GetMethod(“Add”), a, b),
    a, b
);

Given this expression object and a set of to-be-applied parameter values, we want to create a new lambda expression with less (i.e. the remaining) parameters. Let’s step back a while and come up with a generalized signature for currying:

LambdaExpression Curry(LambdaExpression func, params Expression[] parameters);

What we could do now, rather naively, is taking the original lambda expression and wrap it in an InvocationExpression, passing in the supplied parameters (getting rid of the “eaten” lambda parameters) and the remaining lambda parameters and make that the body to a new lambda expression that still has the remaining lambda parameters. More words than lines of code, so here’s how this would look like, using some LINQ to Objects operators:

LambdaExpression Curry(LambdaExpression func, params Expression[] parameters)
{
    ParameterExpression[] lambdaParams = func.Parameters.Skip(parameters.Count).ToArray();
    return Expression.Lambda(Expression.Invoke(func, parameters.Concat(lambdaParams)), lambdaParams);
}

In a “ToString” format the original lambda would look like:

(a, b) => Add(a, b)

and when applying currying like this:

LambdaExpression add1 = Curry((int a, int b) => Add(a, b), Expression.Constant(1));

the result looks like:

b => Invoke((a, b) => Add(a, b), 1, b)

The signature is definitely right, yielding a function with only one remaining argument, but the body looks like hell (imagine what it would look like if you’re currying 1 argument at a time for a 10-argument function). In addition, the parameter “b” is a little special (left to the reader to think about a bit more). Instead we’d like to see a simpler form that really illustrates formal substitution, yielding this:

b => Add(1, b)

 

Formal substitution

Time to switch gears and move from the quick-and-dirty solution above to a better solution that carries out real substitution. How can we achieve this? The first thing we need to know about is the fact that expression trees are immutable. There’s no way to change them, we can only create new ones. That’s exactly what we need to do here: given an expression tree for a lambda expression, take its body and clone it but while doing so, replace a set of given parameters (which will be instances of ParameterExpression) with their corresponding substitution values. Now we need to know how to clone an expression tree while rewriting certain portions on the way. The answer to this need is an expression tree visitor, and yes we have one on MSDN at http://msdn.microsoft.com/en-us/library/bb882521.aspx. What this piece of code does is simply recursively walking the expression tree and for each node it calls out to a virtual method (that we therefore can override) that has the behavior of new’ing up a new instance of an expression having the same values. Actually, ParameterExpressions are a funny exception to this rule since they act as reference placeholders for parameters and their equality is essential for this referencing to work (so, you’ll find simply “return p” in VisitParameter). Anyway, in order to use the visitor, we need to inherit from it and supply our desired behavior:

class CurryVisitor : ExpressionVisitor
{
    private Dictionary<ParameterExpression, Expression> _parameters;

    public CurryVisitor(Dictionary<ParameterExpression, Expression> parameters)
    {
        _parameters = parameters;
    }

    protected override Expression VisitParameter(ParameterExpression p)
    {
        if (_parameters.ContainsKey(p))
            return _parameters[p];

        return base.VisitParameter(p);
    }

    public Expression Clone(Expression exp)
    {
        return base.Visit(exp);
    }
}

So essentially we just have one constructor taking in mappings from parameters to their to-be-substituted-with values and one method to do the actual cloning. The only thing we override is VisitParameter to see whether the parameter being processed occurs in the dictionary of substitutions and if so, we copy in the substitution-valued expression. That’s it. Only remaining thing to look at is the Curry method:

LambdaExpression Curry(LambdaExpression ex, params Expression[] parameters)
{
    if (parameters.Length > ex.Parameters.Count)
        throw new InvalidOperationException("Too many parameters specified.");

    var assignments = new Dictionary<ParameterExpression, Expression>();

    for (int i = 0; i < parameters.Length; i++)
    {
        ParameterExpression parameter = ex.Parameters[i];
        Expression value = parameters[i];

        if (!parameter.Type.IsAssignableFrom(value.Type))
            throw new InvalidOperationException("Incompatible parameter value type for parameter " + parameter.Name);

        assignments[parameter] = value;
    }

    var visitor = new CurryVisitor(assignments);
    return Expression.Lambda(visitor.Clone(ex.Body), ex.Parameters.Skip(parameters.Length).ToArray());
}

This code is fairly straightforward. First, we make sure that the number of arguments we’re about to substitute doesn’t exceed the number of parameters we have available. Next, we cycle through the supplied parameter values, make sure their static types are compatible with the corresponding parameters’ static types, and build up the substitution dictionary. Finally, we create the visitor object, clone the lambda body, therefore eating the parameters starting from the head, and wrap the new body in a new lambda expression with the remaining parameters.

Here are a couple of examples:

Expression<Func<int, int, int, int>> add = (a, b, c) => a + b + c;
Console.WriteLine(add);
Console.WriteLine(Curry(add, Expression.Constant(1)));

Expression<Func<Func<int, int, int>, int, int, int>> binOp = (f, a, b) => f(a,b);
Expression<Func<int, int, int>> binAdd = (int a, int b) => a + b;
Console.WriteLine(binOp);
Console.WriteLine(Curry(binOp, binAdd));

Expression<Func<int, int>> d = a => a + a;
Console.WriteLine(d);
Console.WriteLine(Curry(d, Expression.Constant(1)));

and here’s the corresponding output:

image

The second sample is an interesting one to think about scoping and “name clashes” (or to get in the zen of alpha conversion). Obviously you can use the Compile method on all of the produced LambdaExpression objects above, giving you the delegate result of currying which you can invoke using DynamicInvoke:

Curry(binOp, binAdd).Compile().DynamicInvoke(1, 2); // produces 3

Enjoy your lambda with curry meal!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Recently I gave a talk at TechEd South Africa about Custom LINQ Providers. Unfortunately the session was only 60 minutes, so I had to cut down on the number of topics covered and focus on the bare essentials of query expression tree translation, including a primer to IQueryable<T>. However, the hidden slides – kept as reference material – contain a bunch of helpful tips to consider when implementing custom LINQ query providers and just one of those things that deserves some attention is the act of expression tree normalization.

But before we dig in, let me point out that this technique might or might not be applicable for particular implementations of query providers. There’s no silver bullet and the reason is very simple: when translating stuff (being expression trees) from one language into another, one core concern is matching up the semantics on both sides. How far this matching goes depends on a variety of factors such as the expressiveness of the target language (SQL, CAML, LDAP, …) but also how much you really care. Let me give you an example: do you care about the case sensitivity of string comparison? In other words, even though using C#’s == operator does a case-sensitive string compare for strings, does it mean that something like where p.ProductName == “Chai” also performs a case-sensitive string compare in SQL when using LINQ to SQL?

The thing I want to point out in this post is the fact that different people have different habits, mostly depending on personal background. To illustrate this, consider someone with a Java-background doing a string compare versus someone with a C++-background doing the same. It’s very likely that the former person will go for something of the shape s1.Equals(s2) while the latter person looks for a strcmp equivalent and might find s1.Compare(s2) == 0 a more natural way of thinking. Similarly, native C# and VB speakers will be so used to operator overloading (whether or not they really know this is a case of operator overloading is another point of discussion) and will write s1 == s2 or s1 = s2 respectively. But not only humans have habits, compilers have them too (and it’s far more difficult to change a compiler’s mind). The last two mentioned forms, s1 == s2 and s1 = s2, might be very similar, yet the generated code will be very different since VB uses a runtime library (Microsoft.VisualBasic.dll) that implements operations like string equality compare in such a way to preserve backwards compatibility with pre-.NET versions of the language.

All of this is quite abstract, a sample will clarify things:

using System;
using System.Linq.Expressions;

class S
{
    static void Main()
    {
        Test((s1, s2) => s1 == s2);
        Test((s1, s2) => s1.Equals(s2));
        Test((s1, s2) => String.Equals(s1, s2));
        Test((s1, s2) => String.Compare(s1, s2) == 0);
    }

    static void Test(Expression<Func<string, string, bool>> e)
    {
        Console.WriteLine(e);
        Delegate d = e.Compile();
        Console.WriteLine(d.DynamicInvoke("Bart", "John"));
        Console.WriteLine(d.DynamicInvoke("Bart", "Bart")); 
    }
}

Question is what this will print to the screen. Here is the answer:

image

What you’re seeing here is four different expression trees. Obviously all are LambdaExpression instances, but their Body is fundamentally different. The first one is a BinaryExpression with NodeType set to ExpressionType.Equal while the second and the third are MethodCallExpressions and the last one is a mix of the two (the top node will be a BinaryExpression with the left-hand side being a MethodCallExpression to String.Compare and the right-hand side a ConstantExpression with Value set to 0). And there are even more forms to consider (e.g. what about the last form with the == “arguments” swapped?).

To illustrate that VB has a different opinion about things, let’s do the same in VB 9.0:

Imports System
Imports System.Linq.Expressions

Module T

    Sub Main
        Test(Function(s1, s2) s1 = s2)
        Test(Function(s1, s2) s1.Equals(s2))
        Test(Function(s1, s2) String.Equals(s1, s2))
        Test(Function(s1, s2) String.Compare(s1, s2) = 0)
    End Sub

    Sub Test(e As Expression(Of Func(Of String, String, Boolean)))
        Console.WriteLine(e)
        Dim d = e.Compile()
        Console.WriteLine(d.DynamicInvoke("Bart", "John"))
        Console.WriteLine(d.DynamicInvoke("Bart", "Bart"))
    End Sub

End Module

producing the following result:

image

where the first expression is a MethodCallExpression with three arguments (the third one indicating case-sensitivity for the compare) to a method called CompareString defined in Microsoft.VisualBasic.CompilerServices.Operators. I’ve covered this VB Runtime method extensively in my post on runtime agility, a well-kept secret VB 9.0 feature.

So, how to deal with this flexibility (to use a gentle word)? The answer really is that your parser needs to know about all these possible ways of comparing strings – users can and therefore will use different ways to accomplish the same. Now, if you’re just implementing one provider and there’s only one place where you will encounter such checks in your provider (typically when parsing a Where operator’s predicate), it might be very doable to implement everything in place. But if you need to recognize all of those patterns in a variety of places, either intra- or inter-provider (or both), it might be useful to generalize the mechanism of recognizing those patterns and “normalizing” the different expression trees into one common form. Since expression trees are immutable this would mean using a visitor pattern to create a new, normalized expression tree, or you could just normalize expressions “as you go” while parsing certain parts of the giant query expression tree.

Anyway, here’s a (quick-and-dirty) sample implementation of a normalizer for string equality checks:

static Expression Normalize(Expression e)
{
    Expression left, right;
    left = right = null;

    MethodCallExpression mce;
    BinaryExpression be;

    if ((mce = e as MethodCallExpression) != null)
    {
        if (mce.Method.DeclaringType == typeof(string) && mce.Method.Name == "Equals")
        {
            if (mce.Method.IsStatic)
            {
                left = mce.Arguments[0];
                right = mce.Arguments[1];
            }
            else
            {
                left = mce.Object;
                right = mce.Arguments[0];
            }
        }
    }
    else if ((be = e as BinaryExpression) != null && be.NodeType == ExpressionType.Equal)
    {
        ConstantExpression ce;
        if (   ((mce = be.Left as MethodCallExpression) != null && (ce = be.Right as ConstantExpression) != null)
            || ((mce = be.Right as MethodCallExpression) != null && (ce = be.Left as ConstantExpression) != null))
        {
            if (ce.Value as int? == 0 && mce.Method.DeclaringType == typeof(string) && mce.Method.Name == "Compare")
            {
                left = mce.Arguments[0];
                right = mce.Arguments[1];
            }
        }
    }

    if (left != null && right != null)
    {
        e = Expression.Equal(left, right);
    }

    return e;
}

Notice the VB case isn’t covered here and is left as a trivial exercise for the reader (tip: the “== 0” check emitted by the VB compiler is a BinaryExpression where CompareString can either be left or right…) but more importantly the semantics of string comparison will be weakened by doing this normalization. Why? One thing, as mentioned before, is case sensitivity but there are others as well. What about the behavior of comparing null values (e.g. s1.Equals(s2) versus s1 == s2 where s1 = null)? What about culture-invariant compares versus culture-aware compares? And so on.

Moral of the story: know to what extent you want to preserve semantics (i.e. understand what you’re translating to) before you can even start to think about techniques like normalization.

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Last week, I had the honor to speak at TechEd 2008 South Africa on a variety of topics. In this post I’ll outline all of the resources, including uploads of all my demos, referred to during my presentations. But before I do so, I sincerely want to point out what a great audience I got. Thanks to everyone for attending, asking a lot of both interesting and challenging questions, the kind words, great and honest evaluations and so much more – you were a fabulous audience. Hope to see you all again next year!

DEV 305 – C# 3.0 and LINQ Inside Out

MGT 301 – Next-Generation Manageability – Windows PowerShell and MMC 3.0

DEV 303 – Parallel Extensions to the .NET Framework

DEV 304 – Writing Custom LINQ Providers

Again, thank you very much for attending, have fun and see you around sooner or later!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Collecting a few of my posts for easy quick reference:

If you haven’t read those already, enjoy!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Collecting a few of my posts for easy quick reference:

If you haven’t read those already, enjoy!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

More Posts « Previous page