August 2008 - Posts

As a reference for some planned and unplanned future posts, I wanted to share out my “cheat sheet” for the C# 3.0 translation carried out for query expressions. Obviously it’s based on the C# 3.0 Language Specification more specially section 7.15.2. A few remarks that deserve more attention when reading the specification:

  • Words in bold are contextual keywords; these are not reserved keywords as the language doesn’t introduce new reserved keywords to ensure forward compatibility for programs written in previous language versions (e.g. “from” could be used as a variable name).
  • Method names indicated in red are the query operators known by the compiler as compilation targets for the corresponding query syntax contextual keywords. Where these methods come from is purely a question answered by method resolution rules, obviously including extension methods from C# 3.0 on.
  • The ‘*’ in the translations below stands for the transparent identifier, more of an implementation aspect of the compiler to “carry forward” the range variables captured in the anonymous type produced by a query operation (e.g. in SelectMany). This illustrates that anonymous types (as well as lambda BLOCKED EXPRESSION are essential pieces of glue to make LINQ work (although alternatives based on a hypothetical “tuple type” runtime feature would work too).
  • For the orderby operator, corresponding flavors with descending order have been omitted. Essentially all of the ordering clauses can optionally have the descending keyword, resulting in an OrderByDescending or ThenByDescending call in the corresponding translation.
  • All the rules are mutually recursive: starting with a query expression, the translation will gradually “compile away” certain parts of the query expression syntax into method call driven equivalent expressions. Notice all rules without an ellipsis … on the left-hand side don’t have any query expression keywords left on the right-hand side – these are the terminal “closed” expressions that are entirely expressible in C# 3.0 \ { LINQ }. It’s like peeling off the LINQ layer from the C# 3.0 onion.
  • The first two rules for Select seem redundant, i.e. when substituting v for x in the second rule one gets the first rule. The reason they are spelled out each individually is because the first rule covers degenerate expressions (covered in another post of mine) and rules should be evaluated from top to bottom. The Select ( x => x ) is kept based on the conditions spelled out in section 7.15.2.3.

So here’s my cheat sheet:

image

Feel free to redistribute it in any form but I’d appreciate at least a reference to the official C# 3.0 Language Specification with it as that’s the ultimate resource for the detailed language specifics. A pointer to my blog would be much appreciated as well of course :-).

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Last time we talked about dealing with dynamic code generation using Reflection.Emit to generate calls to our dynamic binder. I’ve shown how to see the IL that gets generated by means of the Dynamic IL Visualizer add-in in Visual Studio. In this post I want to point out that you can actually live without that visualizer and go the hard-core way using SOS, aka “Son of Strike”, the WinDbg extension for managed code debugging that ships with the .NET Framework (sos.dll). A little-known fact is that SOS can be loaded directly in Visual Studio through the Immediate Window.

Note: This post is screenshot-driven; to conserve bandwidth I’ve included only thumbnails in the post itself; “click to enlarge” is the message.

Note: There are many ways to get to the information you care about; in the end we’re dealing with object graphs. This post is more an exploration of the data that you can get at if you want to do so; the various paths to get there are more a matter of style (in physical terms: the potential energy is constant, but the accumulated kinetic energy corresponding to the developer’s finger muscle contractions when dealing with the keyboard may vary).

 

Step 1 – Loading SOS

We’re on a breakpoint in managed code and will try to load SOS through the Immediate Window using .load sos:

image

For this to work, native code debugging needs to be enabled in the project properties:

image

 

Step 2 – Finding dynamic methods

To find the dynamically generated methods, we can search the heap for objects of type DynamicMethod using .dumpheap DynamicMethod. As you can see we don’t have any yet:

image

Using F10 we step to the next method, executing Compile causing the dynamic method for the expression to be compiled. Rerunning the command now yields:

image

We’re in business. As you can see we had two matching types: DynamicMethod and DynamicMethod+RTDynamicMethod. We’re interested in the former one, so we follow the MT field back to the list of objects. MT stands for Method Table which is a runtime structure describing the object layout for a particular type. It can be used to locate fields and methods in preparation to calls. If you want, you can use !dumpmt –MD <MT address> to dump such a table; this will show all of the “methods in the table”.

 

Step 3 – Dumping the IL

Now that we have the DynamicMethod object, we can dump the IL for it using !dumpIL <object address>:

image

As we were compiling the identity function I, the IL shown should just be a ldarg.0 and sure it is.

 

Step 4 – Another sample

We could have stopped with the previous sample but our dynamic dispatch is interesting to analyze too. Breaking after our Substring sample compilation (in a fresh run, so that the old DynamicMethod is no longer displayed) results in:

image

We can follow it through to the IL again:

image

Notice the call to “something in parentheses”. This is the runtime token representing the method, which we can dump using !do <address>. In addition, !dumpIL hints at dumping the token array:

image

The result of doing so is an array of tokens used in the IL stream. I’ll show this in a second but you might wonder what those fancy numbers in the IL stream like “70000002” stand for. Those indicate token types as defined in CorTokenType (see corhdr.h, for instance in the SSCLI “Rotor” distribution). To find the token type, mask with 0xFF000000, so in our sample that leaves 0x70000000 and this is defined as mdtString. The remainder (mask with 0x00FFFFFF) leaves us with the RID (relative ID) of 0x00000002, so entry two in the table contains the corresponding token value:

image

And yes, we see “Substring” appearing. Similarly value 2000003 in IL_0010 gives us a type def token (for System.Object) at offset 3 and value 0a000004 in IL_0031 gives us a member ref token (for our DynamicBinder.Call method) at offset 4. For the latter one, the debugger output gives you the indirection in between parentheses straight away:

image

How convenient!

 

Step 5 - From token to MethodInfo to DeclaringType

Next we can follow the object chains all the way up to the declaring type: first we get from the token to the method it represents and second we can traverse m_declaringType to get the corresponding type:

image

This produces a System.RuntimeType instance containing a Method Table reference:

image

So we can dump the method table with !dumpmt –MD <MT address> as follows:

image

As you can see we’re in our DynamicBinder class.

 

Step 6 – What about the signature?

Instead of following the path to the m_declaringType above, we could follow the m_signature as well:

image

System.Signature wraps a m_signature field of type SignatureStruct which we can dump as well, but as this is a value type we can’t use !do but rather need to use !dumpvc (standing for value class) passing in the method table (otherwise the debugger wouldn’t know how to interpret the struct which is simply a blob of data) and the address.

 

Step 7 – And back to the method being called

From the signature struct we can reach out to the method represented by the signature through m_pMethod. This is a runtime handle, wrapping an IntPtr pointer to where the loaded IL code lives. In other words, we can invoke dumpIL on that address to see the contents of what turns out to be our DynamicBinder.Call method:

image

(Notice the closure classes in the IL generated because of our C# 3.0 lambda expressions embedded in the LINQ query we use for method overload resolution.)

 

Step 8 – Dynamic modules

Dynamic methods live in dynamic modules, so it would be interesting to see those. SOS comes to the rescue with !dumpdomain.

image

Scroll down a bit and we get to see the dynamic modules. With some poking around it turns out that the last one is the one we’re looking for as it contains a multicast delegate, precisely what we've been generating. We can visualize it using !dumpmodule –mt <address> also showing the types that are referenced inside the module (that’s where we see the MulticastDelegate).

image

Also notice the attribute saying “Reflection”. To see how the type definition (TypeDef) is indirected through a method table map (MethodTableMap), follow the arrows below. Green indicates the indexing and again the masked first two bytes of the green value indicate the CorTokenType, in this case a TypeDef. You can do the same exercise for the TypeRef (0x01000000) – follow the memory pointer and get the first (zero-based count obviously) element referred in there (it should read 24 e5 0f 79 as you can infer from the output produced by the debugger, considering little endian conversion).

image

Unfortunately the defined type is marked as unloaded so we’re at a dead end – feel free to explore the Method Table for the type a bit further. In a similar way you can track down the loaded module with our DynamicBinder to do some explorations (also starting from !dumpdomain):

image

Dumping the binder’s method table gives us:

image

Who still needs ILDASM or Reflector? :-)

 

Step 9 – Walking the stack

To finish this post, I’d like to show how to dump the stack objects using !dso to get to some of this information through yet an alternative route:

image

In green I’ve indicated the result of the dynamic call and what it corresponds to. However, the items in red indicate our (mysterious?) unloaded type once more. As you’ll see though, the IL is still available:

image

The result is predictable by now I guess.

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Last time in this series we were able to compile a stunningly complex “dynamic lambda” x => x – also known as I in the world of combinators – into IL code at runtime. As that’s not particularly useful, we want to move on to slightly more complex expressions like:

var o = DynamicExpression.Parameter("o");
var a = DynamicExpression.Parameter("a");
var b = DynamicExpression.Parameter("b");
var call = DynamicExpression.Call(o, "Substring", a, b);
var func = DynamicExpression.Lambda(call, o, a, b);
Console.WriteLine(func);
Console.WriteLine(func.Compile().DynamicInvoke("Bart", 1, 2));

Or, in pretty print,

(o, a, b) => o.Substring(a, b)

 

Setting the scene

We explained how the translation of a dynamic expression tree takes place in general: as we traverse the tree, individual nodes are visited asking them to append code capturing the expression’s semantics to an IL stream, pushing a value on the stack that corresponds to the evaluated expression. The method that does this translation for every dynamic expression is called “Compile”:

/// <summary>
/// Appends IL instructions to calculate the expression's runtime value, putting it on top of the evaluation stack.
/// </summary>
/// <param name="ilgen">IL generator to append to.</param>
/// <param name="ldArgs">Lambda argument mappings.</param>
protected internal abstract void Compile(ILGenerator ilgen, Dictionary<ParameterDynamicExpression, int> ldArgs);

In here we’re using a simplified concept of “lambda parameters in scope” using ldArgs, avoiding getting into slightly more complex techniques such as hoisting that are required for more involved expression trees. Previously you saw how to implement this method for ParameterDynamicExpression and LambdaDynamicExpression, respectively:

protected internal override void Compile(ILGenerator ilgen, Dictionary<ParameterDynamicExpression, int> ldArgs)
{
    if (!ldArgs.ContainsKey(this))
        throw new InvalidOperationException("Parameter expression " + Name + " is not in scope.");

    ilgen.Emit(OpCodes.Ldarg, ldArgs[this]);
}

and

protected internal override void Compile(ILGenerator ilgen, Dictionary<ParameterDynamicExpression, int> ldArgs)
{
    Body.Compile(ilgen, ldArgs);
    ilgen.Emit(OpCodes.Ret);
}

 

Dynamic method calls and binders

For MethodCallExpression things are a bit more involved than for the expression types above. Before we start, remember the most important portion of the Compile method contract: leave one value on top of the stack that corresponds to the evaluated expression, in this case a method call. What does a method call consist of? Here are the ingredients:

public ReadOnlyCollection<DynamicExpression> Arguments { get; private set; }
public DynamicExpression Object { get; private set; }
public string Method { get; private set; }

As we’re seeing other DynamicExpression objects being referenced in here, it’s already clear we’ll have to evaluate those by recursively calling Compile. So, we could do something along the lines of:

compile Object
foreach argument in Arguments
    compile argument
call Method

That’s the typical structure of a call site, pushing arguments on the stack including the object to invoke the method on. From a stack point of view: n + 1 arguments are pushed, where n is the number of arguments and 1 accounts for the instance to invoke the method one, and next all of those stack citizens are eaten by the method call, producing the single return value on top of the stack. This follows the contract of our Compile method.

There’s a slight problem though: we can’t emit the call because we don’t know what type to invoke it one. The reason is well-known in the meantime: the Object nor the Arguments have strongly-typed information, so just given a string named “Method”, we can’t get the required method metadata to emit a call(virt) instruction. Bummer. But that’s the whole point of dynamic programming, delaying the decision about the executed method/function till runtime because the type might dynamically grow with new members (think of ETS in PowerShell as a sample of such a capability).

One way to solve this problem is to emit a bunch of reflection code to investigate the type of Object at runtime, do the same for all of the arguments, try to find a suitable method to call, etc etc. I shouldn’t explain how complicated this would become :-). There are lots of drawbacks to this: we’re baking in the whole dynamic call infrastructure into the call site and as we’re emitting all of that code, the odds to adapt it without having to recompile the code are off. This whole “locate a suitable method” algorithm could be made extensible too if we’re not emitting it into the generated code straight away. In other words, we want to get out of the IL generating business as soon as we can, and introduce a level of indirection. That particular kind of indirection is what we call a binder.

