B# .NET Blog : Dynamic languages

Extension methods ain't Trojan horses – A tale on a covariant city built in and protected by C# 4.0

bart — Fri, 23 Oct 2009 07:06:44 GMT

Introduction

Today, a colleague and I were playing with new C# 4.0 and BCL 4.0 features, me trying (and succeeding I think) to convince my co-worker about the merits of LINQ and its peripheral technologies. Users of Visual Studio 2010 Beta 2 may have noticed the new IObservable<T> and IObserver<T> interfaces in the System namespace:

namespace System
{
    // Summary:
    //     Defines a provider for push-based notification.
    //
    // Type parameters:
    //   T:
    //     The object that provides notification information.This type parameter is
    //     covariant. That is, you can use either the type you specified or any type
    //     that is more derived. For more information about covariance and contravariance,
    //     see Covariance and Contravariance in Generics.
    public interface IObservable<out T>
    {
        // Summary:
        //     Notifies the provider that an observer is to receive notifications.
        //
        // Parameters:
        //   observer:
        //     The object that is to receive notifications.
        //
        // Returns:
        //     The observer's interface that enables resources to be disposed.
        IDisposable Subscribe(IObserver<T> observer);
    }

    // Summary:
    //     Provides a mechanism for receiving push-based notifications.
    //
    // Type parameters:
    //   T:
    //     The object that provides notification information.This type parameter is
    //     contravariant. That is, you can use either the type you specified or any
    //     type that is less derived. For more information about covariance and contravariance,
    //     see Covariance and Contravariance in Generics.
    public interface IObserver<in T>
    {
        // Summary:
        //     Notifies the observer that the provider has finished sending push-based notifications.
        void OnCompleted();
        //
        // Summary:
        //     Notifies the observer that the provider has experienced an error condition.
        //
        // Parameters:
        //   error:
        //     An object that provides additional information about the error.
        void OnError(Exception error);
        //
        // Summary:
        //     Provides the observer with new data.
        //
        // Parameters:
        //   value:
        //     The current notification information.
        void OnNext(T value);
    }
}

Those interfaces deserve whole blog series of their own (I promise to do so, some day) and have to do with the Reactive Framework discussed on various occasions on Channel 9:

More info on this will appear on Channel 9 in the foreseeable future (stay tuned; I’ll be there!) but all that matters in the scope of this post is the use of two interesting keywords in the interface definitions above:

public interface IObservable<out T> { … }
public interface IObserver<in T> { … }

Did you see them? The reuse of keywords out and in as modifiers on generic type parameters is what’s referred to as the new C# 4.0 feature called definition-site generic co- and contravariance for interface and delegate types, or generic co- and contravariance for short. I’ve written about this in the past, explaining the concept in terms of apples of tomatoes:

C# 4.0 Feature Focus – Part 4 – Co- and Contra-Variance for Generic Delegate and Interface Types

If you don’t know about this stuff just yet, take a break and visit the link above before returning back here. The nice thing about all of this is that as a user of generic types declared to be co- and/or contravariant in certain type parameters, you don’t need to worry about it at all. In fact, this feature allows you to write things you couldn’t write before:

IEnumerable<Apple> apples = null;
IEnumerable<Fruit> fruits = apples; // didn't compile before!

But in .NET 4.0 with C# 4.0 and VB 10.0, you can. The point of variance annotations on generic type parameters is to make such operations provably, at compile-time, safe. Before this new language-level feature, generics were always invariant.

An observed problem?

Loaded with my knowledge of generic co- and contravariance, I was surprised to see the following code compile fine. To be honest, the real scenario was more contrived than the simplified one below, with many intermediate types in the picture:

//
// When apples are thrown at us, we'll write them to the screen.
// We don't expect to see other fruits here!
//
// Note: This uses an extension method on IObservable<T> that
//       hides the declaration of an IObserver<T>. C# doesn't
//       have anonymous inner types unfortunately...
//
IObservable<Apple> apples = new AngryAppleThrower();
apples.Subscribe(Console.WriteLine);

//
// Fine, since IObservable<T> is covariant in T.
//
IObservable<Fruit> fruits = apples;

//
// What? A Banana is injected into an observable of Fruits?
// Though you may think this is fine, how will the observer
// above, expecting Apple objects, react to seeing a Banana?
// This is not type-safe; covariance should prevent this!
//
fruits.Inject(new Banana());

It just couldn’t be true that you could somehow sneak a Banana in an observable of Apple objects. That’s the whole point of type safety guarantees provided by co- and contravariance on generic types in C# 4.0. I tried a few things to verify we could really pass subtypes of Fruit into the IObservable<T>. The following didn’t compile while the Banana-case did:

fruits.Inject(new string());

Just looking at the sample above you can already smell what’s going on, maybe? Tip: look at the types of the variables. What letter do they start with? Then, where does Inject come from? If you don’t see it yet, don’t worry as I’ll reveal the answers in a second. Either way, I started to repro the above with simpler fictional types:

interface IO<out T>
{
}

interface IMyIO<out T> : IO<T>
{
    void Inject<S>(S s) where S : T;
}

In fact, the two interfaces shown here sort of add an additional layer of complexity as was the case in the application I was staring at. The above should fail to compile: since IMyIO<T> declares T as a covariant (output-only) type parameter, it should not be possible to inject an object of type T, or any of its subtypes, into it. So Inject should not work. And indeed it didn’t compile:

Invalid variance: The type parameter 'T' must be contravariantly valid on 'IMyIO<T>.Inject<S>(S)'. 'T' is covariant.

What this says is that Inject requires T to be contravariant (available for input positions) but it’s declared to be covariant. Good job dear compiler (and its developers), just what I expected to see here! Still, that was what I was observing in the concrete fruity flavored sample shown to me. To make matters worse, we were dealing with concrete types implementing the interfaces, so things were far less obvious than they are in the sample shown above. Going back to the questions I asked to the reader earlier, it’s clear the Inject method in the Fruit-sample is coming from an extension method definition, as the left-hand side is an interface that doesn’t have the method by itself:

static class EvilLooking
{
    public static IObservable<T> Inject<T, S>(this IObservable<T> source, S s) where S : T
    {
        // Implementation doesn't matter yet...
        return null;
    }
}

Well, clearly this is fine. Inject is just a method sitting on the outside of the type it extends (in this case IObservable<T>), hence it cannot reach into its internals in any way. The syntactical characteristic of extension method invocation as if it were an instance method simply threw me off:

fruits.Inject(new Banana());

Even though it looks like the covariant Fruit container accepts an object of subtype Banana, were not doing so. The three words “covariant”, “accepts” and “subtype” are a contradictio in terminis. Valid triplets are:

contravariant, accept, subtype – e.g. an IComparer<Fruit> can accept Apple objects since IComparer<T> is contravariant in T
covariant, return, subtype – e.g. an IEnumerable<Fruit> can return Apple objects since IEnumerable<T> is covariant in T

All that’s happening is here is that a “peer method” (with no more “privileges” than the caller in terms of reaching out to the fruits object’s state and internals) is being called:

EvilLooking.Inject(fruits, new Banana());

Here it’s clear that fruits is not accepting a Banana directly. And obviously the “Implementation doesn’t matter yet…” comment in the Inject method implementation shown above is wishful thinking. It won’t be able to contaminate the IObservable<T> source object with an S object (where S is a subtype of T) no matter how hard it tries (short of reflection-based techniques that will fail at runtime).

Case solved. Remaining work for the night was to come up with a good illustration (recall the real problem was not with Fruit, Banana or Apple objects, nor with IObservable<T> directly, but with less intuitive types) of how:

The extension method doesn’t break safety at all, though it looks as if it does (to the trained covariant eye);
Co- and contravariance are a great feature;
And maybe throwing in some of the dangers of dynamic typing when used inappropriately (a tangent to the original topic).

Extension methods ain't Trojan horses

Here’s what I came up with on the bus heading home: the story of how the Trojan War could have been gone differently if the city of Troy protected itself against the Trojan horse adequately... Lots of references to this story appear in the code below, so keep a copy of the linked pages on the side (using Windows 7 Snap if you have installed the brand new wonderful OS already). I hope you have as much fun reading it (and working your way through it as bedside lecture) as I wrote it. I know, it’s geeky humor at best. And analogies are just that: analogies. I don’t guarantee it to be perfect.

/* Extension methods ain't Trojan horses
 * 
 * Illustration of safety guarantees provided by generic covariance in C# 4.0
 * and how extension methods can merely provide a fata morgana making you
 * believe they can defeat it.
 * 
 * bartde - 10/22/2009
 */
using System;
using System.Collections.Generic;
using System.Dynamic;
using System.Threading;
using Microsoft.CSharp.RuntimeBinder;

// How the Trojan war could have been...
namespace NewTrojanWar
{
    /// <summary>
    /// Running the attack vector!
    /// </summary>
    class Program
    {
        /// <summary>
        /// Proves the attack DOESN'T work.
        /// </summary>
        static void Main()
        {
            try
            {
                GreekArmy.TheOneAndOnly.Attack();
            }
            catch (EntryPointNotFoundException ex)
            {
                // Ouch. "The gates are closed it says." Maybe they are covariant after all?
                // They got smarter than we thought! Did they hire Anderius?
                Console.WriteLine(ex);

                // What happened to Epeius is left to your own imagination...
            }
        }
    }

    /// <summary>
    /// City protected by covariance.
    /// </summary>
    /// <typeparam name="NotAllowedToComeIn">Persona or objects of this type are not allowed to come in.</typeparam>
    interface ISecureCity<out NotAllowedToComeIn>
    {
        /// <summary>
        /// What can't come in, can go out.
        /// </summary>
        /// <returns>You're fine to leave, but beware of the point of no return!</returns>
        NotAllowedToComeIn Escape();

        /* Thanks to Laocoon and Cassandra, the following is not possible anymore due the covariantly
         * protected city. The Trojans are a little unhappy as the annual horse meeting can't come in
         * anymore though. It was quite an invasion every year; too bad we lost it since Laocoon and
         * Cassandra put their Troy Sharp 4.0 plan into action. The fact they convinced us that the
         * city has support for covariant protection in place since the Troy City Council 2.0 came out
         * almost five years ago, we - the Trojans - are convinced that cancelling the annual horse
         * meeting for additional protection is a good thing. Out with those foreign horses!
         */
        //void Invade(NotAllowedToComeIn evil);
    }

    /// <summary>
    /// Base class for every horse.
    /// </summary>
    class Horse
    {
    }

    /// <summary>
    /// Troy doesn't want horses to come in.
    /// </summary>
    sealed /* we're an incredibly safe city, no-one should override us! */ class Troy :
        DynamicObject /* Another protection put in place by Laocoon and Cassandra, see further... */,
        ISecureCity<Horse /* Laocoon and Cassandra were right */>
    {
        /// <summary>
        /// We constructed it ourselves and are proud of it.
        /// </summary>
        private Troy()
        {
        }

        /// <summary>
        /// There's only one real Troy!
        /// </summary>
        private static Troy s_city;

        /// <summary>
        /// For publication in the Easy Jet brochure.
        /// </summary>
        /// <returns>Attractive city in the sun; and safe against incoming horses!</returns>
        public static ISecureCity<Horse> City
        {
            get
            {
                if (s_city == null)
                    s_city = new Troy();
                return s_city;
            }
        }

        /// <summary>
        /// Troy breeds horses and people can ask for them from the outside.
        /// </summary>
        /// <returns>You want a horse? Have one!</returns>
        public Horse Escape()
        {
            return new Horse();
        }

        /* Sigh. This used to be fun. To be a good covariant citizen, we have to drop it for
         * better or for worse. Now we implement the new ISecureCity interface!
        /// <summary>
        /// Horse parade.
        /// </summary>
        /// <param name="parade">External horses.</param>
        [Obsolete]
        public void Invade(Horse parade) // implemented the invariant old ICity interface
        {
            // Hang out in the streets and watch the horse parade coming in through the gates.
        }
         */

        /// <summary>
        /// We'll pretend to accept dynamic calls.
        /// </summary>
        /// <param name="binder">Greek language invocation.</param>
        /// <param name="args">What are they saying?</param>
        /// <param name="result">We won't every talk to them though...</param>
        /// <returns>Hard cheese.</returns>
        public override bool TryInvokeMember(InvokeMemberBinder binder, object[] args, out object result)
        {
            throw new EntryPointNotFoundException("The gates are closed!");
        }
    }

    /// <summary>
    /// Greeks trying to attack will need to sit in the horse for quite a while till
    /// the Trojans wheel the horse in.
    /// </summary>
    interface ICanSitStill
    {
        void SitStill();
    }

    /// <summary>
    /// Greeks trying to attack by creating a special horse.
    /// </summary>
    /// <typeparam name="T">Objects to put inside the horse.</typeparam>
    abstract class FilledHorse<T> : Horse where T : ICanSitStill
    {
        /// <summary>
        /// The Trojans will be curious to see what's inside the horse and will subscribe
        /// to the present to receive whatever is in there. Greeks will invade through the
        /// well-known OnNext method that fires the attack inside the city walls.
        /// </summary>
        public abstract IObservable<object> Present { get; }
    }

    /// <summary>
    /// Non-HR-compliant base class for the type below, but according to the story all soldiers were men.
    /// </summary>
    class Male
    {
    }

    /// <summary>
    /// Soldiers need to be tough men.
    /// </summary>
    sealed /* inheritance is not allowed in the army */ class GreekSoldier : Male, ICanSitStill
    {
        /// <summary>
        /// Event to launch the attack.
        /// </summary>
        internal ManualResetEvent GoGoGo { get; private set; }

        /// <summary>
        /// Wait for the attack to start.
        /// </summary>
        public void SitStill()
        {
            GoGoGo.WaitOne();
            // Really they looked for the city's gates and let in their friends. But let's assume they were
            // particularly eager to attack straight away. No matter what they do, thanks to the new city
            // security plan, they won’t even get here: Troy won’t burn!
            throw new DestroyTroyException();
        }
    }

    /// <summary>
    /// Destroy Troy!
    /// </summary>
    class DestroyTroyException : Exception
    {
    }

