B# .NET Blog : C# 4.0

Reader Challenge – Fault Handlers in C#

bart — Sun, 06 Dec 2009 20:57:48 GMT

The CLR’s exception handling facilities provide for protected blocks (“try”) one can associate a handler with. There are four kinds of handlers, and exactly one can be associated with a protected block (but nesting can be used to associate multiple handlers with a block of code):

A finally handler is executed whenever the block is exited, regardless of whether this happened by normal control flow or an unhandled exception. C# exposes this using the finally keyword.
A type-filtered handler handles an exception of a specified class or any of its subclasses. Better known as a “catch block”, C# provides this through its catch keyword.
A user-filtered handler runs user-specified code to determine whether the exception should be ignored, handled by the associated handler, or passed on to the next protected block. C# doesn’t expose this, but Visual Basic does by means of its When keyword.
A fault handler is executed if an exception occurs, but not on completion of normal control flow. Neither C# nor Visual Basic provide a fault handler language feature.

In this reader challenge, we’re going to focus on fault handlers. Due to their lack of language surface, their effect is often mimicked by using some local state to determine whether the protected block exited gracefully or not:

bool success = false;
try
{
    // Do stuff
    success = true;
}
finally
{
   if (!success)
   {
       // There was a fault. Do something special.
   }
   // Fault or not; this is what finally does.
}

If an exception happens during “Do stuff”, we end up in the finally block and come to conclude success was never set to true. This indicates an error happened, and we should handle the fault case. However, this technique can get a bit tricky when there are different paths exiting the try block: one could return from the enclosing method in various places, requiring the “success = true” code to be sprinkled around. This is exactly what exception handling was designed for: reducing clutter in your code that has to do with error condition/code tracking. So, we’re defeating that purpose.

Today’s challenge is to create a true fault handler in C#, just for the sake of it. This is merely a brain teaser, encouraging readers to find out what happens behind the scenes of compiled C# code. We won’t be addressing certain concerns like non-local return (the case I mentioned above) but will be hunting for the true “fault” handler treasure hidden deeply in the C# compiler’s IL code emitter. The operational specification is the following:

var f = Fault(() => Console.WriteLine("Okay"),
              () => Console.WriteLine("Fault"));
f();
Console.WriteLine();

var g = Fault(() => { throw new Exception("Oops"); },
              () => Console.WriteLine("Fault"));
try
{
    g();
}
catch (Exception ex)
{
    Console.WriteLine(ex);
}

The above should produce the following output:

Okay

Fault
System.Exception: Oops
   at Program.<Main>b__2()
   (I won’t reveal the secrets here yet…)
   at Program.Main()

Action f illustrates the non-exceptional case where the fault handler is not invoked (a finally handler would get invoked). Action g illustrates the exceptional case where the fault handler gets invoked and the exception bubbles up to the catch-block surrounding its invocation.

It’s strictly forbidden to use local state in Fault (or a method it calls) to track the successful execution of the protected block. Therefore, the below is an invalid solution:

static Action Fault(Action protectedBlock, Action faultHandler)
{
    return () =>
    {
        bool success = false;
        try
        {
            protectedBlock();
            success = true;
        }
        finally
        {
            if (!success)
                faultHandler();
        }
    };
}

Moreover, execution of your Fault method should really use a fault handler as encountered in IL code. It should be a fault handler, not mimic one. In addition, you should not go for a solution where you write a Fault method in ILASM by hand and link it as a netmodule in a C# project, using al.exe:

.class private FaultClosure
{
.field class [System.Core]System.Action protectedBlock
.field class [System.Core]System.Action faultHandler

.method void .ctor()
{
    ldarg.0
    call instance void [mscorlib]System.Object::.ctor()
    ret
}

.method void Do()
{
    .try
    {
      ldarg.0
      ldfld class [System.Core]System.Action Program/FaultClosure::protectedBlock
      callvirt instance void [System.Core]System.Action::Invoke()
      leave.s END
    }
    fault
    {
      ldarg.0
      ldfld class [System.Core]System.Action Program/FaultClosure::faultHandler
      callvirt instance void [System.Core]System.Action::Invoke()
      endfault
    }
    END: ret
}
}

.method static class [System.Core]System.Action Fault(class [System.Core]System.Action protectedBlock, class [System.Core]System.Action faultHandler)
{
.locals init (class Program/FaultClosure V_0)
newobj void Program/FaultClosure::.ctor()
stloc.0
ldloc.0
ldarg.0
stfld class [System.Core]System.Action Program/FaultClosure::protectedBlock
ldloc.0
ldarg.1
stfld class [System.Core]System.Action Program/FaultClosure::faultHandler
ldloc.0
ldftn instance void Program/FaultClosure::Do()
newobj void [System.Core]System.Action::.ctor(object, native int)
ret
}

Again, this exercise is just for fun with no profit other than brain stimulation. Hint: what C# 2.0 or later feature may cause a “fault” block to be emitted (i.e. if you ildasm a compiled valid C# application, you can find a “fault” keyword)?

Happy holidays!

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.

Statement Trees With Less Pain – Follow-Up on System.Linq.Expressions v4.0

bart — Tue, 11 Aug 2009 16:06:22 GMT

Introduction

In my last post, Expression Trees, Take Two – Introducing System.Linq.Expressions v4.0, I showed how to the extensions to the LINQ expression trees API opens up for full-blown statement trees including support for assignment, control flow, etc. One popular question that came up in the comments section is on the lack of language-level support for statement trees, like this:

Expression<Func<int, List<int>>> getPrimes = to =>
{
    var res = new List<int>();
    for (int n = 2; n <= to; n++)
    {
        bool found = false;

        for (int d = 2; d <= Math.Sqrt(n); d++)
        {
            if (n % d == 0)
            {
                found = true;
                break;
            }
        }

        if (!found)
            res.Add(n);
    }
    return res;
};

At this point, the above won’t work and trigger the following compile error:

A lambda expression with a statement body cannot be converted to an expression tree

This hasn’t changed from the previous release. Though it would be a nice feature to have, there are various reasons not to have it integrated with the language at this point. My posts to the comments section of my previous post elaborate on some of the conservative constraints employed during language design, applied to this particular case. So, sorry: not at this point.

The result is the above turns into quite an involved statement tree declaration if done by hand. Let’s repeat it here to set the scene:

var to = Expression.Parameter(typeof(int), "to");
var res = Expression.Variable(typeof(List<int>), "res");
var n = Expression.Variable(typeof(int), "n");
var found = Expression.Variable(typeof(bool), "found");
var d = Expression.Variable(typeof(int), "d");
var breakOuter = Expression.Label();
var breakInner = Expression.Label();
var getPrimes = 
    // Func<int, List<int>> getPrimes =
    Expression.Lambda<Func<int, List<int>>>(
        // {
        Expression.Block(
            // List<int> res;
            new [] { res },
            // res = new List<int>();
            Expression.Assign(
                res,
                Expression.New(typeof(List<int>))
            ),
            // {
            Expression.Block(
                // int n;
                new [] { n },
                // n = 2;
                Expression.Assign(
                    n,
                    Expression.Constant(2)
                ),
                // while (true)
                Expression.Loop(
                    // {
                    Expression.Block(
                        // if
                        Expression.IfThen(
                            // (!
                            Expression.Not(
                                // (n <= to)
                                Expression.LessThanOrEqual(
                                    n,
                                    to
                                )
                            // )
                            ),
                            // break;
                            Expression.Break(breakOuter)
                        ),
                        // {
                        Expression.Block(
                            // bool found;
                            new[] { found },
                            // found = false;
                            Expression.Assign(
                                found,
                                Expression.Constant(false)
                            ),
                            // {
                            Expression.Block(
                                // int d;
                                new [] { d },
                                // d = 2;
                                Expression.Assign(
                                    d,
                                    Expression.Constant(2)
                                ),
                                // while (true)
                                Expression.Loop(
                                    // {
                                    Expression.Block(
                                        // if
                                        Expression.IfThen(
                                            // (!
                                            Expression.Not(
                                                // d <= Math.Sqrt(n)
                                                Expression.LessThanOrEqual(
                                                    d,
                                                    Expression.Convert(
                                                        Expression.Call(
                                                            null,
                                                            typeof(Math).GetMethod("Sqrt"),
                                                            Expression.Convert(
                                                                n,
                                                                typeof(double)
                                                            )
                                                        ),
                                                        typeof(int)
                                                    )
                                                )
                                            // )
                                            ),
                                            // break;
                                            Expression.Break(breakInner)
                                        ),
                                        // {
                                        Expression.Block(
                                            // if (n % d == 0)
                                            Expression.IfThen(
                                                Expression.Equal(
                                                    Expression.Modulo(
                                                        n,
                                                        d
                                                    ),
                                                    Expression.Constant(0)
                                                ),
                                                // {
                                                Expression.Block(
                                                    // found = true;
                                                    Expression.Assign(
                                                        found,
                                                        Expression.Constant(true)
                                                    ),
                                                    // break;
                                                    Expression.Break(breakInner)
                                                // }
                                                )
                                            )
                                        // }
                                        ),
                                        // d++;
                                        Expression.PostIncrementAssign(d)
                                    // }
                                    ),
                                    breakInner
                                )
                            ),
                            // if
                            Expression.IfThen(
                                // (!found)
                                Expression.Not(found),
                                //    res.Add(n);
                                Expression.Call(
                                    res,
                                    typeof(List<int>).GetMethod("Add"),
                                    n
                                )
                            )
                        ),
                        // n++;
                        Expression.PostIncrementAssign(n)
                    // }
                    ),
                    breakOuter
                )
            ),
            res
        ),
        to
    // }
    ).Compile();

