Sean McCarthy's Blog

C#: A Method for Tail Call Recursion

Posted 10/22/2009
Filed under: C#, Functional Programming | Tags: C#, codeproject, Functional Programming

I’ve been reading on F# a bit, and came across it’s ability to do tail call recursion. Tail recursion as defined by Wikipedia:

In computer science, tail recursion (or tail-end recursion) is a special case of recursion in which the last operation of the function, the tail call, is a recursive call. Such recursions can be easily transformed to iterations. Replacing recursion with iteration, manually or automatically, can drastically decrease the amount of stack space used and improve efficiency. This technique is commonly used with functional programming languages, where the declarative approach and explicit handling of state promote the use of recursive functions that would otherwise rapidly fill the call stack.

So, I decided to see if I could implement this in C#, and after a little bit of monkeying around I was able to get something working.

First off, I needed two helper classes, the first of which is the Ref<T> class. It makes it possible to keep track of a reference to an object across closures. There is also an implicit conversion back to the type it is referencing for convenience.

publicclassRef<T>
 {
public T Value { get; set; }
     public static implicit operator T(Ref<T> obj)
     {
         return obj.Value;
     }
 } 

Next was the LazyRef<T>, which is the same as Ref<T> but won’t actually compute the value until it is needed.

publicclassLazyRef<T>
 {
public T Value { get { return Factory(); } }
publicFunc<T> Factory { get; set; }
     public LazyRef()
     {
     }
     public LazyRef(Func<T> factory)
     {
         this.Factory = factory;
     }
     public static implicit operator T(LazyRef<T> obj)
     {
         return obj.Value;
     }
     public static implicit operator LazyRef<T>(T obj)
     {
         return new LazyRef<T>(() => obj);
     }
 } 

Alright, now all that remains is the method that does all of the magic, I’ll present it piecewise then all together at the end. First, let’s look at the method’s signature,

public static Func<T, R> ToTailCall<T, R>(
     this Func<Func<T, LazyRef<R>>, T, LazyRef<R>> target) 

It will return a delegate that represents the tail call optimized method, taking a T as the only parameter and returning an R. The only argument is the target method/delegate to be transformed. Note that the target takes a delegate as it’s first argument, this will be the recurse function that the method will call instead of itself when it wishes to proceed. It then takes a T, and returns a LazyRef to an R.

Now for the first part of the method, just some Ref and LazyRef variables, I’ll explain these as they are used.

var calledRef = new Ref<bool>();
 var paramRef = new Ref<T>();
 var currResult = new Ref<LazyRef<R>>();
 var lazyResult = new LazyRef<R>(
     () => currResult.Value.Value); 

Next up is setRef, it’s the function that will be the recurse function that is passed in as the first argument when target is called.

Func<T, LazyRef<R>> setRef = t => {
     calledRef.Value = true;
     paramRef.Value = t;
     return lazyResult;
 }; 

setRef first flips the calledRef flag, so that we know that target wants to do one more recursion, then we store off the value that target wanted to pass on, and we return the lazyResult. lazyResult will return currResult’s value when asked what it’s value is.

Next, is the actual function that is returned,

return t => {
     paramRef.Value = t;
     do
     {
         calledRef.Value = false;
         currResult.Value = target(setRef, paramRef.Value);
     } while (calledRef.Value);
     return lazyResult.Value;
 }; 

First off, it sets up the current parameter value as t, since it needs to be set for the first iteration. Then it enters the loop and flips the calledRef flag to false, so if target doesn’t call the recurse function the loop will not continue. After that target is called, passing in setRef as the recurse function, and the current parameter value. It’s return is stored as the currentResult which will be lazyResult until target doesn’t call the recurse function, at which point it will return something else. This goes on until target doesn’t call the recurse function and the loop exits. After that we return the value or lazyResult, which is the value or currentResult. Ok, so here is everything all together:

publicstaticclassRecursion
 {
publicstaticFunc<T, R> ToTailCall<T, R>(
thisFunc<Func<T, LazyRef<R>>, T, LazyRef<R>> target)
     {
var calledRef = newRef<bool>();
var paramRef = newRef<T>();
var currResult = newRef<LazyRef<R>>();
var lazyResult = newLazyRef<R>(
             () => currResult.Value.Value);
         Func<T, LazyRef<R>> setRef = t => {
             calledRef.Value = true;
             paramRef.Value = t;
             return lazyResult;
         };
         return t => {
             paramRef.Value = t;
             do
             {
                 calledRef.Value = false;
                 currResult.Value = target(setRef, paramRef.Value);
             } while (calledRef.Value);
             return lazyResult.Value;
         };
     }
 } 

All of the refs end up in closures in either setRef or the return value, so the values they reference can be shared and changed. Having the current result be lazy in itself makes the whole thing possible. If we didn’t have LazyRef target would be expecting a computed value to be returned from recurse which would require actual recursion.

Time for a quick example, this will run until the x overflows:

staticvoid Main(string[] args)
 {
var tailFoo = Recursion.ToTailCall<int, int>((recurse, x) => {
try
         {
Console.WriteLine(x);
             return recurse(x + 1);
         }
         catch (OverflowException)
         {
             return x;
         }
     });
     Console.WriteLine(“Done, {0} was the result.”, tailFoo(0));
     Console.ReadLine();            
 } 

Feel free to post questions and comments.

C# 4.0: Exposer, an evil DynamicObject

Posted 10/08/2009
Filed under: C#, dynamic, Evil | Tags: C#, codeproject, dynamic

Leave a Comment

This class makes every field, property, or method on the wrapped object visible when using it as a dynamic. This version is not thread safe, for the sake of brevity I removed all of the locks. To use, you only need to add this to your project, then call .Expose() on an instance of some object, then assign that to a dynamic variable, like so:

dynamic x = someInstance.Expose();

You may then access any field, property, or method regardless of it’s visibility level. Feel free to comment with questions if anything needs explanation ;).

Code Snippet

using System;
using System.Collections.Generic;
using System.Dynamic;
using System.Linq;
using System.Linq.Expressions;
using System.Reflection;
using System.Text;
 
namespace Evil
{
    public interface IConvertTo<T>
    {
        T Convert();
    }
 
    public interface IObjectWithType
    {
        Type Type { get; set; }
    }
 
    public class Exposer<T> : DynamicObject, IObjectWithType, IConvertTo<T>
    {
        public T Object { get; set; }
        public Type Type { get; set; }
 
        static Dictionary<string, Func<T, object[], object>> _methods = new Dictionary<string, Func<T, object[], object>>();
        static Dictionary<string, Func<T, object>> _getters = new Dictionary<string, Func<T, object>>();
        static Dictionary<string, Action<T, object>> _setters = new Dictionary<string, Action<T, object>>();
 
        static MethodInfo _doConvert = typeof(Exposer<T>).GetMethod(“DoConvert”, BindingFlags.NonPublic | BindingFlags.Static);
 
        public Exposer(T obj)
        {
            this.Object = obj;
            this.Type = obj.GetType();
        }
 
        public override bool TryGetMember(GetMemberBinder binder, out object result)
        {
            var key = binder.Name;
            Func<T, object> getter = null;
 
            if (_getters.ContainsKey(key))
            {
                getter = _getters[key];
            }
            else
            {
                IEnumerable<MemberInfo> members = this.Type.GetMembers(
                    BindingFlags.Instance | BindingFlags.Public | BindingFlags.NonPublic | BindingFlags.GetProperty | BindingFlags.GetField);
 
                members = from mem in members
                          where mem.Name == key
                          select mem;
 
                var member = members.FirstOrDefault();
 
                if (member != null)
                {
                    getter = BuildGetter(member);
                    _getters.Add(key, getter);
                }
            }
 
            if (getter != null)
            {
                result = Wrap(getter(this.Object));
                return true;
            }
            else
                return base.TryGetMember(binder, out result);
        }
 