    /// <summary>
    /// A present for the Trojans.
    /// </summary>
    sealed /* don't mess with us! */ class InterestingHorse
        : FilledHorse<GreekSoldier /* Let's hope they don't look at the type label at the "base" of the horse. */>
    {
        /// <summary>
        /// Invaders.
        /// </summary>
        private IEnumerable<GreekSoldier> _soldiers;

        /// <summary>
        /// Fill the horse with invaders. Make internal not to arouse suspicion.
        /// </summary>
        /// <param name="soldiers">Invaders.</param>
        internal void FillWith(IEnumerable<GreekSoldier> soldiers)
        {
            _soldiers = soldiers;
        }

        /// <summary>
        /// You got a present! Get it and listen to it :-).
        /// </summary>
        /// <remarks>Typed as a mysterious observable of objects. Little do they know the objects are soldiers.</remarks>
        public override IObservable<object> Present
        {
            get { return new WaitingInvaders(_soldiers); }
        }

        /// <summary>
        /// Other than a regular horse, it can be wheeled in.
        /// </summary>
        public void Wheel()
        {
            // This should really override the Horse's feet.
        }

        /// <summary>
        /// But the horse is full of invaders waiting till the attack has to happen at night.
        /// </summary>
        sealed class WaitingInvaders : IObservable<GreekSoldier>
        {
            /// <summary>
            /// Invaders.
            /// </summary>
            private IEnumerable<GreekSoldier> _soldiers;

            /// <summary>
            /// Creating new waiting invaders.
            /// </summary>
            /// <param name="soldiers">Invaders sitting still.</param>
            public WaitingInvaders(IEnumerable<GreekSoldier> soldiers)
            {
                _soldiers = soldiers;
                foreach (var invader in _soldiers)
                    invader.SitStill();
            }

            /// <summary>
            /// Curious Trojans will definitely call this.
            /// </summary>
            /// <param name="observer">The curious Trojans will observe.</param>
            /// <returns>It doesn't give you back something to unsubscribe. In a disappointment, the Trojans go to bed.</returns>
            public IDisposable Subscribe(IObserver<GreekSoldier> observer)
            {
                new Thread(() =>
                    {
                        // Wait till the night falls. We anticipate there will be at most 12 hours of celebration
                        // from the time they wheel in the horse. Then all Trojans will be drunk and asleep.
                        Thread.Sleep(12 * 60 * 60 * 1000);

                        // If coast is clear...
                        foreach (var invader in _soldiers)
                        {
                            observer.OnNext(invader);
                            // Wake-up call! Don't ask me what alarm mechanism they used back then... For one thing,
                            // it wasn't the Windows 7 kernel's thread scheduler.
                            invader.GoGoGo.Set();
                        }
                    }).Start();

                return null; // if you try to dispose the attackers, you'll null-ref yourself :P
            }
        }
    }

    /// <summary>
    /// There's this evil invader that believes in static typing, hence he declared himself as a classy
    /// static man. He can't have anything but static things. In a evil mood, he decided to help out the
    /// Greek army by building the horse and providing an invasion plan for them to enter Troy.
    /// </summary>
    static class Epeius
    {
        /// <summary>
        /// Build the horse.
        /// </summary>
        /// <returns>The invading horse.</returns>
        public static InterestingHorse BuildHorse()
        {
            return new InterestingHorse();
        }

        /// <summary>
        /// How evil. Putting a Gift method before the city door. How could you resist
        /// calling it? But Epeius is faking it, as we shall see. The city is protected
        /// quite well thanks to the Troy Sharp 4.0 feature.
        /// </summary>
        /// <param name="city">The city to invade.</param>
        /// <param name="present">Hmm, horse beef (assuming the Trojans are not vegetarian)!</param>
        public static void Gift(this ISecureCity<Horse> city, InterestingHorse present)
        {
            // Sometimes Epeius silently surrenders to dynamic typing because he's lazy.
            // No-one will suspect him to describe Troy as a dynamic vibrant city. After
            // all, they eagerly want to get into it and Epeius was pretty excited about
            // his job for the Greek army helping them to invade the city. No reason for
            // suspicion at all. We believe Epeius' use of dynamic is fine...
            dynamic vibrantTroy = city;

            // But Epeius didn't find (statically) a method or property on city that accepts
            // the present. He makes the Greek army believe this method works by putting
            // dynamic fairy dust in their eyes though. In fact, Epeius fails here and will
            // let down the Greek army: there is no way to invade Troy. So, the invasion
            // plan (the compiled IL) contains some hidden decision logic on finding out how
            // to carry out the invasion (the DLR machinery behind the scenes). When the
            // soldiers are in the horse, they'll eventually fail right here and their horse
            // will explode (see DynamicObject::TryInvokeMember method implementation!).
            vibrantTroy.Invade(present);

            // Unfortunately, Epeius made himself so static he even doesn't have a this
            // reference to call .Escape() on himself. The rest of the story of what happened
            // with Epeius after the Greek army discovered he cheated on them is not for the
            // sensitive reader.
        }
    }

    /// <summary>
    /// The Greek army is cruel.
    /// </summary>
    class GreekArmy
    {
        /// <summary>
        /// Army.
        /// </summary>
        private List<GreekSoldier> _soldiers;

        /// <summary>
        /// Only one!
        /// </summary>
        private GreekArmy()
        {
            _soldiers = new List<GreekSoldier> { /* recruit good fighters */ };
        }

        /// <summary>
        /// Only one!
        /// </summary>
        private static GreekArmy s_army;

        /// <summary>
        /// Only one!
        /// </summary>
        /// <returns>Only one!</returns>
        public static GreekArmy TheOneAndOnly
        {
            get
            {
                if (s_army == null)
                    s_army = new GreekArmy();
                return s_army;
            }
        }

        /// <summary>
        /// Written by Odysseus who believes Epeius' poisonous Gift call on the City of Troy will work.
        /// </summary>
        public void Attack()
        {
            var horse = Epeius.BuildHorse();
            horse.FillWith(_soldiers);
            Troy.City.Gift(horse); // Sweet, Odysseus sees a Gift command he can shout to the City of Troy...
        }
    }
}

So far for this lecture on Latin epic poems, lectured in C# 4.0.

LINQ to Ducks – Bringing Back The Duck-Typed foreach Statement To LINQ

bart — Tue, 18 Aug 2009 03:20:00 GMT

I promise, it will be a (relatively) short post this time. You all know the foreach statement in C#, don’t you? Think twice before you answer and tell me exactly how the following works:

foreach (int x in src)
{
// Do something with x.
}

Got an answer? Let me disappoint you: if you have the answer, you’re wrong. There’s no single answer to the question above as you need to know more about the type of src to make a final decision on how the above works…

You may say that clearly that object needs to implement IEnumerable or IEnumerable<T>, and maybe you’ll even mention that in the former case the compiler inserts a cast for you when it gets “x” back from the call to the IEnumerator’s Current property getter. In other words, the code gets translated like this:

var e = src.GetEnumerator();
while (e.MoveNext())
{
var x = (int)e.Current; // without the cast if src was an IEnumerable<T>
// Do something with x.
}

A worthy attempt at the translation but not quite right. First of all, the variable x is declared in an outer scope (causing some grief when talking about closures, but that’s a whole different topic…). Secondly, the enumerator may implement IDisposable, in which case the foreach-statement will ensure proper disposal a la “using”:

{
    int x;

    using (var e = src.GetEnumerator())
    {
        while (e.MoveNext())
        {
            x = (int)e.Current; // without the cast if src was an IEnumerable<T>
            // Do something with x.
        }
    }
}

That’s a bit more sane, but we’re missing out on another kind of source foreach can work with: any object, as long as it exposes the enumeration pattern of GetEnumerator in tandem with MoveNext and Current. Here’s a sample object that just works fine with the foreach-statement:

class Source
{
    public SourceEnumerator GetEnumerator()
    {
        return new SourceEnumerator();
    }
}

class SourceEnumerator
{
    private Random rand = new Random();

    public bool MoveNext()
    {
        return rand.Next(100) != 0;
    }

    public int Current
    {
        get
        {
            return rand.Next(100);
        }
    }
}

With its usage shown below:

foreach (int x in new Source())
    Console.WriteLine(x);

Okay, that’s flexible, isn’t it? In fact, the foreach-statement can be said to be duck typed: it’s not the nominal type that matters (i.e. Source is explicitly declared to be an IEnumerable, and SourceEnumerator an IEnumerator) but just the structure of the object that determines “compatibility” with the foreach-statement.

But who says foreach over a collection immediately starts thinking about LINQ, no? Say the consumer of Source looked like this:

List<int> res = new List<int>();
foreach (int x in new Source())
    if (x % 2 == 0)
        res.Add(x);

A great candidate for LINQ it seems, especially as we start adding more and more logic to the “query”. Nothing surprising about this conclusion, but trying to realize it fails miserably:

Why? Because LINQ is statically typed (update: to be taken with a grain of salt, see comments below this post; agreed, it'd be more precise to write LINQ to Objects as the subject of this sentence), so it expects what I’ve referred to as a nominal enumerator implementation: something that has explicitly stated to be an IEnumerable and not something that “accidentally” happens to look like that. Question of the day: how to morph an existing structural enumerator onto a nominal one so it can be used with LINQ? Sure, we could write specialized code for the Source object above that essentially creates an iterator on top of Source:

static void Main()
{
    var res = from x in IterateOver(new Source())
              where x % 2 == 0
              select x;

    foreach (var x in res)
        Console.WriteLine(x);
}

static IEnumerable<int> IterateOver(Source s)
{
    foreach (int i in s)
        yield return i;
}

But maybe you’re in a scenario with plenty of those structural enumerator constructs around (e.g. some Office automation libraries expose GetEnumerator on types like Range, while the Range object itself doesn’t implement IEnumerable hence it’s not usable with LINQ), so you want to generalize the above. Essentially, given any object you’d like to provide a duck-typed iterator over it, a suitable task for another extension method and C# 4.0 dynamic:

static class DuckEnumerable
{
    public static IEnumerable<T> AsDuckEnumerable<T>(this object source)
    {
        dynamic src = source;

        var e = src.GetEnumerator();
        try
        {
            while (e.MoveNext())
                yield return e.Current;
        }
        finally
        {
            var d = e as IDisposable;
            if (d != null)
            {
                d.Dispose();
            }
        }
    }
}

Question to the reader: why can’t we simply write a foreach-loop over the “source casted as dynamic” object? Tip: how would you implement the translation of foreach when encountering a dynamic object as its source?

Yes, you’re cluttering the apparent member list on System.Object, so use with caution or just use plain old method calls to do the “translation”. What matters more is the inside of the operator, using the dynamic type quite a bit to realize the enumeration pattern. Notice how easy on the eye dynamically typed code looks in C# 4.0. With much more casts, it’d look like this:

static class DuckEnumerable
{
    public static IEnumerable<T> AsDuckEnumerable<T>(this object source)
    {
        dynamic src = (dynamic)source;

        dynamic e = src.GetEnumerator();
        try
        {
            while ((bool)e.MoveNext())
                yield return (T)e.Current;
        }
        finally
        {
            var d = e as IDisposable;
            if (d != null)
            {
                d.Dispose();
            }
        }
    }
}

And now we can write:

var res = from x in new Source().AsDuckEnumerable<int>()
          where x % 2 == 0
          select x;

foreach (var x in res)
    Console.WriteLine(x);

Dynamic glue – why not? In fact, even objects from other languages (like Ruby or Python) that follow the pattern will now work with LINQ, and for existing compatible objects the operator call is harmless (but wasteful). Oh, and notice you can also have an IEnumerable of “dynamic” objects if you’re dealing with objects originating from dynamic languages...

Can you implement the AsDuckEnumerable operator in C# 3.0? Absolutely, if you limit yourself to reflection-based discovery methods (left as an exercise for the reader).

Enjoy!

(Mis)using C# 4.0 Dynamic – Type-Free Lambda Calculus, Church Numerals, and more

bart — Mon, 17 Aug 2009 08:35:36 GMT

Introduction

Sunday morning, time for another episode of the Crazy Sundays series. Again one in the category with risk for exploding brains, but that’s what we like, don’t we? This time around, we’re going to have a look at the type free lambda calculus in C#. But wait a minute, isn’t C# a typed language? True. Does that mean everything you do in it should be statically typed? Not necessarily: typing is there as a tool you can leave or take. In this post we’ll take a look at the new C# 4.0 dynamic feature (which provides a static type to do dynamic dispatch) from a somewhat bizarre angle…

Sometimes types do get in the way: maybe something is intrinsically untyped (like XML documents without a schema, web services without a WSDL contract, etc) or meant to be dynamically typed (like objects coming from a dynamic language like Ruby or Python). And then there are notorious APIs that “peter out” in their typing: one moment you’re statically typed, but all of a sudden you end up with System.Object everywhere (like with COM interop to the Office libraries). All such scenarios are what C# 4.0 dynamic is meant for. The classical sample to illustrate the feature is to talk to an IronPython object from C#. First the Python definition:

class Calc:
    def Add(self, a, b):
        return a + b
def GetCalc():
   return Calc()

The nice thing about this Python-based calculator is that it will work with anything that supports an addition operator. In other words, we could feed it two int objects, two string objects, or even a DateTime and a TimeSpan. To make such calls, we use the dynamic keyword in C#:

var py = Python.CreateEngine();
dynamic script = py.ImportModule("Calc");

dynamic calc = script.GetCalc();
int three = calc.Add(1, 2);

Ignore the few lines of plumbing to load the Python file; what matters here is the fact the calc variable is typed to be “dynamic”, meaning all operations invoked on it will be resolved at runtime:

I won’t go into details on how all of this works, maybe another time (outside the scope of Crazy Sundays posts), but that’s the essence of the feature. Instead, we’re going to push this feature to the limits in a “don’t try this at ~~home~~work” style: enter type free lambda calculus.

Type free lambda calculus in a nutshell

The type free lambda calculus, due to Alonzo Church around 1930, is a theory about the computational aspects of functions. It views functions as rules and defines two complimentary operations to work with those: abstraction and application. In essence, that’s all there is but nevertheless the theory gives rise to a whole research area of its own. To convince you about that statement, check the page count for the following book on your favorite online bookshop:

So, allow me to summarize the essentials here, citing/paraphrasing the book above (due to the non-trivial nature of mathematical notation, pasted as images from Word equations). First, we need to define the concept of a lambda term:

As a typical exercise, expand the fourth lambda term in the examples above to its fully parenthesized and bloated form.

All there is to lambda terms is they can denote functions, just like lambda expressions in C# do. For example, the second sample above is a function with argument “x”, returning “x”. In other words, it’s the identity function. However, it has no type: it can operate on anything (in particular, any other lambda term). In C# we could write this as follows:

Func<T, T> I = x => x;

where T stands for a generic parameter. It’s clear this function can operate on values but equally well it can operate on functions: given a function, it will return exactly that function:

I(5) // produces 5
I(I) // produces I

In fact, the middle three samples above are closed terms, meaning all symbols used in their “function body” (the part after the dot) are in “scope” by means of the abstraction(s) over it. We call those combinators:

The last sample term in the previous sample is not closed though: it returns “x” which is not being abstracted over. This reflects the concept of a closure, just as we have in C#:

R x = …;
Func<T, R> f = z => x;

Let’s not go there for now, but suffice to say that fancy words like “closure” are deeply rooted in theoretical foundations. Praise yourself lucky to work with a language layered on top of solid theoretical foundations :-).