I’ve formatted a bunch of nodes in the expression tree above to indicate the “tiles” that are based on the v3.0 subset of the Expression Tree APIs, which do have language support. What if we could simplify the declaration above by leveraging the language support at places where it’s worthwhile? A tour through simplifying statement trees…

Abstraction + application = ???

Without much further ado, let’s dive straight into our pool of expression tree tricks and reveal the goods for this round: abstraction and application. Guess what, we’re back to fundamental lambda calculus. An explanation is in order:

Abstraction is the act of abstracting over an expression, i.e. introducing a parameterized function. Given an expression, turning a symbol therein into a parameter is what it takes to abstract over the expression:
Application is also known as beta-reduction and corresponds to the act of applying a function given one or more arguments (strictly speaking one at a time):

Given those fundamental laws in lambda calculus, we can create a very round-about way of expressing 1 + 2. Just reverse the arrows in the last diagram: 2 becomes y, 1 becomes x, both “abstracting away” the constants one at a time, resulting in a function that’s readily applied to the two constants.

This basic insight is what will help us to simplify the statement tree declaration, allowing us to “tile in” expression trees in the bigger soup of statement tree nodes. But before we go there, let’s show the technique above in practice. Say we want to over-complicate the act of adding 1 and 2 together and do so through a deviation along the road of abstraction and application:

var x = Expression.Parameter(typeof(int), "x");
var y = Expression.Parameter(typeof(int), "y");
var f = Expression.Lambda<Func<int, int, int>>(
    Expression.Add(x, y),
    x, y
);
var three = Expression.Invoke(
    f,
    Expression.Constant(1),
    Expression.Constant(2)
);
var res = Expression.Lambda<Func<int>>(three).Compile();

Console.WriteLine(res());

