Lambda Curry

• Posted by Kris Vandermotten on July 25, 2010
• 4 comments

Note: if you’re looking for lamb curry, you came to the wrong place. This post is about C# programming techniques.

Currying a function is a technique named after Haskell Curry, to transform a function with multiple parameters into a series of functions having one parameter each. The technique is important, because it opens the door to an optimization technique called partial evaluation. Let’s look at an example.

Let’s say you need to write a program that sums a two-dimensional function f(x,y) over a two-dimensional range, e.g. –1000 ≤ x ≤ 1000 and –1000 ≤ y ≤ 1000.

Such a two-dimensional function, assuming double parameters and result, can be represented by Func<double, double, double>, and we can sum it using the following method:

        private static double Sum(Func<double, double, double> f)
        {
            double sum = 0;
            for (int x = -1000; x <= 1000; x++)
            {
                for (int y = -1000; y <= 1000; y++)
                {
                    sum += f(x, y);
                }
            }
 
            return sum;
        }

We can apply this to an arbitrary function, for example:

            Func<double, double, double> f = (x, y) => Math.Sin(x) * Math.Sin(y);
 
            double result = Sum(f);

Currying this is now a simple textual transformation. Instead of defining f as Func<double, double, double>, we define it as Func<double, Func<double, double>>.

    using System;
 
    internal static class Curried
    {
        public static void Main()
        {
            Func<double, Func<double, double>> f = x => y => Math.Sin(x) * Math.Sin(y);
 
            double result = Sum(f);
        }
 
        private static double Sum(Func<double, Func<double, double>> f)
        {
            double sum = 0;
            for (int x = -1000; x <= 1000; x++)
            {
                for (int y = -1000; y <= 1000; y++)
                {
                    sum += f(x)(y);
                }
            }
 
            return sum;
        }
    }

Effectively, a function that took two parameters and returned a result is replaced by a function that takes one parameter and returns a function that takes the second parameter and returns the result. It looks a lot simpler than it sounds. Instead of writing f = (x, y) => Math.Sin(x) + Math.Sin(y), we write f = x => y => Math.Sin(x) + Math.Sin(y). And when calling it, instead of writing f(x, y), we write f(x)(y). Simple.

Unfortunately, every call to f(x) now allocates a new Func<double, double> object, and that can become quite expensive. But that can be fixed easily, so here is a smarter solution:

    using System;
 
    internal static class Smarter
    {
        public static void Main()
        {
            Func<double, Func<double, double>> f = x => y => Math.Sin(x) * Math.Sin(y);
 
            double result = Sum(f);
        }
 
        private static double Sum(Func<double, Func<double, double>> f)
        {
            double sum = 0;
            for (int x = -1000; x <= 1000; x++)
            {
                var fx = f(x);
                for (int y = -1000; y <= 1000; y++)
                {
                    sum += fx(y);
                }
            }
 
            return sum;
        }
    }

I ran a little benchmark on this code. The benchmark executes the main function 20 times, and measures the shortest execution time. It also measures the number of generation 0 garbage collections. This is the result:

Naive: 261 msec, 0 collections
Curried: 340 msec, 733 collections
Smarter: 254 msec, 0 collections

As we can see, the curried version was initially slower due to all the memory allocations, but when we fixed that, the smarter version was as fast as the original. In fact is was just a little bit faster, though nothing to get existed about.

However, this is where partial evaluation kicks in. Currently, we are calculating the sinus of x over one million times, not taking advantage of the fact that we could reuse each calculated value a thousand times! So let’s change our definition of f as follows:

            Func<double, Func<double, double>> f = x => { var sinx = Math.Sin(x); return y => sinx * Math.Sin(y); };

Now the benchmark shows a completely different result:

Optimized: 143 msec, 0 collections

We went from 261 milliseconds in the original version to 143 milliseconds in this version, in fact almost dividing execution time by two! That’s because, to be precise, in the original version we had two times 2001 * 1001 = 8,008,002 Math.Sin calls, and in the optimized version we have 1 time 2001 plus 1 time 2001 * 2001 = 4,006,002 Math.Sin calls. That is a division by a factor of 1.999, yielding a total execution time reduction by a factor of 1.825 (there is some overhead of course).