Next, we need the concept of free variables. In short, this allows us to identify those variables not introduced by an abstraction in a given term. The definition is fairly straightforward:

For combinators, the free variables set will be empty. In contrast, for our last sample (the one resulting in a closure) the set would be a singleton containing “x”. Nothing too fancy, right?

Finally, we can define how application is carried out, based on the concept of substitution:

To avoid name clashes (something that can be formally avoided by using a variable convention, using the definition of FV above), we notice careful renames are possible. We all know this from C#, and this is merely a theoretical foundation for scoping:

Func<T, T> I1 = x => x;

and

Func<T, T> I2 = y => y;

are in fact the “same”. Using such a big word in the context of a whole runtime (CLR) and language (C#) is a dangerous business. I’m not saying that I1 and I2 will refer to the same delegate: there’s no identification between delegates that says “x => x” and “y => y” are the same. Rather, what I’m pointing out here is that the behavior of I1 and I2 will be the same when applied to the same object. In the lambda calculus this is referred to as alpha-conversion.

Ignoring the important concern of avoiding name clashes for the time being, have a closer look at the application “beta-conversion” rule above. The idea is simple: “application of an abstraction with another term results in substitution”. This is pretty much like a delegate call in C#, but yet different enough: in the world of the lambda calculus, substitutions are nothing but mechanical rewrites on terms. In languages like C#, code is compiled as-is and delegate calls don’t magically rewrite the delegate’s body on the fly. But more importantly, in C# we get also immediately concerned with call semantics like call-by-value: before making a call, its arguments need to be reduced to a “value” that can be passed to the receiving end of the call (through the delegate invocation mechanism).

Untyped or uni-typed?

Now the question of the day: can we type (in the CLR/C# type system sense) all lambda terms? It seems we were successful doing so already with the I combinator, concluding it’s a Func<T, T> with the use of generics: passing a value of a certain type T, the result it the same value and hence of the same type. In fact, what about inferring such signatures? C# doesn’t do so, but F# can (through Hindley-Milner type inference as is done typically in ML-inspired languages):

Okay, “I” is inferred to be a type that goes from ‘a to ‘a, where ‘a is the notation for a generic parameter. What about K, the combinator that given two arguments always returns that first one (“constant” value producer):

We’re still good to go it seems. F# has inferred the type ought to be “‘a to ‘b to ‘a”. Wow, what’s going on here? In C#, this would look like Func<T1, Func<T2, T1>>: a function that given an argument of type T1 returns a function that given an argument of type T2 returns a value of type T1. Get it? What’s happening here is “currying”, where a function of n arguments is turned into “nested” functions that consume one argument at a time. This means we can write, say, “K 5” to create a new function that will eat the remaining “y” argument (of any type) and will always return 5.

Note: There’s a little complication here in the context of F#, called the “value restriction”. I won’t go there as this is irrelevant for the discussion here. What we’re focusing on is solely whether or not we can type lambda expressions.

Even for the (relatively) complicated beast S, a type can be inferred:

Impressive? Not so hard in fact. Follow me as we infer the type ourselves by hand, from the function’s body. First of all, we see x followed by two terms: “z” and “(y z)”. That means “x” is a function with two arguments, and we assume it returns something. Assign type names for those things: the first argument “z” gets type ‘a and the result of “(y z)” will get type ‘b. For the result we write ‘c. In other words, the type of “x” is already inferred to be ’a –> ‘b –> ‘c. Next, we need to infer the type for “y” based on our prior identification of the type for “(y z)” as ’b. We see that “y” is a function with one argument, “z”. We already typed “z” to be ‘a, so the type of “y” becomes ‘a –> ‘b. And finally, our “S” function also takes in “z” as a third argument, which is typed to be ‘a. All of this brought together with the return type of the call to “x” leads to the signature shown above.

So, it looks like we can type all lambda terms, right? Unfortunately, no. Here’s the proof:

Here I’ve written a function W that given an argument x applies that to itself. Such a simple lambda term, and yet one can’t find a type for it. Follow me on this brain exercise: W takes one argument x, say of type ‘a. Now, x is applied to x. From this it looks like x is a function type with one argument. The argument is x, which we’ve already typed to be ‘a. What about the return type? Let’s say it’s ‘b, so now we have that x needs to be of type ‘a –> ‘b, which isn’t the same as ‘a we had before: unification fails.

That’s where differences between the type free lambda calculus and typed variants (like the simply typed lambda calculus and for generics and such something called “System F”) crop up. C# being a typed language doesn’t allow us to get rid of types altogether, so there’s no way we can get “untyped”. But what about “uni-typed” (due to Robert Harper): replace all types with one single type. Can we get there? The answer is, with “dynamic” we can!

dynamic W = new Func<dynamic, dynamic>(x => x(x));

The fact we need some ugly delegate constructor call is unfortunate, but notice how we’re assigning the “dynamic –> dynamic” type to a “dynamic” on the left. In other words, we’re treating everything (non-functional values and function “objects” themselves) as dynamic. The code above compiles just fine, but how does the x(x) in the lambda body work? Well, at runtime the system will figure out what the type of x is and ensure it can be used to be called as a unary function. For example:

dynamic W = new Func<dynamic, dynamic>(x => x(x));
W(1);

This will clearly fail. It corresponds to “calling the function integer 1” with argument “integer 1”. Clearly, an integer value cannot be used as a function (a good thing!), so a runtime error results:

Unhandled Exception: Microsoft.CSharp.RuntimeBinder.RuntimeBinderException: Cannot invoke a non-delegate type
   at CallSite.Target(Closure , CallSite , Object , Object )
   at System.Dynamic.UpdateDelegates.UpdateAndExecute2[T0,T1,TRet](CallSite site, T0 arg0, T1 arg1)
   at UntypedLambda.Program.<Main>b__46(Object x)
   at CallSite.Target(Closure , CallSite , Object , Int32 )
   at System.Dynamic.UpdateDelegates.UpdateAndExecuteVoid2[T0,T1](CallSite site, T0 arg0, T1 arg1)
   at UntypedLambda.Program.Main()

How this works internally is beyond the scope of this post (I’m sure I’ll blog about the DLR machinery and the role of the C# and VB compilers in that mix some time in the relatively near future) but the DLR was right to conclude the call above is nonsense.

What about the following?

var I = new Func<dynamic, dynamic>(x => x);
dynamic W = new Func<dynamic, dynamic>(x => x(x));
Console.WriteLine(W(I)(42));

Now, that works. Passing I to W results in I(I), which reduces (using application, or beta-conversion) into I. That function is then used with argument 42 subsequently, returning 42.

You can guess it … we’re going to uni-type our whole programs using dynamic in this Crazy Sundays post. Did I ever mention Scheme? If not, I did now :-).

SKI combinators

As we’ve already played with S, K and I in the samples above, let’s see how those look in uni-typed C#:

//
// Where else to start than with ... SKI combinators.
//
var S = new Func<dynamic, Func<dynamic, Func<dynamic, dynamic>>>(x => y => z => x(z)(y(z)));
var K = new Func<dynamic, Func<dynamic, dynamic>>(x => y => x);
var I = new Func<dynamic, dynamic>(x => x);

Notice we’re currying all functions so that we can partially apply functions. For example, we can do the following to create a “constant function” that always returns 42:

var answer = K(42);
Console.WriteLine(answer("Bart"));
Console.WriteLine(answer(DateTime.Now));
Console.WriteLine(answer(-42));
Console.WriteLine(answer(S));

All of the calls above will print 42, regardless of what’s passed in to answer. Follow the reduction in your head: applying 42 to K returns a function from a parameter called “y” to 42. In other words, “y” is discarded altogether. We’re generating the constant 42, no matter what (both in terms of value and type) we throw to the function as an argument. Not just plain values: in the last line we throw S, another function, to the answer function and yet it persists telling us the answer is 42.

It can be shown, as an easy exercise, that SKK (and SKS) are the same as I, so the following is a complicated way of writing 5:

int five = S(K)(K)(5);

See how functions are first-class citizens: they can be passed or returned everywhere. Also notice how functions have to be called one argument at a time because of currying (due to Schonfinkel, not Curry).

While we’re at it, we’ll write a helper function to apply a function to different argument values and print the result to the screen. In subsequent paragraphs we’ll use this function (and a variant thereof) to aid us in printing test results:

static void Unary<T, PArg, PRes>(string name, Func<dynamic, T> f, Func<dynamic, PArg> printArg, Func<dynamic, PRes> printRes, params dynamic[] values)
{
    foreach (var value in values)
        Console.WriteLine("{0}({1}) = {2}", name, printArg(value), printRes(f(value)));
}

Quite a signature, but essentially we take a friendly function name, a function to be tested, some function to turn the “dynamic” argument into a print-friendly form (and a similar function for the result of the function call), and an array of values to be fed in. For example:

Console.WriteLine("SKI");
Unary("SKK", S(K)(K), I, I, 5, DateTime.Now, "Bart");
Unary("I", I, I, I, 5, DateTime.Now, "Bart");
Console.WriteLine();

This results in the following:

As an exercise, try to do something more meaningful with the S combinator.

Church Booleans

Functions and data are very closely related. More closely than you may think. Most programmers think of functions as pieces of code that have a certain behavior and get applied to zero or more arguments, producing some (or none) value. That’s a very code-centric view of the world, while functions in the mathematical sense are obviously not related to “code” at all. Functions are often defined as graphs and are a special kind of relation between two sets. Sets are all about data, aren’t they? Based on such an observation one can establish functions in a computer programs as table lookup = data.

But there’s more, even values themselves (and not mappings between them) can be encoded using functions. Let’s start easy, with Booleans. Easy because there are only two values to distinguish. Here’s the proposed mapping:

//
// Church Booleans.
// Basic idea: true and false are dyadic functions returning respectively
//             the first or second argument, acting as a conditional (?:)
//
var F = new Func<dynamic, Func<dynamic, dynamic>>(a => b => b);
var T = new Func<dynamic, Func<dynamic, dynamic>>(a => b => a);

Okay, the comment reveals it already: the idea is that true and false are encoded as functions with two arguments (again curried) of which one is returned: false returns the second one, true the first one. Sounds familiar, doesn’t it? Right, the conditional operator (sometimes awkwardly referred to as the ternary operator) in C# does exactly that. Notice that using alpha-conversion, T is exactly the same as K.

Notice it’s easy to convert between the untyped world and the typed world using two back-and-forth conversion functions:

Func<dynamic, bool> toBool = x => x(true)(false);
Func<bool, dynamic> fromBool = b => b ? T : F;

We wouldn’t need toBool if we weren’t to print the results to the screen somehow :-). For completeness, I’ve added fromBool to the equation. Both are easy to understand, but let’s start with fromBool. Plain easy: give it true, and it returns T; give it false, and you get F back. The inverse function, toBool, is simple function application (beta conversion) of the defined functions to C# Booleans: if the function bound to x is T, the first argument will be returned (true). If it’s F, the second one (false) will. Clear as crystal. Notice toBool can be applied with any object as its argument: going from untyped to typed will blame the argument if something goes wrong (due to Philip Wadler).

Not very useful yet, if we don’t have a way to define operations between such Booleans. Again functions come to the rescue (we don’t have anything else after all), so let’s have a look at how we define a simple operator: not.

var not = new Func<dynamic, Func<dynamic, Func<dynamic, dynamic>>>(m => a => b => m(b)(a));

Notice all operators on Church Booleans will be higher-order functions in their very nature, since their arguments are functions already. That’s the nature of the beast we’re dealing with. So, how can we turn a Church Boolean “m” in its opposite? We already know that Church Booleans are dyadic functions, so the result of calling not with a Church Boolean should be a function with two arguments: that’s what “a” and “b” are for. The body of the function may look a bit weird: we’re calling “m” (a Church Boolean, but remember everything is a function hence executable) with arguments b and a. That has a flipping effect as proven below:

Impressive, isn’t it? A word on notation: before doing a beta-reduction we indicate the abstractions we’re going to apply substitutions for by putting a bar on top of them (e.g. in the second step m, in the fourth step x and y). When doing multiple reductions we write an arrow with a double arrowhead. When substituting terms for their definition (like T and F in the proof above), we carry out alpha-conversion to avoid the risk of name clashes (though strictly speaking for closed terms we could play a more risky game).

How can we do binary operators, like and, or and xor? Turns out those are fairly simple to do as well:

var and = new Func<dynamic, Func<dynamic, dynamic>>(m => n => m(n)(m));
var or = new Func<dynamic, Func<dynamic, dynamic>>(m => n => m(m)(n));
var xor = new Func<dynamic, Func<dynamic, Func<dynamic, Func<dynamic, dynamic>>>>(m => n => a => b => m(n(b)(a))(n(a)(b)));

Agreed, one needs to see a proof of correctness before being convinced those functions have the desired behavior. By the way, outside C#, we could save us some parentheses which mainly come from (dynamic) delegate invocations above. Also notice that the functions for and and or don’t have abstractions in their “body”: the result of calling “mnm” or “mmn” already gives a function of the right arity, as can be seen in the proofs below:

The proof for xor is left as an exercise to the reader (feel free to use case analysis of all four combinations of arguments, although you can simplify matters a bit…).

Of course you want to see this in action. We already have our Unary function to test lambda functions with given arguments, let’s define a similar one for binary operators:

static void Binary<T, PArg, PRes>(string name, Func<dynamic, T> f, Func<dynamic, PArg> printArg, Func<dynamic, PRes> printRes, params dynamic[] values)
{
    foreach (var valueL in values)
        foreach (var valueR in values)
            Console.WriteLine("{0}({1}, {2}) = {3}", name, printArg(valueL), printArg(valueR), printRes(f(valueL)(valueR)));
}

It basically creates all combinations of input arguments and applies them to the function, putting some pretty printing to the mix. So we write:

Console.WriteLine("Church Booleans");
Unary("toBool", toBool, toBool, I, F, T);
Unary("not", not, toBool, toBool, F, T);
Binary("and", and, toBool, toBool, F, T);
Binary("or", or, toBool, toBool, F, T);
Binary("xor", xor, toBool, toBool, F, T);
Console.WriteLine();

The use of toBool allows us to go from a “dynamic” function to a concrete C# Boolean value which is printable by Console.WriteLine. The result looks like this:

Looks right, doesn’t it?

Church numerals

If we can do Booleans, we can do numeric values too, right? Let’s restrict ourselves to positive natural numbers (including 0) and we end up with the concept of Church numerals. Now we have an infinite domain of values to represent, we need a way to control this complexity somehow (in order to be able to define nice operators over them). One possible solution is the use of repeated function application to encode a numeric value, as follows:

Can you see it? Calling f on argument x once corresponds to 1, twice corresponds to 2, etc. Quite nice. What kind of simple operations can we define over such value representation? Clearly we don’t want to define all different N-objects for the whole domain of natural numbers. In fact, we don’t even want to define N1 explicitly. Two basic ingredients should suffice to define every natural number: a representation of 0, and a way to “add one” to a Church numeral (i.e. returning a new function that represents the value of the argument, plus one). This is the much desired successor function:

var N0 = new Func<dynamic, Func<dynamic, dynamic>>(f => x => x);
var succ = new Func<dynamic, Func<dynamic, Func<dynamic, dynamic>>>(n => f => x => f(n(f)(x)));

The successor function is a function with one argument “n”, returning a function of two arguments “f” and “x” (like all Church numerals being double-abstractions over some term). The definition is “f(nfx)”, with some more parentheses in C#. But how does it work? See it with your own eyes and feed it N0 for starters: “n” is substituted (beta conversion) for “N0” which by itself is a lambda expression of the form shown in the figure above (goes from f and x to x). A few beta-conversions later you’ll end up with f(x), exactly the definition of N1. In other words, succ simply adds an additional “f” application to the existing term’s body. A more formal proof is given below:

Based on this, can we create a simple conversions function to promote a C# positive integer value into a corresponding Church numeral? The answer is obviously yes and the idea is fairly easy: we’ll call succ repeatedly, n times for integer with value n, starting with N0 as the base. To go back from a Church numeral to a C# unsigned integer we exploit the repeated function call behavior on argument “f” and use a devilish side-effect to increment a counter whenever we are called:

Func<dynamic, uint> toInt = x =>
{
    uint n = 0;
    x(new Action<dynamic>(_ => { n++; }))(null);
    return n;
};

Func<uint, dynamic> fromInt = null;
fromInt = n =>
{
    return (n == 0 ? N0 : succ(fromInt(n - 1)));
};

If you don’t get this immediately, don’t worry. Just feed it some Church numerals and see what happens. For example, N0 is a function that simply returns its second argument. When calling toInt on N0, x is bound to N0, executed with two arguments of which the second one – null – is returned. The function of type Action<dynamic> in the first argument was never called, so the result is 0. But if N1 is fed in, that function in the first argument will get called how many times? Right, just one time. In other words, the side-effecting n++ will be called once, and the result is 1. In other words, we should be able to “roundtrip” C# integers through Church numerals:

for (uint i = 0; i <= 10; i++)
    Console.WriteLine(toInt(fromInt(i)));

Try it at home and you should see the numbers 0 through 10 being printed on the screen. Victory. Oh, and fromInt is simply a recursive function that makes successor calls till n == 0 is reached, at which point N0 is returned. So, fromInt(5) will be encoded as succ(succ(succ(succ(succ(N0)))).

All of this looks good, doesn’t it? Another useful function is a zero-test. In the typed world this would be a function from an integer to a Boolean, but of course in the world of type-free lambda calculus we loose that typing safety net. Nevertheless, here’s how zero looks like:

var zero = new Func<dynamic, dynamic>(n => n(K(F))(T));

Recall that N0 was the same as F, and we know that F returns its second argument for its result. A zero-check on N0 clearly should return T, so the zero function should look like n (???) T. This satisfies the case where N0 is fed in. What about the other cases? Well, the first argument to n (the Church numeral passed in) is the function that gets called repeatedly on the second argument (which we already made T). For all those numerals we want to return F for the zero-check, so the question is whether we know a function that will always return F no matter what argument it’s given? We do, it’s called K with argument F: the constant-generator combinator K which we ask friendly to return hardheadedly F all the time. A formal proof is shown below:

Finally, the real stuff. What about operations like add and multiply, or even exponential? The good thing is they exist indeed :-). And here they are:

var plus = new Func<dynamic, Func<dynamic, Func<dynamic, Func<dynamic, dynamic>>>>(m => n => f => x => m(f)(n(f)(x)));
var mul = new Func<dynamic, Func<dynamic, Func<dynamic, dynamic>>>(m => n => f => n(m(f)));
var exp = new Func<dynamic, Func<dynamic, dynamic>>(m => n => n(m));

How they work is another piece of cake. Here’s a proof for plus’s behavior:

That was fairly easy, wasn’t it? Feel free to feed it a couple of values to confirm the behavior, but we’ll run it through some tests in just a while. For mul and exp, proofs need some inductive reasoning as shown below:

Notice how beautiful the definition of exp is: apply n with argument m, and you got an exponential. Wow. If I’d drink alcohol, this would be a reason to get drunk. I’ll stick with Diet Coke anyhow, but suffice to say I absolutely love it. And far that matter, mul is nice too, don’t you agree?

What about a predecessor and subtract function? Unfortunately those are quite ugly in this Church numeral encoding system:

var pred = new Func<dynamic, Func<dynamic, Func<dynamic, dynamic>>>(n => f => x => n(new Func<dynamic, Func<dynamic, dynamic>>(a => b => b(a(f))))(K(x))(I));

Bweik. It’s so disgusting I’ll leave the definition of a “sub” function (tip: use pred) to the reader. Oh, and if you’re really fearsome, prove the correctness of “pred” using induction.

Anyway, here’s a test-application for Church numerals:

Console.WriteLine("Church numerals");
Unary("toInt", toInt, toInt, I, Enumerable.Range(0, 3).Select(i => fromInt((uint)i)).ToArray());
Unary("succ", succ, toInt, toInt, Enumerable.Range(0, 3).Select(i => fromInt((uint)i)).ToArray());
Unary("pred", pred, toInt, toInt, Enumerable.Range(1, 3).Select(i => fromInt((uint)i)).ToArray());
Unary("zero", zero, toInt, toBool, Enumerable.Range(0, 2).Select(i => fromInt((uint)i)).ToArray());
Binary("plus", plus, toInt, toInt, Enumerable.Range(0, 3).Select(i => fromInt((uint)i)).ToArray());
Binary("mul", mul, toInt, toInt, Enumerable.Range(0, 3).Select(i => fromInt((uint)i)).ToArray());
Binary("exp", exp, toInt, toInt, Enumerable.Range(1, 3).Select(i => fromInt((uint)i)).ToArray());
Console.WriteLine();

We use our beloved fromInt function in combination with some LINQ operators to produce an array of test inputs, for which all combinations will be fed to the passed-in functions:

Wonderful. (Don’t bother to ask about performance…)

Going nuts – recursive functions

We could go much further and define pairs, tuples and lists using Church encodings as well, but as I have another rabbit in my hat for another time, I won’t spoil the beans at this point. A little sneak peak though (this is without C# 4.0 dynamic…), for pairs:

var Pair = λ(x => λ(y => λ(z => ß(ß(z, x), y)))); // \xyz.zxy
var Fst = λ(p => ß(p, T)); // \p.pT
var Snd = λ(p => ß(p, F)); // \p.pF

and for lists:

var Nil = ß(ß(Pair, T), T);
var IsNil = Fst;
var Cons = λ(h => λ(t => ß(ß(Pair, F), ß(ß(Pair, h), t))));
var Head = λ(z => ß(Fst, ß(Snd, z)));
var Tail = λ(z => ß(Snd, ß(Snd, z)));

Instead, let’s conclude this post with two recursive functions:

//
// The icing on the cake.
//
Func<Func<Func<dynamic, dynamic>, Func<dynamic, dynamic>>, Func<dynamic, dynamic>> Fix = null;
Fix = f => x => f(Fix(f))(x);

var fact = Fix(new Func<dynamic, Func<dynamic, dynamic>>(f => x => zero(x)(new Func<dynamic, dynamic>(_ => succ(N0)))(new Func<dynamic, dynamic>(_ => mul(x)(f(pred(x)))))(I)));
var fib = Fix(new Func<dynamic, Func<dynamic, dynamic>>(f => x => zero(x)(new Func<dynamic, dynamic>(_ => N0))(new Func<dynamic, dynamic>(_ => zero(pred(x))(new Func<dynamic, dynamic>(__ => succ(N0)))(new Func<dynamic, dynamic>(__ => plus(f(pred(x)))(f(pred(pred(x))))))(I)))(I)));

Unary("fact", fact, toInt, toInt, Enumerable.Range(0, 10).Select(i => fromInt((uint)i)).ToArray());
Unary("fib", fib, toInt, toInt, Enumerable.Range(0, 10).Select(i => fromInt((uint)i)).ToArray());

This gets quite ugly due to the use of a fixpoint combinator and the chase to circumvent call-by-value semantics (exercise: where and how does that happen precisely in the fragments above?) causing endless evaluations (exhausting the stack), but rest assured those functions work just fine:

Finally, an outtake :-). What does the following result in?

var Omega = new Func<dynamic, dynamic>(x => x(x))(new Func<dynamic, dynamic>(x => x(x)));
Omega(I);

Got a headache? Click here.

Introducing “The C# Ducktaper” – Bridging the dynamic world with the static world

bart — Mon, 10 Nov 2008 15:49:18 GMT

Why this is not a C# 4.0 blog post…

By now most of you have probably heard about the dynamic capabilities that will be added to the C# 4.0 language. Search engines start to fill their databases with lots of descriptions of and discussions about the feature, but for now I won’t (yet) contribute to this (although at the time of fetching the previous link, my post on DynCalc was mistakenly on that list). Not yet, as it will get covered in my C# 4.0 Feature Focus series in the foreseeable future, but let me give away my take on it:

Today’s code is surrounded by an increasing number of dynamic environments and data sources. Targeting these is way too hard today. Think of interactions with JavaScript, loosely typed XML documents, calling into libraries written in dynamic languages, etc. It’s not because you’ve chosen for a statically typed environment like the CLR you should be punished when trying to reach out to any of these environments or data sources. So, dynamic is a good thing when used properly, so the motto should be “static wherever possible, dynamic if necessary”.

So, what’s this post about then? To set the context for further posts on the C# 4.0 dynamic feature and other DLR related topics, I want to highlight a few basic principles of dynamic dispatching first. A while ago, in the context of framework testing frameworks and general DLR-related stuff, I came up with the (not so original) concept of a “ducktaper”. While it’s easy to reach out to a static world from within a dynamic fortress (e.g. PowerShell, IronRuby, IronPython, etc calling into BCL functionality) the reverse, calling dynamic objects as if they were static, is like rowing against the current. The way people dealt with this problem for a long time is by creating statically typed wrappers around dynamic objects, which is a compile-time task as opposed to a runtime tasks. Doing this as a runtime task is what the “ducktaper” is all about.

To wet your appetite, here’s what it’s meant to look like:

object dynamicDuck = GetDuckFrom(DuckSource.Pond);
IDuck duck = dynamicDuck.AsIf<IDuck>();
duck.Walking += (o, e) => { Console.WriteLine(“Duck is walking”); };
duck.Walk(); // How can a static duck walk <g>?
Console.WriteLine(duck.Quack(“Bart”));
duck.Walk();

This post is not only about how to make such a thing work – and there are really a variety of ways to do this; I’ll only present the outcome of the last prototype – but also why this is or isn’t a good idea. Though I intend to keep this to one post (albeit a lengthy one I can already predict now), it might get a tail somehow :-). Notice no guarantees are made about the code, use it at your own risk – it’s merely meant as a brain-dump on dynamic dispatching techniques.