What’s happening here is not that difficult as it may seem at first glance. The “f” lambda expression simply is a function that goes from x and y to x + y (in C# lingo, (x, y) => x + y). Expression.Invoke is used to invoke a delegate (lambdas ultimately are delegates), this time supplying the arguments. So, “three” is shorthand for ((x, y) => x + y)(1, 2), which is longhand for 1 + 2. Finally, the “res” lambda expression is a simple function returning an int, being the result of the invocation of the sum abstraction.

Looking at the generated IL code for the “res” delegate (using the tricks revealed in the previous post), we see the following:

IL_0000: ldc.i4.1
IL_0001: ldc.i4.2
IL_0002: stloc.1
IL_0003: stloc.0
IL_0004: ldloc.0
IL_0005: ldloc.1
IL_0006: add
IL_0007: ret

Did you see it? You did? Great! Exactly, no single trace of a delegate call in here. The combination of application (InvocationExpression) over an abstraction (LambdaExpression) got optimized away. Instead of pushing constants 1 and 2 on the stack in preparation of a delegate invocation call instruction, they get stored in locals, followed by a dump of the invoked function’s IL where the expected ldarg instructions are replaced by ldloc instructions. All in all, it’s still as if we’d written:

var res = Expression.Lambda<Func<int>>(
    Expression.Add(
        Expression.Constant(1),
        Expression.Constant(2)
    )
).Compile();

which translates in slightly simpler IL code:

IL_0000: ldc.i4.1
IL_0001: ldc.i4.2
IL_0002: add
IL_0003: ret

Eliminating the excessive stloc/ldloc pairs in the original fragment is something the JIT compiler could take care of it feels happy to do so, but the core message here is that this trick of “abstract & apply” is cheaper than it looks.

Why am I telling you all of this? In fact, the trick outlined above is what we’ll use to tile in language-generated expression trees in a bigger sea of hand-crafted statement trees. For the sample above, what if we made the function definition through abstraction happen using the language-level support, while keeping the invocation call in plain hand-crafted expression trees:

var three = Expression.Invoke(
    (Expression<Func<int, int, int>>)((x, y) => x + y),
    Expression.Constant(1),
    Expression.Constant(2)
);
var res = Expression.Lambda<Func<int>>(three).Compile();

See it coming? Think about it for a while: we’re combining a compiler-generated expression tree with a manually created bigger one in which we embed the smaller one.

Theory applied

To keep things a bit more controlled, focus on one part of the original statement tree:

Expression.IfThen(
    // (!
    Expression.Not(
        // d <= Math.Sqrt(n)
        Expression.LessThanOrEqual(
            d,
            Expression.Convert(
                Expression.Call(
                    null,
                    typeof(Math).GetMethod("Sqrt"),
                    Expression.Convert(
                        n,
                        typeof(double)
                    )
                ),
                typeof(int)
            )
        )
    // )
    ),
    // break;
    Expression.Break(breakInner)
),

This corresponds to the terminating condition for the inner loop:

for (int d = 2; d <= Math.Sqrt(n); d++)
{
    if (n % d == 0)
    {
        found = true;
        break;
    }
}

As we all know, that’s a plain old valued expression that could be turned into a function as follows:

Func<int, int, bool> cond = (x, y) => x <= Math.Sqrt(y);
for (int d = 2; cond(d, n); d++)
{
    if (n % d == 0)
    {
        found = true;
        break;
    }
}

Now we’re getting somewhere. The code above is exactly the same as the original one, but we’ve abstracted over the condition by turning it into a function of its own, which we subsequently apply given d and n. For regular code, that doesn’t make much sense, but it’s exactly the trick we’re talking about here and that will make the expression tree case simpler. What if we translated the code above as follows?

Expression<Func<int, int, bool>> cond = (x, y) => x <= Math.Sqrt(y);
for (int d = 2; cond.Compile()(d, n); d++)
{
    if (n % d == 0)
    {
        found = true;
        break;
    }
}

Heh, there’s our expression tree for the condition. As we’re still not generating the whole for-loop in a statement tree, we have to call Compile explicitly on the intermediate lambda expression to invoke it in the condition part of the for-loop. Now we can take it one step further and go back to the expression tree for the whole for-loop, patching it up with our intermediate “cond” expression tree … using application. At the same time, we can eat the “Not” node:

Expression.IfThen(
    // (!
    Expression.Not(
        // d <= Math.Sqrt(n)
        Expression.LessThanOrEqual(
            d,
            Expression.Convert(
                Expression.Call(
                    null,
                    typeof(Math).GetMethod("Sqrt"),
                    Expression.Convert(
                        n,
                        typeof(double)
                    )
                ),
                typeof(int)
            )
        )
    // )
    ),
    // break;
    Expression.Break(breakInner)
),

In essence, the first argument to IfThen (i.e. the if-statement’s condition expression) contains two variables from the outer scope: d and n. We’ll abstract over those, introducing an intermediate lambda expression, and invoke (apply) that one using d and n. Code is worth a thousand words:

Expression.IfThen(
    // (!(d <= Math.Sqrt(n)))
    Expression.Invoke(
        (Expression<Func<int, int, bool>>)((x, y) => !(x <= Math.Sqrt(y))),
        d,
        n
    ),
    // break;
    Expression.Break(breakInner)
),

Wow, that got a bit simpler, didn’t it? The formatted (bold, underline) part corresponds to the language-generated expression tree. All we have to do is wrap that thing in an InvocationExpression, passing in d and n as arguments (respectively being bound to x and y).

Similarly, we can simplify other parts of the statement tree. For example:

// if (n % d == 0)
Expression.IfThen(
    Expression.Equal(
        Expression.Modulo(
            n,
            d
        ),
        Expression.Constant(0)
    ),
    // {
    Expression.Block(
        // found = true;
        Expression.Assign(
            found,
            Expression.Constant(true)
        ),
        // break;
        Expression.Break(breakInner)
    // }
    )
)

It doesn’t make sense to try to abstract Expression.Constant calls (it would only blow up the code size and make things more cumbersome), but the n % d == 0 part is something we could ask the compiler to generate for us:

// if (n % d == 0)
Expression.IfThen(
    Expression.Invoke(    
        (Expression<Func<int, int, bool>>)((x, y) => x % y == 0),
        n,
        d
    ),
    // {
    Expression.Block(
        // found = true;
        Expression.Assign(
            found,
            Expression.Constant(true)
        ),
        // break;
        Expression.Break(breakInner)
    // }
    )
)

It’s a little unfortunate lambda expressions need to have a type forced upon them to emit them either as a delegate (Func<…> types) or an expression tree (Expression<Func<…>> types), requiring us to use an explicit cast to demand the compiler to generate an expression tree. This blows up the code significantly, but still we’re saving quite a bit of code. Also for method invocations, we can get rid of the ugly reflection code required to get the right overload, e.g.:

// if
Expression.IfThen(
    // (!found)
    Expression.Not(found),
    //    res.Add(n);
    Expression.Call(
        res,
        typeof(List<int>).GetMethod("Add"),
        n
    )
)

Finding the Add method is simple in this case, but if you end up creating a MethodCallExpression with a bunch of arguments to a method with lots of overloads available, the code gets quite complicated. In the sample above, there’s little to gain, but just for the sake of illustration:

// if
Expression.IfThen(
    // (!found)
    Expression.Not(found),
    //    res.Add(n);
    Expression.Invoke(
        (Expression<Action<List<int>, int>>)((l, e) => l.Add(e)),
        res,
        n
    )
)

Moreover, when typing the lambda expression above you’ll get full-blown (statically typed) IntelliSense:

In fact, this trick is a runtime-aided trick to implement an “infoof” operator (info-of) which I use from time to time. For example, if you want to get the MethodInfo for Console.WriteLine(“{0} is {1}”, “Bart”, 26) that can get quite involved using reflection flags (public, static), a method name in a string (“WriteLine”), a type array for the arguments (beware of the “params” behavior above), etc. Instead, you could do this:

static MethodInfo InfoOf(Expression<Action> ex)
{
    var mce = ex.Body as MethodCallExpression;
    if (mce != null)
    {
        return mce.Method;
    }
    else
    {
        throw new InvalidOperationException("InfoOf called on expression without any kind of member access.");
    }
}

static MemberInfo InfoOf<T>(Expression<Func<T>> ex)
{
    var me = ex.Body as MemberExpression;
    if (me != null)
    {
        return me.Member;
    }
    else
    {
        throw new InvalidOperationException("InfoOf called on expression without any kind of member access.");
    }
}

which we can call as follows:

var cw = InfoOf(() => Console.WriteLine("{0} is {1}", "Bart", 26));
var now = InfoOf(() => DateTime.Now);

So, all in all, the lack of statement tree support in the language is a pity, but by leveraging existing expression tree support we can simplify the task at hand in some cases. The result for our sample is as follows:

var to = Expression.Parameter(typeof(int), "to");
var res = Expression.Variable(typeof(List<int>), "res");
var n = Expression.Variable(typeof(int), "n");
var found = Expression.Variable(typeof(bool), "found");
var d = Expression.Variable(typeof(int), "d");
var breakOuter = Expression.Label();
var breakInner = Expression.Label();
var getPrimes = 
    // Func<int, List<int>> getPrimes =
    Expression.Lambda<Func<int, List<int>>>(
        // {
        Expression.Block(
            // List<int> res;
            new [] { res },
            // res = new List<int>();
            Expression.Assign(
                res,
                Expression.New(typeof(List<int>))
            ),
            // {
            Expression.Block(
                // int n;
                new [] { n },
                // n = 2;
                Expression.Assign(
                    n,
                    Expression.Constant(2)
                ),
                // while (true)
                Expression.Loop(
                    // {
                    Expression.Block(
                        // if
                        Expression.IfThen(
                            // (!
                            Expression.Not(
                                // (n <= to)
                                Expression.LessThanOrEqual(
                                    n,
                                    to
                                )
                            // )
                            ),
                            // break;
                            Expression.Break(breakOuter)
                        ),
                        // {
                        Expression.Block(
                            // bool found;
                            new[] { found },
                            // found = false;
                            Expression.Assign(
                                found,
                                Expression.Constant(false)
                            ),
                            // {
                            Expression.Block(
                                // int d;
                                new [] { d },
                                // d = 2;
                                Expression.Assign(
                                    d,
                                    Expression.Constant(2)
                                ),
                                // while (true)
                                Expression.Loop(
                                    // {
                                    Expression.Block(
                                        // if
                                        Expression.IfThen(
                                            // (!(d <= Math.Sqrt(n)))
                                            Expression.Invoke(
                                                (Expression<Func<int, int, bool>>)((x, y) => !(x <= Math.Sqrt(y))),
                                                d,
                                                n
                                            ),
                                            // break;
                                            Expression.Break(breakInner)
                                        ),
                                        // {
                                        Expression.Block(
                                            // if (n % d == 0)
                                            Expression.IfThen(
                                                Expression.Invoke(    
                                                    (Expression<Func<int, int, bool>>)((x, y) => x % y == 0),
                                                    n,
                                                    d
                                                ),
                                                // {
                                                Expression.Block(
                                                    // found = true;
                                                    Expression.Assign(
                                                        found,
                                                        Expression.Constant(true)
                                                    ),
                                                    // break;
                                                    Expression.Break(breakInner)
                                                // }
                                                )
                                            )
                                        // }
                                        ),
                                        // d++;
                                        Expression.PostIncrementAssign(d)
                                    // }
                                    ),
                                    breakInner
                                )
                            ),
                            // if
                            Expression.IfThen(
                                // (!found)
                                Expression.Not(found),
                                //    res.Add(n);
                                Expression.Invoke(
                                    (Expression<Action<List<int>, int>>)((l, e) => l.Add(e)),
                                    res,
                                    n
                                )
                            )
                        ),
                        // n++;
                        Expression.PostIncrementAssign(n)
                    // }
                    ),
                    breakOuter
                )
            ),
            res
        ),
        to
    // }
    ).Compile();

Still quite involved to write, but a bit simpler than our previous attempt. As an exercise, identify a few other potential rewrite sites in the fragment above. Have fun!

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

bart — Mon, 13 Apr 2009 07:41:00 GMT

Last time around in this series, I promised to talk about generic co- and contra-variance. So that’s why we’re here today. In this post I’ll explain the theoretical concepts behind these fancy-sounding terms, look at the runtime’s take on it, show how to use them in C# 4.0 and most important of all: tell you why you don’t have to worry about all of this :-).

What’s variance?

Language features with names like variance ought to come from a theoretical background, don’t you think so? Absolutely right, and that’s no different for variance with category theory being its source of inspiration. Although we often speak about co- and contra-variance (turns out C# – amongst lots of other languages – already use those concepts , as we’ll see later) there are three sorts of variance to be explained before moving on.

Type ordering

First we need to establish the notion of type ordering. All of you know about object-oriented programming where types are used to indicate the “kind” of data one is dealing with. On top of this, subtyping is used to specialize types. Or, the other way around, operations supported on a supertype can also be applied to its subtypes (possibly with a specialized implementation through overriding and virtual method dispatch).

For example, System.Object has a ToString method. System.DateTime is a subtype of System.Object and therefore also has a ToString method on it (either derived from the base type as-is or overridden, but that doesn’t matter for now).

Let’s use more concise notation to write down such relationships. If D(erived) is a subclass of B(ase), we’ll write D <: B. To say d is an instance of D, we’ll write d : D.

Based on this we can start formulating properties, such as subsumption, the formal notion of subtype-relationships:

If d : D and D <: B, then d : B

For instance, if we substitute d for name, D for System.String and B for System.Object, we end up with:

If name : System.String and System.String <: System.Object, then name : System.Object

We all know this: because name is declared to be a string and the string type is a subtype of object, we can say name ought to be an object. The notation <: is what we call type ordering. I’ll leave it to the math-savvy reader to map those concepts back to the properties of binary relations, such as reflexivity, (anti)-symmetry and transitivity.

Variance

What’s up with variance? In short, variance is a property of operators that act on types. This is very abstract, but we’ll make it very concrete in just a second. For now, think of it very generally: assume op(T1, T2) is an operator “that does something with/based on” T1 and T2 which are both types. For mathematicians (and programmers as it turns out) it makes perfect sense to attribute properties to that operator, capturing its behavior with respect to the types it acts on.

To make things a bit more concrete, let’s map the concept of operators onto generics. (Note for geeks only. Generics are a form of “parametric polymorphism”, which extends the lambda calculus to something known as System F.) As we know, generics allow for type parameterization. Below is a simple example introducing a Pair type:

class Pair<TFirst, TSecond>
{
    public Pair(TFirst first, TSecond second)
    {
        First = first;
        Second = second;
    }

    public TFirst First { get; private set; }
    public TSecond Second { get; private set; }
}

You can think of this type declaration as an operator that, given type values for TFirst and TSecond, can give us a constructed type back (in other words, it’s a type constructor, in the Haskell sense, not the CLR sense). Now we want to be able to express type ordering relationships over such constructed generic types. For example, how does Pair<string, int> relate to Pair<string, object> or to Pair<DateTime, int> or to … whatever. More specifically, we want to be able to infer the relationship between any Pair<T1, T2> and Pair<T3, T4> from relationships between the parameters.

For instance, can we say (this is a question, not an answer just yet…) that:

If T1 <: T3 and T2 <: T4, then Pair<T1,T2> <: Pair<T3,T4>

These are the kind of questions asked by theorists, but obviously by developers today as well.

Covariance

Time to dive into the first kind of variance: covariance. Co as a prefix means “together with”. It means an operator preserves the ordering of types, when compared to its operands. Let me give a concrete sample, based on our Pair class above.

If you know that Apple is a subtype of Fruit (Apple <: Fruit) and Tomato is a subtype of Vegetable (Tomato <: Vegetable), can you also say that Pair<Apple, Tomato> is a subtype of Pair<Fruit, Vegetable>? Looks like that ought to be valid on first sight, no? But there might be some hidden caveats… We’ll get to that soon.

The formalized notion of covariance can be stated as follows:

Operator op(T1, …, Tn) is covariant in Ti (1 <= i <= n) if Si <: Ti implies op(T1, …, Ti-1, Si, Ti+1, …, Tn) <: op(T1, …, Tn)

A very practical case where this comes up is with sequences. For instance, given a LINQ query that returns a sequence of Student objects, can we treat that sequence as one of Person objects, i.e.:

IEnumerable<Person> people = from Student s in db.Students
where s.Age <= 25
select s;

Today, in C# 3.0, you cannot do this because IEnumerable<T> is not covariant in T.

Contravariance

The opposite of “co” is “contra” which means “against”. In the context of variance it means an operator reverses the ordering of types, when compared to its operands. Again a concrete sample is more than welcome I guess.

Let’s stick with fruits. We known – just repeating this obvious fact – that Apple is a subtype of Fruit (Apple <: Fruit). Now say if we want to carry out comparison between apples (IComparer<Apple>), is it possible then to use a comparison between fruits instead (IComparer<Fruit>)? Looks like that should be possible, right? Everything that can handle two pieces of fruit for comparison ought to be able to handle two apples as each apple is a piece of fruit.

The formalized notion of contravariance can be stated as follows:

Operator op(T1, …, Tn) is contravariance in Ti (1 <= i <= n) if Si <: Ti implies op(T1, …, Ti-1, Si, Ti+1, …, Tn) :> op(T1, …, Tn)

A very practical case where this comes up is with action delegates. For instance, given an action that takes in a Person, can we treat that action as one that deals with a Student object instead, i.e.:

Action<Student> submitLetter = (Person p) => {
SendMailTo(p.HomeAddress);
};

Update: I made a mistake in my original post, where I swapped Person and Student in the sample above. Guess it was getting late and despite double-checking all uses of the terminology, it slipped through. Thanks to Chris for pointing this out!

Today, in C# 3.0, you cannot do this because Action<T> is not contravariant in T.

Broken array variance

First a shock to the reader: arrays in the CLR are covariant. “So what?”, you might wonder. Well, and here comes the shock, it turns out covariant use of arrays is not type-safe. (Let you heartbeat go down before reading on.) We’ll get to why covariant treatment of arrays is broken, but first some history. You might assume this “broken array variance” was put in the CLI (Common Language Infrastructure, the standardized specification of the CLR, ECMA-335) intentionally. The mission of the CLI was – and still is, bigger than ever with the whole DLR on top of it – to accommodate executing different languages on the same unified runtime with a unified type system, instruction set, runtime services, etc. One such language was Java, which has broken array covariance, and being able to accommodate that language won over fixing this behavior.

But what makes arrays unsafe for covariance? Another sample with fruits… The story of the fruit farmer.

A fruit farmer produces apples and has a contract with a local grocery store to sell the apples. To do so, the farmer hands over an array of apples to the store. The contract states the store can return the apples that haven’t been sold in the next week, and only the apples that were sold (indicated by empty spots in the array from which the pieces of fruit have been taken) will be billed. The remainder apples – possible rotten by now – are sent to a juice factory nearby that creates sweet apple juice. This scheme is illustrated below:

But because arrays are covariant, the grocery story (on the right) can treat an array of Apples (Apple[]) as if it were an array of Fruits (Fruit[]). Since the cells of arrays are writeable, this opens up a potential hole in the system. What if the grocery store wants to cheat and put some rotten tomatoes in the tray (let’s assume tomatoes are fruits for sake of this discussion; if you don’t agree with this, substitute “rotten tomato” for “rotten lemon” but that doesn’t sound as bad IMO, hence the use of tomatoes). The contract with the farmer stated that only the number of empty places in the tray will be considered in billing the grocery story; so fill a few empty places with unsellable rotten tomatoes and the price gets reduced. This might go unnoticed if the farmer doesn’t enforce runtime fruit/vegetable type safety.

If the contract with the juice factory states that only Apple-arrays can be passed in, but this didn’t get checked by the farmer at runtime after return from the grocery store, their juice will now contain tomato juice as well (a strange combination I guess). Or worse, the juice factory will blow up because the apple peeling machine expects a certain toughness from the apple being peeled and tomatoes are much softer (note: I don’t know anything at all about the factory process involved in creating juice, so I’m just fantasizing about possible horror stories).

This mishap is illustrated below.

But who to blame? The grocery story followed the array-based contract exactly; arrays do not prevent writing operations, so putting tomatoes in is not a violation. Clearly the farmer needs a tighter contract that ensures – statically – the grocery store cannot put other fruits or vegetables in. What the farmer should use is an “pull-based enumerating device for apples” (an IEnumerator<Apple> that is) as shown below:

The spring depicts the enumerating behavior – you can only get things out but can’t push things in (ignore forceful mechanisms and ignoring the fact the spring might crush the apples :-)). Such an IEnumerable<T> is safely covariant because you can’t push anything in, so even if the farmer treats the IEnumerable<Apple> as an IEnumerable<Fruit> all he can do is get pieces of fruit (which always will happen to be apples) out.

This illustrates why arrays T[] are not safely covariant and why IEnumerable<T> is. Or in code:

namespace Rural.Fields
{
    using Market;
    using Industry;

    internal sealed class Farm
    {
        private GroceryStore _store = …;
        private JuiceFactory _juice = …;
        private const decimal APPLE_PRICE = 0.5;

        private Apple[] PluckAppleTrees() { … }

        public void Work()
        {
            Apple[] apples = PluckAppleTrees();
            _store.SellFruits(apples); // here the array is treated covariantly!
            int sold = apples.Where(apple => apple != null).Count();
            _store.SendInvoice(sold * APPLE_PRICE);
            _juice.ProduceAppleJuice(apples); // here the array is treated invariantly
            _juice.SendInvoice((apples.Length – sold) * APPLE_PRICE * 0.8 /* price of rotten apple */);
        }
    }
}

namespace Market
{
    public sealed class GroceryStore
    {
        public void SellFruits(Fruit[] fruits) { … }
        public void SendInvoice(decimal amount) { … }
    }
}

namespace Industry
{
    public sealed class JuiceFactory
    {
        public void ProduceAppleJuice(Apple[] apples) { … }
        public void SendInvoice(decimal amount) { … }
    }
}

To ensure type safety for covariant arrays, the CLR injects runtime type checks for every attempt to store an element in an array. If an object with a type incompatible with the array in memory is attempted to be written to the array, an ArrayTypeMismatchException occurs. In our case above, if the SellFruits method of GroceryStory would try to write a Tomato object to the array that’s passed in (as Fruit[] but that was created as an Apple array, in the PluckAppleTrees method of the Farm) the CLR would detect this and throw the exception.

A more isolated sample:

string[] names = new string[] { “Bart”, “John” };
object[] things = names;
things[0] = 123; // ArrayTypeMismatchException – 123 is not a string
Console.WriteLine(names[0].ToUpper() /* if the above would work, we’d call the non-existing ToUpper method on System.Int32 */);

Today’s co- and contra-variance support

C# actually has places where co- and contra-variance principles are being used, more specifically in delegate types. A typical sample where this comes in useful is when dealing with events.

delegate void CancelEvent(object sender, CancelEventArgs e);
delegate void ProgressEvent(object sender, ProgressEventArgs e);

sealed class Engine
{
    public event CancelEvent Cancelled;
    public event ProgressEvent ProgressChanged;

    public void Run() { … }
    public void Cancel() { … }
}

static class Program
{
    static void Main()
    {
        var engine = new Engine();
        engine.Cancelled += Logger;
        engine.ProgressChanged += Logger;
        // run engine, etc
    }

    void Logger(object sender, EventArgs e) { … }
}

Here we’re attaching an event handler to two events which have different signatures. However, the signature of Logger uses a common supertype of both events’ event arguments type, so the compiler allows this. The reason it does is because input parameters can safely be treated contravariantly. In other words, we’re getting in a more derived type for the event arguments but we treat it as less derived. As the argument appears in an input position, this is safe to do.

Here’s a little exercise for the reader. The following fragment compiles fine because of contravariant treatment for delegate parameters:

class Contra
{
    static void Main()
    {
        var b = new Bar();
        b.Event += Handler;
    }

    static void Handler(object o /* contravariant treatment when used with delegate type D */)
    {
    }
}

delegate void D(string s);

class Bar
{
    public event D Event;
}

However, if we change the parameter on D by adding a ref modifier, it doesn’t work anymore.

static void Handler(ref object o /* ??? */)

delegate void D(ref string s);

Why? Illustrate with a sample showing why contravariant treatment would be malicious if it were allowed here…

Covariant and contravariant generic parameters in the CLI

With the second release of the CLR, as part of .NET Framework 2.0, generics were introduced based on the work done by Don Syme and Andrew Kennedy in the Gyro project. Right from the start, generic parameters have supported the declaration of desired variance behavior. Section 8 in Partition I of the ECMA-335 spec for the CLI states:

In addition, CLI supports covariant and contravariant generic parameters, with the following characteristics:

It is type-safe (based on purely static checking)
Simplicity: in particular, variance is only permitted on generic interfaces and generic delegates (not classes or value-types)
Languages not wishing to support variance can ignore the feature, and treat all generic types as non-variant.
Enable implementation of more complex covariance scheme as used in some languages, e.g. Eiffel.

but so far, C# and VB have been following the third bullet, ignoring the feature. Before we go there, we should have a look at how generics variance is surfaced through IL, proving its support in the CLR today. More information on this can be found in paragraph 9.5 of Partition II:

The CLI supports covariance and contravariance of generic parameters, but only in the signatures of interfaces and delegate classes.
The symbol “+” is used in the syntax of §10.1.7 to denote a covariant generic parameter, while “-” is used to denote a contravariant generic parameter.

Our two main samples have been IEnumerable<T> and IComparer<T>. Let’s define our own interfaces for both (in C#) and see how it looks like at the level of IL:

interface IEnumerable<T>
{
    IEnumerator<T> GetEnumerator();
}

interface IEnumerator<T>
{
    bool MoveNext();
    T Current { get; }
}

interface IComparer<T>
{
    int Compare(T arg1, T arg2);
}

By default generic interface and delegate types are invariant:

However, we can roundtrip through IL to make those types covariant (for IEnumer*<T>) or contravariant (for IComparer<T>)in their generic parameter T. The difference is subtle: adding a + (covariant) or a - (contravariant) to the generic parameter T.

.class interface private abstract auto ansi IEnumerable`1<+T>
{
.method public hidebysig newslot abstract virtual
          instance class IEnumerator`1<!T>
          GetEnumerator() cil managed
{
} // end of method IEnumerable`1::GetEnumerator

} // end of class IEnumerable`1

.class interface private abstract auto ansi IEnumerator`1<+T>
{
.method public hidebysig newslot abstract virtual
          instance bool MoveNext() cil managed
{
} // end of method IEnumerator`1::MoveNext

.method public hidebysig newslot specialname abstract virtual
          instance !T get_Current() cil managed
{
} // end of method IEnumerator`1::get_Current

.property instance !T Current()
{
    .get instance !T IEnumerator`1::get_Current()
} // end of property IEnumerator`1::Current
} // end of class IEnumerator`1

.class interface private abstract auto ansi IComparer`1<-T>
{
.method public hidebysig newslot abstract virtual
          instance int32 Compare(!T arg1,
                                  !T arg2) cil managed
{
} // end of method IComparer`1::Compare

} // end of class IComparer`1

