Lambda Expressions and Higher-Order Functions

[This article has a continuation here]

First, I need to ask you not to be scare of the title I've chosen. Less than two months ago, I barely knew what the first name was and have never heard of the latter.

As you might know, the brand-new C# 3.0 has support to lambda expressions. You can imagine it as a less wordy way to describe anonymous delegates. A major difference between them is that a lambda expression doesn't necessarily needs to be compiled. In fact, it's just a representation of a function. In addition to being compiled, they can be serialized (if you want to pass it on), analyzed and even dynamically created at run-time. I'll be using the last two here.

Now, let me introduce the computational (as well as mathematical) concept of a higher-order funcion (aka operators in math). It's nothing more than a function that receives another function as a parameter and/or returns a function.

Why would a function receive another function as a parameter? If you can't imagine a good answer or are just not convinced there's one, I suggest that you read this very didactic article (this is also good). Anyway, you can implement such functions in c# 2.0 without problems. What I want to examine are functions that returns another functions. If you are not using c# 3.0 (or a functional language), you might find some difficulties. Basically, you would be limited to returning one of a set of pre-declared functions. You could try using closures or dynamic code generation to add some versatility, but it probably would be rather cumbersome.

You may be asking why would anyone need such higher-order function. I will let this question open and focus on how to implement it. I was searching for a good example and can't imagine a better one than the differentiation, i.e., the mathematical process of obtaining the derivative of a function.

So, I'll build a functional that receives a f(x) and return a f'(x). The declaration of this in c# would be like that:

static public Expression<Func<double,double>> Differentiate(this Expression<Func<double,double>> f)
{
//I will find the derivative of f with respect to the variable x (it's the 1st and sole parameter)
ParameterExpression x = f.Parameters[0];

//Diff is the function that actually does the differentiation
Expression derivative = Diff(f.Body, x);

//Build a new lambda expression with the derivative expression body
return Expression.Lambda<Func<double,double>>(derivative, f.Parameters);
}

*Func<double,double> is a delegate type for functions that receives a single double parameter and returns a double. Expression<Func<double,double>> is the type of a lambda expression that represents a Func<double,double> function.

As you can see I used a Diff function that actually calculates the derivative. How does it work? It needs to analyze the original expression and create a new expression that represents its derivative. Luckily enough, this calculation can be done recursively using a set a rules. Let's start with the sum rule: namely, derivatives of sums are equal to the sum of derivatives. Coding that in c# 3.0 is easier than you one might thought. Look:

static Expression Diff(Expression exp, ParameterExpression dx)
{
switch (exp.NodeType) {
case ExpressionType.Add: {
BinaryExpression f = (BinaryExpression)exp;
//Sum rule: [g(x) + h(x)]' == g'(x) + h'(x).
return Expression.Add( //Create an add expression
   Diff(f.Left, dx),  //g'(x) +
   Diff(f.Right, dx)  //h'(x)
);
}
/* other cases omitted ... */
}
}

In similar ways, we can implement the other recursive rules (such as the product rule, the quotient rule, the power rule, etc). However, any recursion need a stop condition. We'll have two stop conditions: for constants, which derivative is zero; and for the variable x, which derivative is one. The code looks like this:

case ExpressionType.Parameter: {
//be aware that f(x) = y is a constant with respect to x
return (exp == dx) ? Expression.Constant(1d) : Expression.Constant(0d);
}
case ExpressionType.Constant: {
return Expression.Constant(0d);
}

There's also the chain rule, that is quite trickier to implement. I did it with very little code, though. As you're not faint of heart, take a look at my full source.

And that's all for the day, folks. Please, comment.