So what’s a binder precisely? It’s simply a class that contains all the functionality to make well-formed decisions (based on certain desired semantics) about method calls (amongst other invocation mechanisms). Actually we have such a thing in the framework already: System.Reflection.Binder. As the documentation says:

Selects a member from a list of candidates, and performs type conversion from actual argument type to formal argument type.

The list of candidates is something that can be made extensible, allowing methods to be “imported” or “attached” to existing types at runtime. The type conversion clause in the sentence above outlines that the binder is responsible to take the actual passed in arguments (in our case weakly typed) and turn them into (i.e. casting) formal argument types that are suitable for consumption by the selected candidate method. The sample on MSDN for System.Reflection.Binder shows what it takes to implement such a beast. We’re not going to do that though, just to simplify matters a bit. As we’re only interested in method calls, we’ll just implement the bare minimum binder to get the job done and explained. Furthermore, we won’t spend time on implicit conversions for built-in types (like int to long) as the mentioned sample illustrates that already. Last but not least, generics are not brought in the equation either.

Without further delay, let’s show a possible binder implementation:

public class DynamicBinder
{
    public static object Call(object @this, string methodName, params object[] args)
    {
        //
        // Here we're going to be lazy for demo purposes only. Our overload resolution
        // will pick the first applicable method without applying "betterness" rules
        // as outlined in the C# specification (v2.0, section $7.4.2). We don't care
        // about extension methods either (how could the namespace be brought in scope
        // in the context of an expression tree...?) nor other dynamic type extensions
        // such as IExpando (~ IMarshalEx) or e.g. PowerShell ETS.
        //

        var result = (from method in @this.GetType().GetMethods()
                      where method.Name == methodName
                      let parameters = method.GetParameters()
                      where parameters.Length == args.Length
                            && parameters.Where((p, i) => p.ParameterType.IsAssignableFrom(args[i].GetType())).Count() == args.Length
                      select new { Method = method, Parameters = parameters }).SingleOrDefault();

        if (result == null)
        {
            StringBuilder sb = new StringBuilder();
            sb.Append("Failed to bind method call: ");
            sb.Append(@this.GetType());
            sb.Append(".");
            sb.Append(methodName);
            sb.Append("(");

            int n = args.Length;
            for (int i = 0; i < n; i++)
                sb.Append(args[i].GetType().ToString() + (i != n - 1 ? ", " : ""));

            sb.Append(").");
            throw new InvalidOperationException(sb.ToString());
        }

        return result.Method.Invoke(@this, args);
    }
}

This needs some explanation I assume. The signature should be straightforward: given an object @this, we want to call method methodName with zero or more arguments args. The result of this will be an object again (notice we don’t support void return types for methods being called, which isn’t too big of deal when considering functions as lambdas – i.e. no statement lambdas). What’s more interesting though is the way we find a suitable method. I chose to write it as a gigantic LINQ expression just to show how powerful LINQ can be. Let me walk you through it:

var result = (from method in @this.GetType().GetMethods()
              where method.Name == methodName
              let parameters = method.GetParameters()

For all methods available on the left-hand side of the call (i.e. @this) select those methods that have the same name (case sensitive compare – this would be a binder that mimics C# name resolution for method calls) and let parameters be a variable containing the parameters for each of the selected methods going forward. In other words, in what follows we’re seeing a sequence of (method, parameters) pairs mapping each suitable (at least concerning the name) method on the parameters it takes. Next we need to do overload resolution:

              where parameters.Length == args.Length

Here we make sure the number of arguments on the candidate method matches the number of arguments passed in to the binder’s Call call. This implies we don’t consider things like optional arguments supported by some languages which would mean that having less matching parameters (but not more!) would keep the method as a candidate, although there would need to be some ordering to make sure that methods with more arguments take precedence over methods with arguments supplied through optional values. Notice this simple check makes it also impossible to call a “params” method without stiffing the argument in an array upfront.

                    && parameters.Where((p, i) => p.ParameterType.IsAssignableFrom(args[i].GetType())).Count() == args.Length

Now we’re in the clause that’s maybe the most interesting. Here we’re taking all the parameters of the candidate and check that the parameter p on position i has a type that’s assignable from the type of the argument passed in to the binder’s Call method. In essence this is contravariance for arguments. Assume we’re examining a candidate method like this:

class ExperimentalZoo
{
    Animal CloneBeast(Mammal g);
}

and we’re calling the binder as follows:

DynamicBinder.Call(new ExperimentalZoo(), “CloneBeast”, new Giraffe())

As we’re calling the binder with an argument of type Giraffe (args[0].GetType()) and Giraffe inherits from Mammal (parameters[i].ParameterType), the candidate is compatible. However, if we’d call the method with an argument of type Goldfish it would clearly not be compatible (as a fish is not a mammal). This is precisely what the Where clause above enforces. The Count() == args.Length trick at the end makes sure all of the arguments pass the test (using the All operator would be ideal but it hasn’t an overload passing in the index; alternatively a Zip operator would be beneficial too).

Finally we have the select clause:

              select new { Method = method, Parameters = parameters }).SingleOrDefault();

which simply extracts the method (of type MethodInfo) and the parameters (of type ParameterInfo[]) and makes sure we only found one match. This is another simplification for illustrative purposes only – to be fully compliant with e.g. the C# language, we’d have to implement all of the overload resolution rules including “betterness rules” that select the most optimal overload. More information on this can be found in the C# specification, in v3.0 under “7.4.3 Overload Resolution”. The key takeaway though is that we can tweak this binder as much as we want (e.g., left as an exercise, we could implement resolution that takes extension methods into account) without affecting the generated IL code that will simply call into the binder’s Call method.

If we find one result, we can just go ahead and call it by calling through the retrieved Method using the Invoke method, passing in the @this pointer and the args array.

 

Connecting the pieces

Now that we have our beloved binder, we need to glue it together with our dynamic expression compilation. In concrete terms this means we need to emit a call to DynamicBinder.Call in the generated IL for the DynamicCallExpression. This isn’t too hard either:

protected internal override void Compile(ILGenerator ilgen, Dictionary<ParameterDynamicExpression, int> ldArgs)
{
    if (Object == null)
        ilgen.Emit(OpCodes.Ldnull);
    else
        Object.Compile(ilgen, ldArgs);

    ilgen.Emit(OpCodes.Ldstr, Method);

    ilgen.Emit(OpCodes.Ldc_I4, Arguments.Count);
    ilgen.Emit(OpCodes.Newarr, typeof(object));

    LocalBuilder arr = ilgen.DeclareLocal(typeof(object[]));
    ilgen.Emit(OpCodes.Stloc, arr);

    int i = 0;
    foreach (DynamicExpression arg in Arguments)
    {
        ilgen.Emit(OpCodes.Ldloc, arr);
        ilgen.Emit(OpCodes.Ldc_I4, i++);
        arg.Compile(ilgen, ldArgs);
        ilgen.Emit(OpCodes.Stelem_Ref);
    }

    ilgen.Emit(OpCodes.Ldloc, arr);

    ilgen.EmitCall(OpCodes.Call, typeof(DynamicBinder).GetMethod("Call"), null);
}

What’s going on here? First, we check whether an Object has been specified. This is more of an extensibility point in case our binder would like to implement global functions (also left as an exercise, for example you could recognize null.Add(1, 2) as a global Add call, translating into Math.Add(…); or, the Method property could be set to “Math.Add” to denote a static method call). We’ll assume the else case holds true for our samples, causing us to call Compile recursively on the Object dynamic expression. This will add the value corresponding to the Object expression tree’s evaluation on top of the stack (note: you can smell call-by-value semantics already, don’t you?). Next, we load the string specified in the Method property onto the stack as well. Currently the stack looks like:

(string) Method
(object) Object.Compile result

Now we get into interesting stuff as our binder’s Call method expects to see an object[] as its third parameter. How many arguments? On for each of the DynamicExpression objects in the Arguments collection, so we do Newarr passing in the object type object after pushing the number of elements to be allocated on the stack using Ldc_I4 passing in Arguments.Count. Now we have our array, we can store it in a local variable we call “arr”. Time to fill the array by first loading the local, then pushing the index followed by a push of the argument’s value – again obtained by a recursive Compile call on the argument “arg” – and finally calling stelem_ref (as we’re dealing with System.Object we need _ref). The loop invariant is that it doesn’t change the stack height: it cleanly loads three “arguments” to stelem_ref which brings the stack delta back to 0).

Ultimately, we load the array local variable and the stack looks like (semantically):

(object[]) Arguments.Select(arg => arg.Compile()).ToArray()
(string) Method
(object) Object.Compile()

ready for a call to DynamicBinder.Call which turns the stack into:

(object) DynamicBinder.Call(Object.Compile(), Method, Arguments.Select(arg => arg.Compile()).ToArray())

Again, we have managed to keep the house clean with regards to the stack behavior, i.e. the element on top of the stack contains the value corresponding to the entire (MethodCall)DynamicExpression.

 

Testing it

Does it work? Let’s try with our running sample:

var o = DynamicExpression.Parameter("o");
var a = DynamicExpression.Parameter("a");
var b = DynamicExpression.Parameter("b");
var call = DynamicExpression.Call(o, "Substring", a, b);
var func = DynamicExpression.Lambda(call, o, a, b);
Console.WriteLine(func);
Console.WriteLine(func.Compile().DynamicInvoke("Bart", 1, 2));

Recognize the patterns in the output IL?

image

A quick walk-through:

  • IL_0000 loads MethodCallDynamicExpression.Object which in turn was compiled into a ldarg V_0 by the ParameterDynamicExpression’s Compile method (this corresponds to “o”)
  • IL_0006 loads MethodCallDynamicExpression.Method
  • IL_000b to IL_0015 prepares the array for the method call arguments to be passed to the binder
  • IL_0016 to IL_0022 puts the first argument (corresponding to “a” translated into ldarg V_1 through ParameterDynamicExpression.Compile) in the array
  • IL_0023 to IL_002f does the same for the second argument (corresponding to “b” translated into ldarg V_2 through ParameterDynamicExpression.Compile)
  • IL_0030 to IL_0036 finally makes the call through the binder, passing in the results of the above and returning the value produced by the binder

If we now set a breakpoint in the DynamicBinder.Call method and let execution continue, we’ll see:

image

The third line in the Call Stack is where DynamicInvoke is happening:

Console.WriteLine(func.Compile().DynamicInvoke("Bart", 1, 2));

and through the “External Code” corresponding to our emitted dynamic method we got back into the DynamicBinder that now will pick the right Substring method given lhs “Bart” and arguments 1 and 2. Ultimately the following prints to the screen:

image

Magic. To show it’s really extensible we can start to compose things endlessly with our two main ingredients: parameter and method call expressions. Here’s a sample (reverse engineering the nested DynamicExpression factory calls is left as an exercise):

image

Also left as an exercise to the reader is to find values for o and a through h that produce the displayed output above :-). For the record, here’s the corresponding IL:

IL_0000: ldarg      V_0
IL_0004: nop       
IL_0005: nop       
IL_0006: ldstr      "Replace"
IL_000b: ldc.i4     2
IL_0010: newarr     Object
IL_0015: stloc.0   
IL_0016: ldloc.0   
IL_0017: ldc.i4     0
IL_001c: ldarg      V_3
IL_0020: nop       
IL_0021: nop       
IL_0022: stelem.ref
IL_0023: ldloc.0   
IL_0024: ldc.i4     1
IL_0029: ldarg      V_4
IL_002d: nop       
IL_002e: nop       
IL_002f: stelem.ref
IL_0030: ldloc.0   
IL_0031: call       System.Object Call(System.Object, System.String, System.Object[])/BinderFun.DynamicBinder
IL_0036: ldstr      "Substring"
IL_003b: ldc.i4     2
IL_0040: newarr     Object
IL_0045: stloc.1   
IL_0046: ldloc.1   
IL_0047: ldc.i4     0
IL_004c: ldarg      V_1
IL_0050: nop       
IL_0051: nop       
IL_0052: stelem.ref
IL_0053: ldloc.1   
IL_0054: ldc.i4     1
IL_0059: ldarg      V_2
IL_005d: nop       
IL_005e: nop       
IL_005f: stelem.ref
IL_0060: ldloc.1   
IL_0061: call       System.Object Call(System.Object, System.String, System.Object[])/BinderFun.DynamicBinder
IL_0066: ldstr      "Replace"
IL_006b: ldc.i4     2
IL_0070: newarr     Object
IL_0075: stloc.2   
IL_0076: ldloc.2   
IL_0077: ldc.i4     0
IL_007c: ldarg      V_5
IL_0080: nop       
IL_0081: nop       
IL_0082: stelem.ref
IL_0083: ldloc.2   
IL_0084: ldc.i4     1
IL_0089: ldarg      V_6
IL_008d: nop       
IL_008e: nop       
IL_008f: stelem.ref
IL_0090: ldloc.2   
IL_0091: call       System.Object Call(System.Object, System.String, System.Object[])/BinderFun.DynamicBinder
IL_0096: ldstr      "PadRight"
IL_009b: ldc.i4     2
IL_00a0: newarr     Object
IL_00a5: stloc.3   
IL_00a6: ldloc.3   
IL_00a7: ldc.i4     0
IL_00ac: ldarg      V_7
IL_00b0: nop       
IL_00b1: nop       
IL_00b2: stelem.ref
IL_00b3: ldloc.3   
IL_00b4: ldc.i4     1
IL_00b9: ldarg      V_8
IL_00bd: nop       
IL_00be: nop       
IL_00bf: stelem.ref
IL_00c0: ldloc.3   
IL_00c1: call       System.Object Call(System.Object, System.String, System.Object[])/BinderFun.DynamicBinder
IL_00c6: ldstr      "ToUpper"
IL_00cb: ldc.i4     0
IL_00d0: newarr     Object
IL_00d5: stloc.s    V_4
IL_00d7: ldloc.s    V_4
IL_00d9: call       System.Object Call(System.Object, System.String, System.Object[])/BinderFun.DynamicBinder
IL_00de: ret       

Enjoy! Next time … who knows what?

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Welcome back to the dynamic expression tree fun. Last time we designed our simplified expression tree class library we’ll be using to enable dynamic treatment of objects. Today, we’ll take this one step further by emitting IL code that resolves the operations invoked on such dynamic objects at runtime through a mechanism called binders. Before we dive in, let me point out that everything discussed in this series is greatly simplified just to illustrate the core ideas and base mechanisms/principles that make dynamic language stuff work.

 

Introducing IL generation

Dynamic code compilation is a wonderful thing. It’s not that hard once you get the basics right (and have some level of IL opcode understanding) but quite hard to debug. Luckily we have tools like Haibo Luo’s IL Visualizer. Since I’ll be using this, download it, extract the ZIP file, compile the whole solution and copy ILMonitor\bin\Debug\*.dll to %programfiles%\Microsoft Visual Studio 9.0\Common7\Packages\Debugger\Visualizers. Alternatively you can put it in your personal Visual Studio 2008\Visualizers folder.

So, what’s our task? Assume we have the following piece of sample code:

class Program
{
    static void Main(string[] args)
    {
        var o = DynamicExpression.Parameter("o");
        var a = DynamicExpression.Parameter("a");
        var b = DynamicExpression.Parameter("b");
        var call = DynamicExpression.Call(o, "Substring", a, b);
        var func = DynamicExpression.Lambda(call, o, a, b);
        Console.WriteLine(func);
        Console.WriteLine(func.Compile().DynamicInvoke("Bart", 1, 2));
    }
}

We already know how to construct the objects and to represent it as a string (which would be (o, a, b) => o.Substring(a, b)). Now we need to focus on the marked Compile method on LambdaDynamicExpression. Starting with the signature of the delegate, we want to create (at runtime) a method that takes in three “dynamic” parameters (corresponding to parameter expressions o, a and b), returning a resulting object. Since we don’t have any type information available, everything should be System.Object, so we’d end up with the following delegate:

delegate object TheDynamicLambdaFunction(object o, object a, object b);

Looking at Compile as a black box, it will return an instance of this delegate pointing at an on-the-fly generated method corresponding to the lambda’s body expression. Returning a System.Delegate, one can call DynamicInvoke (or cast it to a compatible delegate) to invoke it with the given parameters. Obviously we want the call to do “the right thing”, in the sample above it would correspond to a method call to System.String::Substring on “Bart”, passing in startIndex 1 and length 2, producing another string containing “ar”.

It should be clear that we need to emit IL on the fly to translate the lambda expression but also the lambda’s body which could be anything, not just a MethodCallDynamicExpression. Since we lack other expression node types, one such (trivial) thing would be:

var x = DynamicExpression.Parameter("x");
var I = DynamicExpression.Lambda(x, x);
Console.WriteLine(I);
Console.WriteLine(I.Compile().DynamicInvoke("Bart"));

which is just the identity function (the underlined bold ‘o’ above indicates the lamdba’s body). I intentionally named the expression above “I” conform SKI combinators where I is defined as λx . x. Similarly we could define the K combinator as:

var x = DynamicExpression.Parameter("x");
var y = DynamicExpression.Parameter("y");
var K = DynamicExpression.Lambda(x, x, y);
Console.WriteLine(K);
Console.WriteLine(K.Compile().DynamicInvoke("Bart", 123));

but we got sidetracked, so time to move on. The whole point here is that we can’t assume the body of the lambda to be a MethodCallDynamicExpression. So, how do we tackle this? An important observation one can make is this: an expression represents a single value. Right, so what? Wait a minute, is IL-code not stack-based? Adding the two things together we could think of the following solution:

Calling a Compile method on an expression tree object, given a writeable stream for IL instructions, should add all the instructions to the stream required to evaluate the expression, leaving the result of the evaluation on top of the stack.

A LambdaDynamicExpression is the only dynamic expression that supports a publicly visible Compile method. It’s pseudo-code would look like:

  1. Create an IL stream; here the IL stack is empty.
  2. Take the Body expression and compile it by emitting IL instructions for it; this causes the IL stack to be one high.
  3. Add an IL return instruction to return the object on top of the stack.
  4. Return a delegate pointing to the method represented by the generated IL code.

 

Supporting expression compilation

To make this work, we’ll first extend the base class by adding one more method:

/// <summary>
/// Class representing a dynamic expression tree.
/// </summary>
abstract class DynamicExpression
{
    /// <summary>
    /// Appends IL instructions to calculate the expression's runtime value, putting it on top of the evaluation stack.
    /// </summary>
    /// <param name="ilgen">IL generator to append to.</param>
    /// <param name="ldArgs">Lambda argument mappings.</param>
    protected internal abstract void Compile(ILGenerator ilgen, Dictionary<ParameterDynamicExpression, int> ldArgs);

}

This method will take in two things: the IL generator (referred to as “IL stream” in the previous paragraph) and a mapping table for the lambda’s parameter expressions. Why do we need the latter, or better: what does it map the parameter expressions to? Assume we’re compiling

(o, a, b) => o.Substring(a, b)

While traversing the expression tree, asking every node in the correct order to emit IL instructions, we’ll encounter references to the parameters again. Our goal is to write a dynamic method looking like this:

object GeneratedDynamicMethod(object o, object a, object b)
{
    return o.Substring(a, b);
}

where the . obviously denotes a dynamic method call in this case. As we encounter parameter expressions like o, a or b during the translation for the method body, we need to know how to load those parameters from the argument list on the dynamic method. First of all, notice the lambda parameters got mapped in order of specification to correspond to arguments on the generated dynamic method, i.e. o as the first lambda parameter and is the first parameter on the generated method. And so on. This is precisely what the ldArgs argument on Compile stands for: a mapping from the parameter expression representation from the lambda parameters onto the concrete indices for the arguments:

o –> 0
a –> 1
b –> 2

Whenever we encounter such a parameter expression during the compilation, we know the position of the argument, so we can emit a ldarg instruction. This is the most trivial Compile override:

sealed class ParameterDynamicExpression : DynamicExpression
{
    protected internal override void Compile(ILGenerator ilgen, Dictionary<ParameterDynamicExpression, int> ldArgs)
    {
        if (!ldArgs.ContainsKey(this))
            throw new InvalidOperationException("Parameter expression " + Name + " is not in scope.");

        ilgen.Emit(OpCodes.Ldarg, ldArgs[this]);
    }
    …
}

This simply says, whenever code needs to be emitted for a ParameterDynamicExpression, simply try to find it in the dictionary to map it onto the formal parameter index on the dynamic method being emitted and turn it into a ldarg instruction for that argument index. Real full-fledged expression tree implementations would be slightly more complicated because arguments could be hidden when dealing with nested lambdas (quoting, invocation expressions, etc) but that would take us too far away from home.

For the LambdaDynamicExpression, besides a public Compile method, there will also be an override to the inherited one. It simply asks the Body expression to emit itself (which will result in a one-level high stack containing the evaluation result of the body expression), followed by a ret instruction (simply returning the value evaluated through the Body’s IL code preceding it):

sealed class LambdaDynamicExpression : DynamicExpression
{
    protected internal override void Compile(ILGenerator ilgen, Dictionary<ParameterDynamicExpression, int> ldArgs)
    {
        Body.Compile(ilgen, ldArgs);
        ilgen.Emit(OpCodes.Ret);
    }

}

 

Emitting code

For this post, we’ll omit an implementation for MethodCallDynamicExpression as that will be part of the next post focusing on binders. All we want to get to work today is the I combinator or identity function (yeah, another world-beater :-)):

var x = DynamicExpression.Parameter("x");
var I = DynamicExpression.Lambda(x, x);
Console.WriteLine(I);
Console.WriteLine(I.Compile().DynamicInvoke("Bart"));

In other words, today we’ll focus on the plumbing of emitting the code and wrapping the method in a delegate that can be returned upon calling LambdaDynamicExpression.Compile. The result for the sample above would be equivalent to:

public Delegate Compile()
{
    return new Func<object, object>(delegate(object x) { return x; });
}

The underlined portion is the code corresponding to I’s compilation. In IL-terms it would be as simplistic as this:

ldarg.0
ret

This emitted IL method body then needs to get the signature that says “taking in an object, returning an object”. All of this makes up the dynamic method. But we’re not done yet, as we need to return a delegate to it. In the free translation above, I’ve leveraged the generic System.Func<T1,R> delegate but we only have a limited number of those (up to four arguments), so what if we encounter a method that takes more arguments? Indeed, we’ll need to generate our own delegate types as well. Notice we could cache those very efficiently: the ones with arity (~ number of parameters) up to 4 could simply be mapped onto System.Func delegates with System.Object type parameters, while others would be generated on the fly and kept for reuse if another method with same arity gets compiled. We’ll omit this optimization for now.

Here’s how the code to create our own delegate type looks like:

private static Type GetDynamicDelegate(Type[] argumentTypes, Type returnType)
{
    //
    // Assemblies contain modules; generate those with unique names.
    // The generated assembly is runtime only (doesn't need to be saved to disk).
    //
    AssemblyBuilder assemblyBuilder = AppDomain.CurrentDomain.DefineDynamicAssembly(new AssemblyName(Guid.NewGuid().ToString()), AssemblyBuilderAccess.Run);
    ModuleBuilder moduleBuilder = assemblyBuilder.DefineDynamicModule(Guid.NewGuid().ToString());

    //
    // Our delegate is a private sealed type deriving from MultiCastDelegate.
    //
    TypeBuilder typeBuilder = moduleBuilder.DefineType("Lambdas", TypeAttributes.NotPublic | TypeAttributes.Sealed | TypeAttributes.AutoLayout | TypeAttributes.AnsiClass, typeof(MulticastDelegate));

    //
    // The delegate's constructor is a "special name" method with signature (object native int).
    // It doesn't have a method body by itself; rather, it's supplied by the managed runtime.
    //
    ConstructorBuilder ctorBuilder = typeBuilder.DefineConstructor(MethodAttributes.Public | MethodAttributes.HideBySig | MethodAttributes.SpecialName | MethodAttributes.RTSpecialName, CallingConventions.Standard, new Type[] { typeof(object), typeof(IntPtr) });
    ctorBuilder.SetImplementationFlags(MethodImplAttributes.Runtime | MethodImplAttributes.Managed);

    //
    // We only need the Invoke method (BeginInvoke and EndInvoke are irrelevant for us).
    // It doesn't have a method body by itself; rather, it's supplied by the managed runtime.
    // Here our delegate signature is enforced.
    //
    MethodBuilder invokeMethodBuilder = typeBuilder.DefineMethod("Invoke", MethodAttributes.Public | MethodAttributes.NewSlot | MethodAttributes.HideBySig | MethodAttributes.Virtual, CallingConventions.HasThis, returnType, argumentTypes);
    invokeMethodBuilder.SetImplementationFlags(MethodImplAttributes.Runtime | MethodImplAttributes.Managed);

    //
    // Return the created delegate type.
    // Notice we could cache this for reuse by other dynamic methods.
    //
    return typeBuilder.CreateType();
}

Lots of attribute flags which you can read all about in the CLI specification. I don’t pretend to memorize all of those attributes; why would I if ILDASM makes life just great? :-)

image

This is the screenshot of ILDASM showing a delegate for a method with signature object(object, object) as you can see on the Invoke method. We don’t need any of the asynchronous pattern implementation, so we just need a constructor and Invoke method (see section IIA.13.6 on “Delegates” in the CLI standard). One special thing about those is they don’t have an IL code body as they are “runtime managed” (see IIA.14.4.3 on “Implementation Attributes of Methods” in the CLI standard):

image

Now that we can generate the delegate, we just need to ask the lambda (since that’s the root) expression tree to emit its IL code, which will traverse the entire tree. In order to be able to do this, we need to keep mapping information about the lambda parameters mapped onto the formal arguments as mentioned earlier. Here’s the result:

public Delegate Compile()
{
    //
    // Map the lambda parameters onto formal argument indices.
    // Also build up the argument type array.
    //
    var args = new Type[Parameters.Count];
    var ldArgs = new Dictionary<ParameterDynamicExpression, int>();
    for (int i = 0; i < args.Length; i++)
    {
        args[i] = typeof(object);
        ldArgs[Parameters[i]] = i;
    }

    //
    // Compile the expression tree to an IL method body.
    //
    var method = new DynamicMethod("", typeof(object), args);
    var ilgen = method.GetILGenerator();
    Compile(ilgen, ldArgs);

    //
    // Get the delegate matching the dynamic method signature.
    //
    Type dynamicDelegate = GetDynamicDelegate(args, typeof(object));

    //
    // Return a delegate pointing at our dynamic method.
    //
    return method.CreateDelegate(dynamicDelegate);
}

This code should be relatively straightforward. First we create the mapping while building up an array just containing typeof(object)’s (since all arguments are objects in our dynamic world). Next we create a dynamic method with the right signature, produce the IL generator and let the expression compilation do all of the work to emit the IL. And finally we stick the whole thing in a dynamically created delegate that matches the signature, returning that to the caller. Setting a breakpoint on the last line and executing for the “I” identity combinator shows this:

image

This is the IL visualizer we installed earlier. Notice the friendly string representation for the dynamic method shows the signature, which matches the one of the dynamic lambda in the watch window (which is just “I”). Bringing up the IL visualizer shows stunningly complex code:

image

Ignore the NOPs inserted by the IL generator, but IL_0000 was emitted by ParameterDynamicExpression.Compile through the compilation of the lambda body. IL_0006 was emitted subsequently by LambdaDynamicExpression.Compile and the stack is nicely in balance. Sure enough, the result printed is:

image

Woohoo – truly dynamic (though simplistic) execution! Next time: method call expressions and binders.

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

In the previous post, I outlined the use of the expression trees from the System.Linq.Expressions namespace. Let’s recap to set the scene:

Expression<Func<string, int, int, string>> data = (string s, int a, int b) => s.Substring(a, b);

produces (deep breadth)

ParameterExpression s = Expression.Parameter(typeof(string), “s”);
ParameterExpression a = Expression.Parameter(typeof(int), “a”);
ParameterExpression b = Expression.Parameter(typeof(int), “b”);

Expression<Func<string, int, int, string>> data = Expression.Lambda<Func<string, int, int, string>>(
    Expression.Call(s, typeof(string).GetMethod(“Substring”, new Type[] { typeof(int), typeof(int) }), a, b),
    s, a, b
);

Func<string, int, int, string> fun = data.Compile();
Console.WriteLine(fun(“Bart”, 1, 2));

where I’ve indicated all the strong typing using underlines. Wow, that’s a lot dude! Based on all of this strong typing, there are little or no runtime surprises possible concerning running the right method (unless a MissingMethodException occurs for some reason). Obviously, expression trees could be much more complex but to illustrate the core points of the type system, we’ll restrict ourselves to parameters, method calls and lambdas.

So what do we want to try now? We want to design an API similar to the one used above but without all this type information. Essentially, it would look like:

ParameterExpression s = Expression.Parameter(“s”);
ParameterExpression a = Expression.Parameter(“a”);
ParameterExpression b = Expression.Parameter(“b”);

LambdaExpression data = Expression.Lambda(
    Expression.Call(s, “Substring”, a, b),
    s, a, b
);

Delegate fun = data.Compile();
Console.WriteLine(fun.DynamicInvoke(“Bart”, 1, 2));

and all of a sudden we see the dynamic aspect lurking around the corner on the very last line where we call through the weakly-typed delegate passing in three objects which just happen to be a string and two ints, causing the lookup for a Substring method applied to s (becoming “Bart”) with arguments a and b (respectively 1 and 2) to succeed. The important thing here though is that a “Substring” method with a compatible signature might be available on another type, maybe type Bar, but taking in two longs:

class Bar
{
    public Foo Substring(long a, long b) { … }
}

The calling code would still work and the console would print the result of Foo.ToString on the instance returned by Bar.Substring. What it takes to make this work consists of three things:

  • Dynamic expression trees (i.e. as the one above with stripped type information);
  • IL code generation at runtime on the fly (to produce the delegate “fun” in the sample above)
  • Binders (things that provide runtime support to resolve method calls)

Of course you could go much further than this with complete ASTs (the big brothers to expression trees) and “rules” but we’re not going to reinvent the DLR :-). Martin Maly has quite some information on those topics on his blog (must-reads!). Today we’ll cover the first bullet point.

 

Our dynamic expression trees

To disambiguate with the LINQ expression trees, let’s sneak the word Dynamic in, making our sample look like:

ParameterDynamicExpression s = DynamicExpression.Parameter(“s”);
ParameterDynamicExpression a = DynamicExpression.Parameter(“a”);
ParameterDynamicExpression b = DynamicExpression.Parameter(“b”);

LambdaDynamicExpression data = DynamicExpression.Lambda(
    DynamicExpression.Call(s, “Substring”, a, b),
    s, a, b
);

Delegate fun = data.Compile();
Console.WriteLine(fun.DynamicInvoke(“Bart”, 1, 2));

All of those *DynamicExpression classes extend the DynamicExpression base class while having a factory method on DynamicExpression too, following the design of LINQ’s expression trees. We’ll omit the NodeType property for simplicity and the Type property, because we obviously don’t want a static type to be associated with each expression tree node. We’ll also get rid of a lot of node types, just leaving the factories in for our three node types:

image

So, how does this look like? The factory methods will be just convenient syntax around internal constructor calls producing the concrete node types. In addition, we’ll override ToString to produce a friendly-on-the-eye string representation of expression trees, much like our static LINQ friends. First, the DynamicExpression base class:

abstract class DynamicExpression
{
    public static ParameterDynamicExpression Parameter(string name)
    {
        return new ParameterDynamicExpression(name);
    }

    public static MethodCallDynamicExpression Call(DynamicExpression instance, string method, params DynamicExpression[] arguments)
    {
        return new MethodCallDynamicExpression(instance, method, arguments);
    }

    public static LambdaDynamicExpression Lambda(DynamicExpression body, params ParameterDynamicExpression[] parameters)
    {
        return new LambdaDynamicExpression(body, parameters);
    }
    protected internal abstract void ToString(StringBuilder sb);

    public override string ToString()
    {
        StringBuilder sb = new StringBuilder();
        ToString(sb);
        return sb.ToString();
    }
}

We’ll extend this class a bit more in the next part where we’ll tackle compilation, but let’s move on to each of the three subtypes right now:

sealed class ParameterDynamicExpression : DynamicExpression
{
    internal ParameterDynamicExpression(string name)
    {
        Name = name;
    }

    public string Name { get; private set; }

    protected internal override void ToString(StringBuilder sb)
    {
        sb.Append(Name);
    }
}

Nothing surprising here. The expression for a dynamic method call is a slightly bit more complicated :-)…

sealed class MethodCallDynamicExpression : DynamicExpression
{
    internal MethodCallDynamicExpression(DynamicExpression instance, string method, params DynamicExpression[] arguments)
    {
        Object = instance;
        Method = method;
        Arguments = new ReadOnlyCollection<DynamicExpression>(arguments);
    }

    public ReadOnlyCollection<DynamicExpression> Arguments { get; private set; }
    public DynamicExpression Object { get; private set; }
    public string Method { get; private set; }
    protected internal override void ToString(StringBuilder sb)
    {
        Object.ToString(sb);
        sb.Append(".");
        sb.Append(Method);
        sb.Append("(");

        int n = Arguments.Count;
        for (int i = 0; i < n; i++)
        {
            Arguments[i].ToString(sb);
            if (i != n - 1)
                sb.Append(", ");
        }

        sb.Append(")");
    }
}

I told’ya it was going to be mind-blowing. The core thing to notice though is the composability because of the use of DynamicExpressions as the Object (i.e. the instance where we’ll invoke the method on) and the Arguments collection members. Also notice we don’t support static method calls in here (for which Object would be null – you can envision the right checking in the factory method, omitted for brevity) although it would be perfectly possible to come up with such a thing (think about “global functions” for example, but remember we don’t have a type that tells us where to look for the method – ideally you’d have a mixture of statically and dynamically typed trees interwoven). Oh, and the pretty printing logic in ToString isn’t too complex either…

Finally, let’s move on to the lambda expression class:

sealed class LambdaDynamicExpression : DynamicExpression
{
    internal LambdaDynamicExpression(DynamicExpression body, params ParameterDynamicExpression[] parameters)
    {
        Body = body;
        Parameters = new ReadOnlyCollection<ParameterDynamicExpression>(parameters);
    }

    public DynamicExpression Body { get; private set; }
    public ReadOnlyCollection<ParameterDynamicExpression> Parameters { get; private set; }

    public Delegate Compile()
    {
        return null;
    }
    protected internal override void ToString(StringBuilder sb)
    {
        sb.Append("(");

        int n = Parameters.Count;
        for (int i = 0; i < n; i++)
        {
            Parameters[i].ToString(sb);
            if (i != n - 1)
                sb.Append(", ");
        }

        sb.Append(") => ");
        Body.ToString(sb);
    }
}