        public override bool TrySetMember(SetMemberBinder binder, object value)
        {
            var key = binder.Name;
            Action<T, object> setter = null;
 
            if (_setters.ContainsKey(key))
            {
                setter = _setters[key];
            }
            else
            {
                IEnumerable<MemberInfo> members = this.Type.GetMembers(
                    BindingFlags.Instance | BindingFlags.Public | BindingFlags.NonPublic | BindingFlags.SetProperty | BindingFlags.SetField);
 
                members = from mem in members
                          where mem.Name == key
                          select mem;
 
                var member = members.FirstOrDefault();
 
                if (member != null)
                {
                    setter = BuildSetter(member);
                    _setters.Add(key, setter);
                }
            }
 
            if (setter != null)
            {
                setter(this.Object, value);
                return true;
            }
            else
                return base.TrySetMember(binder, value);
        }
 
        public override bool TryInvokeMember(InvokeMemberBinder binder, object[] args, out object result)
        {
            Func<T, object[], object> func = null;
 
            var key = MakeKey(binder, args);
 
            if (_methods.ContainsKey(key))
                func = _methods[key];
            else
            {
                var argTypes = args.Select(arg => arg is IObjectWithType ? (arg as IObjectWithType).Type : arg.GetType()).ToArray();
                IEnumerable<MethodInfo> methods = this.Type.GetMethods(BindingFlags.Public | BindingFlags.NonPublic | BindingFlags.Instance);
 
                methods = from method in methods
                          where method.Name == binder.Name && ArgsMatch(method, argTypes)
                          select method;
 
                var info = methods.FirstOrDefault();
 
                if (info != null)
                {
                    var paramTypes = info.GetParameters().Select(p => p.ParameterType).ToArray();
 
                    var target = Expression.Parameter(this.Type, “obj”);
                    var param = Expression.Parameter(typeof(object[]), “args”);
                    var call = Expression.Call(target, info,
                        paramTypes.Select((p, i) =>
                            BuildConvertExpression(Expression.ArrayAccess(param, Expression.Constant(i)), p)));
 
                    func = Expression.Lambda<Func<T, object[], object>>(
                        Expression.Convert(call, typeof(object)), target, param).Compile();
 
 
                }
 
                _methods.Add(key, func);
            }
 
            if (func != null)
            {
                var res = func(this.Object, args);
 
                result = Wrap(res);
 
                return true;
            }
            else
                return base.TryInvokeMember(binder, args, out result);
        }
 
        public override bool TryConvert(ConvertBinder binder, out object result)
        {
            if (binder.Type.IsAssignableFrom(this.Type))
            {
                result = this.Object;
                return true;
            }
            else
                return base.TryConvert(binder, out result);
        }
 
 
 
        #region Builders
        #region Getter
        private Func<T, object> BuildGetter(MemberInfo member)
        {
            switch (member.MemberType)
            {
                case MemberTypes.Field:
                    return BuildFieldGetter(member as FieldInfo);
                case MemberTypes.Property:
                    return BuildPropertyGetter(member as PropertyInfo);
                default:
                    //Returning null effectively marks this as not supported, since the getter will be null as binding exception will be thrown
                    return null;
            }
        }
 
        private Func<T, object> BuildFieldGetter(FieldInfo fieldInfo)
        {
            var param = Expression.Parameter(this.Type, “obj”);
 
            var lambda = Expression.Lambda<Func<T, object>>(
                Expression.Field(param, fieldInfo),
                param);
 
            return lambda.Compile();
        }
 
        private Func<T, object> BuildPropertyGetter(PropertyInfo propertyInfo)
        {
            var param = Expression.Parameter(this.Type, “obj”);
 
            var lambda = Expression.Lambda<Func<T, object>>(
                Expression.Property(param, propertyInfo),
                param);
 
            return lambda.Compile();
        }
        #endregion
        #region Setter
        private Action<T, object> BuildSetter(MemberInfo member)
        {
            switch (member.MemberType)
            {
                case MemberTypes.Field:
                    return BuildFieldSetter(member as FieldInfo);
                case MemberTypes.Property:
                    return BuildPropertySetter(member as PropertyInfo);
                default:
                    //Returning null effectively marks this as not supported, since the setter will be null as binding exception will be thrown
                    return null;
            }
        }
 
        private Action<T, object> BuildFieldSetter(FieldInfo fieldInfo)
        {
            var param = Expression.Parameter(this.Type, “obj”);
            var value = Expression.Parameter(typeof(object), “val”);
 
            var lambda = Expression.Lambda<Action<T, object>>(
                Expression.Assign(
                    Expression.Field(param, fieldInfo),
                    Expression.Convert(value, fieldInfo.FieldType)),
                param, value);
 
            return lambda.Compile();
        }
 