Notice the ilasm tool doesn’t statically verify the correct use of variance annotations. It’s possible to mark a generic parameter as covariant while it’s used in input positions. It’s the responsibility of language compilers, e.g. for C#, to enforce such rules:

Covariant parameters should only be used in output positions: method return values, get-only properties or indexers.
Contravariant parameters should only occur in input positions: method parameters, set-only properties or indexers.

C# 4.0 support

Starting with C# 4.0, the language does support co- and contra-variance on generic delegate and interface type parameters. This feature has two sides to it:

As a consumer of generic interface or delegate types that behave either co- or contra-variantly, you can now do what you couldn’t do before

IEnumerable<Person> people = from Student s in db.Students
where s.Age <= 25
select s;

IComparer<string> comp = new MyObjectComparer(); // implements IComparer<object>

As a provider of generic interface or delegate types you can now specify the intended behavior. This is done using the out and in keywords, which respectively stand for covariant (output positions only) and contravariant (input positions only). The compiler enforces that parameters that behave in a non-invariant way are used appropriately:

interface IEnumerable<out T>
{
    IEnumerator<T> GetEnumerator();
}

interface IEnumerator<out T>
{
    bool MoveNext();
    T Current { get; }
}

interface IComparer<in T>
{
    int Compare(T arg1, T arg2);
}