What’s in a name?

Well, two parts really: duck and tape. Etymological discussions don’t agree about the origin of the word “duct tape”, but duck is more appropriate in this context. A breakdown:

duck refers to “duck typing”, a programming language concept that allows developers to concentrate on the use of an object rather than its type. A typical way to refer to it is: “If it walks like a duck and quacks like a duck, I would call it a duck.”, so as long as an object accepts (and responds to) Walk and Quack messages, we’re okay to send those messages.
tape, when applied, has the characteristic of putting pieces of stuff together. In this case we’re binding dynamic objects to statically typed contracts, so you can consider it to be type-tape. The glue operator is called AsIf and will be described in a lengthy fashion in this post.

Where to get it?

With all the usual aforementioned restrictions and warnings applied, here’s where you can grab the complete project, including:

Library code for the DuckTaper
Sample use in a console application
Unit tests

The solution and projects are created in Visual Studio 2008.

How does it work?

Starting from a macroscopic level, let’s examine what the following call really looks like from the outside:

IDuck duck = dynamicDuck.AsIf<IDuck>();

The object on which we call AsIf<T> can be anything, so its type ought to be System.Object in order to yield this flexibility. As the System.Object type doesn’t have such a method, we need to cook our own (if it had such a method, this blog post wouldn’t have a reason to exist), so that’s where extension methods enter the picture. This is merely an implementation detail and I won’t even bother discussing whether or not it’s a good idea to put extension methods on the mother of all types (why not?), so I’ll leave the judgment to the reader. More relevant is the generic parameter that accepts an interface type, which becomes the return type. Putting the pieces together, we end up with this signature:

public static T AsIf<T>(this object target) where T : class

Generic constraints (Partition II – 10.1.7) don’t have the expressive power to limit T to be an interface type, so we’ll need a runtime check as well. Our entry-point function ultimately looks like:

public static T AsIf<T>(this object target) where T : class
{
    Type targetType = typeof(T);

    //
    // Check target is an interface.
    //
    if (!targetType.IsInterface)
        throw new InvalidOperationException("Target type of AsIf<T> cast should be an interface.");

    return AsIfInternal<T>(target, targetType, true);
}

What’s behind the scenes in AsIfInternal will follow soon. But let’s elaborate on an important point here first: why does T need to be an interface? Ultimately what our implementation needs to do is generating an object type at runtime that’s “compatible” with the type specified in generic parameter T. Allowing concrete types for T will make matters much more complicated, for lots of reasons (e.g. what if the type is sealed). But also from a philosophical point of view, we desire to “morph” the original object to a given operational contract, so all we want here is some sort of (weak – to be explained below) contract that’s a description of the intended “interface” that’s to be layered on top of the existing object.