        private Action<T, object> BuildPropertySetter(PropertyInfo propertyInfo)
        {
            var param = Expression.Parameter(this.Type, “obj”);
            var value = Expression.Parameter(typeof(object), “val”);
 
            var lambda = Expression.Lambda<Action<T, object>>(
                Expression.Assign(
                    Expression.Property(param, propertyInfo),
                    Expression.Convert(value, propertyInfo.PropertyType)),
                param, value);
 
            return lambda.Compile();
        }
        #endregion
        #region Convert
        public Expression BuildConvertExpression(Expression target, Type type)
        {
            if (type == typeof(object))
                return target;
 
            return Expression.Call(_doConvert.MakeGenericMethod(type), target);
        }
 
        static R DoConvert<R>(object i)
        {
            if (i is IConvertTo<R>)
            {
                return (i as IConvertTo<R>).Convert();
            }
            else
            {
                return (R)i;
            }
        }
        #endregion
        #endregion
 
        #region Helpers
        private static object Wrap(object res)
        {
            if (res == null)
                return null;
 
            var type = res.GetType();
 
            if (type.IsPrimitive)
                return res;
 
            var expType = typeof(Exposer<>).MakeGenericType(type);
 
            return Activator.CreateInstance(expType, res);
        }
 
        private static string MakeKey(InvokeMemberBinder binder, object[] args)
        {
            var ret = new StringBuilder();
            ret.Append(binder.Name);
 
            foreach (var arg in args)
                ret.Append(arg.GetType().Name);
 
            return ret.ToString();
        }
 
        private static bool ArgsMatch(MethodInfo info, Type[] argTypes)
        {
            return info.GetParameters()
                .Select((p, i) => p.ParameterType.IsAssignableFrom(argTypes[i]))
                .All(b => b);
        }
        #endregion
 
        #region IConvertTo<T> Members
 
        public T Convert()
        {
            return this.Object;
        }
 
        #endregion
    }
 
    public static class Extensions
    {
        public static Exposer<T> Expose<T>(this T target)
        {
            return new Exposer<T>(target);
        }
    }
}

C# 4.0: dynamic’s compiler tricks

Posted 05/20/2009
Filed under: C#, dynamic | Tags: C#, codeproject, DLR, dynamic

Comments (3)

So, I was curious today, I had some code that used dynamic and was wondering what the heck the compiler was doing on the back end. So, I wrote up a very small test program, and tore into it using Reflector. The version of Reflector I used still only decompiles to C# 3, so it happily displayed all of the inner workings to me without trying to hide any of it. Here is my test program:

static void Main(string[] args)
{
    dynamic foo = "bar";
    int meep = foo.Length;
}

Nice and simple, it shouldn’t look too bad… Well, the compiler generates a static container class that it uses to keep track of some things, and it names everything using names that can’t possibly collide with the programmer’s code. So, instead of showing you code that could make your eyes bleed, I took the liberty of renaming everything and inserting new lines to help readability, the result was:

static class CallSiteContainer
{
    public static CallSite<Func<CallSite, object, int>> convertSite { get; set; }
    public static CallSite<Func<CallSite, object, object>> getLengthSite { get; set; }
}

private static void Main(string[] args)
{
    object foo = "bar";

    if (CallSiteContainer.convertSite == null)
        CallSiteContainer.convertSite = CallSite<Func<CallSite, object, int>>
            .Create(new CSharpConvertBinder(typeof(int), CSharpConversionKind.ImplicitConversion, false));

    if (CallSiteContainer.getLengthSite == null)
        CallSiteContainer.getLengthSite = CallSite<Func<CallSite, object, object>>
            .Create(new CSharpGetMemberBinder("Length", typeof(Program),
                new CSharpArgumentInfo[] {
                    new CSharpArgumentInfo(CSharpArgumentInfoFlags.None, null)
                }));

    int meep = CallSiteContainer.convertSite.Target.Invoke(
        CallSiteContainer.convertSite,
        CallSiteContainer.getLengthSite.Target.Invoke(
            CallSiteContainer.getLengthSite, foo));
}