Of course, the technique is very much related to loop invariant code motion in imperative programming. For example, imagine a Sum function hardcoded for Sin(x) + Sin(y). Would you write is like this?

        private static double SumSinSin()
        {
            double sum = 0;
            for (int x = -1000; x <= 1000; x++)
            {
                for (int y = -1000; y <= 1000; y++)
                {
                    sum += Math.Sin(x) * Math.Sin(y);
                }
            }
 
            return sum;
        }

Of course not! At least you would move the calculation of Sin(x) out of the loop over y:

        private static double SumSinSin()
        {
            double sum = 0;
            for (int x = -1000; x <= 1000; x++)
            {
                var sinx = Math.Sin(x);
                for (int y = -1000; y <= 1000; y++)
                {
                    sum += sinx * Math.Sin(y);
                }
            }
 
            return sum;
        }

And that is exactly what we did, except of course that the sum function is parameterized and not hardcoded.

So when would you apply this technique? You would apply it when performance matters, and you have a function that you need to call a lot, that takes more than one parameter, where one parameter varies more than another one (in our example, x remained the same for a long time, while y was different on every call), and part of the function can be evaluated knowing only the value of the parameter that varies the least.

In our example above, we could go even further. For example, we could eliminate the multiplication and even the Sin(y) calculation completely is case Sin(x) is 0 (which would be the case in our example only for x == 0).

            Func<double, Func<double, double>> f = x => 
            { 
                if (x != 0.0)
                {
                    var sinx = Math.Sin(x);
 
                    return y => sinx * Math.Sin(y);
                }
                else
                {
                    return y => 0.0;
                }
            };

That is not worth it in this scenario (because the special case applies to less than 0.05 % of all cases), but in some scenarios runtime algorithm specialization can be very significant.

Static Reflection in .NET, part 2

• Posted by Kris Vandermotten on December 14, 2009
• 72 comments

A few weeks ago, I talked about static reflection and its advantages. You’ll remember that the main advantages, compared to the normal reflection API’s, are the compile time checking of parameters and IntelliSense support.

How does it compare at other levels, performance for example? Before we dive into that question, let me state that performance may or may not be important to you. A program that is fast enough is, well, fast enough. It’s unlikely that a (single) reflection call will have a significant impact on, say, the response time of a graphical user interface, and so performance doesn’t matter. If you’re algorithm requires millions of reflection operations, I’m sure you can rewrite it somehow to reduce that number significantly, and then performance again probably doesn’t matter anymore. That being said, we still want to know, right?

First of all, let’s compare code.

Take this line (using the Example class from the last post):

PropertyInfo pi = typeof(Example).GetProperty("Description");

This line compiles to the following IL (simplified for readability):

ldtoken Example 
call class Type Type::GetTypeFromHandle(valuetype RuntimeTypeHandle) 
ldstr "Description" 
call instance class PropertyInfo Type::GetProperty(string)

Compare that to the following line:

PropertyInfo pi = StaticReflector.Create<Example>().PropertyInfo(e => e.Description);

Which compiles to:

call class IStaticReflector`1<!!0> StaticReflector::Create<class Example>()
ldtoken Example
call class Type Type::GetTypeFromHandle(valuetype RuntimeTypeHandle)
ldstr "e"
call class ParameterExpression Expression::Parameter(class Type, string)
stloc.0 
ldloc.0 
ldtoken instance string Example::get_Description()
call class MethodBase MethodBase::GetMethodFromHandle(valuetype RuntimeMethodHandle)
castclass MethodInfo
call class MemberExpression Expression::Property(class Expression, class MethodInfo)
ldc.i4.1 
newarr ParameterExpression
stloc.1 
ldloc.1 
ldc.i4.0 
ldloc.0 
stelem.ref 
ldloc.1 
call class Expression`1<!!0> Expression::Lambda<class System.Func`2<class Example, string>>(class Expression, class ParameterExpression[])
call class PropertyInfo StaticReflectorExtensions::PropertyInfo<class Example, string>(class IStaticReflector`1<!!0>, class Expression`1<class System.Func`2<!!0, !!1>>)