Same deal concerning parameterization based on DynamicExpression instances. I promise you the Compile method will be pretty interesting to say the least, so stay tuned for the next post!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

By now, most of my blog readers will be familiar with the simple concept of expression trees in C# 3.0 and VB 9.0. A quick recap. What’s the type of the expression below?

(string s, int a, int b) => s.Substring(a, b)

Shockingly, you can’t tell. Why? Lambdas have two forms of representation: code (as anonymous methods) or data (as expression trees). One more time:

Func<string, int, int, string> code = (string s, int a, int b) => s.Substring(a, b);

produces

Func<string, int, int, string> code = delegate (string s, int a, int b) { return s.Substring(a, b); };

where

Expression<Func<string, int, int, string>> data = (string s, int a, int b) => s.Substring(a, b);

produces (deep breadth)

ParameterExpression s = Expression.Parameter(typeof(string), “s”);
ParameterExpression a = Expression.Parameter(typeof(int), “a”);
ParameterExpression b = Expression.Parameter(typeof(int), “b”);

Expression<Func<string, int, int, string>> data = Expression.Lambda<Func<string, int, int, string>>(
    Expression.Call(s, typeof(string).GetMethod(“Substring”, new Type[] { typeof(int), typeof(int) }), a, b),
    s, a, b
);

When calling the Compile method on the produced (lambda-expression) data object we’ll get exactly the same IL code but generated at runtime through the form of a (delegate pointing at a) dynamic(ally generated) method using Reflection.Emit. So far, so good. But what are the characteristics of the expression tree’s generated code? Two things:

  • statically typed
  • early-bound

In more human terms, we know at compile time the type of all the involved expressions – at the entry points (i.e. the leaf levels) we’re passing it in with uttermost detail (see the Parameter factory method’s first argument for instance) but all intermediate nodes in the expression tree have a type too. E.g. the Expression.Call factory call returns a MethodCallExpression whose wrapped method call’s return type is System.String, hence that becomes the type of the node. Talking about method calls, those are bound at compile time too: we know precisely what method to call because of all the type information available about the arguments.

Isn’t this cool? Sure it is, but what about dynamic languages? Are those able to use this particular form of expression trees? The simple answer is no; well, at least not in a dynamic way, meaning with dynamic typing (i.e. the type of every node is determined at run time) and late binding for methods (i.e. we hope to find a suitable method overload at runtime). What can we do about this? Here we’re getting in the realm of DLR stuff and such. This blog series is not about DLR itself though, it’s rather about outlining some crucial concepts of dynamic typing including “dynamic expression trees” emitting dynamic call sites using binders.

In the first part coming up soon, we’ll start by investigating how to build dynamic expression trees.

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

By now, most – if not all – readers of my blog will be familiar with this C# 3.0 and VB 9.0 feature called Local Variable Type Inference or Implicitly Typed Local Variables. The idea is simple: since the compiler knows (and hence can infer) type information for expressions, also referred to as rvals, there’s no need for the developer to say the type. In most cases it’s a convenience, for example:

Dictionary<Customer, List<PhoneNumber>> phonebook = new Dictionary<Customer, List<PhoneNumber>>();

That’s literally saying the same thing twice: declare a variable of type mumble-mumble and assign it a new instance of type mumble-mumble. Wouldn’t it be nice just to say:

var phonebook = new Dictionary<Customer, List<PhoneNumber>>();

while it still means exactly the same as the original fragment? That’s what this language feature allows us to do without loosing any of the strong typing. The reason it’s very convenient in the sample above is because of the introduction of arbitrary type construction capabilities due to generics in CLR 2.0. Before this invention, types couldn’t compose arbitrarily big and type names tend to be not too long-winded (namespaces help here too).

As convenient as the case above can be, sometimes type inference is a requirement which is introduced by the invention of anonymous types. Typically those are used in projection clauses of LINQ queries although they can be used in separation as well. E.g.:

var res = from p in Process.GetProcesses() select new { Name = p.ProcessName, Memory = p.WorkingSet64 };

This piece of code gives birth to an anonymous type with two properties Name and Memory (notice the type of those properties is inferred in a similar way from their assigned right-hand side) which is – as the name implies – a type with an unspeakable name. In reality the above produces something like:

IEnumerable<AnonymousType1> res = from p in Process.GetProcesses() select new { Name = p.ProcessName, Memory = p.WorkingSet64 };

where the AnonymousType1 portion is unknown to the developer, so type inference comes to the rescue.

Alright. But when is it appropriate to use the type inference feature? Here are some personal rules I tend to apply quite strictly:

  • Do use type inference…
    • where anonymous types are used – you can’t go without it (unless you want to treat them as System.Object of course and only care about their ToString method or so):

      var point = new { X = 10, Y = 5 }; //OK – what else could you do?
      var res = from p in Process.GetProcesses() select new { Name = p.ProcessName, Memory = p.WorkingSet64 }; //OK – what else could you do?
    • when the right-hand side explicitly states the type or the type is clearly inferable by humans given the context:

      var phonebook = new Dictionary<Customer, List<PhoneNumber>>(); //OK – object construction, with generics
      var point = new Point { X = 10, Y = 5 }; //OK – object construction
      var
      customer = (Customer)someObject; //OK – cast
      var products = objects.Cast <Product>(); //Debatable – clearly something with Product objects, but a List<T>, a T[], an IEnumerable<T>, or …? Also, the type is mentioned quite far to the right, which doesn’t work too well with left-to-right parsing humans
  • Don’t use type inference…
    • for assigning constants to variables of built-in types, e.g. what’s the type of the variables below:

      var i = 0123456789; //NOK – an Int32
      var l = 9876543210; //NOK – an Int64
      var name = “Bart”; //Debatable – what do you gain?
    • for “smart” type inference in foreach loops (unless you’re faced with a source of anonymous types):

      foreach (var x in xs) //Debatable – depending on meaningful variable names there might be “good” exceptions to the rule
          ;

      Moreover, foreach inserts casts for you if the source sequence is just an IEnumerable (i.e. not “Of T” aka “<T>”), so the best guess with type inference would be System.Object.
    • when the right-hand side doesn’t clearly indicate the type:

      var something = someObject.WeirdMethod().AnotherProperty; //NOK – need to know the specific API
    • if you want to forcefully exercise some abstraction, e.g. because of your development methodology allowing for “planned refactorings” down the road:

      IAnimal animal1 = new Lion(); //OK
      var animal2 = new Giraffe(); //NOK – will be the most specific type, i.e. Giraffe

      This is an interesting one as all of the refactoring support in the IDE will be based on the most specific type and with var, you force it into the most specific type.

Also, it’s important to realize that mechanical changes to variable declarations (for fun?) can yield undesired behavior due to a change in semantics. A few cases pop to mind:

  • Lambdas don’t play well with type inference. A lambda can either be represented as code or as data (through an expression tree), so without saying what you want, the compiler can’t know. Indeed, not every rhs has a type by itself:

    Func<int> f = () => 123;
    Expression<Func<int>> e = () => 123;
  • Implicit conversion – the long that became an int:

    checked
    {
        long i = 1; // don’t change to var…
        while (true)
            Console.WriteLine(i *= 2); // quiz: does i <<= 1 have the same effect?
    }
  • Explicit interface implementations:
  • static void Main(string[] args)
    {
        IBar b1 = new Bar();
        b1.Foo();
    
        var b2 = new Bar();
        b2.Foo();
    }
    interface IBar
    {
        void Foo();
    }
    
    class Bar : IBar
    {
        public void Foo()
        {
            Console.WriteLine("Bar.Foo");
        }
    
        void IBar.Foo()
        {
            Console.WriteLine("IBar.Foo");
        }
    }
  • Method hiding:
  • static void Main(string[] args)
    {
        Foo f1 = new ExtendedFoo();
        f1.Bar();
    
        var f2 = new ExtendedFoo();
        f2.Bar();
    }
    class Foo
    {
        public virtual void Bar()
        {
            Console.WriteLine("Foo.Bar");
        }
    }
    
    class ExtendedFoo : Foo
    {
        public new void Bar()
        {
            Console.WriteLine("ExtendedFoo.Bar");
        }
    }

In the end, as usual, there’s no silver bullet. However, one should optimize code for reading it (write-once, read-many philosophy). When trying to understand programs (at least imperative ones <g>) we already have to do quite some mental “step though” to absorb the implementation specifics with loops, conditions, class hierarchies, etc. We shouldn’t extend this process of mental debugging or reverse engineering with type inference overhead in cases where it’s not immediately apparent what the intended type is. Even though the IDE will tell you the type of an implicitly-typed local when hovering over it, it’s not the kind of thing we want to rely on to decipher every single piece of code. Similarly, IntelliSense is working great for implicitly typed local variables, but that only affects the write-once side of the story.

After all, every powerful tool imposes a danger when misused. Type inference is no different in this respect.

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

I didn’t intend to make this a series of posts but that’s the way things go. Based on feedback from readers and additional questions raised, one decides that add that little bit more to it and ultimate you’re writing a sequel. Where have we been on this journey? First, we took a look at the abstract concept of currying in Curry for dummies. Next, evaluation strategies were outlined in Curry for dummies cont'd - A note on purity, outlining that formal substitution relies on assumptions about the expression involved, i.e. they better are side-effect free to be able to employ call-by-name semantics as opposed to – the much embraced in the imperative world – call-by-value semantics. To challenge the readers, I wrote this:

Readers looking for a challenge are invited to think about how it would be possible to adapt the original (substitution-driven) Curry for dummies code to work with call-by-need semantics; in other words, how can a lambda expression be applied (the number of arguments provided is not really relevant in this discussion) with arguments that are lazily (one time at most) evaluated? I'll post the answer some time soon.

What I’m suggesting here is to implement call-by-need semantics for applying (in formal terms, using beta-reduction) arguments to functions represented as lambdas. To help with the basic plumbing, I provided the Cell<T> class that looks like this:

class Cell<T>
{
    private bool _assigned;
    private Func<T> _func;
    private T _value;

    public Cell(Func<T> func)
    {
        _func = func;
    }

    public T Value
    {
        get
        {
            if (!_assigned)
            {
                _value = _func();
                _assigned = true;
            }

            return _value;
        }
    }
}

In essence, this class allows us to evaluate a function upon the first call to retrieve its value. For example,

var val = new Cell<long>(() => DateTime.Now.Ticks);
Console.WriteLine(DateTime.Now.Ticks + " " + val.Value);
Thread.Sleep(1000);
Console.WriteLine(DateTime.Now.Ticks + " " + val.Value);

To convince you it really doesn’t change its mind after the initial evaluation, look at the following output:

image

The orange is the capture value and is stable. Obviously it’s later than the green one (why? ironically because of call-by-value semantics to String.Concat in the first Console.WriteLine) and earlier than the red one one second later. Anyway, this is our “smart function evaluator” which obviously relies on the fact that the function it captures doesn’t change its mind. The sample above violates this rule but it provides a way to show you it really works.

Next, let’s take a look at the signature for function application:

static LambdaExpression CallBy____(LambdaExpression func, params Expression[] parameters)

We want to create three such functions:

  • CallByValue
  • CallByName
  • CallByNeed

all of which will have the same signature. The way the functions work is as follows: given a lambda expression and a set of parameters, we’ll return another lambda expression that calls the original function, possibly having some remaining parameters. A sample:

var a = Expression.Parameter(typeof(int), "a");
var b = Expression.Parameter(typeof(int), "b");

var add = Expression.Lambda(Expression.Add(a, b), a, b); // represents (int a, int b) => a + b
var addOne = CallByValue(add, Expression.Constant(1));   // represents (int b) => 1 + b
var three = CallByValue(addOne, Expression.Constant(2)); // represents () => 3

If we’d call through the last function, three, without any parameters, we’d get 3. For call-by-value semantics, it would look like:

() => Invoke(b => Invoke((a, b) => (a + b),1,b),2)

but that will become clearer as we move forward. Time to switch gears and start implementing all of the strategies.

 