So, the first thing to notice is that the compiler is generating a static inner container class that holds the call sites for the operation so that it doesn’t have to keep creating them over and over. A call site is a point where we interact with a dynamic object, we have two here, the get on .Length and the conversion of the result of that get to an integer. Also notice that foo is actually just an object when things are all said and done, the compiler just wraps all interactions with it.

The generic parameter on the CallSite class ends up determining the signature of the call site’s Invoke method. Since the CallSiteContainer.convertSite ends up being the equivalent of the folling lambda, it takes Func<CallSite, object, int> to say that it takes a CallSite, and the object to convert as parameters, then returns an integer.

Func<object, int> convertSite = obj => (int)obj;

It just takes whatever object and tries to convert it to an int. The other call site is a bit trickier, because you cannot express it as a lambda at compile time, but you could generate one at runtime, look here for details on that. What we do know is that the CallSiteContainer.getLengthSite fetches the value of the Length property or field off of whatever object it is handed. It’s not yet clear to me why the CSharpGetMemberBinder takes the Program type and that CSharpArgumentInfo array, but it probably has something to do with how the DLR caches the code it generates. This whole thing is powered by the DLR, which does all the code generation and caching transparently on the back end. So be thankful for IronPython being around to kick all of this stuff off ;).

When we want to actually perform our operation, getting the Length of foo, and assigning it to meep, it just Invokes both of the call sites, passing the output of the getLengthSite to the convertSite, then taking the result of that and giving it to meep. I don’t know why each call site is passed itself as the first parameter, but after that comes what would be passed into the lambda equivalent of each call site. When the call site is Invoked, it is passed in so it can be updated to handle new cases that it hasn’t seen before, then all of the arguments that would have been passed into the lambda equivalent follow.

Well, that’s about it, all of this generated code isn’t too complex, it’s just pretty wordy. Looking at this and DynamicObject, it occurs to me that implementing Ruby style Mixins, methodMissing, and send shouldn’t be too hard. If you feel like I left anything out, please point it out in the comments.

EDIT: Incorporated information that Curt provided in the comments.

C# 4.0: DXLinq, a DynamicObject example

Posted 05/19/2009
Filed under: C#, dynamic | Tags: C#, codeproject, dynamic

Comments (5)

System.Xml.Linq is a great library, it lets us very easily manipulate XML, in very close fashion to how we would interact with other data sources. My only issue is that it tends to seem a little redundant, given this XML:

<A>
  <B X="1"/>
  <B X="2"/>
</A>

We would do the following to get the value of both the X attributes:

var root = XElement.Load("Sample.xml");

foreach (var b in root.Elements("B"))
    Console.WriteLine(b.Attribute("X").Value);

That’s not exactly the cleanest code ever, so what if we could do this instead:

var root = XElement.Load("Sample.xml");

dynamic xml = new DXElement(root);

foreach (var b in xml.B)
    Console.WriteLine(b.X);

Using the combination of C# 4.0’s new dynamic type, and the DynamicObject class, getting this working is actually pretty easy. What we need is a dynamic that will map properties to child elements and attributes. The DynamicObject base class provides an overloadable TryGetMember method that is called whenever the code tries to get a property off of a dynamic. For example, when xml.B is used above, DynamicObject.TryGetMember is called, asking the DynamicObject to return the value of the member. So the DXElement gets to decide what type and value to return, at runtime. Here is my DXElement class, in its entirety:

public class DXElement : DynamicObject
{
    public XElement BaseElement { get; set; }

    public DXElement(XElement baseElement)
    {
        this.BaseElement = baseElement;
    }

    public override bool TryGetMember(GetMemberBinder binder, out object result)
    {
        //Go ahead and try to fetch all of the elements matching the member name, and wrap them
        var elements = BaseElement.Elements(binder.Name).Select(element => new DXElement(element));

        //Get the count now, so we don't have to call it twice
        int count = elements.Count();
        if (count > 0)
        {
            if (count > 1)
                result = elements; //We have more than one matching element, so let's return the collection
            else
                result = elements.FirstOrDefault(); //There is only one matching element, so let's just return it

            return true; //return true cuz we matched
        }
        else
        {
            //Ok, so no elements matched, so lets try attributes
            var attributes = BaseElement.Attributes(binder.Name).Select(attr => attr.Value);
            count = attributes.Count();

            if (count > 0)
            {
                if (count > 1)
                    result = attributes; //more than one attribute matched, lets return the collection
                else
                    result = attributes.FirstOrDefault(); //only one attribute matched, lets just return it

                return true; // return true cuz we matched
            }
        }

        //no matches, let's let the base class handle this
        return base.TryGetMember(binder, out result);
    }
}