For example, assume the retrieved duck object looks as follows (remember, for now we’re not considering arbitrary dynamic objects, so we’ll use plain C# class definition syntax here), omitting member definitions for clarity and brevity:

class Duck
{
    public void Walk();
    public void Walk(int steps);
    public string Quack(object name);
    public ConsoleColor Color { get; set; }
    public event EventHandler Walking;
}

Next, consider the following desired “weak contract”:

weak contract IDuck
{
    void Walk();
    void Walk(int steps);
    object Quack(string name);
    ConsoleColor Color { get; set; }
    event EventHandler Walking;
}

Notice I’m not using the interface keyword above. We’re entering the realm of a hypothetical C# look-a-like. Going even further down the road of hypothetism, what we’re really looking for here is some kind of asif keyword that can “cast” an object to a weak contract, handing back a wrapper object that behaves like the contract but dispatches to the underling original object underneath:

IDuck duck = dynamicDuck asif IDuck;

- or even -

IDuck duck = dynamicDuck asif {
    void Walk();
    void Walk(int steps);
    object Quack(string name);
    ConsoleColor Color { get; set; }
    event EventHandler Walking;
};

which is to be read as: “as if it were” or “as if it adhered to”. But why referring to this as a weak contract? Interfaces, as we know them in C#, represent a strong contract. To the CLI, it doesn’t matter that much (Partition I – 8.2.3):

A type fully describes a value if it unambiguously defines the value’s representation and the operations defined on that value. (…) Some types are only a partial description; for example, interface types. (…)

The word contract doesn’t enter the picture here. However, languages like C# state things in a stronger manner (C# 3.0 specification, chapter 13):

An interface describes a contract. A class or struct that implements an interface must adhere to its contract. (…)

Both the provider of the interface and all of its consumers agree upon the contract and implementing an interface is like signing a strong mutual contract. In here, the consumer agrees to adhere to the contract in its implementation, while the provider guarantees the contract is kept stable (with no room for small print). An interface embodies more than typing: interfaces often act as protocols between different parties, which are not expressible in the type system. For instance, the contract might require you to call Initialize first, followed by anything else as long as Dispose isn’t called. In practice this means interfaces cannot be changed, both on the type-level (messing with interface methods, adding/removing them, etc) and the semantic level. Changing stuff means creating a new interface – typically with a version number suffix – and having consumers sign the new contract.

Why is this relevant in this context? Notice the Duck class above, it doesn’t implement IDuck (and assume IDuck is a strong contract – i.e. an interface in realistic C# terms – for now) in an explicit manner. This means it’s not participating in the strong contract IDuck provides and we can only guess that the Duck object behaves like the IDuck specification. That’s what duck typing is about: the object looks like a duck, so there’s a chance it’s really a duck. The hypothetical asif operator expresses taking the bet that the duck object really is a duck. In the sample case, the bet has little chances to be wrong, but we don’t have guarantees.

To illustrate this, consider the following:

object dynamicDuck = GetDuckFrom(DuckSource.Oven);
IDuck duck = dynamicDuck.AsIf<IDuck>();
duck.Walk();

Most likely a baked duck will throw a NotSupportedException (or a more plastic exception type, depending on your imagination) when calling Walk, but what if IDuck assumes a living duck and doesn’t indicate NotSupportedException as a possible exception? Or what if the Quack method on IDuck specifies a specific duck language dialect to be spoken by the duck (although that could be expressed in the type system)? The duck implementer did never explicitly say his duck implementation adheres to the rules of IDuck, and there can be a variety of reasons for this: maybe the implementer didn’t know about the IDuck interface, or maybe his duck isn’t compliant with the IDuck contract.

Sometimes making a guess is relatively safe though. C# already does this to a limited extent:

foreach only requires a GetEnumerator method to be present on the collection being iterated over;
LINQ query comprehension keywords translate in method calls;

both without a specific interface requirement. In the case of LINQ, requiring an interface to be used would result in a gigantic interface (containing all query operators) no-one would be interested in to implement (for more information on how to resolve this tension, see The Most Funny Interface Of The Year … IQueryable<T>). Another place with similar flexibility rules is the C# 3.0 collection initializers feature that require an Add method on an IEnumerable object (no, not an ICollection, this is not a typo – see paragraph 7.5.10.3 of the C# 3.0 specification).

However, weak contracts are not a supported runtime or language construct at this point, so the best we can get is something that mimics a “collection of members” pretty well: interfaces. And this is an important caveat to point out: we’re piggybacking on strong contracts to realize weak contracts, which is not ideal. (It turns out it will get even a bit messier in the implementation in terms of visibility, see further…) Actually, we can put a band-aid mitigation in place as well, by sprinkling a custom attribute on interfaces indicating they’re used as a weak contract, and refusing to use any non-marked-as-such interfaces in the context of AsIf<T> (but as you realize, this is a uni-directional fix-up as it doesn’t avoid weak contracts to be used as a strong one). This strategy is implemented in the code that’s available for download:

weak contract IBar
{
void Foo();
}

is indicated as

[WeakContract]
interface IBar
{
void Foo();
}

How does it really work?

Now that we’ve pointed out a few important aspects of the implementation philosophy and restrictions imposed by the runtime and language concepts at hand, we can turn our attention to more implementation details. Our internal entry-point looks like this:

/// <summary>
/// Creates a wrapper object of type <typeparamref name="T">T</typeparamref> around the specified <paramref name="target">target</paramref> object.
/// </summary>
/// <typeparam name="T">Target type.</typeparam>
/// <param name="target">Object to be wrapped.</param>
/// <param name="targetType">Target type (avoids having to call typeof again).</param>
/// <param name="shortCircuit">Indicates whether or not short-circuiting is allows if the object already implements the specified interface.</param>
/// <returns>Wrapper around the specified object.</returns>
private static T AsIfInternal<T>(object target, Type targetType, bool shortCircuit) where T : class

‘All’ we have to do in here is creating something that looks like T while really acting as target. The first part of the equation translates into type generation, the second part into dispatching calls. Putting the pieces together we end up with type generation of a wrapper dispatching to the original object. This is where System.Reflection.Emit kicks in. By itself this has a few caveats:

A feature known as “restricted skip visibility” (see DynamicMethod on MSDN) is not available at this level, nor is it applicable (Why did I refer to it anyway? Well, because in philosophy it’s the same as what we need.) in our case. Since we’re implementing T (which, remember, denotes an interface type), what this really means is that the interface type should be public in order to have a dynamically emitted type in a dynamically emitted assembly implement it.
Loading a dynamically generated assembly into the current application domain makes it impossible to unload it; marshalling it across application domain boundaries would introduce its own set of problems. Actually the dynamic assembly (and module) is a side-effect of what we really need: just a dynamically generated type. On this field though, things will improve in .NET Framework 4.0 (but also for other reasons, making large parts of this blog post’s exercise dispatchable to the CLR/DLR synergy).

Remember this is a proof of concept implemented in today’s world of .NET, so we’ll ignore those issues for now. So, what are we up to? Some IL generation for sure, but let’s try to minimize the amount of IL that needs to be generated. As we’re wrapping an object – and not extending it in any way (for reasons outlined earlier) – we have the luxury to pull off a wrapper type that can derive from a base class. This has the additional benefit of having a way to determine statically whether an object is a dynamic object wrapper or not, by checking whether it derives from that particular wrapper base class (just an “is” or “as” suffices). Let us call this base class type Dynamic, then what we need to do translates into the following (in pseudo-meta-code):

class <NameForTheWrapperObject> : Dynamic, T
{
    <%
        foreach (MemberInfo member in typeof(T).GetMembers())
            ImplementInterfaceMember(member);
    %>
}

The relevant piece here is the type hierarchy, creating a subtype of Dynamic while implementing interface T. Yet another reason why we need T to be an interface as multiple inheritance is banned from our world (for good enough reasons, but that’s a different discussion). A few remarks on this meta-code:

GetMembers is considered to do a recursive scan of all members in the type hierarchy denoted by T. It’s possible that the interface T “inherits from” other interfaces, so we need to cover all members in the entire tree starting from T.
Interface members can be methods, properties, indexers (which are really a special kind of properties) and events.
Implementation of interface members will be the most complicated part obviously and will not only involve implementing the method with some stock code that does the dispatch but we’ll also need some fields to make everything work, see further.

But let’s start at the root: Dynamic. What does the Dynamic class need to be capable of doing? Here are its basic tasks:

It holds the wrapped object.
It has a way to dispatch invocations from the (to-be-implemented-by-subclass) interface members to the underlying wrapped objects.

To speed up dispatching we can introduce an intermediate concept that maintains a cache of possible invocation dispatch targets on a per-member basis. Doing so opens up for opportunities to provide fast paths when an invocation is repeated and have method overload resolution mechanisms decentralized from the wrapper object’s code and Dynamic base class’s code itself. Such a concept is often referred to as a “call site”, so let’s call that guy a CallSite. Although we won’t implement it in an advanced way, I still want to have it around to explain a few concepts. In fact you could well live without it, having the wrapper call into the base on some “InvokeMember” method that does the dispatch and implements caching strategies by itself. Here we enter the domain of what the DLR excels at, but we’ll avoid all of that complexity for the purposes of this blog post.

Putting the pieces together, here’s what we end up with for Dynamic:

/// <summary>
/// Base class for dynamic objects.
/// </summary>
public abstract class Dynamic
{
    /// <summary>
    /// Target object.
    /// </summary>
    private object _target;

    /// <summary>
    /// Creates a new dynamic object wrapping the specified <paramref name="target">target object</paramref>.
    /// </summary>
    /// <param name="target">Wrapped target object.</param>
    protected Dynamic(object target)
    {
        this._target = target;
    }

    /// <summary>
    /// Gets the wrapped target object.
    /// </summary>
    public object Target
    {
        get
        {
            return _target;
        }
    }

    /// <summary>
    /// Determines whether the wrapped object refers to the same object as the object wrapped by the passed in dynamic object.
    /// </summary>
    /// <param name="obj">Object to compare to.</param>
    /// <returns>true if the wrapped object refers to the same object as the object wrapped by the passed in dynamic object; false otherwise.</returns>
    /// <remarks>Equality between a dynamic wrapped object and a non-wrapped object object always returns false as we can't guarantee commutativity.</remarks>
    public override bool Equals(object obj)
    {
        Dynamic dynamic = obj as Dynamic;

        if (dynamic == null)
            return false;

        return object.ReferenceEquals(dynamic._target, this._target);
    }

    /// <summary>
    /// Returns the hash code of the wrapped object.
    /// </summary>
    /// <returns>Hash code of the wrapped object.</returns>
    public override int GetHashCode()
    {
        return _target.GetHashCode();
    }

    /// <summary>
    /// Returns the string representation of the wrapped object.
    /// </summary>
    /// <returns>String representation of the wrapped object.</returns>
    public override string ToString()
    {
        return _target.ToString();
    }

    /// <summary>
    /// Creates a call-site for the specified <paramref name="member">member</paramref>.
    /// </summary>
    /// <param name="member">Member to create a call-site for.</param>
    /// <returns>Call-site for the specified <paramref name="member">member</paramref>.</returns>
    protected CallSite GetCallSite(string member)
    {
        return new CallSite(this._target, member);
    }
}

Notice how Dynamic is a tiny wrapper around a System.Object instance also just forwarding methods like ToString and GetHashCode to the wrapped object. Equals is defined in terms of referential equality of the wrapped object too. Other than that, there are two pieces meant for use by the generated subclasses: the constructor (notice how the _target field is hidden from the subclasses – those subclasses don’t call into the Target getter either but you’ll have to take my word for it just for now) and the GetCallSite method.

This GetCallSite method is of particular interest. The subtype of Dynamic will hold a CallSite field for every method implemented for the requested interface type. Notice I’m saying every method which is not the same as every member, because properties/indexers can have one or two methods (getter and/or setter) and so do events (add and/or remove methods). Those call site objects will be created lazily: on the first call to an implemented method, they are retrieved and stored in a private field. In other words, methods are resolved through call sites as they are called. This has pros and cons, which you can think about for a while (tip: early binding versus late binding; take the real dynamic nature of dynamic objects and expandos into account as well). Time to move on to CallSite. As mentioned before this is really a rudimentary implementation and DLR / C# 4.0 mechanisms would be very appropriate here, which I’ll talk about another time:

/// <summary>
/// Call site used to dispatch method calls on a thunk type instance to the underlying wrapped type.
/// </summary>
public class CallSite
{
    /// <summary>
    /// Object being wrapped by the thunk this call-site belongs to.
    /// </summary>
    private object _target;

    /// <summary>
    /// Name of the member to dispatch. CLI naming conventions are followed for special-name methods.
    /// </summary>
    private string _member;

    /// <summary>
    /// Creates a call-site to invoke the specified <paramref name="member">member</paramref> on the specified <paramref name="target">target object</paramref>.
    /// </summary>
    /// <param name="target">Target object to dispatch to.</param>
    /// <param name="member">Member to invoke.</param>
    public CallSite(object target, string member)
    {
        _target = target;
        _member = member;
        Invoke = ResolveCall;
    }

    /// <summary>
    /// Helper method to resolve a call the first time it's made through the call-site.
    /// </summary>
    /// <param name="args">Arguments to call the member with.</param>
    /// <returns>Return value from the dispatched call.</returns>
    private object ResolveCall(object[] args)
    {
        //
        // TODO: Richer dispatching techniques, using DLR and C# 4.0 technologies.
        //

        //
        // Simplistic bind and invoke. Ideally we should call specialized binders here,
        // figure out whether the member is available and throw if it isn't. Once we
        // have the target member, we can set up the fast path by overwriting Invoke.
        //
        Invoke = arguments => _target.GetType().InvokeMember(_member, BindingFlags.InvokeMethod, null, _target, args, CultureInfo.InvariantCulture);

        //
        // First time call.
        //
        return Invoke(args);
    }

    /// <summary>
    /// Invocation function used by the emitted code in the thunk to dispatch to the target method wrapped by this call-site.
    /// </summary>
    public Func<object[], object> Invoke { get; private set; }
}

One key concept is illustrated here: thunking. As the call site object is created, the Invoke member (which will be called by the emitted wrapper object, see further) is initially set to ResolveCall. When Invoke is called for the first time, the ResolveCall method it’s pointing at does all the (omitted/simplified in the code above) magic it needs to do in order to resolve the call (what’s in a name?), ultimately replacing Invoke by a new function that calls directly into the underlying member. Again there are pros and cons with regards to caching and the flexibility to do a re-resolve at a later time, so once more: this just illustrates one way of approaching things.

Keep in mind where the CallSite corresponds to in the emitted object: an individual interface method implementation. This means the number of arguments passed in through the args array will always be the same, which is relevant for the call dispatch resolution as well since multiple overloads of the same method on the target interface will each have their own call site object. The way we solve the binding and dispatching here is in the most lame way imaginable: Type.InvokeMember with the default binder. More flexibility, including calling through expando objects, IDynamicObject, etc can be obtained by switching to DLR mechanics (with or without a different call site approach). Obviously you could experiment a little with your own logic in ResolveCall, for example to handle IExpando objects.

Thunking is a technique used in a variety of places, including the CLR’s JIT infrastructure. The way it works there is as follows: upon loading an assembly and its types (assuming the non-ngen case), MethodTable structures in the EE will be filled with entries to a so-called pre-stub helper that invokes the JIT compiler for that method’s associated IL stream when called for the first time. The JIT compiler carries out IL-to-native translation, generating the native code on the heap and patching up the MethodTable entry with an address pointing at the start of the emitted native code. From that point on, for that method, the JIT compiler is out of the picture for the lifetime of the type in memory.

How we cook our wrapper type

Now that we know the macroscopic structure, it’s time to dive into the microscopic world, and how better to start this than looking at what the emitted code should look like? Here’s the hypothetical target code, where the contract is really implemented as an interface of type IDuck:

IDuck duck = dynamicDuck asif {
    void Walk();
    void Walk(int steps);
    object Quack(string name);
    ConsoleColor Color { get; set; }
    event EventHandler Walking;
};

Goal is to define the wrapper type now. We already reached an agreement on its type declaration before, i.e.:

class <NameForTheWrapperObject> : Dynamic, IDuck
{
    <%
        foreach (MemberInfo member in typeof(IDuck).GetMembers())
            ImplementInterfaceMember(member);
    %>
}

Now what does an individual member of the interface look like? In this case IDuck stands by itself, so the call to GetMembers results in the degenerate case where no recursion is required, but in the general case we need recursion. Creating such a recursive method without getting stuck in cycles isn’t too hard, so let’s skip that technicality in this write-up as you can read the code yourself. What’s more interesting is how an individual interface member is implemented like. Starting with the base case of a method, here’s what we intend to do:

object Quack(string name);

becomes

private CallSite _site1;

public object Quack(string name)
{
    if (_site1 == null)
        _site1 = base.GetCallSite(“Walk”);

    return (object)_site1.Invoke(new object[] { name });
}

Here we make sure the field representing the call site for this particular method (overload) is initialized, followed by a call through the site’s Invoke delegate passing in all parameters as an object array and casting the return value back to the return type on the interface member (which turns out to be object anyhow).

As we don’t have the compiler as a service just yet, we need to cook our own IL emission here, so this calls for System.Reflection.Emit magic. As we’re building a type we can’t get away with the DynamicMethod class, so we need to buy in to the entire stack of builder types that provide the chain of “assembly contains modules contains types contains members”. We can short-circuit stuff a bit by limiting ourselves to one assembly containing one module which will contain all the built wrapper types during the execution of the program (actually on a per appdomain level, but let’s ignore that for now).

First we need to have all the machinery to ensure a singleton ModuleBuilder instance:

/// <summary>
/// Ensures the module builder singleton is available.
/// </summary>
private static void EnsureModuleBuilder()
{
    if (s_moduleBuilder == null)
    {
        AssemblyBuilder assemblyBuilder = AppDomain.CurrentDomain.DefineDynamicAssembly(new AssemblyName("DuckTaperGen"), AssemblyBuilderAccess.Run);
        s_moduleBuilder = assemblyBuilder.DefineDynamicModule("Thunks");
    }
}

One relevant thing here is the AssemblyBuilderAccess enum value passed in. We’ll only emit the assembly to run it in memory, but with RunAndSave we could save our thunk-types for reuse as well (I’m overloading the word “thunk” here to indicate a type that acts as a thunk around the wrapped object, feel free to substitute thunk with wrapper in what follows – with some goodwill, the thunking part of it is actually the fact it fills in call sites lazily). Now we have this, it’s time to new up the required TypeBuilder for our thunk type:

/// <summary>
/// Gets a type builder for a type with the specified <paramref name="thunkTypeName">type name</paramref>.
/// </summary>
/// <param name="thunkTypeName">Name of the type to create a type builder for.</param>
/// <returns>Type builder for the specified <paramref name="thunkTypeName">name</paramref>.</returns>
private static TypeBuilder GetTypeBuilder(string thunkTypeName)
{
    return s_moduleBuilder.DefineType(thunkTypeName, TypeAttributes.Class | TypeAttributes.Public | TypeAttributes.AutoLayout | TypeAttributes.AnsiClass | TypeAttributes.Sealed | TypeAttributes.BeforeFieldInit);
}

Here we follow the metadata flags used on classes emitted by the C# compiler, all of which you can find the meaning for in ECMA 335: public, sealed and class are straightforward, others have to do with the type layout, string treatment and initialization guarantees. How will we name our thunk type? It definitely needs to be unique and it’s auto-generated so let’s make it a little obscure:

/// <summary>
/// Gets a unique name for the thunk created for the specified <paramref name="targetType">target type</paramref>.
/// </summary>
/// <param name="targetType">Target type to get a unique thunk type name for.</param>
/// <returns>Thunk type name for the specified <paramref name="targetType">target type</paramref>.</returns>
private static string GetThunkTypeName(Type targetType)
{
    return "<>__Thunks." + targetType.FullName;
}

Remember the CLR doesn’t know about namespaces at all, so the FullName of the passed in type will contain the namespace as well as the prefix (looking as the top namespace), so we’re sure to have a unique name. Given those pieces of glue, we can start moving (back) on to the entry point and take it from there:

/// <summary>
/// Creates a wrapper object of type <typeparamref name="T">T</typeparamref> around the specified <paramref name="target">target</paramref> object.
/// </summary>
/// <typeparam name="T">Target type.</typeparam>
/// <param name="target">Object to be wrapped.</param>
/// <param name="targetType">Target type (avoids having to call typeof again).</param>
/// <param name="shortCircuit">Indicates whether or not short-circuiting is allows if the object already implements the specified interface.</param>
/// <returns>Wrapper around the specified object.</returns>
[SuppressMessage("Microsoft.Design", "CA1004:GenericMethodsShouldProvideTypeParameter", Justification = "By design.")]
private static T AsIfInternal<T>(object target, Type targetType, bool shortCircuit) where T : class
{
    //
    // Short-circuit objects that already implement the interface.
    //
    if (shortCircuit)
    {
        T targetAsT = target as T;
        if (targetAsT != null)
            return targetAsT;
    }

    //
    // Singleton module builder.
    //
    EnsureModuleBuilder();

    //
    // Get the thunk type.
    //
    Type thunkType = GetThunk(targetType);

    //
    // Create and return the thunk instance.
    //
    return (T)Activator.CreateInstance(thunkType, target);
}

/// <summary>
/// Gets the thunk type definition for the specified target type.
/// </summary>
/// <param name="targetType">Target type to get a thunk type definition for.</param>
/// <returns>Thunk type definition for the specified target type.</returns>
/// <remarks>If a thunk type has already been created for the target type, the same type definition will be returned.</remarks>
private static Type GetThunk(Type targetType)
{
    string thunkTypeName = GetThunkTypeName(targetType);

    //
    // Don't regenerate the thunk type if it already exists for the specified target type.
    //
    Type thunkType = s_moduleBuilder.GetType(thunkTypeName, false, false);
    if (thunkType == null)
    {
        thunkType = BuildThunkType(targetType, thunkTypeName);
    }

    return thunkType;
}

Notice how we reuse thunk types in GetThunk if they were already created for the target interface. Thunk types are generic on a per-interface basis as their underlying code deals with a weakly typed object they dispatch to; the individual instances of the thunk type have the opportunity to diverge in terms of their generated call sites in order to provide the fastest possible dispatch to the underlying object for that object’s concrete runtime type. So, the type definition is the same, but the runtime instance can and will vary.

/// <summary>
/// Builds a thunk type definition with the specified <paramref name="thunkTypeName">name</paramref> for the specified <paramref name="targetType">target type</paramref>.
/// </summary>
/// <param name="targetType">Target type to create a thunk type definition for.</param>
/// <param name="thunkTypeName">Name to be used for the created thunk type definition.</param>
/// <returns>Thunk type definition for the specified <paramref name="targetType">target type</paramref>.</returns>
private static Type BuildThunkType(Type targetType, string thunkTypeName)
{
    TypeBuilder typeBuilder = GetTypeBuilder(thunkTypeName);

    //
    // Set the parent type to Dynamic.
    //
    typeBuilder.SetParent(typeof(Dynamic));

    //
    // Implement constructor for thunked object.
    //
    ImplementConstructor(typeBuilder);

    //
    // Implement all interfaces.
    //
    int siteCounter = 0;
    foreach (Type interfaceType in GetInterfaces(targetType))
    {
        ImplementInterface(interfaceType, typeBuilder, ref siteCounter);
    }

    return typeBuilder.CreateType();
}

In BuildThunkType we do the real work in case a thunk hasn’t been created yet. First we set the parent to be Dynamic, next we implement the constructor and finally we implement all interfaces specified by the target type, where we take the closure of all interfaces required. Skipping ImplementConstructor for a while (see next paragraph) and ignoring the recursive definition for GetInterfaces, here’s how ImplementInterface looks like:

/// <summary>
/// Implements the specified <paramref name="interfaceType">interface type</paramref>.
/// </summary>
/// <param name="interfaceType">Interface type to implement.</param>
/// <param name="typeBuilder">Type builder to emit to.</param>
/// <param name="siteCounter">Global counter for site fields used in the thunk type being generated.</param>
private static void ImplementInterface(Type interfaceType, TypeBuilder typeBuilder, ref int siteCounter)
{
    //
    // Add implements clause.
    //
    typeBuilder.AddInterfaceImplementation(interfaceType);

    //
    // Implement all members.
    //
    foreach (MemberInfo member in interfaceType.GetMembers())
    {
        ImplementInterfaceMember(member, typeBuilder, ref siteCounter);
    }
}

Besides the base class set through SetParent, all interfaces end up as base types (in CLI-style speak) and make up the type definition. For every to-be-implemented interface we finally implement every single member in it (otherwise the type would, naturally, be invalid and the CLR would refuse to new it up in the CreateType call). Notice the AddInterfaceImplementation will require the interface to be public as it will be part of another dynamically generated assembly, which is another limitation to our duck taper implementation, since such a weak contract interface is not really meant to be public in most circumstances. Oh well…

Where IL generation kicks in

ImplementConstructor and ImplementInterfaceMember are the remaining pieces of code needed in order to make up the thunk type definition at runtime. The constructor is almost a triviality: simply call the base constructor on Dynamic and return:

/// <summary>
/// Implements the constructor for a thunk type definition.
/// </summary>
/// <param name="typeBuilder">Type builder to emit to.</param>
private static void ImplementConstructor(TypeBuilder typeBuilder)
{
    //
    // public <class>(object @object) : base(@object)
    // {
    // }
    //
    ConstructorBuilder ctorBuilder = typeBuilder.DefineConstructor(MethodAttributes.Public | MethodAttributes.HideBySig | MethodAttributes.SpecialName | MethodAttributes.RTSpecialName, CallingConventions.Standard, new Type[] { typeof(object) });
    ILGenerator ctorILGen = ctorBuilder.GetILGenerator();
    ctorILGen.Emit(OpCodes.Ldarg_0);
    ctorILGen.Emit(OpCodes.Ldarg_1);
    ctorILGen.Emit(OpCodes.Call, typeof(Dynamic).GetConstructor(BindingFlags.Instance | BindingFlags.NonPublic, null, new Type[] { typeof(object) }, null));
    ctorILGen.Emit(OpCodes.Ret);
}

Recall the zero’th argument on an instance method represents the current instance, so Ldarg_1 and above fetch the real arguments. The base constructor we’re calling takes the same argument, i.e. the wrapped object. Ultimately, AsIf calls this constructor passing in the target object that needs to be AsIf’d:

//
// Create and return the thunk instance.
//
return (T)Activator.CreateInstance(thunkType, target);

Now the real work: ImplementInterfaceMember. Here we dispatch based on the type of the member to be implemented:

/// <summary>
/// Implements the specified <paramref name="member">interface member</paramref>.
/// </summary>
/// <param name="member">Member to generate an implementation for.</param>
/// <param name="typeBuilder">Type builder to emit to.</param>
/// <param name="siteCounter">Global counter for site fields used in the thunk type being generated.</param>
private static void ImplementInterfaceMember(MemberInfo member, TypeBuilder typeBuilder, ref int siteCounter)
{
    switch (member.MemberType)
    {
        case MemberTypes.Method:
            ImplementInterfaceMethod(member as MethodInfo, typeBuilder, ref siteCounter);
            break;
        case MemberTypes.Property:
            ImplementInterfaceProperty(member as PropertyInfo, typeBuilder, ref siteCounter);
            break;
        case MemberTypes.Event:
            ImplementInterfaceEvent(member as EventInfo, typeBuilder, ref siteCounter);
            break;
        case MemberTypes.NestedType:
            //
            // Nested interfaces are supported in VB. We ignore the nested interfaces and just implement the top-level interface.
            // This is fine as the nested interface isn't really part of the outer contract (and not an implementation requirement
            // in terms of CLI), but is merely a syntactic convenience method to structure types that belong together.
            //
            break;
        default:
            throw new InvalidOperationException("Unexpected interface member type encountered: " + member.MemberType);
    }
}

I won’t cover all of the three member types individually here. The key take-away is that all are implemented very similarly and ultimately resort to the implementation of methods (properties have getters and setters, events have adders and removers), all of which are the same:

A call site field.
Code to ensure the call site field is initialized (lazy on-demand call site creation) and to call through it.

How to dispatch calls?

The code to dispatch a call isn’t that hard either, but let’s introduce it piece-meal:

/// <summary>
/// Emits a thunk method with the specified <paramref name="methodName">name</paramref>, <paramref name="parameterTypes">parameter types</paramref> and <paramref name="returnType">return type</paramref>.
/// </summary>
/// <param name="typeBuilder">Type builder to emit to.</param>
/// <param name="methodName">Name for the generated method.</param>
/// <param name="parameterTypes">Parameter types for the generated method, or an empty array for no parameters.</param>
/// <param name="returnType">Return type for the generated method. Use typeof(void) for a void-returning method.</param>
/// <param name="targetMethodName">Target method name to call on the object being thunked.</param>
/// <param name="siteCounter">Global counter for site fields used in the thunk type being generated.</param>
/// <param name="specialName">Indicates whether or not the emitted method should be marked as a special name method. Used for properties and events.</param>
/// <returns>Method builder for the generated method.</returns>
private static MethodBuilder EmitMethod(TypeBuilder typeBuilder, string methodName, Type[] parameterTypes, Type returnType, string targetMethodName, ref int siteCounter, bool specialName)
{
    //
    // Method attributes.
    //
    MethodAttributes attributes = MethodAttributes.Public | MethodAttributes.HideBySig | MethodAttributes.NewSlot | MethodAttributes.Virtual | MethodAttributes.Final;
    if (specialName)
        attributes |= MethodAttributes.SpecialName;

Notice draw the distinction between method name and target method name. The former is the one that needs to be implemented on the generated thunk, i.e. the one used in the interface, while the latter denotes the target to call on the wrapped object. This opens up for the possibility to have target method mappings using custom attribute metadata:

public interface IFoo
{
    [TargetMember("Fo")]
    int Foo { get; set; }
}

I won’t elaborate on this mechanism as it’s pretty straightforward to implement, refer to the code for more information. Back to our EmitMethod definition, focusing on a few remaining interesting arguments:

siteCounter is used to number the call site fields on the thunk type; as all our methods here are static we’re threading this around (an attractive alternative in case we’d have more state to drag around would be to have a ThunkBuilder class);
specialName is set to true for “special name methods” such as getters, setters, adders and removers.

Other metadata flags have to do with the vtable dispatching (NewSlot, Virtual) and such. Again, for more information, refer to the CLI spec ECMA 335. Now we start to build the real code:

//
// Define the method.
//
MethodBuilder methodBuilder = typeBuilder.DefineMethod(methodName, attributes, CallingConventions.HasThis, returnType, parameterTypes);
ILGenerator methodILGen = methodBuilder.GetILGenerator();

//
// Get method header to retrieve a reference to the call-site for this method.
//
FieldBuilder callSiteField = EmitGetCallSite(typeBuilder, ref siteCounter, targetMethodName, methodILGen);

First we declare the method, with HasThis calling convention (we’re writing an instance method, so the first argument is to be treated as “this”) and the indicated signature. The first thing we do is emitting the code responsible to ensure the call site object is not null and to create the backing field for it. First the field generation:

/// <summary>
/// Declares a call-site field associated with the target interface method and emits the code for retrieval of the call-site field in the method being generated.
/// </summary>
/// <param name="typeBuilder">Type builder to emit to.</param>
/// <param name="siteCounter">Global counter for site fields used in the thunk type being generated.</param>
/// <param name="targetMethodName">Target method name for the method to dispatch to.</param>
/// <param name="methodILGen">IL generator for the method being generated.</param>
/// <returns>Field builder for the emitted call-site field.</returns>
private static FieldBuilder EmitGetCallSite(TypeBuilder typeBuilder, ref int siteCounter, string targetMethodName, ILGenerator methodILGen)
{
    //
    // Add call-site field.
    //
    FieldBuilder callSiteField = GetNewCallSiteField(typeBuilder, ref siteCounter);

    //
    // Ensure the call-site is initialized.
    //
    EmitCallSiteNullCheckAndInit(callSiteField, targetMethodName, methodILGen);

    //
    // Return field for further reference.
    //
    return callSiteField;
}

/// <summary>
/// Defines a new call-site field.
/// </summary>
/// <param name="typeBuilder">Type builder to emit to.</param>
/// <param name="siteCounter">Global counter for site fields used in the thunk type being generated.</param>
/// <returns>New call-site field.</returns>
private static FieldBuilder GetNewCallSiteField(TypeBuilder typeBuilder, ref int siteCounter)
{
    return typeBuilder.DefineField("_site" + (++siteCounter), typeof(CallSite), FieldAttributes.Private);
}

Here we add a field to our type and increment our global site counter. Now we can refer to it in our method to ensure the field is initialized before calling the Invoke delegate:

/// <summary>
/// Emits code to populate the specified <paramref name="callSiteField">call-site field</paramref> (if not done already) and to retrieve it.
/// </summary>
/// <param name="callSiteField">Call-site field to populate and retrieve.</param>
/// <param name="methodName">Name for the method being generated.</param>
/// <param name="methodILGen">IL generator for the method being generated.</param>
private static void EmitCallSiteNullCheckAndInit(FieldBuilder callSiteField, string methodName, ILGenerator methodILGen)
{
    //
    // if (<callSiteField> == null)
    //     <callSiteField> = base.GetCallSite(<methodName>);
    //
    Label makeCall = methodILGen.DefineLabel();
    methodILGen.Emit(OpCodes.Ldarg_0);
    methodILGen.Emit(OpCodes.Ldfld, callSiteField);
    methodILGen.Emit(OpCodes.Brtrue, makeCall);
    methodILGen.Emit(OpCodes.Ldarg_0);
    methodILGen.Emit(OpCodes.Ldarg_0);
    methodILGen.Emit(OpCodes.Ldstr, methodName);
    methodILGen.Emit(OpCodes.Call, typeof(Dynamic).GetMethod("GetCallSite", BindingFlags.Instance | BindingFlags.NonPublic, null, new Type[] { typeof(string) }, null));
    methodILGen.Emit(OpCodes.Stfld, callSiteField);

    //
    // Target of conditional jump in case call-site was already initialzed; fall-through otherwise.
    //
    methodILGen.MarkLabel(makeCall);
}

Recall our (simplistic) GetCallSite method on Dynamic? Here we call this one in case the current call site field is null. The generated IL goes as follows (_|_ stands for bottom of the stack frame, { … } indicates equivalent C# code executed at that point):

    ldarg_0                      // _|_, this
    ldfld _site1                 // _|_, this._site
    brtrue MakeCall              // _|_ { if (this._site != null) goto MakeCall }
    ldarg_0                     // _|_, this
    ldarg_0                      // _|_, this, this
    ldstr “TargetMethod”         // _|_, this, this, “TargetMethod”
    callvirt Dynamic.GetCallSite // _|_, this, base.GetCallSite(“TargetMethod”)
    stfld _site1                 // _|_ { this._site = base.GetCallSite(“TargetMethod”) }

MakeCall:
    …

Next comes the real work, where we pack up the arguments for the member call and dispatch to our Invoke delegate on the CallSite object. Recall the Invoke delegate is our source of major flexibility: here we yield control to the CallSite implementation to do whatever it sees fit to make the call as efficient as possible. For instance, if it comes to the conclusion you’re invoking a statically defined member on an object, there’s no good reason not to cache the invocation path, maybe on its turn by means of IL generation in a DynamicMethod. We’re lame though and just implement the bare minimum dispatch mechanism, but we still need to make sure we get there, so that’s where calling through the delegate comes in, continuing in our EmitMethod implementation. First we get the delegate:

//
// Func<object[], object> <invoke> = <callSiteField>.Invoke;
//
methodILGen.Emit(OpCodes.Ldarg_0);
methodILGen.Emit(OpCodes.Ldfld, callSiteField);
methodILGen.Emit(OpCodes.Callvirt, typeof(CallSite).GetProperty("Invoke").GetGetMethod());

or, in terms of the generated IL,

    ldarg_0                      // _|_, this
    ldfld _site1                 // _|_, this._site
    callvirt get_Invoke          // _|_, base.Invoke

We even don’t store the delegate instance in a local variable and just keep it on top of our stack. Next we need to pack the arguments to our method in an object array that becomes the argument to the call through Invoke. This is a bit tricky as we might have value types that need to get boxed.

//
// object[] <args> = new object[<number_of_params>];
//
LocalBuilder args = methodILGen.DeclareLocal(typeof(object[]));
methodILGen.Emit(OpCodes.Ldc_I4, parameterTypes.Length);
methodILGen.Emit(OpCodes.Newarr, typeof(object));
methodILGen.Emit(OpCodes.Stloc, args);

//
// <args>[0] = <param_1>;
// <args>[1] = <param_2>;
// ...
// <args>[n] = <param_n+1>;
//
int i = 0;
foreach (Type paramType in parameterTypes)
{
    methodILGen.Emit(OpCodes.Ldloc, args);
    methodILGen.Emit(OpCodes.Ldc_I4, i);
    methodILGen.Emit(OpCodes.Ldarg, i + 1);
    if (paramType.IsValueType)
        methodILGen.Emit(OpCodes.Box, paramType);
    methodILGen.Emit(OpCodes.Stelem_Ref);
    i++;
}

First we declare a local of type object[]. We need this one as we constantly need to load it to store the arguments in one-by-one in the foreach loop below. The dimension of the array is determined by the number of parameters on the member. For methods this count is trivial, for property setters this will include the “value” parameter but also all of the possible indexer arguments. However, we don’t see those complexities in EmitMethod, so I’ll elaborate on this a little further. The IL to create the array and store it in the local variable should be clear. Next we iterate over all of the parameters and implement code to fetch the corresponding argument from the current method call and stick it in the array. Notice the ldarg instruction:

methodILGen.Emit(OpCodes.Ldarg, i + 1);

Here we use i + 1, as the first argument to the method call will be the this pointer and we don’t need that one as an argument to our dispatched method call. Another point of attention is the conditional emission of a boxing instruction when adding a value type to the parameters array. Here’s a typical run in IL including stack transitions, for a method call to Bar(string name, int age):

    ldc_i4 2                     // _|_, 2
    newarr                       // _|_, new object[2]
    stloc args                   // _|_ { args = new object[2] }
    ldloc args                   // _|_, args
    ldc_i4 0                     // _|_, args, 0
    ldarg 1                      // _|_, args, 0, name
    stelem_ref                   // _|_ { args[0] = name }
    ldloc args                   // _|_, args
    ldc_i4 1                     // _|_, args, 1
    ldarg 2                      // _|_, args, 1, age
    box                          // _|_, args, 1, (object)age
    stelem_ref                   // _|_ { args[1] = (object)age }

Now we have packed up the arguments to the call, the next step is to call through the delegate to dispatch the call to the target method through the CallSite thunking mechanisms. The code to emit the IL is very simple:

//
// object <res> = <invoke>(<args>);
//
methodILGen.Emit(OpCodes.Ldloc, args);
methodILGen.Emit(OpCodes.Callvirt, typeof(Func<object[], object>).GetMethod("Invoke"));

which simply calls the delegate’s Invoke method. Finally, if the method is not void-returning, we need to bubble up the return value to the caller, possibly unboxing the return value in case it’s a value type (as the delegate returns us an object). The pop instruction below is required to keep the stack balanced (in the case of ret from a void method):

//
// return <res>;
//
if (returnType != typeof(void))
{
    if (returnType.IsValueType)
        methodILGen.Emit(OpCodes.Unbox_Any, returnType);
}
else
    methodILGen.Emit(OpCodes.Pop);

methodILGen.Emit(OpCodes.Ret);

return methodBuilder;

That’s it – we now how our IL tool arsenal ready to dispatch any call to the underlying object.

How to deal with properties and events

Properties and events are just a little more than regular methods – they also have metadata containing type information and references to the associated methods. If you wonder about indexers, they’re merely the same as properties but with additional arguments. As events are quite similar to properties, we’ll just stick with properties. In a top-down approach, we start by creating a PropertyBuilder:

/// <summary>
/// Implements the specified <paramref name="propertyInfo">property</paramref>.
/// </summary>
/// <param name="propertyInfo">Property to generate an implementation for.</param>
/// <param name="typeBuilder">Type builder to emit to.</param>
/// <param name="siteCounter">Global counter for site fields used in the thunk type being generated.</param>
private static void ImplementInterfaceProperty(PropertyInfo propertyInfo, TypeBuilder typeBuilder, ref int siteCounter)
{
    //
    // Reconstruction of the signature.
    //
    Type returnType = propertyInfo.PropertyType;
    Type[] parameterTypes = propertyInfo.GetIndexParameters().Select(parameter => parameter.ParameterType).ToArray();

    //
    // Get the full name for the member.
    //
    string propertyName = GetTargetMemberName(propertyInfo);

    //
    // Define the property.
    //
    PropertyBuilder propertyBuilder = typeBuilder.DefineProperty(propertyName, PropertyAttributes.None, returnType, parameterTypes);

    //
    // Getter.
    //
    if (propertyInfo.CanRead)
        ImplementInterfacePropertyGetter(propertyInfo, typeBuilder, propertyBuilder, parameterTypes, ref siteCounter);

    //
    // Setter.
    //
    if (propertyInfo.CanWrite)
        ImplementInterfacePropertySetter(propertyInfo, typeBuilder, propertyBuilder, parameterTypes, ref siteCounter);
}

First we determine the “signature of the property”, which is relevant for indexed properties (indexers in C# lingo). Next, we perform the mapping between the interface member and the underlying property name to dispatch to. In the regular case this will be a one-on-one mapping, but using TargetMemberAttribute one can change that default:

public interface IFoo
{
[TargetMember("Fo")]
int Foo { get; set; }
}

GetTargetMemberName is the one that performs this mapping resolution using custom attributes. Finally we define the property and add a getter and/or setter to it depending on what the interface requires. Here we get in the terrain of our old EmitMethod friend, but with some intermediate work left to do in order to resolve the underlying method name (like get_, set_, etc):

/// <summary>
/// Emits the method definition for a property getter.
/// </summary>
/// <param name="propertyInfo">Property to generate a property getter implementation for.</param>
/// <param name="typeBuilder">Type builder to emit to.</param>
/// <param name="propertyBuilder">Property builder to associate the getter method with.</param>
/// <param name="parameterTypes">Parameters used for indexed properties, or an empty array for regular properties.</param>
/// <param name="siteCounter">Global counter for site fields used in the thunk type being generated.</param>
private static void ImplementInterfacePropertyGetter(PropertyInfo propertyInfo, TypeBuilder typeBuilder, PropertyBuilder propertyBuilder, Type[] parameterTypes, ref int siteCounter)
{
    const string GETPREFIX = "get_";

    //
    // Get thunk-to-target name mapping.
    //
    string methodName;
    string targetMethodName;
    GetMethodNamesForThunkAndTarget(propertyInfo, GETPREFIX, out methodName, out targetMethodName);

    //
    // Emit the getter.
    //
    MethodBuilder methodBuilder = EmitMethod(typeBuilder, methodName, parameterTypes, propertyBuilder.PropertyType, targetMethodName, ref siteCounter, true);

    //
    // Set the getter.
    //
    propertyBuilder.SetGetMethod(methodBuilder);
}

The only piece of glue here is a method called GetMethodNamesForThunkAndTarget that constructs the names of both the source method (e.g. get_Price, on the interface) and the target method (e.g. get_UnitPrice, on the target object). One other relevant thing here is the last parameter to EmitMethod, which is set to true, indicating the fact the emitted method is a “special name” one.

What’s the result?

To make all this IL voodoo concrete, here’s the corresponding C# code for the class generated on our original sample:

IDuck duck = dynamicDuck asif {
    void Walk();
    void Walk(int steps);
    object Quack(string name);
    ConsoleColor Color { get; set; }
    event EventHandler Walking;
};

becomes

IDuck duck = new <>__Thunks.IDuck(dynamicDuck);

where

namespace <>__Thunks
{
    public sealed class IDuck : Dynamic, TheNamespaceWhereIDuckLives.IDuck
    {
        public IDuck(object o) : base(o) { }

        private CallSite _site1;

        public void Walk()
        {
            if (_site1 == null)
                _site1 = base.GetCallSite(“Walk”);
            _site1.Invoke(new object[0]);
        }

        private CallSite _site2;

        public void Walk(int steps)
        {
            if (_site2 == null)
                _site2 = base.GetCallSite(“Walk”);
            _site2.Invoke(new object[] { steps });
        }

        private CallSite _site3;

        public object Quack(string name)
        {
            if (_site3 == null)
                _site3 = base.GetCallSite(“Quack”);
            return _site3.Invoke(new object[] { name });
        }

        private CallSite _site4;
        private CallSite _site5;

        public ConsoleColor Color
        {
            get
            {
                if (_site4 == null)
                    _site4 = base.GetCallSite(“get_Color”);
                return _site4.Invoke(new object[0]);
            }

            set
            {
                if (_site5 == null)
                    _site5 = base.GetCallSite(“set_Color”);
                return (ConsoleColor)_site5.Invoke(new object[] { value });
            }
        }

        private CallSite _site6;
        private CallSite _site7;

        public EventHandler Walking
        {
            add
            {
                if (_site6 == null)
                    _site6 = base.GetCallSite(“add_Walking”);
                _site6.Invoke(new object[] { value });
            }

            remove
            {
                if (_site7 == null)
                    _site7 = base.GetCallSite(“remove_Walking”);
                _site7.Invoke(new object[] { value });
            }
        }
    }
}

How’s performance doing?

Now that we have our new toy, time to evaluate how we’re doing at this stage from a performance point of view. Before we discuss though, it’s important to emphasize the fact we’re focusing on a dynamic casting operation, i.e. it should work regardless of the object passed in (assuming that method implements the right members). What we have now is a degenerate case though, where we have CallSites that are only aware about the possibility to dispatch to a static type in a late-bound way. Additional tests, such as checking for expandos or IDynamicObjects, would be required to get the desired level of flexibility and will definitely incur a runtime cost. However, with our simplified code we can set a baseline on what to expect.

Here’s a very simple test that compares the performance of calling through a vtable directly based on static type knowledge, versus dispatching through our duck taper:

static void TestDucks()
{
    MeasureDuckPerformance("Static duck", () => new Duck2());
    MeasureDuckPerformance("Dynamic duck", () => GetDuck().AsIf<IDuck>());
}

static void MeasureDuckPerformance(string description, Func<IDuck> duckGetter)
{
    TimeSpan performance = DuckTest(duckGetter, 10000, duck =>
    {
        duck.Color = ConsoleColor.Blue;
        duck.Walking += duck_Walking;
        duck.Walk();
        duck.Quack("Bart");
        duck.Walk(3);
        duck.Walking -= duck_Walking;
    });

    Console.WriteLine(description + ": " + performance);
}

static TimeSpan DuckTest(Func<IDuck> duckGetter, int count, Action<IDuck> duckTest)
{
    IDuck duck = duckGetter();

    Stopwatch sw = new Stopwatch();
    sw.Start();
    for (int i = 0; i < count; i++)
        duckTest(duck);
    sw.Stop();

    return sw.Elapsed;
}

The results looks as follows:

Dynamic duck: 00:00:01.1504488
Static duck: 00:00:02.2274213

A factor two the difference, not too bad after all. This should be enough to satisfy our curiosity around dynamic dispatch mechanisms. There’s a lot of additional possibilities here, ranging from controlling dispatch behavior (early or late binding), optimizing with caching strategies, and so on. In future posts I might delve into the details of more flexible dispatching mechanisms, advanced ways to do caching and the technique of implementing “fast paths”. But then I might as well start talking about the crossroads where DLR and C# 4.0 meet, and we’re back to our promise: “why this is not a C# 4.0 blog post”.

Have fun!

“The C# Programming Language Third Edition” and thoughts on language evolution

bart — Mon, 20 Oct 2008 02:22:53 GMT

With a hypothetical next release of the C# language around the corner (more about that after Anders, our language Caesar, has delivered his “Future of C#” talk on the PDC 08), I’ve had the honor to receive an early print of The C# Programming Language Third Edition. As you can guess, this book is the successor to The C# Programming Language Second Edition, now extended with coverage for the C# 3.0 features and based on the unified C# Language Specification 3.0.

So why would you want to buy a language specification in book format? Personally I like to have those things in print on my desk, just like I have The Common Language Infrastructure Annotated Standard on my desk (unfortunately lagging behind a bit on ECMA 335). But there’s more to it with this new edition of the book: it got annotated by a bunch of people, providing additional insights about the different language features, design decisions, consequences of those decisions, best practices on when and how to use certain features, etc. In other words, if you like to have the ultimate coverage of the C# language (not its uses through certain tools using certain libraries) but don’t want to be bored to death by language specification legalese, this book is for you. The annotations are numerous, enlightening and by times funny.

Some language history

Talking about language evolution, people often raise the question where the language is going with all those new fancy features. Doesn’t it become too bloated? Well, every new feature definitely ages the language (quoting Anders here) and some of the original features are ready for the graveyard because they got superseded by newer more powerful features. And yes, having more features means there’s more to learn when approaching the language. But at the same time, one shouldn’t forget about the core value of a language: capturing common paradigms and patterns, making them easier to use (expressiveness) and less error-prone. A few samples to illustrate this point.

Starting with C# 1.0, one of the common design themes of the language was what I’d call “honesty and pragmatism”. Programmers were talking all the time about e.g. properties, events and function pointers, so why shouldn’t these concepts become constructs directly available in the language? Such observations not only shaped the language but the underlying runtime as well, resulting in first-class support for metadata everywhere (well, almost everywhere). Pragmatic, yes, but honest? Sure enough. Although strictly speaking concepts like properties are foreign to minimalistic object-oriented programming (yes, you can mimic function pointers by one-method-interfaces, and events can be simulated by likewise means), sprinkling a little bit of syntactical sugar and equally important metadata on top provides great benefits with regards to code understandability, tooling and runtime metadata inspection features (known as reflection). But this was only the beginning, as the “Cool” (C-style object oriented language) language also embraced and captured common patterns such as iteration (foreach), proper handling of resources (using), resource locking (lock), etc. Nevertheless, there have always been features that are very powerful but shouldn’t be abused or misused, such as operator overloading, unsafe code, … And of course, the language doesn’t expose all of the underlying runtime’s features such as – just to name a few, there are many more – tail calls, typed references and arglists (somehow that sounds familiar).

In C# 2.0, generics were introduced, making the “Cup of T” approach for collections (and more) a first-class citizen in the runtime and language, resulting in less errors and various other benefits (performance, richer IntelliSense, etc). At the same time, generics made previous “features” (partially) redundant. To point out one of these cases, refer to section 8.8.4 in the book you’re about to buy, covering the foreach loop. Before we had IEnumerable<T>, foreach had to deal with the non-generic counterpart resulting in quite some interesting complications that have to do with boxing and the use of casts on the iteration variable (as developers typically would like to iterate over the collection using a type more specific than System.Object, but there were no generics to give guarantees about the collection’s element type). This is a sample of where a new feature solves known problems while also opening the gateway to lots of new things that weren’t possible before. One such thing is a generalization of “nullability”, the lack of which has plagued many developers before when dealing with database records where the distinction between value and reference types doesn’t exist typically. Looking at the nullable type feature in C# 2.0, again the common theme of making common tasks easier pops up, while solving subtle shortcomings of previous releases, in this particular case with the unified type system lacking nullability for value types (a more fundamental “issue” that has quite some language impact, e.g. the use of the default keyword when dealing with generics, more cases to consider in the generics constraint mechanism, etc).

Although C# 2.0 was mostly about catching up on original design plans, there was also room for some innovation. I don’t know precisely when the idea about iterators came up, but these were definitely one of the more exotic features in the second release of the language, opening for lots of new possibilities. While standing on the shoulders of giants (in this case generics), newer language features start building again upon these (as you can guess I’m referring to LINQ to Objects, heavily relying on iterators). One especially notable thing about the C# 2.0 release was its dependence on new runtime-level features to support generics (ECMA 335 and TR/89), so there’s no “Lost in translation” C#-2.0-to-1.0 approach possible. And again, the language didn’t expose the underlying empowering runtime mechanism fully, namely with regards to generics variance (ECMA 335 II.9.5).

Our latest release so far, C# 3.0, followed the same principles but was really the first one to innovate or revolutionize the way we develop typical applications, whether it’s in the business domain (first class data querying with LINQ), in a scientific atmosphere (lambda BLOCKED EXPRESSION or to enter the New World of Meta Programming (expression trees). Once more, features from previous releases, such as generics and iterators, become increasingly important to build newer features on. Radically different from C# 1.0 to 2.0, no runtime extensions were needed, allowing for a real “Lost in translation” translation from C# 3.0 onto equivalent C# 2.0 constructs (not saying anything about readability of such a translation’s result though). Again in the realm of simplifying programming, other constructs like auto-implemented properties and local variable type type inference were introduced, giving the language a more dynamic feeling while keeping strong-typing all the way through. Silly complexities to new up objects or collections were eliminated with new initializer syntaxes and specifying functions does no longer require noisy keywords like “delegate” (referring to the use in anonymous methods) thanks to lambda syntax. And while I admit that some of the syntax looks foreign, most of it can be understood straight away (maybe the only exception is the lambda arrow that requires one aha-erlebnis), so readability doesn’t suffer. As usual, features can get abused just like a Swiss knife is a powerful tool but can be used for bad purposes too. Samples include over-use of local variable type inference at the cost of readability, or inappropriate use of extension methods.

A changing landscape

Languages (especially general-purpose ones) need to adapt to a changing programming landscape if they want to stay relevant. And while specialized domains hugely benefit from non-general purpose languages (not to use words like DSLs just yet) – and a mixed-language approach to solving problems is entirely possible thanks to the CLS – some concepts that used to be exotic or irrelevant are becoming mainstream for the first time (or again after being doomed dead a while ago). One such first-timer is functional style of programming. I’m deliberately highlighting the word style as I’m not referring to extremist functional programming (lazy evaluation, no side-effects, use of monads) but rather to influences originating from functional languages and all the underlying theory making their way into mainstream languages. C# 2.0 introduced the glue with true closures, C# 3.0 provided easier syntax with lambdas. And those investments have already paid off hugely with the advent of libraries like the Task Parallel Library and various LINQ implementations. In some sense, LINQ’s mission brought more clarity (insider’s joke) to the concurrency domain, almost as a side-effect :-).

Concurrency is huge; Anders called it the elephant in the room in his JAOO talk (actually our hypothetical new version got a name in an interview with Anders on JAOO, I promise you the name won’t be a big surprise…). It has many faces, spreading from one machine to multiple machines, impacting not only the languages but also the way libraries are built and programs are written. Not to talk about tool support, operating system level changes, and the subtle interactions with hypervisor technologies (VM guests that want to benefit from multiple cores, trying not to collide with one another, etc). So there’s lots of work to be done in this domain to shape languages and tackle the beast. It doesn’t come for free though and things will have to give in: shifting from imperative style to a more declarative style, giving up on “mutable data structures everywhere” (notice the placing of the quotes), etc. Essentially sharing knowledge about the problem at hand with the runtime, rather than over-specifying a particular approach to solve the problem.

But there are other things going on as well, more specifically in the camp of dynamic languages and libraries. Call it the Python or Ruby movement if you want. Several years ago it felt as if the importance of dynamic languages was decreasing but several factors have given them a boost once more. First of all there’s the productivity gain by using interactive editors and consoles: fast prototyping, script-driven development, etc. For that same reason, Windows PowerShell has become so popular and all of the benefits from dynamic languages are apparent in PowerShell: interactively investigating the system as you go, scripting support, a rich and extensible type system (ETS, get-member), and more to come with v2.0 (mobile types for remoting to name just one feature). Actually Windows PowerShell proves that reaching out to statically typed libraries from a dynamic world is incredibly easy, and so do F#, IronPython and IronRuby, all bringing the huge .NET Framework libraries in reach within the dynamic world (F# shares some of the dynamic characteristics such as an interactive console, but just has a huge amount of type inferencing that helps to decrease the verbosity of statically typed languages). But what about the reverse operation, calling dynamic libraries from a statically typed world? Why would one want to do such a thing you might wonder? For one, there are huge useful libraries in that camp too, so why should one not be able to reach out to these? But there’s more, with the increasingly popular web/cloud-oriented software approach, code gets surrounded more and more by a dynamic sea: JavaScript, AJAX, REST, etc all have dynamic characteristics while platforms like Silverlight are floating around in that sea, embedded in web pages. Having easy interop facilities between both worlds is therefore becoming increasingly important and relevant. Think of it as reversing the arrow in “talking from DLR to CLR is easy”.

Finally, I’d point out a third source of language potential: the meta-programming paradigm. It’s maybe the least understood and most ill-defined of the three, but domain specific islands within general-purpose environments (not to just say languages) have an enormous potential, if not abused. Environments like PowerShell have first-class support for regular expressions (-match operator), C# 3.0 and VB 9.0 have LINQ, but what about giving developers the means to cook their own DSLs when appropriate? Here we enter the realm of expression, statement and declaration trees (as implemented in the DLR), running compilers as services (CodeDOM and complete-program source compiler invocations – as in ASP.NET code behind – were the first, albeit degenerate and brute force approach, glimpse of this technique; later followed by LambdaExpression.Compile). Fluent interfaces can be seen as the poor man’s DSLs and going beyond that with Internal DSLs is something that might prove useful in the future. Some people have (and still) bet on AOP as the new big paradigm after OO. Well, I’d put more bets on MP if I get to choose. While it’s not incompatible with ideas from OO, it has the potential of adding another dimension to programming. We already have a spatial extent with data-driven (OO) and operation-driven (procedural and functional) decomposition axes; MP could add a dimension to this picture, in the form of specialized problem space islands within a bigger language. Whether or not it’s really orthogonal is a question we’ll leave open for the time being…

Future will tell, and part of that future is coming at PDC 08. Enjoy!

To Bind or Not To Bind – Dynamic Expression Trees – Intermezzo: SOS in Visual Studio

bart — Fri, 29 Aug 2008 10:05:16 GMT

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:

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

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:

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:

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>:

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:

We can follow it through to the IL again:

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:

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:

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:

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:

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

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

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:

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:

(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.

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).

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).

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):

Dumping the binder’s method table gives us:

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:

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:

The result is predictable by now I guess.

To Bind or Not To Bind – Dynamic Expression Trees – Part 3

bart — Thu, 28 Aug 2008 17:35:00 GMT

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?

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:

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:

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):

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?

To Bind or Not To Bind – Dynamic Expression Trees – Part 2

bart — Wed, 27 Aug 2008 23:05:00 GMT

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:

Create an IL stream; here the IL stack is empty.
Take the Body expression and compile it by emitting IL instructions for it; this causes the IL stack to be one high.
Add an IL return instruction to return the object on top of the stack.
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? :-)

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):

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:

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:

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:

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

To Bind or Not To Bind – Dynamic Expression Trees – Part 1

bart — Wed, 27 Aug 2008 05:40:00 GMT

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:

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!