You might wonder why the compiler doesn’t infer the applicable variance annotation on behalf of the user. This could easily lead to “accidental” incorrect treatment as things evolve. Although it’s not a good idea to start changing interfaces, during development your interface types might be in flux and it would be disruptive if consumer code starts breaking all of a sudden because a generic parameter’s variance treatment has changed. It was felt it’d be better to have developers be explicit about variance.

Obviously a bunch of interface and delegate types in the BCL have been modified with variance annotations. IComparer<T>, IEnumerable<T> and IEnumerator<T> are just a few samples. Others include the Func and Action delegates:

delegate R Func<in T1, in T2, …, in Tn, out R>(T1 arg1, T2 arg2, …, Tn argn);
delegate void Action<in T1, in T2, …, in Tn>(T1 arg1, T2 arg2, …, Tn argn);

That’s it. I told’ya it was simple, no? The good thing is, you shouldn’t really know much about all of this: It Just Works (now also available for C# – inside joke).

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!

C# 4.0 Feature Focus - Part 3 - Intermezzo: LINQ's new Zip operator

bart — Tue, 04 Nov 2008 07:11:43 GMT

After named parameters and optional parameters, we'll take a little breadth and deviate a bit from the language specifics to present a new LINQ operator: Zip. Just like a zipper zips two streams of materials together, LINQ's Zip operator can zip together two sequences. Here's the signature of the new method:

public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func);

Sample

Given two sequences and a function that combines two elements from both sequences, a sequence of zipped pairs is produced. Here's a sample:

string[] names = { "Bart", "John" };
int[] ages = { 25, 60 };

names.Zip(ages, (name, age) => name + " is " + age + " years old.");

This produces a sequence with the sentences "Bart is 25 years old." and "John is 60 years old.". The lambda syntax for the passed-in function should speak for itself, and notice we're using extension method invocation here, so names is propagated to become the left-hand side of the method call.

How Zip works

Previously I've implemented the Standard Query Operators for reference purposes on the Codeplex site at http://www.codeplex.com/LINQSQO. I won't update that sample library just yet, but here's an illustration on how easy Zip is to implement, ignoring exception handling (which is more subtle than you might think, see further):

static class Enumerable
{
    public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func)
    {
        var ie1 = first.GetEnumerator();
        var ie2 = second.GetEnumerator();

        while (ie1.MoveNext() && ie2.MoveNext())
            yield return func(ie1.Current, ie2.Current);
    }
}

The Zip operation is implemented using iterators inside ("yield return") and stops as soon as one of the sequences runs out of juice (the case of the asymmetric zipper).

Zip without Zip?

As a curiosity, is it actually possible to build Zip out of existing LINQ operators, ignoring performance worries? Unsurprisingly, it turns out this is the case. Here's how:

static class Enumerable
{
    public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func)
    {
        return first.Select((x, i) => new { X = x, I = i }).Join(second.Select((x, i) => new { X = x, I = i }), o => o.I, i => i.I, (o, i) => func(o.X, i.X));
    }
}

(Exercise for the reader: think of more alternatives.) How does this work? To explain this we need a bit of vocabulary, so let's refer to Wikipedia for a second and apply an isomorphism between textile sciences and computer sciences (something in me screams "zip, zipper, zippest"):

The ~~bulk~~ signature of a ~~zipper~~ Zip consists of two ~~strips~~ sequences of ~~fabric~~ element taypes, each affixed to one of the two ~~pieces~~ sequence instances to be joined, carrying tens or hundreds or anything below OutOfMemoryException conditions of ~~specially~~ regularly ~~shaped~~ allocated ~~metal~~ reference- or ~~plastic~~ value-typed ~~teeth~~ elements. (...) The ~~slider~~ Func<TFirst, TSecond, TResult> delegate, operated by ~~hand~~ executing Zip, moves along the ~~rows~~ sequences of ~~teeth~~ elements. Inside the ~~slider~~ Func<TFirst, TSecond, TResult> delegate is a ~~Y-shaped~~ strongly-typed ~~channel~~ function that meshes together ~~or separates~~ the opposing ~~rows~~ sequences of ~~teeth~~ elements, ~~depending on the direction of its movement~~. The ~~friction~~ binding and ~~vibration~~ application of the ~~slider~~ Func<TFirst, TSecond, TResult> delegate ~~against~~ on the ~~teeth~~ elements causes a characteristic ~~buzzing~~ callvirt'ing noise, which is probably not the origin of the name zipper. The name also may have originated in the greater speed and ease with which the two sides of a ~~zipper~~ Zip can be joined, compared to the time needed for ~~fastening~~ executing ~~laces or buttons~~ the method above.

Well, that's exactly what happens: opposing ~~rows~~ sequences of ~~teeth~~ elements are combined by a ~~Y-shaped~~ strongly-typed ~~channel~~ function. How to determine opposing sequence elements? Using Select's overload that provides (besides the element itself) an index denoting the element's position in the original sequence. Matching the opposing elements is a matter of joining both sequences, extracting the keys (marked as I in the anonymous type) and combining the selected pairs of elements from both sequences (marked as X in the anonymous type) by feeding them in to the ~~slider~~ Func<TFirst, TSecond, TResult> delegate. I told you the explanation was straightforward, or did I?

Iterators and exceptions

Most of the LINQ operators are implemented using iterators. You might wonder this this is relevant at all. Obviously we need it as LINQ operators need to be lazy. Only when you start fetching results by iterating of the sequence, the internal machinery should kick in. Declaring a query doesn't cause any execution whatsoever. Internally iterators are implemented as state machines. Every state can do on "yield", after which the state machine is suspended till the consumer asks for the next element in the sequence being produced by calling MoveNext on the IEnumerator<T> object.

Our Zip implementation above is turned into an equivalent piece of code (slightly simplified for illustrative purposes):

public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func)
{
    return new ZipIterator<TFirst, TSecond, TResult>(first, second, func);
}

private sealed class ZipIterator<TFirst, TSecond, TResult> : IEnumerable<TResult>, IEnumerator<TResult>
{
    //
    // Captured iterator method parameters.
    //
    private IEnumerable<TFirst> _first;
    private Func<TFirst, TSecond, TResult> _func;
    private IEnumerable<TSecond> _second;

    //
    // Iterator's enumerator state and thread affinity.
    //
    private State _state;
    private int _initialThreadId;

    //
    // Value currently yielded by the iterator's enumerator.
    //
    private TResult _current;

    //
    // Local variables used by the iterator's enumerator.
    //
    private IEnumerator<TFirst> _ieFirst;
    private IEnumerator<TSecond> _ieSecond;

    //
    // Captured iterator method parameters used by enumerator.
    //
    private IEnumerable<TFirst> first;
    private Func<TFirst, TSecond, TResult> func;
    private IEnumerable<TSecond> second;

    //
    // Public constructor to create an iterator in the initial ready state.
    //
    public ZipIterator(IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func)
        : this()
    {
        this._first = first;
        this._second = second;
        this._func = func;
    }

    //
    // Private constructor to set state and thread affinity.
    //
    private ZipIterator()
    {
        this._state = State.Before;
        this._initialThreadId = Thread.CurrentThread.ManagedThreadId;
    }

    //
    // Gets a new enumerator over the iterator.
    //
    IEnumerator<TResult> IEnumerable<TResult>.GetEnumerator()
    {
        ZipIterator<TFirst, TSecond, TResult> iterator;

        //
        // Can reuse the current enumerator if thread affinity and state permit it.
        //
        if (Thread.CurrentThread.ManagedThreadId == _initialThreadId && _state == State.Before)
        {
            iterator = this;
        }
        else
        {
            iterator = new ZipIterator<TFirst, TSecond, TResult>();
        }

        iterator.first = this._first;
        iterator.second = this._second;
        iterator.func = this._func;

        return iterator;
    }

    //
    // Gets a new enumerator over the iterator.
    //
    IEnumerator IEnumerable.GetEnumerator()
    {
        return ((IEnumerable<TResult>)this).GetEnumerator();
    }

    //
    // Advances the iterator one yield return at a time.
    //
    bool IEnumerator.MoveNext()
    {
        switch (this._state)
        {
            case State.Before:
                this._ieFirst = this.first.GetEnumerator();
                this._ieSecond = this.second.GetEnumerator();
                goto case State.Suspended;

            case State.Suspended:
                if (this._ieFirst.MoveNext() && this._ieSecond.MoveNext())
                {
                    this._current = this.func(this._ieFirst.Current, this._ieSecond.Current);
                    this._state = State.Suspended;
                    return true;
                }
                break;
        }

        this._state = State.After;
        return false;
    }

    //
    // Retting the iterator enumerator is not supported; create a new one instead by calling GetEnumerator.
    // The foreach statement does this anyway.
    //
    void IEnumerator.Reset()
    {
        throw new NotSupportedException();
    }

    //
    // Gets the value currently yielded from the iterator.
    //
    TResult IEnumerator<TResult>.Current
    {
        get
        {
            return _current;
        }
    }

    //
    // Gets the value currently yielded from the iterator.
    //
    object IEnumerator.Current
    {
        get
        {
            return _current;
        }
    }

    //
    // IDisposable implementation.
    //
    void IDisposable.Dispose()
    {
    }

    //
    // Internal iterator enumerator states.
    //
    private enum State
    {
        Before,
        Running,
        Suspended,
        After
    }
}