Not too bad right? Now, it makes a couple of assumptions about the input XML, which are most likely false, but for examples sake, we’ll just ignore that fact ;). As you can see, there isn’t much code needed, just the TryGetMemeber overload using XLinq against the BaseElement to find what we want to return as the result.

Dynamic Linq Queries

Posted 05/05/2009
Filed under: C# | Tags: C#, codeproject, Expressions, Linq

Leave a Comment

Alright, let’s assume that we are lazy coders, we have building a lot of Linq queries lately, and it’s getting repetitive. We keep having to remember to add a certain where clause to every query, couldn’t we just abstract this somehow? Well sure, we can use Expressions!

Let’s first take a look at the System.Linq.Queryable.Where extension method, here is the method’s signature:

public static IQueryable<TSource> Where<TSource>(
    this IQueryable<TSource> source,
    Expression<Func<TSource, bool>> predicate);

Notice that it takes a lambda expression, which we can generate dynamically. For examples sake, let’s make a Foo and a Bar class, and two methods that generate a list of each:

static IEnumerable<Foo> MakeFoos()
{
    for (int i = 0; i < 10; i++)
        yield return new Foo { A = "Foo " + i, B = i };
}

static IEnumerable<Bar> MakeBars()
{
    for (int i = 0; i < 10; i++)
        yield return new Bar { A = "Bar " + i, B = i };
}

class Foo
{
    public string A { get; set; }
    public int B { get; set; }
}

class Bar
{
    public string A { get; set; }
    public int B { get; set; }
}

So what if we want to get all of the items in a collection with a and even B? What we need is an extension method that applies our filter to an IQueryable<> of any type. First off, let’s look at the method signature:

public static IQueryable<T> FilterB<T>(this IQueryable<T> query)

It’s fairly simple, it is an extension method that takes an IQueryable<T> and returns an IQueryable<T> so that we can keep our fluent interface going. The first thing we have to do in our method is create a parameter and property expression,

var param = Expression.Parameter(typeof(T), "x");
var prop = Expression.Property(param, "B");

Then we need a binary expression that %’s our property by 2,

var two = Expression.Constant(2);
var mod = Expression.MakeBinary(ExpressionType.Modulo, prop, two);

The ConstantExpressions are pretty self explanatory, they just hold the value that they are given. BinaryExpressions can represent any kind of binary expression, which is any expression that has a left and right side, like a == b, a != b, a + b, and b – a for example. Next, we need to make another binary expression that checks to see if our first binary expression, mod, is equal to zero:

var zero = Expression.Constant(0) ;
var eqZero = Expression.MakeBinary(ExpressionType.Equal, mod, zero);

Notice that we used one binary expression as a parameter for another, MakeBinary’s second and third parameters are just Expressions which can be any type of expression. All that is left to do is create the lambda expression, where it and return it:

var lambda = Expression.Lambda<Func<T, bool>>(eqZero, param);
return query.Where(lambda);

We don’t have to compile the lambda here because query providers use it in its raw expression tree form which they translate into whatever they need to get the job done. Here is the entire method:

public static IQueryable<T> FilterB<T>(this IQueryable<T> query)
{
    var param = Expression.Parameter(typeof(T), "x");
    var prop = Expression.Property(param, "B");

    var two = Expression.Constant(2);
    var mod = Expression.MakeBinary(ExpressionType.Modulo, prop, two);

    var zero = Expression.Constant(0);
    var eqZero = Expression.MakeBinary(ExpressionType.Equal, mod, zero);

    var lambda = Expression.Lambda<Func<T, bool>>(eqZero, param);
    return query.Where(lambda);
}