Call-by-value

This is the simplest one. We won’t change the function itself (so, no forms of substitution are carried out in the lambda body), rather we’ll call it with the (evaluated) supplied arguments, keeping remaining arguments. Here’s what it looks like:

static LambdaExpression CallByValue(LambdaExpression func, params Expression[] parameters)
{
    if (parameters.Length > func.Parameters.Count)
        throw new InvalidOperationException("Too many parameters specified.");

    ParameterExpression[] lambdaParams = func.Parameters.Skip(parameters.Length).ToArray();
    return Expression.Lambda(Expression.Invoke(func, parameters.Concat(lambdaParams)), lambdaParams);
}

Ignoring the validation, we create a new lambda expression with the remaining parameters, and a body that calls the original lambda with the supplied arguments. A sample:

var a = Expression.Parameter(typeof(int), "a");
var b = Expression.Parameter(typeof(int), "b");

var add = Expression.Lambda(Expression.Add(a, b), a, b); // represents (int a, int b) => a + b
var addOne = CallByValue(add, Expression.Constant(1));   // represents (int b) => 1 + b

The CallByValue call above does the following:

ParameterExpression[] lambdaParams = func.Parameters.Skip(parameters.Length).ToArray();

becomes { a, b }.Skip(1).ToArray() = { b }. So, the lambdaParams variable contains the remaining parameters. Next, it returns a new lambda expression that does the following:

Expression.Invoke(func, parameters.Concat(lambdaParams)

which is semantically equivalent to func(1, b). To clarify this, the parameters are 1 (which is passed in as Expression.Constant(1)) and b, the remaining parameter(s). More precisely, we keep the number of arguments to call the original lambda the same, but we’ve concretized one of them (i.e. a := 1). This lambda body is now wrapped in a new lambda that only has b as a parameter. In the end it looks like (pseudo-code):

b => ((a, b) => a + b)(1, b)

where the outer b is different from the inner b (they have different scope) and the binding of a with the constant 1 is pointed out. The ToString result of the produced lambda is:

b => Invoke((a, b) => (a + b),1,b)

What are the characteristics of this approach?

  • Arguments are evaluated before calling the function, which means they are evaluated exactly once.
  • As an implication of the previous, arguments that are not used in the body of the function yield redundant evaluations.
  • An argument that evaluates to the “denotational bottom” (e.g. throws an exception or doesn’t terminate) prevents the call from being made (bail out early, but maybe – see previous point – for no real reason).
  • On the positive side, the technique is easy to understand and compatible with lots of languages (e.g. for interop reasons).

 

Call-by-name

Slightly more complicated but still easy to understand is call-by-value. The idea here is to substitute occurrences of the parameters in the function’s body to create a new function. To put it another way, we don’t wrap the original function but clone it and rewrite it as a new function with fewer arguments. For the same sample:

var a = Expression.Parameter(typeof(int), "a");
var b = Expression.Parameter(typeof(int), "b");

var add = Expression.Lambda(Expression.Add(a, b), a, b); // represents (int a, int b) => a + b
var addOne = CallByName(add, Expression.Constant(1));   // represents (int b) => 1 + b

the comments on the right actually point out literally what’s happening. Indeed, a ToString of the resulting lambda looks like:

b => 1 + b

It’s important to realize that the ‘1’ here could be an arbitrary complex expression that’s put in place wherever ‘a’ was found (because of the binding to the parameter). So, if you’d have the following:

var a = Expression.Parameter(typeof(int), "a");
var twice = Expression.Lambda(Expression.Add(a, a), a); // silly way to double things: (int a) => a + a
var six = CallByName(twice, Expression.Add(Expression.Constant(1), Expression.Constant(2))); // calling twice with argument (1 + 2)

we’d get, by formal substitution of a in (int a) => a + a,

() => (1 + 2) + (1 + 2)

while call by value would evaluate the (1 + 2) first, resulting in:

() => 3 + 3

How do we implement it? The original Curry for dummies post introduces the use of the expression visitor which we inherit from to create an expression tree cloner that replaces parameter occurrences by a given expression like this:

class CurryVisitor : ExpressionVisitor
{
    private Dictionary<ParameterExpression, Expression> _parameters;

    public CurryVisitor(Dictionary<ParameterExpression, Expression> parameters)
    {
        _parameters = parameters;
    }

    protected override Expression VisitParameter(ParameterExpression p)
    {
        if (_parameters.ContainsKey(p))
            return _parameters[p];

        return base.VisitParameter(p);
    }

    public Expression Clone(Expression exp)
    {
        return base.Visit(exp);
    }
}

Using this tool – that we’ll reuse in the call-by-need implementation as well – we can write call-by-name like this:

static LambdaExpression CallByName(LambdaExpression func, params Expression[] parameters)
{
    if (parameters.Length > func.Parameters.Count)
        throw new InvalidOperationException("Too many parameters specified.");

    var assignments = new Dictionary<ParameterExpression, Expression>();

    for (int i = 0; i < parameters.Length; i++)
    {
        ParameterExpression parameter = func.Parameters[i];
        Expression value = parameters[i];

        if (!parameter.Type.IsAssignableFrom(value.Type))
            throw new InvalidOperationException("Incompatible parameter value type for parameter " + parameter.Name);

        assignments[parameter] = value;
    }

    var visitor = new CurryVisitor(assignments);
    return Expression.Lambda(visitor.Clone(func.Body), func.Parameters.Skip(parameters.Length).ToArray());
}

The most important thing here is that we go through all of the specified parameters (in the sample above that’s the expression (1 + 2)), hand-in-hand with the parameter expressions that correspond to it, adding them to a dictionary. For our sample, the dictionary will contain

a –> (1 + 2)

which is then fed in to the CurryVisitor to clone the original lambda’s body (i.e. a + a) while replacing the dictionary key occurrences (a) by the mapped substitution (1 + 2). The new body will be (1 + 2) + (1 + 2), which is hooked up as the body for the new lambda expression with the remaining arguments (in this case none at all) in precisely the same way as in call-by-value.

What are the characteristics of this approach?

  • Arguments are not evaluated when they are not needed in the function body for the particular invocation.
  • On the sunny side, too, fatal side effects (denotational bottom) have no effects for unused arguments.
  • But … arguments may be evaluated multiple times, which means side-effects would be multiplied.
  • Also, in order to do the substitution we need to gain access to the function itself, which would be a runtime (in the two senses of the word) task.

 

Call-by-need

As mentioned in Curry for dummies cont'd - A note on purity, call-by-need is an improvement on top of call-by-name. It follows the same principles of substitution but it employ memoization, a caching technique to remember the evaluation result for an expression, to avoid reevaluation expressions. In other words, it eliminates common subexpressions that are introduced by formal parameter substitution. To continue with the same sample, consider:

var a = Expression.Parameter(typeof(int), "a");
var twice = Expression.Lambda(Expression.Add(a, a), a); // silly way to double things
var six = CallByNeed(twice, Expression.Add(Expression.Constant(1), Expression.Constant(2))); // calling twice with argument (1 + 2)

What happens now though is something I’m going to denote using some special syntax. When evaluating twice, it’s rewritten as:

() => [| () => 1 + 2 |] + [| () => 1 + 2 |]

The cool thing about denotational semantics is you can invent your own symbols :-). Here I’m introducing what I’d call pillar syntax: i.e. [| … |]. The body of it denotes a parameter-less function using lambda syntax. In practical terms this means we have a delay-loaded or lazy-loaded value: it’s only calculated on-demand. Now by means of common subexpression elimination, the compiler can rewrite this as follows (relying on the fact that the function would be pure, i.e. there are no side-effects that call for the need of doing the evaluation every time again):

x = [| () => 1 + 2 |]
() => x + x