As you can see, this code doesn’t load the “Description” string, it uses the ldtoken instruction instead. Some bloggers have suggested that this would make it more efficient. Unfortunately, even if the ldtoken instruction is efficient, it is largely offset by the construction of the lambda expression. I ran a little benchmark, in which I compare execution time (in ticks) and memory usage (in generation 0 garbage collection runs) of both approaches, executing each one a million times. This is the result (on my laptop):

Using Reflection       Time:    1089308 Collections:    45
Using StaticReflection Time:   13513777 Collections:   264

As you can see, the Static Reflection approach is about 13.5 times slower than the good old dynamic reflection, and it uses a lot more memory. That should be no surprise either: both cases allocate a PropertyInfo object, but the static case also allocates the expression, which is nothing but food for the garbage collector.

So, one approach seems good at compile time, and the other is good at run time. It seems we’re stuck between a rock and a hard place. But the situation isn’t so bad: we have two options to choose from, each with their pro’s and con’s. What the best one is depends on your requirements, and what you value the most: compile time checking (which may result in productivity and maintainability benefits), or performance.

And who knows, maybe there is a third option, giving the best of both worlds. But that’s for next time.

String.Trim() fixed in .NET 4.0

• Posted by Kris Vandermotten on October 27, 2009
• 31 comments

A long time ago, I wrote a blog post about the problems with String.Trim(). I’m happy to see that all three issues have been addressed in the .NET Framework 4.0.

To start with, Trim() will now be consistent with Char.IsWhiteSpace(). Theoretically, this is a breaking change, but I don’t expect many programs to have a problem with this change. Note that the change is very well documented in the online help.

Secondly, the code of Trim() has been cleaned up considerably. A string that consists entirely of whitespace is no longer scanned twice. I haven’t done any benchmarks, but I expect the performance to be at least as good as for the same function in .NET 2.0 – 3.5.

Last but not least, the frequent abuse of the Trim() function to simply validate strings will greatly decrease with the introduction of the static IsNullOrWhitespace(string value) function, which is much faster than calling Trim().

It’s a small detail, compared to all the other goodies .NET 4.0 brings, but a good addition to the toolbox nonetheless.

Static Reflection in .NET

• Posted by Kris Vandermotten on September 25, 2009
• 137 comments

LINQ expressions have proven to be extremely versatile, popping up in all sorts of areas. “Static Reflection” seem to be the latest hype. But what is static reflection anyway, and why is it good or why is it bad?

Reflection is used to obtain information about the code you are executing, and to use that information to interact with the code dynamically. Sometimes reflection is used to interact dynamically with code that is statically known by a program already. For example, data binding heavily relies on reflection to dynamically read and write properties. The calling program knows about those properties statically, but the data binding libraries do not. In data binding, object properties are often identified by their name, expressed as a string. That string is then used by the libraries to construct a PropertyInfo object.

Time for an example. Given this class:

public class Example
{
    public string Description { get; set; }
}

You can obtain a PropertyInfo object describing the Description property as follows:

PropertyInfo pi = typeof(Example).GetProperty("Description");

We may have an issue here. If I make a typing mistake in the GetProperty call, I don’t get a compiler error. At runtime, the call will return null, probably leading to a NullReferenceException down the road. And of course, Visual Studio Intellisense will not help me to type it right. Also, if I rename the property, for example to “Summary”, the GetProperty call will be broken, without a compile-time error. Static Reflection is one technique to avoid these issues.

Using LINQ expressions, we could create an API that allows us to do something like the following:

PropertyInfo pi = StaticReflector.GetProperty(Example e => e.Description);

The downside of this approach is that it doesn’t work with anonymous types. So I propose a different mechanism. What we need is something that statically gives us access to a type. Any generic interface will do. I propose the following:

public interface IStaticReflector<T>
{
}

Given this interface, we can define a series of extension methods, for example:

public static class StaticReflectorExtensions
{
    public static PropertyInfo PropertyInfo<T, U>(this IStaticReflector<T> obj, Expression<Func<T, U>> selector)
    {
        var body = selector.Body as MemberExpression;
        return body.Member as PropertyInfo;
    }
}

Notice how the obj parameter is not really used in the PropertyInfo method. It does serve a purpose however: it allows us to use type inference on the type T, and I get full Intellisense. For example:

IStaticReflector<Example> reflector = null;
PropertyInfo pi = reflector.PropertyInfo(e => e.Description);

Granted, initializing a variable to null and then calling a method on it is a bit weird. We need a more elegant way to create these things:

public static class StaticReflector
{
    public static IStaticReflector<T> Create<T>()
    {
        return null;
    }
}

Now we can write:

PropertyInfo pi = StaticReflector.Create<Example>().PropertyInfo(e => e.Description);

This still doesn’t work on anonymous types though. For those, we could use the following:

public static class ObjectExtensions
{
    public static IStaticReflector<T> GetReflector<T>(this T obj)
    {
        return null;
    }
}

Now we can write things such as:

var anonymous = new { Description = "Example" };

PropertyInfo pi = anonymous.GetReflector().PropertyInfo(e => e.Description);

I do prefer the StaticReflector.Create<T>() method is case the type name is known though.

Are we done? Not really. Let’s go back to dynamic reflection using string names. Lot’s of things could go wrong there, and we don’t get any warnings. The situation has not gone worse, but still lot’s of things can go wrong. So the PropertyInfo method needs some parameter validation. Also, properties certainly aren’t the only thing we can reflect upon. What about fields, methods and constructors? Here’s a full implementation:

using System;
using System.Linq.Expressions;
using System.Reflection;

public static class StaticReflectorExtensions
{
    public static PropertyInfo PropertyInfo<T, U>(this IStaticReflector<T> obj, Expression<Func<T, U>> selector)
    {
        if (selector == null)
        {
            throw new ArgumentNullException(Strings.Selector);
        }

        PropertyInfo pi = obj.MemberInfo(selector) as PropertyInfo;

        if (pi == null)
        {
            throw new ArgumentException(Strings.InvalidPropertySelector, Strings.Selector);
        }

        return pi;
    }

    public static FieldInfo FieldInfo<T, U>(this IStaticReflector<T> obj, Expression<Func<T, U>> selector)
    {
        if (selector == null)
        {
            throw new ArgumentNullException(Strings.Selector);
        }

        FieldInfo fi = obj.MemberInfo(selector) as FieldInfo;

        if (fi == null)
        {
            throw new ArgumentException(Strings.InvalidFieldSelector, Strings.Selector);
        }

        return fi;
    }

    public static MemberInfo MemberInfo<T, U>(this IStaticReflector<T> obj, Expression<Func<T, U>> selector)
    {
        if (selector == null)
        {
            throw new ArgumentNullException(Strings.Selector);
        }

        var body = selector.Body as MemberExpression;

        if (body == null)
        {
            throw new ArgumentException(Strings.InvalidMemberSelector, Strings.Selector);
        }

        if (body.Expression.NodeType != ExpressionType.Parameter)
        {
            throw new ArgumentException(Strings.InvalidMemberSelector, Strings.Selector);
        }

        return body.Member;
    }

    public static MethodInfo MethodInfo<T, U>(this IStaticReflector<T> obj, Expression<Func<T, U>> selector)
    {
        if (selector == null)
        {
            throw new ArgumentNullException(Strings.Selector);
        }

        var body = selector.Body as MethodCallExpression;

        if (body == null)
        {
            throw new ArgumentException(Strings.InvalidMethodSelector, Strings.Selector);
        }

        // instance methods must be called on the parameter
        if (body.Object != null && body.Object.NodeType != ExpressionType.Parameter)
        {
            throw new ArgumentException(Strings.InvalidMethodSelector, Strings.Selector);
        }

        // static methods must be defined in the type of the parameter or a base type
        if (body.Object == null && !body.Method.DeclaringType.IsAssignableFrom(typeof(T)))
        {
            throw new ArgumentException(Strings.InvalidMethodSelector, Strings.Selector);
        }

        return body.Method;
    }

