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.