The semantics are as follows: when declared ("stage 0” if you want), the function is not evaluated, it’s simply cached. Next, when evaluated for the first time (“stage 1”), the function is called and the value is kept. I’m not building a formal specification here (I’m defining the “valuation function” in words after all), but realize that I’m introducing some state mutation here (let’s not get into monads and beasts like unsafePerformIO this time). On subsequent evaluations, the function isn’t called but the cached value is returned straight away (“stage > 1”). So, applying our function above becomes:

six()
= let x = [| () => 1 + 2 |] in x + x
= [| () => 1 + 2 |] + [| () => 1 + 2 |]
= [| () => 3 |] + [| () => 1 + 2 |]
= [| 3 |] + [| 3 |] 'here mutation happens; x is a “reference” variable
= 6

This is precisely what our Cell<T> does. How can we make this work though? What we need is an “environment” in which we keep all the constructed cells. Such an environment establishes bindings between parameters and the corresponding cell that captures the bound expression lifted in a function. This needs some clarification. When calling CallByNeed in the sample above, the argument (1 + 2) needs to be wrapped in a parameter-less function to make it “on-demand” evaluated. The parameter to call “twice” with is:

Expression.Add(Expression.Constant(1), Expression.Constant(2)) // 1 + 2

and needs to become

Expression.Lambda(Expression.Add(Expression.Constant(1), Expression.Constant(2))) // () => 1 + 2

Next, this lambda needs to be wrapped in a Cell<T>. T is inferred from the type of the parameter, i.e. int, and the constructor of Cell<T> takes in a Func<T>. We can turn a LambdaExpression into a delegate by calling Compile on it. We do this for all the parameters (in the same we only have one) and keep the resulting cells in a dictionary mapping the name of the parameter (a string, in this running sample “a”) onto the corresponding cell. This piece of voodoo plumbing ensures that we have just one reference to a cell per parameter and that’s the whole point of the memoization: we don’t want to reevaluate parameters when they occur in the function body multiple times. To put this in terms of the sample:

var environment = new Dictionary<string, object>();

environment["a"] = new Cell<int>(() => 1 + 2);

One more question to answer now is how to carry out formal substitution? More specially, what should we replace ParameterExpression occurrences with during the “tree visitation” by the CurryVisitor? The answer isn’t too hard either: a lookup into the environment dictionary, returning a Cell<T>, on which we can call Value causing either evaluation (“stage 1”) or return of the memoized value (“stage > 1”):

((Cell<int>)environment["a"]).Value

In other words, our call to twice returns an expression tree like this:

() => ((Cell<int>)environment["a"]).Value + ((Cell<int>)environment["a"]).Value

You’ll wonder where environment is kept – the answer is in some kind of “closure” that’s created when the lambda expression is compiled, but you can consider this to be an irrelevant detail at this point (if you’re really curious, invoke the Method property on the generated delegate and observe the passed-in ExecutionScope object).

Time to dive in the code:

static LambdaExpression CallByNeed(LambdaExpression func, params Expression[] parameters)
{
    if (parameters.Length > func.Parameters.Count)
        throw new InvalidOperationException("Too many parameters specified.");

    var environment = new Dictionary<string, object>();
    var assignments = new Dictionary<ParameterExpression, Expression>();

    MethodInfo envItem = typeof(Dictionary<string, object>).GetMethod("get_Item");

    for (int i = 0; i < parameters.Length; i++)
    {
        ParameterExpression parameter = func.Parameters[i];
        Expression value = parameters[i];

        if (!parameter.Type.IsAssignableFrom(value.Type))
            throw new InvalidOperationException("Incompatible parameter value type for parameter " + parameter.Name);

        LambdaExpression lazyValue = Expression.Lambda(value);
        object cell = typeof(Cell<>).MakeGenericType(value.Type).GetConstructors()[0].Invoke(new object[] { lazyValue.Compile() });

        environment[parameter.Name] = cell;
        assignments[parameter] = Expression.Property(Expression.Convert(Expression.Call(Expression.Constant(environment), envItem, Expression.Constant(parameter.Name)), typeof(Cell<>).MakeGenericType(value.Type)), "Value");
    }

    var visitor = new CurryVisitor(assignments);
    return Expression.Lambda(visitor.Clone(func.Body), func.Parameters.Skip(parameters.Length).ToArray());
}

This is roughly the same as the CallByName implementation (indeed, some refactoring could be done), but the most notable differences (indicated in bold) are:

  • Besides assignments, we’re building up an environment which consists of mappings from parameter.Name strings onto cell objects capturing the lambda built around the parameter expression.
  • The assignments themselves are property .Value calls on the result of retrieving the cell from the environment through the get_Item dictionary indexer, passing in the parameter.Name as the key, and casting the result to Cell<T>.

The substitution using the CurryVisitor is the same as before, only the mappings of ParameterExpressions onto the replacement values are different.

What are the characteristics of this approach?

  • Same as call-by-name but:
    • Arguments are evaluated once at most, which brings it closer to call-by-value compared to call-by-name.
    • However, formal substitution is still the driving mechanism here.
  • Also notice we need access to the implementation of the function to do the substitution. This access is not shallow – if a lambda calls into another function, the laziness of arguments needs to be propagated all the way through. When you hit the border where a call into the non-pure lazy world is needed (e.g. interop code), the landscape changes into call-by-value with eager evaluation of the arguments at the call-site. However, laziness is still beneficial because the code in between the function entry point and the interop code much lower in the stack (including OS function calls that are typically call-by-value) might be separated by a bunch of code paths that do not necessarily need to carry on all of the arguments of the original function. In other words, a (not necessarily proper) subset of the input arguments has the potential of getting discarded without any need for evaluation while others will be “degraded” to forced eagerness.

 

The final test

To test this stuff, I wrote this little test framework:

static Dictionary<string, Func<LambdaExpression, Expression[], LambdaExpression>> s_tests
= new Dictionary<string, Func<LambdaExpression, Expression[], LambdaExpression>> { { "By Value", CallByValue }, { "By Name", CallByName }, { "By Need", CallByNeed } }; static void Test(string testName, LambdaExpression func, params Expression[] parameters) { Test(testName, null, func, parameters); } static void Test(string testName, Action cleanUp, LambdaExpression func, params Expression[] parameters) { Console.WriteLine(testName); Console.WriteLine(new string('-', testName.Length)); foreach (var test in s_tests.Keys) { LambdaExpression res = s_tests[test](func, parameters); try { // this assumes all parameters have been supplied Console.Write(test + " -> " + res + " = ");
Console.WriteLine(res.Compile().DynamicInvoke()); } catch (Exception ex) { Console.WriteLine(ex.InnerException.Message); } if (cleanUp != null) cleanUp(); } Console.WriteLine(); }

As we’re in a functional mood, the use of a dictionary with delegates shouldn’t be too surprising. In essence, s_tests contains mappings of friendly names to delegate instances pointing at each of the CallBy* methods (which all have the same signature). Notice the use of C# 3.0 collection initializers to build up this dictionary. The test execution harness is simple: it iterates over all of the directory entries, extracts the test and calls it with the given lambda expression and the given parameters (assuming all parameters are “eaten” so that we can call DynamicInvoke without passing in any remaining arguments). There’s also support to clean up shared mutable state which comes in handy to compare results.

Now the tests itself:

static void Main()
{
    var a = Expression.Parameter(typeof(int), "a");
    var b = Expression.Parameter(typeof(int), "b");
    var add = Expression.Lambda(Expression.Add(a, b), a, b); // represents (int a, int b) => a + b
    var one = Expression.Constant(1);
    var two = Expression.Constant(2);
    Test("Add test", add, one, two);

    var bad = Expression.Divide(one, Expression.Constant(0));
    var twice = Expression.Lambda(Expression.Add(a, a), a, b); //doesn't use b
    Test("Eagerness test", twice, one, bad);

    var sideEffect = Expression.Call(typeof(Program).GetMethod("ChangingMind", BindingFlags.NonPublic | BindingFlags.Static), null);
    Test("Laziness test", () => { s_i = 0; }, twice, sideEffect, one /* not used */);
}

static int s_i = 0;

static int ChangingMind()
{
    return s_i++;
}

The first test deals with a pure function – we expect all strategies to come up with the same answer. The second one passes in an unused expression that results in a divide by zero. Call-by-value will crash while the others won’t. Finally, the side-effecting test calls out to a function that has mutating state (which we clean up after every iteration of the test bench since we want to see the effects on a per-strategy basis). This is a bit more subtle. Call-by-value will just call ChangingMind once, before calling the twice function. Call-by-name will duplicate the ChangingMind calls, while call-by-need will still do in-place substitution but because of the memoization with Cell<T> the ChangingMind function is only called once when the parameter is really needed. In fact, it would be a good exercise (left to the reader) to combine the last two tests. Here’s the output:

image

The results are as expected. Mission accomplished. You can download the code here.

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Everyone knows array initializers; they’ve been part of the language since the very beginning. But do you know how this innocent looking construct really works?

var ints = new [] { 1, 2, 3 };

Before we continue, I should point out that the above sample uses a couple of C# 3.0 specific features, namely local variable type inference (var keyword) and implicitly typed arrays (new []). It’s exactly the same as:

int[] ints = new int[3] { 1, 2, 3 };

And actually you could also write:

int[] ints = { 1, 2, 3 };

You might expect the above to work just like:

int[] ints = new int[3];
ints[0] = 1;
ints[1] = 2;
ints[2] = 3;

Unfortunately, that’s not completely right. There’s a hidden subtlety that I’ll point out further on. Let’s put on our “IL freak” T-shirt and dive into the implementation details right now. Here’s what the translation of the original (and by equivalence the second and third, but not the fourth) code fragment results into:

image

Holy cow! What’s up with this <PrivateImplementationDetails>mumblemumble thing? Before I can reveal this, let’s take a look at Q::Main, where I’ve interleaved the stack state after every relevant line (left = top of stack):

.method private hidebysig static void  Main() cil managed
{
  .entrypoint
  // Code size       20 (0x14)
  .maxstack  3
  .locals init (int32[] V_0)
  IL_0000:  nop
  // {}
  IL_0001:  ldc.i4.3
  // {3}
  IL_0002:  newarr     [mscorlib]System.Int32
  // {&int[3]}
  IL_0007:  dup
  // {&int[3], &int[3]}
  IL_0008:  ldtoken    field valuetype '<PrivateImplementationDetails>{8C802ECE-B24C-4A20-AE34-9303FE2DD066}'/'__StaticArrayInitTypeSize=12' '<PrivateImplementationDetails>{8C802ECE-B24C-4A20-AE34-9303FE2DD066}'::'$$method0x6000001-1'
  // {&int[3], &int[3], #'$$method0x6000001-1'}
  IL_000d:  call       void [mscorlib]System.Runtime.CompilerServices.RuntimeHelpers::InitializeArray(class [mscorlib]System.Array,
                                                                                                      valuetype [mscorlib]System.RuntimeFieldHandle)
  // {&int[3]}
  IL_0012:  stloc.0
  // {}
  IL_0013:  ret
} // end of method Q::Main

Let’s do a line-by-line analysis. On lines IL_0001 and IL_0002 we create a new array with element type System.Int32 and dimension 3. IL_0007 is a bit more surprising: the reference to the array is duplicated on the evaluation stack. Why? Blindly assume for a second that IL_0008 and IL_000d are two lines that initialize the array (we’ll come back to that in just a second). Now look one line further to IL_0012, where the value on top of the stack – again the array – is assigned to local variable with index 0, i.e. our “ints” variable. What would happen if we’d assign the array to the local variable already in line IL_0007, like this?

ldc.i4.3
newarr     [mscorlib]System.Int32
stloc.0
ldloc.0

ldtoken    field valuetype '<PrivateImplementationDetails>{8C802ECE-B24C-4A20-AE34-9303FE2DD066}'/'__StaticArrayInitTypeSize=12' '<PrivateImplementationDetails>{8C802ECE-B24C-4A20-AE34-9303FE2DD066}'::'$$method0x6000001-1'
call       void [mscorlib]System.Runtime.CompilerServices.RuntimeHelpers::InitializeArray(class [mscorlib]System.Array,
                                                                                          valuetype [mscorlib]System.RuntimeFieldHandle)

Well, the assignment wouldn’t be atomic anymore: from that point on, an external observer watching the local variable would already be able to see the array but in a incompletely initialized state, i.e. the elements wouldn’t be there yet. And that initialization is precisely what IL_0008 and IL_000d are doing. So, the compiled code is not equivalent to:

int[] ints = new int[3];
ints[0] = 1;
ints[1] = 2;
ints[2] = 3;

It’s more accurate to say it’s semantically equivalent to:

int[] t = new int[3];
t[0] = 1;
t[1] = 2;
t[2] = 3;
int[] ints = t;

Although the implementation avoids the creation of two local variables as we can see in the IL code. This leaves us with two dark matter lines:

  IL_0008:  ldtoken    field valuetype '<PrivateImplementationDetails>{8C802ECE-B24C-4A20-AE34-9303FE2DD066}'/'__StaticArrayInitTypeSize=12' '<PrivateImplementationDetails>{8C802ECE-B24C-4A20-AE34-9303FE2DD066}'::'$$method0x6000001-1'
  IL_000d:  call       void [mscorlib]System.Runtime.CompilerServices.RuntimeHelpers::InitializeArray(class [mscorlib]System.Array,
                                                                                                      valuetype [mscorlib]System.RuntimeFieldHandle)

No fears, this isn’t too hard either. Essentially we’re seeing a call to RuntimeHelpers.InitializeArray passing in our array (which is on the top of the stack after executing IL_0007) and a RuntimeFieldHandle, which is the representation of a “field” pointer referenced through an IL token which is loaded in IL_0008. That token corresponds to the line highlighted below:

image

Actually the indicated line a static field in some private class with an unspeakable, obviously compiler-generated, name. There are a few important things to notice here. First, this private class has a nested class called __StaticArrayInitTypeSize=12. This class represents any array with total native byte size (i.e. the sum of the sizes of all elements) of 12 bytes. How we come to 12 bytes is trivial: an Int32 is 32-bits, or 4 bytes, and we have three of those, hence 12 bytes. Notice this class extends System.ValueType. I guess the readers are familiar with the implications of value types with respect to stack allocation, so let’s not go there. How does the type actually get its 12 bytes? Just putting somewhere in the name isn’t enough for the CLR obviously, so if you take a look at the implementation (using ildasm.exe q.exe /out=q.il, opening the generated q.il file) you’d see:

.class private auto ansi '<PrivateImplementationDetails>{8C802ECE-B24C-4A20-AE34-9303FE2DD066}'
       extends [mscorlib]System.Object
{
  .custom instance void [mscorlib]System.Runtime.CompilerServices.CompilerGeneratedAttribute::.ctor() = ( 01 00 00 00 )
  .class explicit ansi sealed nested private '__StaticArrayInitTypeSize=12'
         extends [mscorlib]System.ValueType
  {
    .pack 1
    .size 12
  } // end of class '__StaticArrayInitTypeSize=12'

  .field static assembly valuetype '<PrivateImplementationDetails>{8C802ECE-B24C-4A20-AE34-9303FE2DD066}'/'__StaticArrayInitTypeSize=12' '$$method0x6000001-1' at I_00002050
} // end of class '<PrivateImplementationDetails>{8C802ECE-B24C-4A20-AE34-9303FE2DD066}'

The .size directive instructs the CLR that a memory block of the specified size (in bytes) should be allocated upon creation of an instance of the type. If you’re curious about the .pack directive, this one specifies that the fields within the class should be placed at addresses that are a multiple of the specified value (only powers of 2 up to 128 are supported). This is used primarily for COM interop to match up unmanaged data type layouts.

On to the field now:

.field static assembly valuetype '<PrivateImplementationDetails>{8C802ECE-B24C-4A20-AE34-9303FE2DD066}'/'__StaticArrayInitTypeSize=12' '$$method0x6000001-1' at I_00002050

Its type is straightforward, albeit a quite long name due to the nesting of classes (notice the separator for nested classes is /). The name is indicated in green but more interesting is the “at” part indicated in red. This is a reference to a so-called data label which is basically a pointer into the PE file itself. In the ILDASM output you’ll see the following:

.data cil I_00002050 = bytearray (
                 01 00 00 00 02 00 00 00 03 00 00 00)

This is the declaration of the data label and is set to a byte array with values (in little-endian) 01000000, 02000000 and 03000000 – or in readable terms: 1, 2 and 3. Now we should understand how the call to InitailizeArray works:

call       void [mscorlib]System.Runtime.CompilerServices.RuntimeHelpers::InitializeArray(class [mscorlib]System.Array,
                                                                                          valuetype [mscorlib]System.RuntimeFieldHandle)

Given the array object, which already has information about the size (we did ldc.i4.3; newarr [mscorlib]System.Int32 before), and a pointer to the field that just wraps the data at the specified ‘at’ offset, the runtime is capable of loading the calculated amount of bytes (3 x 4 = 12) from the specified location, resulting in an initialized array. I told you it was easy, or didn’t I? Actually for the real geeks, where does I_00002050 come from? It’s the so-called RVA or Relative Virtual Address, that is the relative offset to the start of the PE file. Using dumpbin we can dump the executable PE file (dumpbin /all q.exe) which shows this (click the image to admit you’re a geek):

image

A few more interesting things. The compiler reuses the __StaticArrayInitTypeSize class for all arrays that have the same size. So, writing the following:

int[]  ints  = { 1, 2, 3, 4, 5, 6, 7, 8 };
long[] longs = { 1, 2, 3, 4 };
byte[] bytes = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 };