    public static MethodInfo MethodInfo<T>(this IStaticReflector<T> obj, Expression<Action<T>> selector)
    {
        if (selector == null)
        {
            throw new ArgumentNullException(Strings.Selector);
        }

        var body = selector.Body as MethodCallExpression;

        if (body == null)
        {
            throw new ArgumentException(Strings.InvalidMethodSelector, Strings.Selector);
        }

        // instance methods must be called on the parameter
        if (body.Object != null && body.Object.NodeType != ExpressionType.Parameter)
        {
            throw new ArgumentException(Strings.InvalidMethodSelector, Strings.Selector);
        }

        // static methods must be defined in the type of the parameter or a base type
        if (body.Object == null && !body.Method.DeclaringType.IsAssignableFrom(typeof(T)))
        {
            throw new ArgumentException(Strings.InvalidMethodSelector, Strings.Selector);
        }

        return body.Method;
    }

    public static ConstructorInfo ConstructorInfo<T>(this IStaticReflector<T> obj, Expression<Func<T>> selector)
    {
        if (selector == null)
        {
            throw new ArgumentNullException(Strings.Selector);
        }

        var body = selector.Body as NewExpression;

        if (body == null)
        {
            throw new ArgumentException(Strings.InvalidConstructorSelector, Strings.Selector);
        }

        return body.Constructor;
    }

    private static class Strings
    {
        internal const string InvalidFieldSelector = "Invalid field selector";
        internal const string InvalidPropertySelector = "Invalid property selector";
        internal const string InvalidMemberSelector = "Invalid member selector";
        internal const string InvalidMethodSelector = "Invalid method selector";
        internal const string InvalidConstructorSelector = "Invalid constructor selector";
        internal const string Selector = "selector";
    }
}

Next time, we’ll talk about the disadvantages of this approach, and we’ll look at an alternative.

Paint.NET Effects updated

• Posted by Kris Vandermotten on April 6, 2009
• 156 comments

StyleCop for C# released

• Posted by Kris Vandermotten on May 21, 2008
• 70 comments

.NET 3.5 SP1 Beta available

• Posted by Kris Vandermotten on April 23, 2008
• 136 comments

Having fun with Linq to Nullable types

• Posted by Kris Vandermotten on March 31, 2008
• 271 comments

static double? Add(double? x, double? y) 

{

     return x + y; 

}

static double? Add(double? x, double? y) 

{

    return x.HasValue && y.HasValue ? new double?(x.GetValueOrDefault() + y.GetValueOrDefault()) : null; 

}

static double? Abs(double? x) 

{

     return Math.Abs(x); // won't compile 

}

static double? Abs(double? x) 

{

     return from d in x select Math.Abs(d); 

}

public static T? Select<T>(this T? x, Func<T, T> selector)

     where T : struct 

{

     return x.HasValue ? new T?(selector(x.Value)) : null; 

}

public static T? Where<T>(this T? source, Func<T, bool> predicate)

     where T : struct 

{

     return source.HasValue && predicate(source.Value) ? source : null; 

}

static double? Asin(double? x) 

{

     return from d in x where d >= -1 && d <= 1 select Math.Asin(d); 

}

public static V? SelectMany<T, U, V>(this T? source, Func<T, U?> k, Func<T, U, V> resultSelector)

     where T : struct

     where U : struct

     where V : struct 

{

     if (k == null)

     {

         throw new ArgumentNullException("k");

     }

     if (resultSelector == null)

     {

         throw new ArgumentNullException("resultSelector");

     }

     return source.HasValue && k(source.Value).HasValue ?

          new V?(resultSelector(source.Value, k(source.Value).Value)) : null; 

}

static double? SinCos(double? x, double? y) 

{

     return from xd in x

            from yd in y

            select Math.Sin(xd) * Math.Cos(yd); 

}

AssemblyInfo updated

• Posted by Kris Vandermotten on March 31, 2008
• 200 comments

PaintDotNetEffects updated for Paint.NET 3.30

• Posted by Kris Vandermotten on February 22, 2008
• 168 comments