This should work with any query provider including Linq to SQL and the Entity Framework. We haven’t built in any error checking so expect it to throw if you use it on a collection of a type that does not have a B property. So, given the types we defined above, let’s see how we would use it:

var foos = MakeFoos().AsQueryable();
var bars = MakeBars().AsQueryable();

foreach (var foo in foos.FilterB())
    Console.WriteLine(foo.A);

foreach (var bar in bars.FilterB())
    Console.WriteLine(bar.A);

We are first getting collections of both Foos and Bars, and then changing them into IQueryable collections. we then just iterate over each collection after calling FilterB() on them. We could chain other calls after the FilterB call if we wanted. The output will be:

Foo 0

Foo 2

Foo 4

Foo 6

Foo 8

Bar 0

Bar 2

Bar 4

Bar 6

Bar 8

Yay! It works!

Using Expressions for Fun and Profit

Posted 05/04/2009
Filed under: C# | Tags: C#, codeproject, Expressions, Linq

Comments (4)

Well, by now we all know how to abuse System.Reflection to the point of absurdity, so now it’s time to start the abuse of System.Expressions. The System.Expressions namespace contains everything you need to build lambda expressions on the fly, then compile them at run time for use. One may ask “Why Bother?”, well my friend, the answer is Speed. If you are using reflection heavily in your projects, you are likely to get a nice speed boost by switching to Expressions. There are is one detail to keep in mind though, that the actual compilation of expressions can take some time, so you will want to cache the result.

First off, let’s take a look at a simple lambda, and then try to build it dynamically. Say we want to grab the length of a string:

Func<string, int> getStrLen = x => x.Length;

The lambda expression that we are assigning to the delegate has 2 main parts, the x parameter, and the x.Length property access. Let’s go ahead and create these two smaller expressions. Expressions use a factory pattern and can only be instantiated through static methods of off Expression so here is the code to build those two parts:

var param = Expression.Parameter(typeof(string), "x");
var prop = Expression.Property(param, "Length");

Expression.Parameter take a Type as the first parameter, which is the type of the parameter, and a string as the second parameter which is only used when you .ToString() the expression. Expression.Property takes another Expression as the first parameter, in our case we are using the ParameterExpression we created on the line before, but it can be a few other things like other PropertyExpressions, ConstantExpressions, CallExpressions, etc. The second parameter of Expression.Property is a string, it is just the name of the property you want to get. All that is left to do now is to build the lambda expression itself, and compile it:

var lambda = Expression.Lambda<Func<string, int>>(prop, param);
Func<string, int> result = lambda.Compile();

Expression.Lambda has both regular and generic versions, we want to use the generic because we want to be able to call it as directly as possible. The first parameter it takes is the body of the lambda, and in our case that is x.Length, which is our prop variable. Every parameter after the first should be ParameterExpressions representing parameters that you are passing to the lambda, and should match the order and number of the generic parameters on the delegate type that is used as the generic for Expression.Lambda. The call to lambda.Compile() is where the real magic happens, the library compiles our expression tree down to executable code. So, we’ve dynamically built the same lambda as we have assigned to getStrLen. if you are looking for more proof, check lambda.ToString(), which also comes in handy when you are trying to debug your expression building code. Alright, now let’s build a nice generic method using the same pieces as above, starting off with the method signature:

Func<T,R> BuildGetProperty<T, R>(string propName)

Our method will have two generic parameters, T which is the type containing the property, and R which is the type of the property, and one string that will be the name of the property to get. The body of our method is going to be almost verbatim of what is outlined above, except that we are going to substitute our generic types and property name. The end result is:

public static Func<T,R> BuildGetProperty<T, R>(string propName)
{
    var param = Expression.Parameter(typeof(T), "x");
    var prop = Expression.Property(param, propName);

    var lambda = Expression.Lambda<Func<T, R>>(prop, param);
    return lambda.Compile();
}

So, we could replace our getStrLen lambda above with:

var getStrLen = BuildGetProperty<string, int>("Length");

And to use it:

var len = getStrLen("woot");

Which would yield 4 as the result. I’ll be covering more on Expressions in further posts, so stay tuned. Also, comments are more than welcome since this is my first post.

Sean McCarthy’s Blog