Notice that the code above holds the middle between the specification (paragraph 10.14 of the C# 3.0 specification) and the actual implementation in the Visual C# 2008 compiler. More specifically, I've made the discrete states (which are internally represented as integers) match the ones in the specification, but haven't gone all the way in matching the code up with the

Of all this machinery, the MoveNext method is the most interesting one from the iterator's point of view. Here a state machine is built, rewriting the original iterator block by splitting it into discrete blocks. To perform this transformation, yield return statements are replaced as follows:

yield a;

becomes

this._current = a;
this._state = State.Suspended;
return true;

Similar rewrites happen for yield break statements, but that's not relevant here. Furthermore all the iterator block code is placed in a MoveNext method, switching on the current state. The specification only mentions the four states I've implemented above, but we're lucky the number of states for our sample matches up with the number of states that's specified. In cases where there are more yield statements, more states are needed to suspend the machine and resume at the same point during the next MoveNext call. Other transformations needed include rewriting of loops (things like while don't really play well with suspension points and need to be rewritten in terms of if/goto, where gotos require additional states). Applying all those tricks gives us:

bool IEnumerator.MoveNext()
{
Begin:
    switch (this._state)
    {
        case State.Before:
            this._ieFirst = this.first.GetEnumerator();
            this._ieSecond = this.second.GetEnumerator();
            this._state = State.Running;
            goto Begin;

        case State.Running:
        case State.Suspended:
            if (this._ieFirst.MoveNext() && this._ieSecond.MoveNext())
            {
                this._current = this.func(this._ieFirst.Current, this._ieSecond.Current);
                this._state = State.Suspended;
                return true;
            }
            break;
    }

    this._state = State.After;
    return false;
}

Here the local variables used in the iterator block are captured in the initial pass through MoveNext, when state is still set to Before. Strictly speaking we move from Before to Running all the way to the first point where the code gets suspended, but in our case states can be merged quite a bit. In fact the code really produced by the compiler looks like this:

bool IEnumerator.MoveNext()
{
    switch (this._state)
    {
        case 0:
            this._state = -1;
            this._ieFirst = this.first.GetEnumerator();
            this._ieSecond = this.second.GetEnumerator();
            while (this._ieFirst.MoveNext() && this._ieSecond.MoveNext())
            {
                this.current = this.func(this._ieFirst.Current, this._ieSecond.Current);
                this._state = 1;
                return true;
            Resume:
                this._state = -1;
            }
            break;
        case 1:
            goto Resume;
    }
    return false;
}

But why am I telling you all this? Because it's fascinating? Yes, for that reason too. But I promised to tell you something about exceptions, right? Let me quote from the C# 3.0 specification paragraph 10.14.4.1 first:

(...) The precise action performed by MoveNext depends on the state of the enumerator object when MoveNext is invoked:

If the state of the enumerator object is 'before', invoking MoveNext:
- Changes the state to 'running'.
- Initializes the parameters (including this) of the iterator block to the argument values and instance value saved when the enumerator object was initialized.
- Executes the iterator block from the beginning until execution is interrupted (as described below).

(...)

The red line is what's of interest to us, and you should read it in reverse:

The code from the beginning of the iterator block till the place where execution is interrupted (i.e. a yield occurs) is executed by MoveNext when transitioning from 'before' to 'running'.

What if that code contains exception throwing statements?

static class Enumerable
{
    public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func)
    {
        if (first == null)
            throw new ArgumentNullException("first");

        if (second == null)
            throw new ArgumentNullException("second");

        var ie1 = first.GetEnumerator();
        var ie2 = second.GetEnumerator();
        while (ie1.MoveNext() && ie2.MoveNext())
            yield return func(ie1.Current, ie2.Current);
    }
}

As you can guess, this code won't get executed till the very first passage through the iterator's enumerator object's MoveNext method. Recall what foreach corresponds to:

foreach (V v in x) embedded-statement

becomes (with C the collection type, E the enumerator type, V the local variable type and T the element type)

{
    E e = ((C)(x)).GetEnumerator();
    try {
        V v;
        while (e.MoveNext()) {
            v = (V)(T)e.Current;
            embedded-statement
        }
    }
    finally {
        ...
    }
}

So just calling the iterator does nothing that can cause the exceptions to be thrown, until a call is made to MoveNext, e.g. by using a foreach loop. As we want the exception to be thrown straight away when calling Zip with invalid arguments, the right way to implement our Zip method is:

static class Enumerable
{
    public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func)
    {
        if (first == null)
            throw new ArgumentNullException("first");

        if (second == null)
            throw new ArgumentNullException("second");

        return ZipInternal(first, second, func);
    }

    private static IEnumerable<TResult> ZipInternal<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> func)
    {
        var ie1 = first.GetEnumerator();
        var ie2 = second.GetEnumerator();
        while (ie1.MoveNext() && ie2.MoveNext())
            yield return func(ie1.Current, ie2.Current);
    }
}

Conclusion

The addition of Zip to LINQ is a nice one, but not a mind-blower. So I hope you'll accept my apologies for using this as a lame excuse to nag about the implementation of iterators and their subtle impact on exceptions. Next time: generics co- and contra-variance in C# 4.0.

C# 4.0 Feature Focus - Part 2 - Named parameters

bart — Sun, 02 Nov 2008 05:58:53 GMT

In the previous episode of this feature focus series we talked about optional parameters. Today we'll cover another feature introduced in C# 4.0, named parameters. One of the most applicable places for optional and named parameters is when dealing with COM interop such as interaction with the Office automation APIs, but they can also be used as a stand-alone language feature. Just like optional parameters, named parameters are a symmetric feature: you can both consume and declare them.

The syntax

Assume the following simple subtraction method is defined:

static int Subtract(int a, int b)
{
return a - b;
}

The typical way to call this method is obviously by specifying the parameters in order, like Subtract(5, 3). However, with named parameters it's possible to write the following:

static void Main()
{
Console.WriteLine(Subtract(b: 3, a: 5));
}

Ultimately this translates into a call to Subtract(5, 3). It's clear the sample above is not very realistic (but you have to admit it's simplistic). Typically named parameters are used where optional parameters appear in the target method, but you're not interested in lots of those:

static void Bar(int a = 1, string b = null, bool c = false)
{
// ...
}

Now assume you're only interested in the last parameter, without the named parameter feature you'd have to write Bar(1, null, ...) but now you can go ahead and write:

Bar(c: true);

You might wonder why the syntax uses a colon (:) instead of an assignment equals character (=). The answer is straightforward: assignments have a value and can be used everywhere a value is expected:

bool c = false;
Bar(c = true);

This will assign true to the local variable c and feed that value in as the first argument of Bar. So colon is the way to go (and I'm not going to start religious debates about the spacing around the :, I'll leave that to the C/C++ community as those people are experienced in this kind of discussions, trying to reach an agreement on the totally irrelevant placing for the * character <g>).

The implementation

It should be clear that the implementation only affects the call site, not the caller. Here's how the Main method from above looks like:

.method private hidebysig static void Main() cil managed
{
.entrypoint
// Code size       19 (0x13)
.maxstack 2
.locals init (int32 V_0,
           int32 V_1)
IL_0000: nop
IL_0001: ldc.i4.3
IL_0002: stloc.0
IL_0003: ldc.i4.5
IL_0004: stloc.1
IL_0005: ldloc.1
IL_0006: ldloc.0
IL_0007: call       int32 Program::Subtract(int32,
                                               int32)
IL_000c: call       void [mscorlib]System.Console::WriteLine(int32)
IL_0011: nop
IL_0012: ret
} // end of method Program::Main

First of all, notice the names of parameters don't appear in the call site in any way (they never have, that's not the way IL works). Ultimately we simply call Subtract with the parameters supplied in the right order. But how we get there is important to take a closer look at:

IL_0001: ldc.i4.3
IL_0002: stloc.0
IL_0003: ldc.i4.5
IL_0004: stloc.1
IL_0005: ldloc.1
IL_0006: ldloc.0

The thing to notice here are the mirrored stloc (store to local variable) versus ldloc (load from local variable) instructions. On lines IL_0002 and IL_0004 values are stored to variables 0 and 1, while on lines IL_0005 and IL_0006 they're read out in reverse order. What's happening here is that arguments to the method call are evaluated in lexical order, something that boils down to a one-liner in section 14.4.1 of the C# specification (ECMA-334):

14.4.1    Argument lists
...
The expressions of an argument list are always evaluated in the order they are written.
[Example: Thus, the example
class Test
{
static void F(int x, int y, int z) {
    System.Console.WriteLine("x = {0}, y = {1}, z = {2}", x, y, z);
}

static void Main() {
    int i = 0;
    F(i++, i++, i++);
}
}

produces the output

x = 0, y = 1, z = 2

end example]

This becomes relevant in the context of side-effects but it should be clear by now that it's better not to rely on those kind of side-effects at all. Nevertheless, consistency is a must and hence the named parameters invocation syntax follows those rules as well. Here's the new sample you can predict the output for based on the previous observations:

class Test
{
static void F(int x, int y, int z) {
    System.Console.WriteLine("x = {0}, y = {1}, z = {2}", x, y, z);
}

static void Main() {
    int i = 0;
    F(z: i++, x: i++, y: i++);
}
}

The caveat

This time the caveat is trivial: don't rename parameters on public methods as they might be used in conjunction with the named parameter feature. Here's a sample.

Step 1: Compile the following (csc /t:library namedlib.cs)

public static class NamedLib
{
    public static int Subtract(int a, int b)
    {
        return a - b;
    }
}

Step 2: Compile the following (csc named.cs /r:namedlib.dll)

using System;

class Program
{
    static void Main()
    {
        Console.WriteLine(NamedLib.Subtract(b: 3, a: 5));
    }
}

Step 3: Run named.exe

> named.exe
2

Step 4: Change the library and recompile
public static class NamedLib
{
    public static int Subtract(int x, int y)
    {
        return x - y;
    }
}

Step 5: Recompile the application

named.cs(7,27): error CS1739: The best overload for 'Subtract' does not have a parameter named 'b'

Names matter. Obviously reordering parameters of the same type without recompiling consumers is a breaking change too (the types of the parameters in the signature doesn't change, so the overload is still valid but semantics of the parameters have changed), but that's unrelated to the use of named parameters.

Conclusion

Named parameters provide an easy way to omit ("skip over") optional parameters and are typically used in conjunction with that particular feature. However, they can be used in isolation as well. Once more, library designers should be cautious about messing with the public methods they provide. In particular, make sure names on publicly exposed methods are stable as changes to those have the potential of breaking callers. Another reason to spend time on XML documenting public members, as you'll double-check (I hope) the <param /> tag for its name.

Oh, and did you notice the parallels with concepts in PowerShell on positional and named cmdlet arguments? The only piece missing are aliases ;-).

