Andy's observations as he continues to attempt to know all that is .NET...

Wednesday, April 02, 2008

Generic Sum

Its been a while since I blogged about trying to re-implement C++ STL using .NET generics.  Last night I was skimming through an excellent book on Linq "Linq in Action" published by Manning, and whilst reading the section on how Expression trees work in C# v3.0 it occured to me that I could potentially use them for creating a generic Sum method.

First a quick look at C# v3.0 expressions,  the lambda expression here is not being turned into a method as would be the norm for anonymous methods but it is turned into an AST.  Abstract Syntax Tree used to describe the function of the lambda expression.

Expression<Func<int, int, int>> addExpr = (lhs, rhs) => lhs + rhs;

Func<int, int, int> addMethod = addExpr.Compile();

Console.WriteLine(addMethod(5, 5));

In this case that produces a root node to the expression tree that is a Lambda node, that then contains a single Add node, which is a binary operator thus containing two further nodes for the left hand side and right hand side of the add operation.

Reflector spits out the following code

private static void Main(string[] args)
{
ParameterExpression CS$0$0000;
ParameterExpression CS$0$0001;
Console.WriteLine(
      Expression.Lambda<Func<int, int, int>>(
        Expression.Add(
           CS$0$0000 = Expression.Parameter(typeof(int), "lhs"), 
           CS$0$0001 = Expression.Parameter(typeof(int), "rhs")),
       new ParameterExpression[] { CS$0$0000, CS$0$0001 }
     ).Compile()(5, 5));
}

This got me thinking could I build an expression using generic arguments, the code as spit out by reflector certainly looks like its possible.  My first crack was as follows






public static T Sum<T>(T[] vals)
{

     Expression<Func<T, T, T>> addExpr = (lhs, rhs) => lhs + rhs;

      T total = default(T);

         Func<T, T, T> addMethod = addExpr.Compile()


          foreach (T val in vals)
         {
             total = addMethod(total, val);
         }


         return total;
}


Unfortunately this failed, with the typical "Operator + cannot be applied to operands of type T and T" error that has been the reason why you can't easily write generic Sum in .NET.  However not put off I built the expression tree by hand


 






private static Func<T, T, T> CreateAdd<T>()
        {
            ParameterExpression lhs = Expression.Parameter(typeof(T), "lhs");
            ParameterExpression rhs = Expression.Parameter(typeof(T), "rhs");

            Expression<Func<T, T, T>> addExpr = Expression<Func<T, T, T>>.


            Lambda<Func<T, T, T>>(
                    Expression.Add(lhs, rhs),


                   new ParameterExpression[] { lhs, rhs });



             Func<T, T, T> addMethod = addExpr.Compile();


            return addMethod;
        }


The method above now returns a delegate instance that adds two values both of type T, and returns a value as type T.


Generic Sum can now be rewritten as follows






public static T Sum<T>(T[] vals)
{

      T total = default(T);

      Func<T, T, T> addMethod = CreateAdd<T>();

     foreach (T val in vals)
     {
           total = addMethod(total, val);
      }

      return total;
}


 


This now works for arrays for ints, doubles etc.  It will not work for types not supported by the Add Expression, so only works for simple numeric types, but it is certainly a lot simpler than the approach I took a year or so ago although not as flexible.  Its a shame that the C# compiler expression tree builder won't accept generic arguments since it is possible to represent a expression tree this way, as this would result in a lot easier way to generate such code.

2 comments:

Remigiusz said...

I would like to suggest a more generic solution. Probably with better performance.

int[] list = new int[100];
Enumerable.Aggregate(list, delegate(int left, int right) { return left + right; });

Andy Clymer said...

Remigiusz ,

The purpose of the post wasn't to show an optimised implementation of Sum, but to show that it was possible to use numeric operations inside a generic type/method.

If performance is the goal, then you can't beat

your own for loop , and own body to add the items.

Andy

About Me

My photo
Im a freelance consultant for .NET based technology. My last real job, was at Cisco System were I was a lead architect for Cisco's identity solutions. I arrived at Cisco via aquisition and prior to that worked in small startups. The startup culture is what appeals to me, and thats why I finally left Cisco after seven years.....I now filll my time through a combination of consultancy and teaching for Developmentor...and working on insane startups that nobody with an ounce of sense would look twice at...