causes the same type to be used since all of the types are 32 bytes:

.field static assembly valuetype '<PrivateImplementationDetails>{AA6C9D77-5FAD-47E0-8B55-1D8739074F1F}'/'__StaticArrayInitTypeSize=32' '$$method0x6000001-1' at I_00002050
.field static assembly valuetype '<PrivateImplementationDetails>{AA6C9D77-5FAD-47E0-8B55-1D8739074F1F}'/'__StaticArrayInitTypeSize=32' '$$method0x6000001-2' at I_00002070
.field static assembly valuetype '<PrivateImplementationDetails>{AA6C9D77-5FAD-47E0-8B55-1D8739074F1F}'/'__StaticArrayInitTypeSize=32' '$$method0x6000001-3' at I_00002090

.data cil I_00002050 = bytearray (
                 01 00 00 00 02 00 00 00 03 00 00 00 04 00 00 00
                 05 00 00 00 06 00 00 00 07 00 00 00 08 00 00 00)
.data cil I_00002070 = bytearray (
                 01 00 00 00 00 00 00 00 02 00 00 00 00 00 00 00
                 03 00 00 00 00 00 00 00 04 00 00 00 00 00 00 00)
.data cil I_00002090 = bytearray (
                 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 10
                 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F 20)

Furthermore, for arrays with only 1 or 2 elements, a shortcut is taken:

int[] ints = { 1, 2 };

produces the following IL:

.method private hidebysig static void  Main() cil managed
{
  .entrypoint
  // Code size       19 (0x13)
  .maxstack  3
  .locals init (int32[] V_0,
           int32[] V_1)
  IL_0000:  nop
  IL_0001:  ldc.i4.2
  IL_0002:  newarr     [mscorlib]System.Int32
  IL_0007:  stloc.1

  //
  // V_1[0] = 1
  //
  IL_0008:  ldloc.1
  IL_0009:  ldc.i4.0
  IL_000a:  ldc.i4.1
  IL_000b:  stelem.i4

  //
  // V_1[1] = 2
  //
  IL_000c:  ldloc.1
  IL_000d:  ldc.i4.1
  IL_000e:  ldc.i4.2
  IL_000f:  stelem.i4

  //
  // V_0 = V_1
  //

  IL_0010:  ldloc.1
  IL_0011:  stloc.0

  IL_0012:  ret
} // end of method Q::Main

Here the trick of two local variables is used, one (V_1) acting as a temporary variable for the “array under construction”, and another one (V_0) for the final destination variable (ints).

Finally, why was this implementation method (referring to the InitializeArray approach) chosen over a repetitive sequence of array assignment calls? A variety of reasons. First of all, code size. When using InitializeArray, the cost is constant, while for a naive implementation the cost would be 4 instructions (ldloc the array, ldc the index to be assigned to, ldc the value to be assigned, stelem to do the assignment) per element to be initialized. Secondly, the data to be assigned would be fragmented throughout the expanded code, so we can’t benefit from the fact that the data will be stored sequentially in memory (an array is ultimately just a starting address + an element size). So by trading instructions for data, we can gain a lot. Let’s do some kind of meta-programming to illustrate this:

using System;
using System.Text;

class G
{
    static void Main()
    {
        int N = 10000;

        StringBuilder sb = new StringBuilder();
        sb.AppendLine("using System;");
        sb.AppendLine("using System.Diagnostics;");
        sb.AppendLine("");
        sb.AppendLine("class Program");
        sb.AppendLine("{");
        sb.AppendLine("    static void Main()");
        sb.AppendLine("    {");
        sb.AppendLine("        Stopwatch watch = new Stopwatch();");
        sb.AppendLine("        watch.Start();");
        sb.Append    ("        var ints1 = new int[] { "); for (int i = 0; i < N; i++) sb.Append(i + ", "); sb.AppendLine(" };");
        sb.AppendLine("        watch.Stop();");
        sb.AppendLine("        Console.WriteLine(watch.Elapsed);");
        sb.AppendLine("");
        sb.AppendLine("        watch.Reset();");
        sb.AppendLine("        watch.Start();");
        sb.AppendLine("        var ints2_t = new int[" + N + "];");
        for (int i = 0; i < N; i++)
        sb.AppendLine("        ints2_t[" + i + "] = " + i + ";");
        sb.AppendLine("        var ints2 = ints2_t;")
        sb.AppendLine("        watch.Stop();");
        sb.AppendLine("        Console.WriteLine(watch.Elapsed);");
        sb.AppendLine("    }");
        sb.AppendLine("}");

        Console.WriteLine(sb);
    }
}

This generates code like this:

using System;
using System.Diagnostics;

class Program
{
    static void Main()
    {
        Stopwatch watch = new Stopwatch();
        watch.Start();
        var ints1 = new int[] { 0, 1, …, N };
        Console.WriteLine(watch.Elapsed); 

        watch.Reset();
        watch.Start();
        var ints2_t = new int[N];
        ints2_t[0] = 0;
        ints2_t[1] = 1;
        …
        ints2_t[N] = N;
        var ints2 = ints2_t;
        watch.Stop();
        Console.WriteLine(watch.Elapsed);
    }
}

Compiling and executing the resulting program for N=10000 shows:

00:00:00.0000861
00:00:00.0004129

As you can see, the difference is substantial. Hope this post helps to eliminate some compiler obscurity!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

While preparing for another one of my posts, soon to be published, I received the following:

image

What can one do when observing such a message? Since watching a grown man cry is both a pathetic and embarrassing situation, downloading the language specification is a good start. Here are my findings. Section 11.21 on Query Expressions says:

A query expression is an expression that applies a series of query operators to the elements of a queryable collection.

Query operators are what I’m playing with – as will become apparent later on – but what’s supposed to be a “queryable collection”? Somewhere further, in paragraph 11.21.2 on Queryable Types the following is said:

Query expressions are implemented by translating the expression into calls to well-known methods on a collection type. These well-defined methods define the element type of the queryable collection as well as the result types of query operators executed on the collection. Each query operator specifies the method or methods that the query operator is generally translated into, although the specific translation is implementation dependent.

Right, but what makes up a “queryable collection”? Where not getting closer yet but somewhere further in the same paragraph one can make a little jump in the air to express a joyful mood:

A queryable collection type must satisfy one of the following conditions, in order of preference:

  • It must define a conforming Select method.
  • It must have have one of the following methods

    Function AsEnumerable() As CT
    Function AsQueryable() As CT

    which can be called to obtain a queryable collection. If both methods are provided, AsQueryable is preferred over AsEnumerable.
  • It must have a method

    Function Cast(Of T)() As CT

    which can be called with the type of the range variable to produce a queryable collection.

In here CT stands for a (queryable) collection with elements of type T. The definition is actually recursive: one of the three bullets needs to be satisfied in order for something to be “queryable CT”. It’s clear that the latter two act as (the recursive case) escape valves to turn something “non-queryable” into something queryable because their result type is denoted as CT. So, all the power lies ultimately in the first bullet (the base case) on a “conforming Select method”. A bit further in the paragraph we read:

It is not necessary for a collection object to implement all of the methods needed by all the query operators, although every collection object must at least support the Select query operator.

Why this restriction? The VB 9.0 spec doesn’t really tell but actually C# does have a similar rule, which is more explanatory. In the C# 3.0 Specification there’s a paragraph 7.15.2.3 on so-called “Degenerate query expressions”:

A degenerate query expression is one that trivially selects the elements of the source. (…) It is important (…) to ensure that the result of a query expression is never the source object itself, as that would reveal the type and identity of the source to the client of the query. Therefore this step protected degenerate queries written directly in source code by explicitly calling Select on the source. (…)

In other words, something like

from c in customers select s

translates into

customers.Select(c => c)

which looks as unnecessary (in the end the lambda passed in is the identity function) but it makes sure that a query can never degenerate in its original source, which ensures the source is kept hidden (some form of encapsulation if you want) from the query consumer. Indeed, the paragraph continues:

It is then up to the implementers of Select and other query operators to ensure that these methods never return the source object itself.

Let’s turn it into practice. Assume we have the following class definitions:

class Bar
{
    public Foo Where(Func<object, bool> predicate)
    {
        // …
    }
}

class Foo
{
    // …
}

then the following query would translate fine:

var res = from b in new Bar() where true select b;

which strictly speaking translates into

var res = new Bar().Where(b => true).Select(b => b);

but Where already “hides” the original source, so the degenerate Select can be trimmed away:

var res = new Bar().Where(b => true);

The fact the result of b.Where, an instance of Foo, doesn’t have a Select method won’t bit us in this case (notice that Where(b => true) could be treated as a degenerate case as well; however, the compiler doesn’t treat it that way and leaves the Where call in). However, when the query is the following:

var res = from b in new Bar() select b;

the translation would look like

var res = new Bar().Select(b => b)

Dropping Select would make the result equal to the source, which is a violation of the rules in 7.15.2.3, so the compiler complains about the non-existence of Select on class Bar (trivial question: why not on Foo this time?) in this case:

image

So, implementing Select is a bare minimum for query provider implementations (that do not go through IQueryable<T> because those already “inherit” a Select implementation). Here’s the resulting code in VB:

Module W
    Sub Main
        Dim res = From b In New Bar Where True
    End Sub
End Module

Class Bar
    Public Function Where(p As Func(Of Object, Boolean)) As Foo
        Return Nothing
    End Function


    Public Function [Select](s As Func(Of Object, Object)) As Bar
        Return Nothing
    End Function

End Class

Class Foo
End Class

that makes the compiler happy. Notice VB doesn’t require you to say “Select b”, a little but handy feature although it makes degenerate queries even more hidden. Why? Tell me what the following means:

Dim res = From b In New Bar

Indeed, the compiler will insert a Select method call for you (hence the reason it needs a Select method in order to be able to do this):

image

where the referenced lambda is as trivial as you can imagine.

Conclusion: We don’t allow degenerate queries to occur; both compiler errors are manifestations of that rule. Obviously this relies on a trust relationship with query providers to play according to the rules; those should never return the original query source when applying a query on it, even if that query just selects all elements from the source. Why? The source object may contain things such as connection strings that you don’t want to leak across the border established by a query over that source object. Providers like LINQ to Objects (returns an iterator yielding all elements in the input source when presented with a degenerate select), LINQ to SQL (establishes some Query<T> object over a Table<T> even when presented with a degenerate select) and LINQ to XML (which is just LINQ to Objects with a special API powering it) play according to those rules.

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

More Posts Next page »