Next time, before we dive into more language-specific features, a short intermezzo in LINQ with a new operator: Zip. Enjoy!

C# 4.0 Feature Focus - Part 1 - Optional parameters

bart — Sat, 01 Nov 2008 04:31:42 GMT

Welcome to the first post in my new C# 4.0 Feature Focus series. Today we'll start by taking a look at optional parameters, a long-standing request from the community that made it to C# 4.0. By itself, the feature is definitely useful but in conjunction with the mission to make COM interop easier, there's even more value to it. In this post I'll outline what the feature looks like, how it's implemented and what the important caveats are.

The syntax

C# 4.0 can both declare and consume optional parameters. Here's a sample of a very simple method that declares a parameter as optional:

public static class OptionalDemoLib
{
   public static void SayHello(string s = "Hello World!")
   {
      Console.WriteLine(s);
   }
}

This means you can either call Do with one argument or without an argument, in which case the default value is used:

public static class OptionalDemo
{
   public static void Main()
   {
      OptionalDemoLib.SayHello();
      OptionalDemoLib.SayHello("Hello Bart!");
   }
}

Notice all optional parameters need to come at the end of the argument list.

optlib.cs(3,58): error CS1737: Optional parameters must appear after all required parameters

If this weren't the case all sorts of ambiguities would result, e.g.:

public static void SayHello(string s1 = "Hello World!", string s2)

What would a call with a single string argument result in? Would the parameter be bound to s1, overriding the default, or would it bind to s2?

The implementation

How does it work? Let's start by taking a look at the definition side. Here's the IL corresponding to the declaration of SayHello above:

.method public hidebysig static void SayHello([opt] string s) cil managed
{
.param [1] = "Hello World!"
// Code size 9 (0x9)
.maxstack 8
IL_0000: nop
IL_0001: ldarg.0
IL_0002: call void [mscorlib]System.Console::WriteLine(string)
IL_0007: nop
IL_0008: ret
} // end of method OptionalDemoLib::SayHello

Two things are relevant here. First of all, the parameter is decorated with the [opt]. Second, the method body contains a .param directive. It turns out both of those primitives have been supported in the CLI since the very beginning. Visual Basic is one of the languages that already uses this today. Let's dive a little deeper using the CLI specification (ECMA 335), partition II:

15.4 Defining methods

opt specifies that this parameter is intended to be optional from an end-user point of view. The value to be supplied is stored using the .param syntax ($15.4.1.4).
15.4.1 Method body

| .param `[` Int32 `]` [ `=` FieldInit ] Store a constant FieldInit value for parameter Int32.
15.4.1.4 The .param directive

This directive stores in the metadata a constant value associated with method parameter number Int32, see $22.9. (...) Unlike CIL instructions, .param uses index 0 to specify the return value of the method, index 1 to specify the first parameter of the method, ...
22.9 Constant : 0x0B

The Constant table is used to store compile-time, constant values for fields, parameters, and properties. The Constant table has the following columns:
- Type ...
- Parent ...
- Value (an index into the Blob heap)

Note that Constant information odes not directly influence runtime behavior, although it is visible via Reflection. Compilers inspect this information, at compile time, when importing metadata, but the value of the constant itself, if used, becomes embedded into the CIL stream the compiler emits. There are no CIL instructions to access the Constant table at runtime.

I'll come back to the remark in paragraph 22.9 in just a second. An important thing here is that the value needs to be constant, so no new'ing up of stuff or results of methods calls are allowed:

optlib.cs(3,23): error CS1736: Default parameter value for 's' must be a compile-time constant

What does the call-site look like if the parameter is omitted?

.method private hidebysig static void Main() cil managed
{
.entrypoint
// Code size       24 (0x18)
.maxstack 8
IL_0000: nop
IL_0001: ldstr      "Hello World!"
IL_0006: call       void [optlib]OptionalDemoLib::Do(string)
IL_000b: nop
IL_000c: ldstr      "Hello Bart!"
IL_0011: call       void [optlib]OptionalDemoLib::Do(string)
IL_0016: nop
IL_0017: ret
} // end of method OptionalDemo::Main

Notice how remark 22.9 applies here. At the call-site both calls look like a call with one argument. The optional argument is "compiled away" on the side of the caller.

The caveat

The remark above quoting the CLI specification is a very important one:

Note that Constant information odes not directly influence runtime behavior, although it is visible via Reflection. Compilers inspect this information, at compile time, when importing metadata, but the value of the constant itself, if used, becomes embedded into the CIL stream the compiler emits. There are no CIL instructions to access the Constant table at runtime.

In human words, default values are burned into the call site. The metadata specified by the .param directive is only used to keep the constant value around, but as soon as a method is called and optional parameters are used in that call (as determined by the compiler), that value gets copied literally to the call site where it sticks. Let's illustrate this:

Step 1: Compile the following (csc /t:library optlib.cs)

using System;

public static class OptionalDemoLib
{
   public static void SayHello(string s = "Hello World!")
   {
      Console.WriteLine(s);
   }
}

Step 2: Compile the following (csc opt.cs /r:optlib.dll)

using System;
using System.Reflection;

public static class OptionalDemo
{
   public static void Main()
   {
      OptionalDemoLib.SayHello();
      Console.WriteLine(typeof(OptionalDemoLib).GetMethod("SayHello").GetParameters()[0].RawDefaultValue);
   }
}

Step 3: Run opt.exe

> opt.exe
Hello World!
Hello World!

Step 4: Change the library and recompile (don't recompile the opt.cs demo caller)

using System;

public static class OptionalDemoLib
{
   public static void SayHello(string s = "Hello Universe!")
   {
      Console.WriteLine(s);
   }
}

Step 5: Run opt.exe

> opt.exe
Hello World!
Hello Universe!

In step 2 we're introducing the use of reflection to get the default value for the optional parameter. This is run-time reflection that actually inspects the metadata associated with the method's parameter. However, as 22.9 mentions: "There are no CIL instructions to access the Constant table at runtime.", so the default value gets burned into the call site by the compiler. This is no different than the same constant-ness encountered in the difference between readonly variables and constants. The key take-away from this: once you expose a default parameter value on a public method, you can never change it without recompiling all clients that depend on it. For library writers, this never means never ever. If you need the flexibility of changing defaults afterwards, consider providing overloads instead:

using System;

public static class OptionalDemoLib
{
   public static void SayHello()
   {
      SayHello("Hello Universe!");
   }

   public static void SayHello(string s)
   {
      Console.WriteLine(s);
   }
}

This way the constant remains on the definition side and can be changed over there at will. Not that you should do so regularly of course, as you're after all changing defaults that are hopefully documented somewhere in the XML comments for your public methods. Yet another way to attack the problem if you have a bunch of parameters is to take in a property "bag" as the argument to the method (in practice and object with properties for all the supported setting "parameters"). That way every value can be optional and the method can examine whether certain omissions can be granted. Dispatching to the internal implementation with the maximum parameter list could use techniques like null-coalescing (??):

public static void ComplexSayHello(Message arg)
{
ComplexSayHelloInternal(..., arg.Text ?? "Hello Universe!", ...);
}

Use the right approach - all techniques have their benefits.

The past

We've talked about the future, but let me point out it was actually possible to declare optional parameters in C# before, using parameter metadata custom attributes:

using System;
using System.Runtime.InteropServices;

public static class OptionalDemoLib
{
   public static void SayHello([Optional][DefaultParameterValue("Hello Universe!")] string s)
   {
      Console.WriteLine(s);
   }
}

This produces the same IL as the sample shown earlier using C# 4.0 syntax. C# couldn't consume this method though without specifying all parameters, but now it can.

Conclusion

Optional parameters are a beautiful feature and will make life easier when dealing with old COM-driven libraries that were designed with this language feature in mind (amongst others such as named parameters, see next post). To keep the picture symmetric, C# 4.0 also provides the ability to define optional parameters, but be well-aware of the call site burning fact mentioned above. Only use optional parameters if the optional value is really constant in the time dimension unless you're never going to expose the optional value to the outside world (but it's damn easy to make a previously internal or private method public and forgetting about this fact, so the first rule should be the strongest decisive factor...). Don't get me wrong: I like the feature a lot, but powerful weapons need safety warnings.

Next time: named parameters. Enjoy!