This is an EX blog...

Generic Value Object With Yield Return

2009-06-09T11:37:00.002+01:00

Inspired by this and this, here's my version.

Jan Van Ryswyck is right to use static reflection, and to do that he "registers" the properties in a list. On the other hand, assuming you'd have a lot of these objects building up in the GC, it might prove important to reduce the number of ancillary allocations going on, so it may be better to avoid creating a list of the properties in every single instance.

It's not really necessary to have the full information about the properties via reflection; we only need the values. Also it's a pain to have to distinguish between fields and properties. Finally, we are really doing operations on a sequence of values, which can be expressed very neatly with Linq operators, and specified in the derived class with an iterator method.

So here's what I came up with:

public abstract class ValueObject<T> : IEquatable<T>
   where T : ValueObject<T>
{
   protected abstract IEnumerable<object> Reflect();

   public override bool Equals(Object obj)
   {
       if (ReferenceEquals(null, obj)) return false;
       if (obj.GetType() != GetType()) return false;
       return Equals(obj as T);
   }

   public bool Equals(T other)
   {
       if (ReferenceEquals(null, other)) return false;
       if (ReferenceEquals(this, other)) return true;
       return Reflect().SequenceEqual(other.Reflect());
   }

   public override int GetHashCode()
   {
       return Reflect().Aggregate(36, (hashCode, value) => value == null ?
                               hashCode : hashCode ^ value.GetHashCode());
   }

   public override string ToString()
   {
       return "{ " + (string) Reflect().Aggregate((l, r) => l + ", " + r) + " }";
   }
}

First off, it's a lot shorter! Aside from the standard ReferenceEquals checks, every method is a one-liner, a return of a single expression. Check out how SequenceEqual does so much work for us. And Aggregate is designed for turning a sequence into one value, which is exactly what GetHashCode and ToString are all about.

This is all possible because we're treating the properties or fields as just a sequence of values, obtained from the Reflect method, which the derived class has to supply.

(You could easily add operator== and operator!= of course. Also in case you're wondering about the way ToString appears not to check for null, actually it does, because one odd thing about .NET is that string concatenation can cope with null strings.)

Secondly, the way you use it is pretty neat as well:

public class Person : ValueObject<Person>
{
   public int Age { get; set; }
   public string Name { get; set; }

   protected override IEnumerable<object> Reflect()
   {
       yield return Age;
       yield return Name;
   }
}

It wouldn't matter if I yielded the values of fields or properties, and there's no need for expression-lambda trickery to get a PropertyInfo.

If you're unfamiliar with how iterator methods work, you may be wondering, what if I have twenty fields and the first fields of two instances are unequal, isn't this going to waste time comparing the other nineteen fields? No, because SequenceEqual will stop iterating as soon as it finds an unequal element pair, and iterator methods are interruptible.

(Note that if you need this to work on .NET 2.0, you can grab Jared Parsons' BCL Extras library to get the necessary sequence operations. If you're using the C# 2.0 compiler you just need to rejig the method call syntax to avoid using them as extension methods. Iterator methods were already available in 2.0, so nothing here is dependent on 3.0.)

Lazy Sequence Generation without using Yield Return

2009-06-04T11:34:00.002+01:00

C# has the yield return feature, which makes it easy to write state machines as if they were plain old methods:

class Program
{
    static IEnumerable<int> SomeNumbers()
    {
        Console.WriteLine("Started");

        yield return 1;
        
        Console.WriteLine("Yielded 1");

        yield return 2;
            
        Console.WriteLine("Yielded 2");

        yield return 3;

        Console.WriteLine("Finished");
    }

    static void Main(string[] args)
    {
        foreach (int n in SomeNumbers())
        {
            Console.WriteLine(n);
        }
    }
}

The output shows that the sequence of numbers is generated "lazily", with each chunk of code in the method being executed only on demand as the foreach pulls values from sequence.

How close can we get to this using only lamdbas? Pretty close:

class Program
{
    static Lazy.Yielding<int> SomeNumbers()
    {
        Console.WriteLine("Started");

        return Lazy.Yield(1, () => {

        Console.WriteLine("Yielded 1");

        return Lazy.Yield(2, () => {
        
        Console.WriteLine("Yielded 2");

        return Lazy.Yield(3, () => {

        Console.WriteLine("Finished");

        return null; }); }); });
    }

    static void Main(string[] args)
    {
        foreach (int n in Lazy.Enumerate<int>(SomeNumbers))
        {
            Console.WriteLine(n);
        }
    }
}

By messing with the nesting of my curly braces, I've made it look like the original, but really it's made of three nested lambdas. So this version of SomeNumbers is, deep breath... a function that returns a function that returns a function that returns a function.

Each returned function supplies the code to execute for the next step.

The main remaining ingredient is a helper function Lazy.Enumerate that turns our strange contraption into a plain IEnumerable, so we can loop through it conveniently.

public static class Lazy
{
    public class Yielding<T>
    {
        public readonly T Result;
        public readonly Func<Yielding<T>> Next;

        public Yielding(T result)
        {
            Result = result;
            Next = null;
        }

        public Yielding(T result, Func<Yielding<T>> next)
        {
            Result = result;
            Next = next;
        }
    }

    public static Yielding<T> Yield<T>(T value, Func<Yielding<T>> next)
    {
        return new Yielding<T>(value, next);
    }

    public static Yielding<T> Yield<T>(T value)
    {
        return new Yielding<T>(value);
    }

    public class Seq<T> : IEnumerable<T>
    {
        private readonly Func<Yielding<T>> _generator;

        public Seq(Func<Yielding<T>> generator)
        {
            _generator = generator;
        }

        private class Iter : IEnumerator<T>
        {
            private Func<Yielding<T>> _generator;

            public Iter(Func<Yielding<T>> generator)
            {
                _generator = generator;
            }

            public T Current { get; set; }

            public void Dispose() { }

            object System.Collections.IEnumerator.Current
            {
                get { return Current; }
            }

            public bool MoveNext()
            {
                if (_generator == null)
                    return false;

                Yielding<T> yielding = _generator();
                if (yielding == null)
                {
                    _generator = null;
                    return false;
                }

                Current = yielding.Result;
                _generator = yielding.Next;
                return true;
            }

            public void Reset()
            {
                throw new NotImplementedException();
            }
        }

        public IEnumerator<T> GetEnumerator()
        {
            return new Iter(_generator);
        }

        System.Collections.IEnumerator 
            System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }

    public static IEnumerable<T> Enumerate<T>(
                      Func<Yielding<T>> generator)
    {
        return new Seq<T>(generator);
    }
}

Most of the code is "boilerplate" implementation of IEnumerable/IEnumerator. The important bit is the MoveNext method, which calls the generator method to get the next value and the next generator method.

So what's missing? The major thing (aside from the misery of getting the syntax right, closing all the right brackets, etc.) is the lack of try/finally support, which turns out to be extremely useful. We could add support for that, however. Firstly, we'd add this member to Yielding.

public readonly Action Finally;

The generator code would initialize that field to whatever action it liked, to represent the finally block, before returning the Yielding instance. And Lazy.Seq.Iter would store it so it could execute it before retrieving the next value, and it would also execute it from the Dispose method, so that the Finally action would run even if the loop was abandoned.

VC++16 has decltype in Beta 1 (so Linq to C++0x looks a little nicer)

2009-05-22T13:56:00.003+01:00

This post has moved to my new(er) blog and can be found here: http://smellegantcode.wordpress.com/2009/05/22/vc16-has-decltype-in-beta-1-so-linq-to-c0x-looks-a-little-nicer/

A while ago I wrote up a little demo of using lambdas to implement convenient lazy list comprehension in C++0x, but at the time the VC++ compiler I was using lacked decltype, and I found a need for it.

I just tried out the Beta 1 that was released this week, and it has decltype, so here's the updated sample:

#include <iostream>
#include <vector>
#include <sstream>

// Some helpers for working with decltype 
// (maybe these are in std:: somewhere?)
template <class T>
T *make_ptr() { return (T *)0; }

template <class T>
const T &make_ref() { return *(make_ptr<T>()); }

// so you don't need to obtain boost::lexical_cast!
template <class T>
std::string to_string(const T &v)
{
    std::ostringstream s;
    s << v;
    return s.str();
}

// Unary function that always returns true
template <class T>
struct always_true
{
    bool operator() (const T &) const { return true; }
};

// Unary function that returns its argument
template <class T>
struct pass_thru
{
    T operator() (const T &e) const { return e; }
};

template <class TElemFrom, 
          class TElemTo, 
          class TIterFrom, 
          class TSelector,
          class TPredicate>
class filter
{
    TIterFrom from_;
    TIterFrom end_;
    const TSelector &selector_;
    const TPredicate &predicate_;

public:
    filter(TIterFrom from, TIterFrom end, 
             const TSelector &selector, 
             const TPredicate &predicate)
        : from_(from), end_(end), 
          selector_(selector), 
          predicate_(predicate) {}

    class const_iterator
    {
        TIterFrom from_;
        TIterFrom end_;
        const TSelector &selector_;
        const TPredicate &predicate_;

        void locate()
        {
            while (!done())
            {
                if (predicate_(*from_))
                    return;

                ++from_;
            }
        }

        bool done() const { return (from_ == end_); }

    public:
        const_iterator(TIterFrom from, TIterFrom end, 
                       const TSelector &selector,
                       const TPredicate &predicate)
            : from_(from), end_(end), 
              selector_(selector),
              predicate_(predicate) { locate(); }

        TElemTo operator*() const { return selector_(*from_); }

        const_iterator operator++()
        {
            ++from_;
            locate();
            return *this;
        }

        bool operator==(const const_iterator &other) const
            { return done() && other.done(); }

        bool operator!=(const const_iterator &other) const
            { return !done() || !other.done(); }
    };

    typedef TElemFrom value_type;

    const_iterator begin() const 
        { return const_iterator(from_, end_, selector_, predicate_); }

    const_iterator end() const 
        { return const_iterator(end_, end_, selector_, predicate_); }

    template <class TSelector>
    filter<TElemTo, 
             decltype(make_ref<TSelector>()(make_ref<TElemTo>())),
             const_iterator, 
             TSelector,
             always_true<TElemTo> >
        select(const TSelector &selector)
    {
        return filter<TElemTo, 
            decltype(make_ref<TSelector>()(make_ref<TElemTo>())), 
                      const_iterator, 
                      TSelector, 
                      always_true<TElemTo> >
                    (begin(), 
                     end(), 
                     selector, 
                     always_true<TElemTo>());
    }

    template <class TPredicate>
    filter<TElemTo, 
              TElemTo,
             const_iterator, 
             pass_thru<TElemTo>, 
             TPredicate> 
        where(const TPredicate &predicate)
    {
        return filter<TElemTo, 
                        TElemTo,
                        const_iterator, 
                        pass_thru<TElemTo>, 
                        TPredicate>
                    (begin(),
                     end(),
                     pass_thru<TElemTo>(), 
                     predicate);
    }
};

template <class TCollFrom>
filter<typename TCollFrom::value_type, 
         typename TCollFrom::value_type,
         typename TCollFrom::const_iterator, 
         pass_thru<typename TCollFrom::value_type>,
         always_true<typename TCollFrom::value_type> >
    from(const TCollFrom &from)
{
    return filter<typename TCollFrom::value_type, 
                    typename TCollFrom::value_type, 
                    typename TCollFrom::const_iterator, 
                    pass_thru<typename TCollFrom::value_type>, 
                    always_true<typename TCollFrom::value_type> >
                (from.begin(), 
                 from.end(), 
                 pass_thru<typename TCollFrom::value_type>(), 
                 always_true<typename TCollFrom::value_type>());
}

int main(int argc, char* argv[])
{
    std::vector<int> vecInts;
    vecInts.push_back(5);
    vecInts.push_back(2);
    vecInts.push_back(9);

    auto filtered = from(vecInts)
        .where([] (int n) { return n > 3; })
        .select([] (int n) { return "\"" + to_string(n) + "\""; });

    for (auto i = filtered.begin(); i != filtered.end(); ++i)
        std::cout << *i << std::endl;

    return 0;
}

The main function is the pay-off, of course. I have a vector of ints, and I wrap it something that ends up stored in a variable called filtered, which I can then iterate through. The filtering (discarding anything not greater than 3) and transforming (int to quoted string) of the items happens on-the-fly during that iteration.

(And to clarify, this is different from the last time I posted it because select no longer requires any type parameters to be explicitly given - thanks to decltype).

Recovery

2009-05-14T11:38:00.002+01:00

If you want your application to be able to recover from a crash, it would NOT be ideal for it to restore the exact state it was in immediately before the crash, because then it would just crash again.

(Same goes for economies, presumably).

When to use Stored Procedures?

2009-05-11T11:09:00.002+01:00

No coding blog would be complete without an overly-simplistic salvo fired into this bloody online battlefield, so here's mine.

What if you're writing an application that will make heavy use of an RDBMS?

If you're writing an packaged app for sale to customers who want to run it on the RDBMS of their choice, don't use stored procedures.

But what if you're writing something bespoke?

Maybe you've never in practice had to change RDBMS in mid-project. But maybe that's because you automatically ruled it out as an impossibility - how do you know what advantages you might have had, what client license bundle offers you could have benefitted from, if you maintained the ability to switch RDBMS vendors on a whim? Competition pressure is what keeps vendors competitive, and competition pressure disappears if customers lose the ability to switch. The vendors know this, which is why they want to lock you in. So if you want to be able to get the best deal out of RDBMS vendors, don't use stored procedures.

But what if you want to have a layered architecture?

Adding more languages doesn't enable more layers. It just adds more development cost. You can write a data access abstraction layer in any language - and in Java and .NET, open source toolkits like [n]Hibernate already make this child's play, largely eliminating the need to generate your own SQL strings or DDL.

If you want to reduce development costs by keeping the number of language skills required to maintain an app lower, by writing all business logic and data layer logic in one language, don't use stored procedures.

But what if you're prepared to take on extra cost because you want to optimise by moving execution into the RDBMS?

If you haven't yet done any comparative profiling to establish where such optimisation is really needed or makes any measurable difference, don't use stored procedures.

... otherwise, knock yourself out!

General form of C# Object Initializers

2009-03-29T15:48:00.004+01:00

C# has a language feature that allows several properties of an object to be assigned to as a suffix to a new expression, namely the object initializer:

var myObj = new MyClass
            {
                SomeProperty = 5,
                Another = true,
                Complain = str => MessageBox.Show(str),
            };

As properties can have hand-coded setters, this is an opportunity to call several methods on the newly constructed object, without having to make each method return the same object.

The limitations on property setters are:

They can only accept one argument
They cannot be generic

I would like it if we could call methods and enlist in events, as well as assign to properties, inside an object initializer block.

var myObj = new MyClass
            {
                SomeProperty = 5,
                Another = true,
                Complain = str => MessageBox.Show(str),
                DoSomething(),
                Click += (se, ev) => MessageBox.Show("Clicked!"),
            };

And why should such a block of modifications only be applicable immediately after construction? We could have:

myObj with
{
    SomeProperty = 5,
    Another = true,
    Complain = str => MessageBox.Show(str),
    DoSomething(),
    Click += (se, ev) => MessageBox.Show("Clicked!"),
}

The with would be a new keyword that operates on an object of some type and produces the same object and type - note that this would be an expression, not a statement.

So you could use initializer-style syntax regardless of whether you'd got the object from a new expression or from an IOC or factory method, etc.

In fact you could use with after a complete new and it would be equivalent to the current style of object initializer:

var myObj = new MyClass() with
            {
                SomeProperty = 5,
                Another = true,
                Complain = str => MessageBox.Show(str),
                DoSomething(),
                Click += (se, ev) => MessageBox.Show("Clicked!")
            };

I mused about this in a Stack Overflow answer, and Charlie Flowers pointed out something I should have realised immediately - we can implement with as an extension method.

public static T With(this T with, Action<T> action)
{
    if (with != null)
        action(with);
    return with;
}

Equivalent of normal object initializer, but with event enlisting:

var myObj = new MyClass().With(w =>
            {
                w.SomeProperty = 5;
                w.Another = true;
                w.Click += (se, ev) => MessageBox.Show("Clicked!");
            };

And on a factory method instead of a new:

var myObj = Factory.Alloc().With(w =>
            {
                w.SomeProperty = 5;
                w.Another = true;
                w.Click += (se, ev) => MessageBox.Show("Clicked!");
            };

I couldn't resist giving it the "maybe monad"-style check for null as well, so if you have something that might return null, you can still apply With to it and then check it for null-ness.

Readonly Fields and Thread Safety

2009-03-06T10:30:00.002Z

In C# you can mark the fields of a type as readonly (indeed you generally should if it's a struct). By doing so, you make it illegal to change the fields except in a constructor of the type.

The advantage of this is that readonly data can be shared freely between threads without any thread causing updates that may be seen "in progress" by other threads, simply because there never will be any updates.

But is this strictly speaking true? Nope. It would be true if it were impossible for another thread to gain access to a partially constructed object. This seems true at first because the constructor of an object effectively "returns" a reference to itself via the new operator, which then becomes available to the caller of new, at which point the object is available to be passed around and is also fully constructed.

But a constructor can call methods, and it can pass this to methods. Those methods could pass that information to other threads. So you have to be careful what you do in a constructor. Maybe the compiler will help to check this somehow in a future version of the language.

This ties in nicely with some general advice about constructors that Brad Abrams gives in the Annotated C# Programming Language: do as little as possible in the constructor, and do everything else "lazily" - that is, the first time you need it. If you find yourself requiring non-readonly fields to achieve that, then you potentially have a problem with your design, because your class as a whole is not going to be readonly and so will not be trivially shareable in the way you originally assumed.

JavaScript Invaders!

2009-03-04T23:31:00.001Z

Click in the small text field in the top left corner to give allow the game to receive keyboard events.

Z = left
X = right
M = fire

Compatible with IE, Firefox and Safari, pure JavaScript and HTML

I wrote this during a train journey, just to see if it was practically possible. Only then did I google for other examples, and found quite a few going back years. This version of Pacman has excellent attention to detail.

The Amazing Speed of the .NET Garbage Collector

2009-03-01T17:16:00.002Z

Coming from a C++ background, I always balk at designs that involve lots of small heap allocations. It’s something I’m gradually training myself to stop doing, because in managed code, it’s a completely irrational concern.

Given the constant usefulness of lambdas for things like this, it is worth reassuring myself (and others) that the overhead of such techniques is negligible. I already knew it probably was, but I had no idea just how negligible. It really is ridiculously unimportant.

Here’s my simple test program – most of the operations it does are meaningless busywork (like a typical school day). The important thing is the difference between Foo1 and Foo2:

public class Program
{
    private static readonly Queue<string> _q = new Queue<string>();

    public static int _c;

    public static void Push() { _q.Enqueue(_c.ToString()); }
    public static void Pop() { _q.Dequeue(); }
    public static void Count() { _c++; }

    public static int Foo1()
    {
        int x = 0;
        Push();
        Count();
        x++;
        Pop();
        return x;
    }

    public static void Gateway(Action a)
    {
        Push();
        a();
        Pop();
    }

    public static int Foo2()
    {
        int x = 0;
        Gateway(() =>
                       {
                           Count();
                           x++;
                       });
        return x;
    }

    public static double Time(Action a)
    {
        Stopwatch s = new Stopwatch();
        s.Start();
        a();
        s.Stop();
        return s.ElapsedMilliseconds;
    }

    public static void Main(string[] args)
    {
        _q.Enqueue("x");
        _q.Enqueue("y");
        _q.Enqueue("z");

        int reps = 100000000;

        double direct = Time(() =>
        {
            for (int n = 0; n < reps; n++)
                Foo1();
        });
        
        Console.WriteLine("Direct, " + reps + " calls: " + direct / 1000 + " s");

        double lambda = Time(() =>
        {
            for (int n = 0; n < reps; n++)
                Foo2();
        });

        Console.WriteLine("Lambda, " + reps + " calls: " + lambda / 1000 + " s");

        double overhead = (lambda - direct);
        double percall = overhead / reps;

        Console.WriteLine("Overhead per call: " + percall * 1000000 + " ns");
    }
}

Foo1 calls Push, Count and Pop and also fools around with a local variable, x. Note that Push and Pop manipulate a queue of strings. The queue stays a constant length during the test, with newly allocated strings being inserted and old strings being removed, so the GC has some work to do. The reason I used a queue was so that the lifetimes of GC objects would not simply coincide with the stack of function calls, forcing the CLR (I vaguely assume) to truly allocate objects in Generation 0 instead of “cheating” and using the stack to store everything.

Foo2 does the same, but it does so via Gateway. Also note that it captures the local variable x in a closure, so it can be read and modified in Foo2 and in the nested lambda.

This means that for every call to Foo2, it is necessary to allocate two GC objects. Firstly, the closure is implemented by a compiler generated class, which would look like this:

[CompilerGenerated]
private sealed class <>c__DisplayClass1
{
    public int x;

    public void <Foo2>b__0()
    {
        Program.Count();
        x++;
    }
}

The local variable x has become a field of that class. So every time Foo2 is called, an instance of <>c__DisplayClass1 is allocated to store the variable x. Then there’s the lambda, which has become the method <Foo2>b__0 of the class. In order to pass it to Gateway, an instance of the Action delegate must be created that has an Invoke method that forwards to <Foo2>b__0.

To confirm this, look at the IL for Foo2:

.method public hidebysig static int32 Foo2() cil managed
{
    .maxstack 3
    .locals init (
        [0] class Program/<>c__DisplayClass1 CS$<>8__locals2)
    L_0000: newobj instance void Program/<>c__DisplayClass1::.ctor()
    L_0005: stloc.0 
    L_0006: ldloc.0 
    L_0007: ldc.i4.0 
    L_0008: stfld int32 Program/<>c__DisplayClass1::x
    L_000d: ldloc.0 
    L_000e: ldftn instance void Program/<>c__DisplayClass1::<Foo2>b__0()
    L_0014: newobj instance void [System.Core]System.Action::.ctor(object, native int)
    L_0019: call void Program::Gateway(class [System.Core]System.Action)
    L_001e: ldloc.0 
    L_001f: ldfld int32 Program/<>c__DisplayClass1::x
    L_0024: ret 
}

Sure enough, there are two calls to newobj – the first one allocates the storage for the closure, the second allocates the Action delegate. Compare this with the much cleaner-looking code for Foo1:

.method public hidebysig static int32 Foo1() cil managed
{
    .maxstack 2
    .locals init (
        [0] int32 x)
    L_0000: ldc.i4.0 
    L_0001: stloc.0 
    L_0002: call void Program::Push()
    L_0007: call void Program::Count()
    L_000c: ldloc.0 
    L_000d: ldc.i4.1 
    L_000e: add 
    L_000f: stloc.0 
    L_0010: call void Program::Pop()
    L_0015: ldloc.0 
    L_0016: ret 
}

No allocations, just some method calls. So the overhead of Foo2 must be pretty big, right? Especially when those heap-allocated objects will need to be garbage-collected all the time. What if a lot of them build up? Won’t that put “pressure” on the GC and make everything grind to a halt?

Well, try running the test program. It does a hundred million calls to Foo1, and then the same number of calls to Foo2. It then figures out the difference in the timings for these runs. On my VM of Windows XP running on a MacBook Pro, the output is:

Direct, 100000000 calls: 27.209 s
Lambda, 100000000 calls: 33.515 s
Overhead per call: 63.06 ns

Now, it’s customary with this kind of test to observe that 33 seconds is longer than 27 seconds and try to conclude something from that, like “lambdas make your code about 25% slower”. However, that would be completely stupid. The point is that the code in the test is doing very little, apart from keeping the GC a little busy, so that makes the overhead appear more significant than it would be in a real program. The important point is that it only took 6 seconds longer even though we are doing a hundred million calls, i.e. the overhead per call is about 60 nanoseconds. Which is very, very small. Code that actually did something useful would make such an overhead utterly invisible.

Note that if the GC was not collecting at regular intervals during the test, we would have a build up of 400 million objects (100 million strings in Foo1, another 100 million in Foo2, which also needs 100 million closures and 100 million delegates). The overhead on an object is 8 bytes (two pointers used by the CLR), so that’s approximately 3 GB of memory requirement even without considering the actual data stored in the objects. So the GC clearly is cleaning up old objects during the test, or else it wouldn’t finish successfully.

So the GC heap is so fast that in a real program, even in tight loops, you can use closures and delegates without even giving it a second’s thought (or even a few nanosecond’s thought). As always, work on a clean, safe design, then profile to find out where the overhead is.

Making Lambdas and Iterators Play Nicely Together

2009-02-26T22:42:00.002Z

The major problem with this idea is in my favourite feature of C#. In an iterator (a function containing the yield keyword), the code is transformed into a state machine represented by a class. It has to be chopped up into sections, so the function can be “paused” after each yield return. Those pieces must all be in the same function, so sadly lambdas don’t play well with iterators.

There are a couple of possible future language features which would completely solve this, however.

Firstly, how about yield foreach. This would take an IEnumerable<T> and yield all the items of it. It would remove the need to write an explicit foreach loop to return a nested sequence. This amazing paper shows how this feature would be implemented (they even picked the same keyword), although the use-case there is to support recursion with good performance.

Secondly, I’d like to be able to write an anonymous iterator. This would be a matter of using yield return in the middle of a lambda, and hey presto, the compiler would build me an iterator instead of a normal anonymous method.

How would these two features help here? Suppose I wanted to use my TraceWriter (see the source download) class in an iterator. Here’s how it would look:

IEnumerable<int> MyIterator(TraceWriter w)
{
    yield return 1;
    w.WriteLine("Not indented yet");

    yield foreach w.Indented(() =>
    {
        yield return 2;
        w.WriteLine("Indented now");
        yield return 3;
    });

    w.WriteLine("Un-indented again");
    yield return 4;
}

So we have the same readability as before. This would require a special implementation of the Indented method, specifically for iterators:

public IEnumerable<T> Indented<T>(IEnumerable<T> sequence)
{
    WriteLine("{");
    _indent++;

    yield foreach sequence;

    _indent--;
    WriteLine("}");
}

It’s handy, that yield foreach thing, isn’t it?

Fatal Exceptions, and Why VB.NET Has a Purpose!

2009-02-26T21:14:00.002Z

There’s a feature in the CLR that is exposed in VB.NET and not in C#. Apparently this is a deliberate decision made by the C# team, which so far they’ve stuck to. Unfortunately, it’s a pretty important feature.

I was prompted by Andrew Pardoe of the CLR team to look more closely at this when considering try/finally and the problem of “fatal” exceptions. By fatal, I mean an exception that you have no idea how to handle. A good example is NullReferenceException, which almost certainly indicates a bug. If there’s a bug, your program is in an unknown state, and you need to capture that state exactly as it is. Ideally the program would terminate at that point. In the interests of flexibility, the CLR does allow you to catch such exceptions. (Then the CLR team tells you that you shouldn’t – it’s a “fruit of the tree of knowledge” type of situation.)

Very often a method will throw a variety of exceptions to indicate that it was unable to finish what it was supposed to do, but it ain’t the end of the world. These are recoverable exceptions. A simple example is FileInfo.Delete:

string errorMessage = null;

try
{
    new FileInfo(@"c:\myfile.txt").Delete();
}
catch (SecurityException x)
{
    errorMessage = x.Message;
}
catch (IOException x)
{
    errorMessage = x.Message;
}
catch (UnauthorizedAccessException x)
{
    errorMessage = x.Message;
}

if (errorMessage != null)
    MessageBox.Show("You idiot - " + errorMessage);

Now, there’s a slight problem, which we’ll gloss over – how do you know what exceptions a method will throw? Ultimately, you need accurate, reliable, up-to-date documentation for every method. But instead of waiting for hell to freeze over, let’s move on.

When you have an operation that performs many such calls to various APIs, 3rd party libraries and so on, the ideal place to put the handler is at the outermost layer where you can recover. For example, the user presses the button and you run a lot of code to do what the user has asked. The best place to put the try/catch is around that whole sequence of operations, so that the catch can display the error to the user, and so they can figure out why they’re such an idiot. Inside that operation, you need to use try/finally (and related constructs) to ensure that any half-finished stuff is always properly undone. Nice and simple.

Except for one slight irritation: now the set of exceptions you need to catch is the union of all the recoverable exceptions that might be thrown by all the operations performed within that combined operation. This means that your try/catch block potentially has a ridiculously long list of types. It’s also very easy to miss an exception type here or there, which would mean that your program would crash when it didn’t need to. Whenever someone performs maintenance on the big operation (or any of the APIs or 3rd party libraries it calls on to), the huge list of catch blocks needs to be updated to ensure nothing is missed.

Also this all needs to be done separately for every try/catch statement. So you might think of reducing this hideous boilerplate repetition by writing it once:

public static bool Recover(Action action, Action<Exception> recover)
{
    try
    {
        action();
        return true;
    }
    catch (SecurityException x)
    {
        recover(x);
    }
    catch (IOException x)
    {
        recover(x);
    }
    catch (UnauthorizedAccessException x)
    {
        recover(x);
    }
    //others...

    return false;
}

You can now write nice neat lambdas to provide the code for the action to try and the single recovery handler. But you still have the same major problem: this long list of all the recoverable exceptions has to include every single one that might be thrown anywhere in any operation.

What if your product is extensible, such that 3rd parties can write plug-ins for it? How do they add their own recoverable exceptions to the Recover function? They simply can’t. And even if they could, what if they don’t remember to? How does your application protect itself?

So you have explosive complexity and apparently no way to control it.

At this point, the following quite reasonable thought occurs to you: surely the number of fatal exceptions is smaller than the number of non-fatal ones. Indeed, the number of non-fatal ones is constantly growing as we create new exception classes of our own. Also, if I make any mistakes in constructing my software, I’d prefer to not crash rather than crash.

The natural conclusion, which therefore naturally occurs to everyone eventually, is to do this:

try
{
    new FileInfo(@"c:\myfile.txt").Delete();
}
catch (Exception x)
{
    MessageBox.Show("Couldn't delete file: " + x.Message);
}

But then you remember that there’s such a thing as a fatal exception. Although you’d generally prefer your software not to crash, in the event of a definite bug, it is better for it to crash – that way, you get an accurate snapshot of the program’s state. So you need to examine the exception object before you try to handle it:

try
{
    new FileInfo(@"c:\myfile.txt").Delete();
}
catch (Exception x)
{
    if (!ExceptionPolicy.IsExceptionRecoverable(x))
        throw;

    MessageBox.Show("Couldn't delete file: " + x.Message);
}

Of course, that IsExceptionRecoverable method has to be written by you, but only once, and it probably has a relatively short list of exception types to look out for, and that list doesn’t grow so fast as the list of recoverable exceptions.

The above solution represents the state of the art according to the Microsoft Enterprise Library. Unfortunately, it’s still not right. The problem is to do with the thing I mentioned above about how to correctly write the code within each long and complex operation:

Inside that operation, you need to use try/finally (and related constructs) to ensure that any half-finished stuff is always properly undone.

The problem is, you only want the finally blocks to run for recoverable exceptions, not fatal ones. To repeat what I said right at the start:

If there’s a bug, your program is in an unknown state, and you need to capture that state exactly as it is.

So you definitely don’t want to run any finally blocks before that state is captured. They might modify it (in fact, that’s the whole point of them). They might make it worse, cause further corruption, or even throw another exception and so hide the original bug.

My first thought when this occurred to me was that try/finally presents a serious problem. How can we make it execute the finally block for a recoverable exception but not for a fatal exception?

Well, we can, sort of. If you don’t ever catch an exception, the finally blocks never run. When an exception is thrown, the CLR does not immediately run the finally blocks. First, it checks to see if there is a suitable catch in the stack for the current exception. If there is, and only if there is, it runs the enclosed finally blocks, and then runs the catch block.

This is why the correct advice is to never catch fatal exceptions, because merely catching them will trigger the silent execution of finally blocks when the program is already in an unrecoverable situation.

But this is sadly no good to us, because we’ve already established that explicitly catching only the recoverable exception types will lead us to a situation of hideously and unmanageable complexity, and programs that crash when they don’t need to. It’s just not practical to work that way.

The problem all stems from the fact that catch blocks can only decide to run based on the type of the exception, and this has to be an “opt in”. It can’t be coded the other way round, as an “opt out”. Yes, exceptions can be arranged in hierarchies and so that one catch block can catch all exception types derived from some base class, but this turns out to be useless because there’s no base class that all recoverable exceptions have in common, except for the class which is also the base class of all fatal exceptions as well.

So we cry: if only the CLR allowed us to run some code of our own to decide whether to catch an exception, before the finally blocks run.

The surprising answer (to a C# programmer) is that the CLR does allow us to do that. It just isn’t made available in C#. Only in VB.NET. Devastating, huh?

So to do exception handling in C#, in a way that is actually manageable, but also doesn’t execute code after a fatal exception, you first have to crank up VB.NET and create a class library containing this class:

Imports System

Public Class Exceptions
    Public Shared Sub TryFilterCatch(ByVal tryAction As Action, _
            ByVal filter As Func(Of Exception, Boolean), _
            ByVal handler As Action(Of Exception))
        Try
            tryAction()
        Catch ex As Exception When filter(ex)
            handler(ex)
        End Try
    End Sub
End Class

This effectively turns the magic feature of VB.NET – the When clause that appears next to the Catch – into something we can reuse in any CLR-based language. Having built that, you can now go back to C#… phew!

Now, supposing you still have that IsExceptionRecoverable method handy, you can do this:

Exceptions.TryFilterCatch(() =>
{
    new FileInfo(@"c:\myfile.txt").Delete();
},
ExceptionPolicy.IsExceptionRecoverable, x =>
{
    MessageBox.Show("Couldn't delete file: " + x.Message);
});

Given that we are effectively forced to this conclusion by the above reasoning process, it’s very strange to look at where we’ve ended up. Essentially, if you want a manageable, fault-tolerant, practical approach to exception handling, the above example is what you need to use, instead of using C# try/catch statements.

How does this situation persist? Why isn’t general exception filtering exposed in C#, as it is in VB.NET? These are very good questions. It seems that the C# team doesn’t accept the line of reasoning I gave above. According to them, we should all write long and unmanageable lists of catch handlers, explicitly listing the recoverable exceptions, based on the apparently trustworthy documentation of every software component we ever call into.

The CLR team, on the other hand, is well aware of this problem, and is aware that people are forced to try an alternative, and so inevitably make their way down the chain of reasoning I’ve described here, and the Microsoft Enterprise Library is probably representative of where most people stop in that chain.

The earliest reference I’ve found for all this stuff is here. It covers all the technical details, and mentions the idea of exposing VB.NET’s filtering capability.

This is the blog post that Andrew Pardoe pointed me to. The more I think about it, the more I think it’s a message to the C# team, rather than to users. The chances of many users hearing the message is low, and the chances of them understanding the implications is probably a little lower still. They must be hoping that the C# team will hear it and understand it. I guess C# is a customer of CLR, so the C# team is “always right” in that relationship. Consequently the message will need to come from customers of the C# team!

In the meantime, the CLR team is doing something about this problem:

In version 4 of the CLR, the product team is making exceptions that indicate a corrupted process state distinct from all other exceptions.

This is only part of the solution, of course, because in some situations our own exception types can indicate that the program is in an invalid state. The “corruption” is not of the low-level, random byte trashing kind, but it is corruption by a bug, nonetheless. So we need the recoverability criterion to be specified in a customizable way for each try/catch situation.

This means that, even after version 4 of the CLR, we will still need that snippet of VB code. Until the C# team catch-es up with the VB.NET team.

What's Wrong With C# 4.0's dynamic Keyword, and How I Think It Should Be Fixed

2009-02-25T10:08:00.003Z

Update: Exactly what I want, already implemented, complete with caching of the call site. Also, Microsoft's Mads Torgersen responds to this suggestion here.

C# 4.0 proposes to add the dynamic keyword to the language. There are a few problems with it:

Beginners have no clue what the difference is between object, var and dynamic. This is a relatively minor problem compared to the others, but it's worth considering.
The dependency of a program on specific features of a dynamic object are not captured in a central definition, defeating the type system. I'll explain this a bit better below.
There's no intellisense support (this is really the same thing as point 2, but it's so important that it's worth highlighting on its own).
New language features are an unnecessary pain if you can meet the same need with a library feature - and I believe you can do a better job with a library feature in this case.

In a nutshell, I sincerely hope that dynamic is removed from C# 4.0. In its place, there should be a static class in a namespace System.Dynamic. It would have one method, an extension on object:

public static TInterface AsDynamic<TInterface>(this object obj)
      where TInterface : class

This would take any object at all and return a dynamic wrapper that implements the specified interface by forwarding calls onto the wrapped object. The wrinkle here is that TInterface really should be an interface but there's no way of constraining to that (now there's a language feature I'd accept quite happily).

Now in order to make use of a dynamic object (that is, an object whose type is unknown to me) I simply declare the features I require of that object, in an ordinary interface. Whenever I receive such an object, I wrap it with that interface as soon as possible, and use that interface to refer to it thereafter.

What's so great about this? Suppose my dynamic object is a frog. So first I declare an interface IFrog:

public interface IFrog
{
   void Ribbit();
}

This states in a single location what features a dynamic frog must have.

Now I can make the majority of my code use this interface to refer to frogs. At the "dynamic boundary" where I receive weird objects from the outside world, I immediately convert them to IFrog so the rest of my code can use them:

IFrog f = something.AsDynamic<IFrog>();

This doesn't change the dynamic nature of what is happening. Exactly the same kind of method resolution now has to happen at runtime, and no capability has been lost compared to the present dynamic keyword design.

But there are big advantages. Firstly, users don't need to understand a new keyword that clashes conceptually with two other things. Secondly, what if the dynamic system that passes me frogs changes the way it works, so now it expects an argument to be passed to Ribbit? No problem for me. I just update my interface:

public interface IFrog
{
   void Ribbit(bool loudly);
}

Now when I recompile, the C# compiler will find all the places in my code where I need to provide the new argument. The lesson here is that all languages (whether statically or dynamically typed) end up having these kinds of contracts or dependencies on the features of objects. The advantage of static languages is that it pays to declare those contracts centrally, so you can update them more easily.

Then there's the intellisense - obviously this works as usual with IFrog. It doesn't work at all with the current C# 4.0 design.

Finally, this would be a library feature. It would be available in a consistent way from C#, VB, F#, Eiffel, and so on. It's also very optional - if you don't want to see the AsDynamic extension appearing on every class, then don't add using System.Dynamic to your source file.

Also I may as well point out that it would be easy to instantly find all uses of dynamic type conversion within a solution, by simply finding all references to the AsDynamic method. So no need for a new IDE feature there.

This solution contains the dynamic stuff rather than spreading it around. It strikes me as being far more in the spirit of C# as a statically typed language designed for large-scale development. Yes, the dynamic keyword makes short examples look cool on the page. But it doesn't make them fun to write in the first place (no intellisense), or to maintain (no central type definition).

How about it, Microsoft?

General Theory of Resources

2009-02-13T20:47:00.002Z

Having blogged the other day about a different way of doing automatic cleanup, I’ve been mulling it over and also answering a question on StackOverflow, and decided that I need to assemble a taxonomy of resources; what kinds there are, how to recognise them by their distinctive markings, guidelines for upkeep, training, feeding, breeding, etc. And because I’m obsessive-compulsive, I also wanted to develop a complete and rigorous theory of resources from the ground up.

I don’t like it when I have to say “In that sort of situation I normally try something like this and it usually seems to work.”

So without further ado, I present the General Theory of Resources.

Resources Modeled by Conceptual Bits

Imagine an array of bits, ones and zeros. Each represents something that has to be rationed between the parts of your program that want to use it. Only one “user” at a time can take ownership of the thing represented by the bit. When the thing is in use, its corresponding bit is set to 1. Otherwise, it is set to 0. If all the bits are 1 when you show up with your begging bowl, you’re out of luck. Note that these are just conceptual bits; real implementations might not actually maintain an array of bits or Booleans specifically for this purpose. But the two-state nature is always there nonetheless. We can imagine each available resource being modeled by a bit indicating whether it is currently reserved for exclusive use.

Are we talking about an infinite number of bits? Of course not. If we were, then we wouldn’t need to go any further in this discussion. We are frequently talking about a single bit. Often we are talking about a number of bits just large enough to fool us into thinking that our program is correct, only to find out later that it isn’t because it eventually runs out of bits.

Enter and Exit

Atop this set of bits, there is a pair of operations, which I’ll call Enter and Exit. When Enter executes, it sets a bit, or possibly a bunch of bits to 1. When Exit executes, it sets the bits back to 0 again. The two operations abstract over the underlying set of bits.

We sometimes say that a resource “exists” whenever we have executed Enter but have not yet executed Exit in the right way to reverse the state changes caused by Enter. A correct program must execute Exit once for every time it executes Enter.

Fungibility

You don’t complain to the bank if they give you “someone else’s cash”; it can be any old cash, as long as it adds up to the required value.

Some resources are fungible, meaning that the caller doesn’t care which particular bunch of bits is set to 1. An incorrect program would run out of such fungible bits because it would forget to Exit and so the number of 1-bits would build up over time, until eventually there would be no 0-bits remaining.

If you came home after leaving your kids with the babysitter, and found that they were different kids, you wouldn’t be satisfied if the baby sitter said, “They look pretty similar to your kids, don’t they?”

Other resources are non-fungible, meaning that the caller requests that a specific bit must be set, so each bit has a meaningful identity. An incorrect program would try to set a non-fungible bit to 1 that it had already set to 1. Sometimes a resource has only one bit to play with, in which case it is surely non-fungible, because we cannot use it without implicitly specifying which bit we want to use.

Orthogonality

Some resource types are orthogonal, meaning that the states of the bits are effectively mutually independent (they may be bunched together by the Enter and Exit operations, but if those bunches are mutually orthogonal then we still say that the resource is orthogonal).

Some are non-orthogonal, meaning that the states of the bits are entangled in some way, even though they are manipulated by separate Enter and Exit operations. Sometimes a resource has only one bit to play with, in which case we may as well call it orthogonal (because there is nothing for the single bit to be entangled with).

The only non-orthogonal kind of resource I consider here is stack-like. There may be other useful kinds, but I can’t think of any off hand.

Some Examples

Here’s a nice table of some contrived examples and their various attributes:

Resource	Enter	Exit	Bits	Fungible	Orthogonal
Unmanaged memory in C	malloc	free	One per word of memory	Yes	Yes
A stack of integers	A Push method	A Pop method	One bit per stack depth	No	No
A static Boolean flag, _entered, protecting a method from reentrance	// start of method if (_entered == true) return; _entered = true;	// end of method _entered = false;	One	No	Yes
A file	The CreateFile API	The CloseHandle API	One per file	No	Yes
An XML output stream	A method such as BeginElement	A method such as EndElement	One per open element	No	No
A thread-local integer, _entered, that monitors recursion into a method	// start of method _entered++;	// end of method _entered--;	One per possible level of recursion	No	No

Something to consider: I give no example that is both fungible and non-orthogonal. If a resource is non-orthogonal, it means that the user has to be careful about the order in which it takes ownership of or releases ownership instances of that resource. It cannot do this if it is required to treat the resource as fungible, to not care which instance it is holding onto. So non-orthogonal implies non-fungible.

Another thing that should certainly be clear by now is that a "resource" is not something the operating system provides you with, implemented in native code. It can be, in the case of resources encapsulated in kernel handles that can be closed with CloseHandle, but there are other things, which you can write all by yourself, in pure C# or VB.NET or F#, which are also best thought of as resources.

Now let’s pick a few of them apart to make sure it’s all clear.

Unmanaged Memory in C

This may seem like a strange example to pick, because we have managed memory these days. But managed memory is fundamentally the same as unmanaged memory except that the runtime performs lazy cleanup automatically on another thread, and the question we must ask is: what makes this an appropriate solution for managing a resource? With what kinds of resource may we use such a clever solution?

Firstly, consider the C unmanaged memory heap, also known as the “free store”. We’ll assume memory has a resolution of one “word” (which would typically be either 4 or 8 bytes, but that doesn’t matter right now). Each word is either part of the free memory or it is part of some allocated memory. So apart from its actual contents (which we don’t presently care about at all), each word has one of two states associated with it: 0 for free, or 1 for allocated. These state bits are all completely orthogonal - independent from each other.

On top of this simple model, the heap provides a convenient abstraction: you can use Enter to find N contiguous free words for you and it will mark them as allocated (set the bit corresponding to each word). Later on, you can pass to Exit the address of the first word you were allocated and the heap will set those words back to the unallocated state (unset the bits). Each bunch of bits is orthogonal with respect to all other bunches, because the bunches can never overlap.

To reiterate, we are not talking about manipulating the stuff stored in the words (that’s the application’s job). We’re just imagining that the heap keeps track of which words are in use and which are free by recording those facts in a separate array of bits, one bit for each word of memory in the process. Of course in practice the heap can optimize its data structures so it doesn’t actually need to keep an array of bits to track the allocation status of every word separately.

If we rewrite the heap’s operations in C#, using my names for them, then they look like this:

     IntPtr Enter(int wordsToAllocate);

    void Exit(IntPtr blockToFree);

This is the standard pattern for an orthogonal resource. The parameter(s) to Enter do not give the identity of the bits that need to be set. Instead, they describe what is needed in a more general sense, and the Enter operation finds a group of bits that fit the bill: any group of bits representing a contiguous region of words of the length requested.

We then have this token or receipt being returned by Enter and we have to give it back to Exit when we no longer need the memory. The token can be used to access the block of memory, and it also is the key to freeing it.

A Stack of Integers

Now consider a stack of integers, something like a Stack<int>. The Enter operation takes the thing to put on the stack. This puts the system (the stack) into a state of being taller than it was before. However, the Exit operation does not require any information. It is the nature of a stack to only let you remove the top-most item, so all you need to tell it is that you would like it to remove something. You don’t have to tell it which item to remove (if you could do that, it wouldn’t be a stack). If this isn’t what your program needs, then you shouldn’t be using a stack.

As with any other resource manager, a stack has a conceptual array of bits. It is usually very large, but of course not infinite. Most of the bits are set to 0, most of the time. All the bits set to 1 are at the front of the array, and each 1-bit represents an item on the stack.

…

When we push something on the stack, we set the next 0-bit to 1:

…

When we pop something off the stack, we set the last 1-bit to 0:

…

Obviously there is nothing like orthogonality here. The bits are very much entangled such that no state change can occur that would stop the bits from being properly sorted into two neat groups. You certainly can’t just flip the state of any bit. Nor is there fungibility, because the identity of a specific bit to modify is implied by the operation we execute (non-orthogonality implies non-fungibility, remember?)

If we wanted to we could make our stack resource fit the same pattern as the unmanaged heap functions, with a little creativity and shoehorning. Firstly, the Enter operation might return the new height of the stack, which would serve as a unique resource handle. Exit would then accept that same value. Now we’d have an interface much like the above memory interface. But Exit would have to throw an exception if we passed it a value that was not the current height of the stack. Apart from performing this check, there is no other purpose in passing a value to it. So it is thoroughly misleading to expose the above interface on a stack-like resource. Instead, stack-like resources should have this kind of interface:

    void Enter(T item);

    T Exit();

This makes it obvious that there is no choice about which state the stack will be restored to next. Bear in mind that the item parameter is quite optional. As with the memory example, we’re not interested here in what the job stack is doing, but merely it how it behaves as a resource.

A Boolean Flag as a Recursion Guard

Sometimes you need to protect a method against re-entrance. For example, suppose you have an event handler that in turn fires another event. There is a danger that someone else will wire up the other event to fire the event your handler is wired up to, and there will be an endless recursion. To protect against this, you can create a static Boolean variable and make your event handler do nothing at all if it is true. Otherwise your event handler is able to run normally. First it sets the flag to true, then it goes about its business (firing the other event), and then sets the flag back to false again. This stops the infinite recursion from happening.

But it also means that your event handler (or whatever method you apply this approach to) is a resource, albeit a very limited one. It can only be used by one client at a time in the whole process. Consequently it is modeled by a single logical state-bit (indeed, it is implemented by one, in the form of the Boolean variable).

This definitely makes it non-fungible (because we cannot help but specify which bit we want to take over) but also orthogonal (because there are no other bits for this single bit to be entangled with).

File Handles

Now for the really complicated example. With file handles, the Enter operation produces a unique identifier that you have to hold on to. You then have to pass the same identifier back to Exit to close the file handle. So far, it looks a lot like memory. But there’s an added wrinkle, which is that there are two different kinds of resource here: files and handles.

The OS maintains a set of handles, and that constitutes a system which does indeed have the same properties as the C memory heap. Each possible handle value has an orthogonal Boolean state (allocated, unallocated) associated with it, just as every word of memory does. Applications are not interested in which handle value they receive, making them also fungible.

But the OS also maintains persistent files with unique names on your hard drive, and these each have an orthogonal state-bit associated with each of them, if we consider write-locking, which is the most problematic case. But these are definitely non-fungible, because they are identified by their names. (Note that if you build an abstraction on top if this system to make up random temporary filenames, then they become fungible again, but that’s another story.)

In reality, the Enter operation presented to applications is actually two operations that together form an atomic transaction. First the specified file is locked, meaning that its associated bit is set to 1. Then an unallocated handle is found (which is entirely the choice of the OS, because like money and memory, handle values are fungible) and its bit is also set to 1.

Consequently, although the “handle system” allows multiple simultaneous handles to exist, the file system forces us to treat files very carefully as resources. It is vital to understand this, because the Enter/Leave API looks treacherously similar to the memory API:

    IntPtr Enter(string fileName);

    void Exit(IntPtr handleToClose);

It has to look like that because handles work that way. But files do not – they are closer to the example of using a Boolean flag to guard against reentrance.

This frequently tricks people into thinking that they can treat file handles in the same way as memory – that is, let a lazy garbage collector take care of calling Exit automatically some time, hopefully not too long after there are no remaining references to the file handle. But the difference is in the information being passed into Enter. It is not a general description of what might fit the bill, but the specific identity of the one and only thing that is needed.

So the truth is that a program that fails to close its file handles in a well-understood way is probably not going to work very well. On Windows there is in fact no way of opening a file without locking it against at least one other operation (deletion), so even non-exclusive file handles have some problems.

As a digression, consider directories or folders in the file system. Enter creates a directory and Leave destroys it. There is one root directory which cannot be destroyed, and all other directories must have a parent directory. The result is a tree-like structure. But we can conceptually simplify it by thinking of it as a set of interleaved stacks. The chain from any leaf directory to the root is a stack, so we know for sure that tree-like resources are at least as restrictive as stack-like resources.

The other two examples are not appreciably different from what we’ve already examined. A stream of XML being written sequentially – however it is implemented – is effectively a stack. Each 1-bit represents an open element. The elements must be closed in the right order to ensure well-formed XML is produced. And the integer being used to monitor the level of recursion into a method, that too is a stack: one that stores nothing except a record of its current depth.

Internal Resources vs External Resources

One crucial point that should be clear by now is that there is not really a distinction between states “inside” your program and states “outside” of it. There is a tendency among C# programmers to think of the stuff they write themselves as “managed” (because it’s in managed code) and the concepts exposed by the operating system as native or “unmanaged”.

In fact, if your program internally maintains state, and the state needs to obey rules like the ones described here, then it inevitably defines resources of its own. And unless you take steps to provide automatic management of the lifetimes of your custom resources, then they are unmanaged resources, no matter what language they are written in or what runtime technology they are based on.

While an object exists in the CLR, it may have internal mutable state, and there may be rules for the correct use of that state, such that we have to conclude unavoidably that it is a type of resource, and it may or may not be be fungible or orthogonal. So the fact that the whole object will eventually be garbage collected is no comfort. What matters is that the state of it is modified correctly during its lifetime. We need some kind of automatic resource management to deal with the internal state of our own objects, as well as the objects exposed to us the operating system.

So what does all this tell us? It tells us that managed memory is one kind of resource among many, that the fundamental nature of resources means that they require management of some kind, and that the technique (lazy garbage collection) applicable to management of memory is only applicable because of specific properties of that kind of resource (fungibility, orthogonality). Other resources do not have those properties, and yet still need to be managed. So we need other techniques for them.

Resource Management Techniques

How can we manage resources easily in C#? By taking advantage of facilities in the language wherever possible. We have the interface to the resource in the form of the Enter and Exit functions, but we would like to avoid the kind of problems that occur when we forget to call Exit once for each call to Enter. So we want something easier than merely putting in the calls manually.

There are three solutions:

Finalizers
IDisposable/using
Gateways (methods that Enter, forward to a delegate, then Exit)

The first two are often confused and conflated. The last one is, to my mind, massively superior to the other two, for reasons that should become clear, and yet is rarely described in this context as far as I know. I’ve coined the term “gateway” because I’m not aware of another term for them, so please let me know if there’s a better name.

Finalizers

Finalizers are essentially horrid nasty things. It should rarely be necessary to write one. It is notoriously difficult to write one correctly. I have never bothered.

The basic idea is to hitch a ride with the GC’s ability to lazily dispose of memory resources. The information needed to Exit a resource is stored in an object, and when that object is reclaimed by the GC, the object’s finalizer executes and calls Exit for the resource.

The GC schedules the finalizer to run lazily (that is, some time soon but not immediately or at a predictable time), which means that it is only really useful for resources that are fungible. Consider what this means for file handles: finalization will ensure that your process does not run out of handles, because they are fungible and in plentiful supply, but it does not help at all in avoiding bugs caused by holding onto file locks for longer than necessary, because files are non-fungible.

And don’t even consider trying to manage stack-like resources with finalizers. Imagine the mess, with things being popped when they shouldn’t be.

The information needed to Exit the resource must be stored in value-type fields only; it is not generally safe to access other reference objects (classes) from a finalizer. This means that finalizers are only really useful for resources defined by the operating system as kernel objects (and in fact there is a better way of encapsulating those, called the SafeHandle.)

So the less said about finalizers the better.

IDisposable/using

The other official way of managing resources is to encapsulate the resource in an object (as with the finalizer approach) and to give it a Dispose method, as defined in the interface IDisposable. The construction of the object corresponds to Enter, and Dispose serves as an Exit.

Then the language provides the using statement as a convenient way of ensuring that Dispose will be called when the flow of control leaves a specified scope:

 using ( resource-acquisition ) embedded-statement

This approach is fully deterministic and non-lazy. It has none of the limitations of finalizers. Because the using statement weaves itself into the thread’s method-call stack, it works very well with stack resources - each object’s Dispose is guaranteed by the C# specification to be called in the reverse order that the objects were constructed, assuming they were constructed in the resource-acquisition.

There are several intrinsic technical drawbacks, however:

The fact that Dispose is available as a public method gives the impression of an orthogonal resource. You don’t have to employ the using statement – you can just call Dispose manually whenever you want. This would play havoc with a stack-like resource just as surely as using a finalizer.
It is surprisingly easy to forget to put in the using statement. There are ways to mitigate this, but the problem is that you do have to know that the problem exists before you can take the necessary steps. Implementing a resource as an object does not make it difficult to abuse. It makes it easy to abuse.
The using statement ensures that Dispose is called even if an exception propagates from the embedded-statement. However, little is said about what happens if Dispose then throws another exception. This is all too likely in many common cases. What actually happens is that the CLR discards the first exception, so all information about the original cause is lost.

So the IDisposable/using technique doesn’t exactly call out to the user to employ it correctly. There are various ways to use it wrongly, and the exception problem is especially irritating. Nevertheless it is possible to use it correctly with a wide range of resources. Because it follows the program stack as it grows and shrinks, it obeys the rules of stack-like resources. Because it is deterministic, it is able to provide the predictable immediate Exit necessary when handling non-fungible resources.

The Cultural Problem with IDisposable

But these mere technical problems are minor compared with the cultural problem that exists around this technique. These are caused by copious amounts of official or semi-official documentation which confuse it with finalizers, in apparent denial of their different areas of applicability. For example, in this article we are shown the “basic IDisposable pattern” and sure enough, it has a finalizer as well. In such articles IDisposable is described as a safety feature to be added to any class that has a finalizer, when in fact it is a general mechanism for hooking into the program stack unwinding process via objects, built on top of the more fundamental try/finally mechanism.

The logical fallacy that results is like Woody Allen’s conclusion that “All men are Socrates”. The advice, if read carefully, is merely that all finalizable classes should also implement IDisposable. But the idea people frequently come away with is that any class that implements IDisposable should also have a finalizer. They get it completely the wrong way around.

I’ve found it almost impossible to shift this two-way link from many people’s minds, so much so that it is often controversial to suggest managing a stack-like resource with IDisposable, because some people will insist that the resource must also have a finalizer “just in case the user forgets to call Dispose”. Of course, for a stack-like resource the finalizer will be no help at all. In fact it will be no use for any resource defined in terms of reference objects, because it is not safe to manipulate them from a finalizer.

This cultural problem doesn’t exist in C++/CLI, because there the existence of IDisposable is hidden behind the C++ language facility called a destructor. A typical C++/CLI program would have lots of classes that implement IDisposable without the programmer giving it a second thought, and none of them would have finalizers. In C++, destructors are quite often used to manage stack-like resources, which in C++/CLI automatically translates into IDisposable being employed for that same purpose. This is due mostly to Herb Sutter, whose annotations here are particularly illuminating.

Gateways

The cultural problems around IDisposable prompted me to look for an alternative, and happily I’ve found one that is applicable in a lot of cases. I already described it in a previous blog post, although there I merely extolled its virtue of being more expressive than the using statement.

But I mostly glossed over its other technical advantages. First and foremost is the way it is extremely difficult to abuse. Providing access to a resource only through the gateway of a function is practically impossible to get wrong. You can’t forget to put in the using statement, because you don’t need one. Nor can you call the Dispose method of nested stack-like resources in the wrong order, because no such method is exposed to you.

For some kinds of resource, it is not necessary or desirable to force them to exit when an exception occurs. The reason for this is that you would expect an exception to abort the whole operation in which the resource is relevant. An example is the TraceWriter class that I included in the source code of this post. It includes this gateway method:

public void Indented(Action whileIndented)
{
    WriteLine("{");
    _indent++;
    whileIndented();
    _indent--;
    WriteLine("}");
}

This allows me to write very readable code:

writer.WriteLine("string comparison:");
writer.Indented(() =>
    {
        writer.WriteLine(leftValue);
        writer.WriteLine(rightValue);
        writer.WriteLine(new String(' ', index)
                         + "^ difference at index " + index);
    });

It is absolutely impossible for me to forget to un-indent after I’ve indented, thanks to the use of a gateway function to control the use of the indenting “resource”. However, I’ve made the Indented method completely ignore exceptions, because in this program, if an exception occurs during the logging process, I expect the whole log file to be abandoned anyway. Had this not been the case, I would have use try/finally within Indented.

Only by writing our own gateway functions can we make the right choice for each case.

This works for all kinds of resources, of course. It is not only free from the cultural/educational baggage surrounding IDisposable, but it also does a better job technically, giving us control over the handling of exceptions and protecting us from accidental abuses.

So in summary: where resource-like patterns of state occur in your own programs, I recommend where possible making little gateway functions to provide access to those states, instead encapsulating the resource in an IDisposable class.

Displaying a nested evaluation tree from Expression>

2009-02-13T10:25:00.002Z

Updated: The downloadable source (see link below) is now tidied up a bit, and also displays any embedded string comparisons in a similar way to NUnit.

This might be useful as a way to write Assert statements in tests. Instead of requiring many different forms of Assert to capture values and intents, we could just have one Assert that accepts a lambda:

public static void Assert(Expression<Func<bool>> expr)
{
    if (!(bool)Trace(expr.Body, 0))
    {
        // throw an exception...
    }
}

Now all we need is a Trace function. The challenge is making it include all the relevant information about the test, including the values being used. But this isn't actually that hard, because you just recursively search through the tree of nested expressions, evaluating them all:

public static object Trace(Expression part, int indent)
{
    string indentString = new String(' ', indent*2);

    Console.Write(indentString);
    Console.Write(GetExpressionText(part));
    Console.Write(" == ");
    LambdaExpression lambda = Expression.Lambda(part);
    Delegate callable = lambda.Compile();
    object result = callable.DynamicInvoke(null);

    if (result is string)
        result = "\"" + result + "\"";

    Console.Write(result);

    var nestedExpressions = part
        .GetType()
        .GetProperties()
        .Where(p => typeof(Expression).IsAssignableFrom(p.PropertyType))
        .Select(p => (Expression)p.GetValue(part, null))
        .Where(x => (x != null) && !(x is ConstantExpression));

    if (nestedExpressions.Any())
    {
        Console.WriteLine(" where");
        Console.Write(indentString);
        Console.WriteLine("{");

        foreach (Expression nested in nestedExpressions)
            Trace(nested, indent + 1);

        Console.Write(indentString);
        Console.WriteLine("}");
    }
    else
        Console.WriteLine();

    return result;
}

I just use reflection and a bit of LINQ to hunt for nested expressions, so I don't need to laboriously handle the various kinds of expression.

I don't bother presenting the value of constants, because it would just explain to the user that 5 == 5, which isn't very enlightening.

The GetExpressionText function is a helper to tidy up the output. Variables captured in the lambda have some nasty looking prefix to identify which compiler-generated class they belong to, but that's unlikely to be useful here, so I strip it out:

public static string GetExpressionText(Expression expr)
{
    string text = expr.ToString();

    const string prefix = "value(";
    const string suffix = ").";

    StringBuilder builder = new StringBuilder();

    int start = 0;
    int pos = text.IndexOf(prefix);
    while (pos != -1)
    {
        builder.Append(text.Substring(start, pos - start));
        start = text.IndexOf(suffix, pos) + suffix.Length;
        pos = text.IndexOf(prefix, start);
    }

    if (start < text.Length)
        builder.Append(text.Substring(start, text.Length - start));

    return builder.ToString();
}

And now for a little demo:

int x = 3;
string t = "hi";
Assert(() => 5*x + (2 / t.Length) < 99);

Which produces the remarkably readable output:

(((5 * x) + (2 / t.Length)) < 99) == True where
{
  ((5 * x) + (2 / t.Length)) == 16 where
  {
    (5 * x) == 15 where
    {
      x == 3
    }
    (2 / t.Length) == 1 where
    {
      t.Length == 2 where
      {
        t == "hi"
      }
    }
  }
}

Obviously not a hugely strenuous test, but I suspect any other edge cases could easily be dealt with.

The way I've written Assert is just for demo purposes, because I wanted to see the trace regardless of whether the test passes or fails. In a real framework you'd only print out the trace if the test failed. Apart from making the successful output as short as possible (silence is golden) it would also help your tests run faster.

Download full source here: http://www.earwicker.com/blogfiles/ExpressionTracer.zip

A functional replacement for the using statement

2009-02-08T18:51:00.002Z

The using-statement is just that: a statement. Why does this bug me?

The FileStream object has a Length property. Assuming I have a function Open that returns a FileStream ready for us, it is awfully tempting to do this:

     Console.WriteLine(Open().Length);
  

But that is wrong, wrong, wrong, because it postpones the closing of the file handle until the finalization thread gets around to it. No good.

To obtain a value from a disposable object after that object is disposed, you have to store it in a variable declared outside the using-statement, like this:

    long length;

    using (FileStream file = Open())

        length = file.Length;

    Console.WriteLine(length);

Not very nice. But how about this?

    Console.WriteLine(Open().Use(file => file.Length));
  

Only a little uglier than the wrong version, but a whole lot righter. The Use extension method executes the function passed to it, and returns whatever that function returns, but also disposes of the object it was called on:

    public static class DisposableExtensions

    {

        public static TResult Use<TArg, TResult>(

            this TArg arg, Func<TArg, TResult> usage)

            where TArg : IDisposable

        {

            try

            {

                return usage(arg);

            }

            finally

            {

                arg.Dispose();

            }

        }

    }

Of course, this technique allows us to do something very similar even when we aren’t dealing with objects that implement IDisposable. What we are really doing here is putting the system into some temporary state, then computing something, then undoing that temporary state change. That’s all a “resource” really is: some state the system gets into that you’ll need to back out of soon. The definition of “soon” varies; for memory allocation, we can be pretty lax, because we have enough memory to support a very large number of small allocations simultaneously, but we can only support a single exclusive file handle on a given file, so we have to be extremely careful.

So a resource is two bits of code: get-into-state and get-out-of-state. Suppose I have a really simple kind of “lock”. I actually support any number of simultaneous locks, but I want to know how many are held at any given time. So my “lock” is just an integer field in my class. To take out a lock, increment it, and to release the lock, decrement it:

    public class Lockable

    {

        private int _lockCount;

        public int OpenLocks

        {

            get { return _lockCount; }

        }

        public void Lock()

        {

            _lockCount++;

        }

        public void Unlock()

        {

            _lockCount--;

        }

    }

How can I help users of my class to ensure they don’t forget to release the lock in a timely fashion?

If you understood the definition of a “resource” I gave above, you’ll have realised that the resource in this case is not the class itself, but a state in which there has been a call to Lock without a corresponding Unlock call. So if the value of _lockCount happens to be 63, then there are 63 resources alive in our program, and we want them to be cleaned up at some point.

So the object-oriented (which doesn’t necessarily mean “good”) way to expose this is to reify our resource, by giving it a class of its own:

    public class Lock : IDisposable

    {

        private readonly Lockable _res;

        public Lock(Lockable res)

        {

            _res = res;

            _res.Lock();

        }

        public void Dispose()

        {

            _res.Unlock();

        }

    }

Now the users of MyResource can employ the using-statement to call Dispose for them, which takes care of calling Unlock.

    Lockable mr = new Lockable();

    int locks;

    using (new Lock(mr))

        locks = mr.OpenLocks;

    Console.WriteLine(locks);

Fair enough, but as we saw above, that makes it ugly when we just want to write an expression that computes a value while the lock is held. Yes, we could use my Use extension method:

    Console.WriteLine(new Lock(mr).Use(l => mr.OpenLocks));
  

But why not cut out the middleman altogether?

    public class Lockable

    {

        private int _lockCount;

        public int OpenLocks

        {

            get { return _lockCount; }

        }

        public T WithinLock<T>(Func<T> f)

        {

            _lockCount++;

            try

            {

                return f();

            }

            finally

            {

                _lockCount--;

            }

        }

    }

We get rid of the public Lock/Unlock so there’s no way to break the rules, and instead provide a way to conveniently get a parameterless lambda executed inside a lock, guaranteeing that the lock will be released when the computation finishes:

    Console.WriteLine(mr.WithinLock(() => mr.OpenLocks));
  

This addresses a very common complaint about IDisposable, which is that the user has to remember to call Dispose, or else they have to remember to use a using-statement, and it is very easy to forget. With the above alternative technique, the user is not given the ability to forget.

I call such methods "Gateways", although in Java this is called the Execute Around idiom, and it is also exemplified by Common Lisp macros that start with the prefix with-, such as with-open-file.

Of course, there is a minor downside. C# has the error: “Cannot use void as a type argument”. So you have to write a second version of WithinLock that returns void and accepts an Action as its parameter, of which more in my next post.

Further Muddying the ForEach Waters

2009-02-03T15:02:00.002Z

ForEach is regularly proposed as a missing feature in the BCL but has been rejected in the past apparently because it wouldn't be "functional" enough, doesn't return anything so calls cannot be chained together in a LINQ-like pipeline, and so on. So here's a different approach that is undeniably functional, and does support chaining together.

public static IEnumerable<Action> ForEach<T>(this IEnumerable<T> source, 
                                             Action<T> action)
{
    foreach (T item in source)
    {
        T captured = item;
        yield return () => action(captured);
    }
}

That extension method turns a list of items of any type into a list of actions, by binding a dedicated action to each item. The resulting list can then be operated on further - e.g. interleaved with other lists, reversed, counted, and so on.

Another useful operation is a specialised form of Aggregate that turns a list of actions into a single action. The CLR already has an efficient representation of this: a multicast delegate, so that's what I prepare and return:

public static Action Aggregate(this IEnumerable<Action> actions)
{
    Action del = null;

    foreach (Action action in actions)
        del += action;

    return del;
}

So now I can write things like:

int[] arr = { 3, 1, 4 };

Action act = arr.ForEach(Console.WriteLine)
            .Concat(arr.ForEach(Console.WriteLine).Reverse())
            .Aggregate();

act();

(Oh, how much clearer that would look with operator overloading through extension methods, using + to concatenate the lists, but I digress...)

Which prints:

So the bound actions generated from the lists can be chained, reversed, rechained, signed in triplicate and finally buried for three months and then recycled as firelighters.

By the way, the feedback from MS on the plain ForEach suggestion is baffling in any case. They don't want to support stateful, imperative programming? Then they need to remove quite a lot of existing features from the language, such as assignment! By all means support functional programming smoothly with C# (a brilliant strategy) but don't get confused into thinking that you're maintaining F#. The whole point of C# is to be the number 1 language for building and using libraries in the CLR, and such libraries are expressed through components that are, for better or worse, brimming with mutable state.

Meanwhile, you can add features for specifying whether a given data structure is mutable or not, and this will take control of naughty mutation far more effectively than merely failing to add frequently useful features to the BCL.

Using Collection Initializers with Immutable Lists

2009-01-29T13:42:00.002Z

The Incomparable Mr Skeet mentions how irksome it is that collection initializers assume that the collection is mutable.

Suppose we defined an "immutable-yet-initializable collection" as any type that supports this interface:

public interface IImmutableCollection<TCollection, TItem> : IEnumerable<TItem>
       where TCollection : IImmutableCollection<TCollection, TItem>, new()
{
    TCollection Add(TItem item);
}

In other words, it can be enumerated, it can be default-constructed (to get an empty list) and it has an Add method that returns a new list with the item added to it.

And suppose our simple demo implementation of that is as follows:

public class SimpleImmutableList<TItem> : 
             IImmutableCollection<SimpleImmutableList<TItem>, TItem>
{
    private SimpleImmutableList<TItem> _next;

    private TItem _head;

    public SimpleImmutableList<TItem> Add(TItem item)
    {
        return new SimpleImmutableList<TItem>
                   {
                       _next = this,
                       _head = item
                   };
    }

    public IEnumerator<TItem> GetEnumerator()
    {
        for (SimpleImmutableList<TItem> i = this; 
             i._next != null; i = i._next)
            yield return i._head;
    }

    System.Collections.IEnumerator 
           System.Collections.IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

Not very sophisticated, doesn't attempt to solve the well-known "OMG! my list is backward" problem. But anyway. Our problem is that we want this delightful experience:

List<string> mutableList = 
        new List<string>
                   {
                       "First",
                       "Second",
                       "Third"
                   };
Debug.Assert(mutableList.Count() == 3);
Debug.Assert(mutableList.ElementAt(2) == "Third");

Except that we want to make a SimpleImmutableList<string> instead of a List<string>. Well, we can get pretty close:

SimpleImmutableList<string> immutableList = 
        new Initializer<SimpleImmutableList<string>, string>
                    {
                        "First",
                        "Second",
                        "Third"
                    }.Result;
Debug.Assert(immutableList.Count() == 3);
Debug.Assert(immutableList.ElementAt(2) == "First"); // OMG! etc

I've picked out in red ink the extra noise we have to add, but it's not that bad. The enabling thing is that Initializer class:

public class Initializer<TCollection, TItem>  : IEnumerable<TItem>
       where TCollection : IImmutableCollection<TCollection, TItem>, 
                           new()
{
    public Initializer()
    {
        Result = new TCollection();
    }

    public void Add(TItem item)
    {
        Result = Result.Add(item);
    }

    public TCollection Result { get; private set; }

    public IEnumerator<TItem> GetEnumerator()
    {
        return Result.GetEnumerator();
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return Result.GetEnumerator();
    }
}

So if anyone tells you that it is impossible to initialize an immutable collection with a collection initializer, tell them about the time you met a crazy old man with some wild ideas about an Initializer class, and see what they say¹.

1. "Get out of my house".

Linq to C++0x

2009-01-26T18:18:00.002Z

Updated 2009-01-28 - completely different approach to get a fluent interface.

Updated 2009-05-22 - See new post with decltype goodness!

C++ has long had some functional-styled things in its standard library, in particular a header file called <functional>. But actually using it in a functional way has been painful, largely due to the lack of lambdas.

But C++0x (very good Wikipedia page, by the way) solves this, amongst many other long-standing problems.

With lambdas in place, the next thing I naturally wonder is: what about a complete system of lazy-evaluated list processing, which is to say: what about Linq to Objects in C++?

The C++ equivalent of IEnumerable<T> is a collection of T. Another good thing in C++0x is concepts, which allows us to state for the first time precisely what we mean by a collection in C++. I don't yet have a compiler that supports concepts, so I'll just say that for the sake of argument, a collection is anything that has a nested type called const_iterator and two const methods called begin and end that return instances of that const_iterator type. (I'm using const iterators because I want to support functional style programming, and support for immutability is one area where C++ still leaves C# in the dust).

The iterator is the equivalent of IEnumerator<T>, and must have an * operator so we can retrieve the current item, and a ++ operator so we can navigate to the next item. We discover if we're at the end by comparing the iterator with the instance returned by end, so iterators must also have equality comparison.

Just as a minimal demonstration, I want to recreate the Select and Where extension methods. They don't actually use any new C++0x features, but as we'll see, they become much more pleasant to use as a result of lambdas.

In order to share as much code as I can, I'll create a single new container-like class template called filter, which simulates a container by borrowing the contents of another container. It will have built-in features to support skipping over some elements, and to transform elements to new values (not necessarily of the same type).

Because of this approach, I'll need a way to switch off these features when I don't need them. When deciding whether to skip over an element, we will use a predicate, which is a function that takes some value and returns a bool. To switch off that feature, we'd simply pass a predicate that always returns true:

template <class T>
struct always_true
{
    bool operator() (const T &) const { return true; }
};

Similarly to switch off element transformation we need a function that just passes through whatever it is given:

template <class T>
struct pass_thru
{
    T operator() (const T &e) const { return e; }
};

I could of course re-write these simple functions as lambdas wherever I need them, but as I need them in a couple of places it makes sense to name them in the traditional way.

And now here's the filter class template.

template <class TElemFrom, 
          class TElemTo, 
          class TIterFrom, 
          class TSelector,
          class TPredicate>
class filter
{
    TIterFrom from_;
    TIterFrom end_;
    const TSelector &selector_;
    const TPredicate &predicate_;

public:
    filter(TIterFrom from, TIterFrom end, 
             const TSelector &selector, 
             const TPredicate &predicate)
        : from_(from), end_(end), 
          selector_(selector), 
          predicate_(predicate) {}

    class const_iterator
    {
        TIterFrom from_;
        TIterFrom end_;
        const TSelector &selector_;
        const TPredicate &predicate_;

        void locate()
        {
            while (!done())
            {
                if (predicate_(*from_))
                    return;

                ++from_;
            }
        }

        bool done() const { return (from_ == end_); }

    public:
        const_iterator(TIterFrom from, TIterFrom end, 
                       const TSelector &selector,
                       const TPredicate &predicate)
            : from_(from), end_(end), 
              selector_(selector),
              predicate_(predicate) { locate(); }

        TElemTo operator*() const { return selector_(*from_); }

        const_iterator operator++()
        {
            ++from_;
            locate();
            return *this;
        }

        bool operator==(const const_iterator &other) const
            { return done() && other.done(); }

        bool operator!=(const const_iterator &other) const
            { return !done() || !other.done(); }
    };

    typedef TElemFrom value_type;

    const_iterator begin() const 
        { return const_iterator(from_, end_, selector_, predicate_); }

    const_iterator end() const 
        { return const_iterator(end_, end_, selector_, predicate_); }

    template <class TElemTo2, class TSelector>
    filter<TElemTo, 
             TElemTo2,
             const_iterator, 
             TSelector,
             always_true<TElemTo> >
        select(const TSelector &selector)
    {
        return filter<TElemTo, 
                        TElemTo2, 
                        const_iterator, 
                        TSelector, 
                        always_true<TElemTo> >
                    (begin(), 
                     end(), 
                     selector, 
                     always_true<TElemTo>());
    }

    template <class TPredicate>
    filter<TElemTo, 
              TElemTo,
             const_iterator, 
             pass_thru<TElemTo>, 
             TPredicate> 
        where(const TPredicate &predicate)
    {
        return filter<TElemTo, 
                        TElemTo,
                        const_iterator, 
                        pass_thru<TElemTo>, 
                        TPredicate>
                    (begin(),
                     end(),
                     pass_thru<TElemTo>(), 
                     predicate);
    }
};

All the real work is done by the nested const_iterator class, which performs skipping using the predicate in the ++ operator and performs transformation using the 'selector' in the * operator.

It's quite an unwieldy class to construct, what with all those type parameters and actual parameters, but we can make it much easier by providing a free function called from:

template <class TCollFrom>
filter<typename TCollFrom::value_type, 
         typename TCollFrom::value_type,
         typename TCollFrom::const_iterator, 
         pass_thru<typename TCollFrom::value_type>,
         always_true<typename TCollFrom::value_type> >
    from(const TCollFrom &from)
{
    return filter<typename TCollFrom::value_type, 
                    typename TCollFrom::value_type, 
                    typename TCollFrom::const_iterator, 
                    pass_thru<typename TCollFrom::value_type>, 
                    always_true<typename TCollFrom::value_type> >
                (from.begin(), 
                 from.end(), 
                 pass_thru<typename TCollFrom::value_type>(), 
                 always_true<typename TCollFrom::value_type>());
}

This does nothing much apart from wrapping a real container inside an instance of filter, and switching off all filtering or transformation, so we can then call the where or select members. As those members also return instances of filter, this gives us a convenient "fluent interface". Those concerned about performance should be reassured that the compiler ought to be able to inline away all of this syntactical plumbing when it sees the trivial definitions of pass_thru and always_true.

For example, filter a list of integers and turn them into quoted strings:

std::vector<int> vecInts;
vecInts.push_back(5);
vecInts.push_back(2);
vecInts.push_back(9);

auto filtered = from(vecInts)
    .where([] (int n) { return n > 3; })
    .select<std::string>([] (int n)
        { return "\"" + 
                 boost::lexical_cast<std::string>(n) + 
                 "\""; });

for (auto i = filtered.begin(); i != filtered.end(); ++i)
    std::cout << *i << std::endl;

And that prints:

"5"
"9"

How is this select function different to std::transform? Because it is evaluated lazily. None of the work is done until we are in the final for loop, and I could break out of that early if I wanted to.

The one irritation is the fact that I have to tell select what the output value type will be, even though the compiler can lambda deduce it from the lambda in this case. Why can't the compiler join up the dots for us? In fact, in a full implementation of C++0x, it could, but I don't yet have access to such a compiler. Here's how I believe it would work.

First, we need the decltype keyword, which yields the compile-time type of any expression. Suppose we have something function-like of type TSelector, and we want to know what it would return when called. We also happen to know that it takes one parameter of type TElemTo (because we're taking the output of the previous filter).

So we need an instance of TSelector:

TSelector()

And then on that, we need to call it, passing it an instance of TElemTo:

TSelector()(TElemTo())

And then we want the type of that expression:

decltype(TSelector()(TElemTo()))

Hey presto, we might think: this can replace the TElemTo2 type parameter, so callers would no longer need to write select<std::string>.

But I suspect this won't work, because it's very likely that TSelector will not be default-constructible (if it is a lambda that captures by reference, for example). The trick in such situations is a make_ptr function:

template <class T>
T *make_ptr() { return (T *)0; }

It actually returns a NULL pointer of the specified type. We can then define a make_ref that turns that into a reference, and our expression becomes:

decltype(make_ref<TSelector>()(make_ref<TElemTo>()))

Of course, if that particular operation was ever executed, it would result in major crash-ola. But it never will be executed; decltype doesn't execute the expression, it just figures out the resulting type.

Then we can get rid of TElemTo2, and our example call looks like this:

auto filtered = from(vecInts)
    .where([] (int n) { return n > 3; })
    .select([] (int n) { return "\"" + 
                         boost::lexical_cast<std::string>(n) + 
                         "\""; });

I hope decltype makes it into MSVC++ version 16.

Ora Stories

2008-12-16T16:33:00.002Z

I've written an add-in for Visual Studio called Ora. You can read more about it via that link but here's some background to it.

It's designed to replace a common use of regions - though I'd call it a common abuse of regions - so it's called Ora, which means a bunch of things in various languages, but can mean region in Latin.

Regions are a feature of C# that generate some controversy, inevitably known as the region wars. Sample posts:

I think regions mostly suck, at least in the way they are commonly used. They're a form of comment, so they should come with the same warning as comments:

Do not redundantly replicate in a comment any information that is clearly stated in the code itself.

With this advice in mind, and applying it consistently to regions as well, it would make little sense to put a region called Private Static Methods around all your private static methods - it's already perfectly obvious what they are. It says so completely unambiguously in the code. But of course, one day someone will decide that one of the methods should be public - at which point they either have to remember to physically move the method out of that region, or else the region is no longer correct (which is the ultimate fate of all redundant comments).

So it's almost distressing to see advice like this being handed out:

I've seen class templates, intended to be used by anyone who is starting a new class, which come ready stocked with over a dozen regions called Private Fields, Static Public Properties, and so on. Suddenly, instead of writing elegant self-descriptive code, you're filling in a tax form. And when you've captured a simple concept in a class with only a few members, it will contain a dozen empty regions, just in case someone one day wants to put things in it that don't belong in it.

The only justification I know of for this is that it helps anyone reading the code to navigate it. But as a solution, regions are utterly unworkable, so let's state the actual problem clearly:

A reader of the code needs to see a simple overview of a class, in which the members have been grouped in various helpful ways, so they can navigate to a member in the source code by clicking on its name in the overview.

So what they need is something that automatically builds such an overview on the fly, directly from the code under the cursor. This is the purpose of Ora, my add-in for Visual Studio.

The Maybe Monad in C#

2008-12-11T17:40:00.002Z

The Maybe Monad is extremely simple. It represents a value that might be there, but might not, and also provides a neat way of working with such values.

This Haskell-related page makes it pretty clear:

The Maybe monad embodies the strategy of combining a chain of computations that may each return Nothing by ending the chain early if any step produces Nothing as output. It is useful when a computation entails a sequence of steps that depend on one another, and in which some steps may fail to return a value.

Change Nothing to null and we're talking in C#. Furthermore, it advises:

If you ever find yourself writing code like this:
case ... of
  Nothing -> Nothing
  Just x  -> case ... of
               Nothing -> Nothing
               Just y  -> ...
you should consider using the monadic properties of Maybe to improve the code.

Again, translating into C#, we're talking about code like this:

    public static Role GetRole(string urlString)

    {

        string[] url = SplitUrl(urlString);

        RecordCompany company = Music.GetCompany("4ad.com");

        if (company != null)

        {

            Band band = company.GetBand("Pixies");

            if (band != null)

            {

                Member member = band.GetMember("David");

                if (member != null)

                    return member.Role;

            }

        }

        return null;

    }

As we navigate our way through a graph of objects, we repeatedly have to check whether the road is blocked by a null. When a situation like this occurs inside our nice tidy Linq expression, it makes it look really ugly.

But how can we improve on this in C#?

Firstly, we should be clear that a reference variable (such as company in the above code) is ideally suited for representing the Maybe monad. Any class type can be "stored" in a reference, otherwise that reference has the special value null. So don't be misled by the example on this page; it's correct (it's a great article) but it might make you think that we need to define a special new class to make a monad. In this case, as long as we're referring to class types (rather than unboxed value types), we don't need to.

What we're observing is that reference types already have one of the operations required by a monad: a Unit function. By simply assigning a new object to a reference variable, you are storing that object in a location that might have been null before you assigned to it, and may become null again later on. So assignment to the reference variable is the Unit function for our monad; it's built into the language.

That's all very well, but what are we actually trying to achieve? Going by the Haskell description, it's as if we'd like to be able to casually write a chunk of code like this:

    RecordCompany company = Music.GetCompany("4ad.com");

    Band band = company.GetBand("Pixies");

    Member member = band.GetMember("David");

    return member.Role;

If any of those operations returned null, then the return value of the whole thing would be null. But of course we don't always want C# to apply that rule, and how would the compiler figure out when to stop treating a chain of operations in this special way?

What we're missing from our monad is a Bind function:

    public static TOut IfNotNull<TIn, TOut>(

        this TIn v, Func<TIn, TOut> f) where TIn : class 

                                       where TOut: class

    {

        if (v == null)

            return null;

        return f(v);

    }

The type parameters in this generic function constrain us to dealing with class types, so what we have here is an extension method that applies to any reference variable (weird distinction: it makes more sense to think of extension methods applying to the reference variable than to the object stored in the variable, because it's perfectly okay to call an extension method on a null reference variable).

This extension method takes a function that "transitions" from one object to another. They don't have to be the same type. To see the point of all this, let's see how our ugly code looks if we rewrite it:

    return Music.GetCompany("4ad.com")

                .IfNotNull(company => company.GetBand("Pixies"))

                .IfNotNull(band => band.GetMember("David"))

                .IfNotNull(member => member.Role);

Now it's all just one expression! Cool!

(If you're wondering why is this important, there are lots of reasons, but here's one to start you off. The original version of the code was a sequence of statements, so it couldn't be represented by an expression tree, whereas the new version can be.)

So why is IfNotNull a good Bind function? It's not immediately obvious that it is, because a Bind function talks to its caller in terms of values wrapped in the monad, but deals in "naked" values with the function passed to it. But IfNotNull uses ordinary reference variables in both situations.

This is because there is a feature missing from C#. It ought to be possible to somehow tag a reference variable to say that it is definitely not null.

Response to comment from Marcel:

The : (colon) operator sounds good, but I'd argue that it's a little inflexible. It's a member access operator, like an alternative to the . (dot) so it works for the example I've given here. But what if the way I'd like to transition to the next object in the chain is by passing the current object as a parameter to some function? For example, look up the next object in a Dictionary with TryGetValue, using the current object as a key. With IfNotNull, the non-null object is given a named reference so I can do whatever I want with it.

As for verbosity, what I'd really like here is the ability to write what might be called extension operators, something Microsoft has considered but unfortunately isn't planning to implement anytime soon. These are like a cross between extension methods and operator overloads. This SO question pretty much covers the idea.

If that was possible, we could change IfNotNull to a binary operator such as | (pipe), allowing us to pipe values between lambdas like this:

    return Music.GetCompany("4ad.com")

            | company => company.GetBand("Pixies")

            | band => band.GetMember("David")

            | member => member.Role;

I think that would be just about perfect.

Optimizing Aggregate for String Concatenation

2008-12-10T11:01:00.002Z

Linq lets you think in a very generally applicable way and solve a very wide variety of problems with a few key concepts. That’s a great thing. But it’s irritating when the elegant solution doesn’t perform as well as an ugly special case.

Using a combination of well-known Linq features I’m going to demonstrate that we already have the power to get the best of both worlds: speed and elegance.

One example that has always irked me (and which is simple enough to demonstrate the idea with) is this:

     Enumerable.Range(0, size) 

              .Select(n => n.ToString())

              .Aggregate((a, b) => a + ", " + b);

It’s got all the attributes of a beautiful Linq-style solution – a single expression that produces the thing we want, using very general operations that are parameterized by self-contained functions.

But if size gets large, it’s dreadfully slow. The reason is that Aggregate takes the first two items, uses the function to combine them, then you can kind of imagine it putting the result back on the start of the list to replace the original two items. So each time it does that, the list shrinks, until eventually there’s only one item left, which it returns. All very logical and beautiful – the items on the list are from a set and we have defined a closed binary operation on them, so I guess it’s a magma.

But that first item is an ever-growing string, and each time around it has to be copied into a new string. This is a recipe for disastrous performance. To get faster performance, we need to use a different function, which I’ll call Oggregate:

    public static string Oggregate(this IEnumerable<string> source, string delimiter)

    {

        StringBuilder builder = new StringBuilder();

        builder.Append(source.First());

        foreach (string s in source.Skip(1))

        {

            builder.Append(delimiter);

            builder.Append(s);

        }

        return builder.ToString();

    }

But this is irksome, because you have to know when to use this optimized version, and then you have to know how to modify your original code. You can’t just flick the “go faster” switch.

A good programming language defines general concepts that compose (go together) well. A good compiler then takes programs written in that language and does terrifying things to them, without telling you, so that they still do what you asked, but they do it fast. The compiler does this by spotting patterns and saying “Ah, I see what you’re trying to do. I know a faster way to do that.” You don’t have to explicitly tell it to do it the fast way. It just notices the pattern and makes the smart decision. Such capabilities are called compiler optimizations. They’re “turnkey” solutions, in the sense that all you have to do is turn the key and they start up. You don’t typically have to think too hard about it. Somebody already did that for you.

So my ideal solution for the above problem would be for the compiler (or a library) to notice the pattern I’m using and use the StringBuilder approach instead. If I’m not using that pattern, it should fall back to doing what it usually does.

I can’t change the compiler, so can I write a library? The problems facing us are three fold:

We want to replace the standard library’s version of an algorithm that can operate on any sequence.
We only want to do that for sequences of strings.
We only want to do it if the function parameter has a very narrowly-defined shape.

Skipping the first one for now, the solution to the second problem is to write a version of Aggregate for the special case of string sequences. The solution to the third is clearly going to involve Linq expressions, as they give us a way to examine the structure of simple expression-like functions, and also to apply such a function to some parameters if necessary:

    public static string Aggregate(this IEnumerable<string> source, 

                     Expression<Func<string, string, string>> func)

    {

        ... look at the func to decide what to do

Having defined such a function in some namespace, what happens if we add a using directive at the top of the source file where we want to use it? That’s no good, because the compiler has two choices for which function to use. In C++, the thing we’ve written is a kind of “template specialization”, and the rules for template resolution in C++ usually mean that the most specialized choice is the one that the compiler picks. But this isn’t the case in C#. The compiler just gives up and says that we’re being ambiguous.

But if we put our using directive inside a namespace block, then the C# compiler is happy to assume that it should select our version of Aggregate:

    using System;

    using System.Linq;

    using System.Diagnostics;

    namespace ConsoleApplication5

    {

        using Optimizations.AggregateStringBuilder;

        class Program

        {

            static void Main(string[] args)

            {

The location of the using directive affects the overload resolution priority assigned to the functions in that namespace. So we can switch on our optimisation at the level of a namespace block. I’m satisfied with that – it constitutes an on/off switch, for my purposes.

Here’s what the Aggregate function looks like:

    public static string Aggregate(this IEnumerable<string> source, 

                            Expression<Func<string, string, string>> func)

    {

        BinaryExpression root = func.Body as BinaryExpression;

        if (root != null)

        {

            if (root.NodeType == ExpressionType.Add)

            {

                BinaryExpression left = root.Left as BinaryExpression;

                if (left != null)

                {

                    if (left.NodeType == ExpressionType.Add)

                    {

                        ParameterExpression leftLeft = 

                            left.Left as ParameterExpression;

                        if (leftLeft != null)

                        {

                            ConstantExpression leftRight = 

                                left.Right as ConstantExpression;

                            if (leftRight != null)

                            {

                                ParameterExpression right = 

                                    root.Right as ParameterExpression;

                                if (right != null)

                                {

                                    if ((leftLeft.Name == func.Parameters[0].Name) 

                                      && (right.Name == func.Parameters[1].Name))

                                        return source.Oggregate(

                                            (string)leftRight.Value);

                                }

                            }

                        }

                    }

                }

            }

        }

        return source.Aggregate(func.Compile());

    }

In other words, it looks pretty ugly. But that’s optimizations for you. It really just looks at the lambda to see if it fits a very rigid pattern: (a + c) + b, where a and b are the parameters to the lambda and c is a constant. If so, it calls Oggregate. Otherwise, it falls back to letting the compiler run the lambda as it usually would. A compiled delegate doesn’t match our Expression<T> argument, so the normal version of Aggregate is called.

This means that, where it’s an appropriate optimization, all it does is examine a few enum properties, perform a few casts, compare a couple of strings and then call Oggregate. So all the extra work (which is very minor) happens outside the loop.

The remaining question is, how badly does it hurt performance when it isn’t an appropriate optimization? As usual, it depends greatly on how you use it. If you’re using Aggregate to concatenate a small number of strings, the compilation step is wasteful to be sure. But again, it happens outside the loop. And in any case, if you find that your program runs slower, it’s just as easy to switch off the optimization as it is to switch it on.

So in conclusion, although this example is pretty simple and so not exactly earth-shattering in itself, it serves to demonstrate how C# gives us the tools to introduce our own turnkey optimizations for special cases of the very general algorithms available in Linq, which was a pleasant surprise for me.

I posted this as a quiz question on Stack Overflow. The reaction to the idea of someone posting a question as a quiz was quite mixed – the votes for the question went negative a few times before averaging out at zero. I think this is a good use of the site, because the end result is a question with an answer and some associated discussion to give more detailed background, alternative approaches, etc. I think it annoyed people who didn’t know the answer, because (as I would freely admit) part of the reward of using Stack Overflow is the ego-boost of handing out knowledge to those in need. If you meet someone who already knows the answer to their question, and then – even worse – you don’t know the answer, then it kind of spoils the fun for you (one guy in particular seemed quite upset). But the fact remains that such an exercise produces the same kind of valuable addition to the site.

Other Examples of Iterators and Async IO

2008-12-09T13:44:00.002Z

The idea of returning functions via yield return to simply asynchronous IO programming has a precedent in Microsoft's Concurrency and Coordination Runtime:

http://msdn.microsoft.com/en-us/library/bb648753.aspx

Although they are yielding interfaces, really they are yielding functions:

http://msdn.microsoft.com/en-us/library/microsoft.ccr.core.itask_members.aspx

The ITask interface has only one really important method: Execute, which means that really it's a function (a delegate in C# terms). I think the functional style makes the whole thing cleaner, but the point is that the idea was already in use in the Microsoft's CCR, perhaps as long ago as 2005 (although that's difficult to verify).

More on Jeffrey Richter’s AsyncEnumerator and Functional Programming

2008-12-06T23:34:00.002Z

If you do asynchronous programming (or have been put off it in the past by the complexity) and you haven’t already looked at this, then you really should:

http://msdn.microsoft.com/en-us/magazine/cc546608.aspx

I blogged yesterday about an idea for doing the same kind of thing but using lambdas to encapsulate the last remaining bit of complexity. Today I’ve applied the same idea, but with the goal of providing a thin layer that works along with Jeffrey Richter’s AsyncEnumerator class, essentially providing an optional new way of working with it. As I am not especially familiar with the asynchronous APIs, it would be especially stupid for me to try and reinvent the wheel instead of building on the work Jeffrey has already done.

I should point out that everything in this article is provided “as is”, but even more so than people usually mean by that phrase, because I haven’t even tried running any of this code (although it does compile, at least). I’ve merely attempted to analytically prove (by substitution and expansion) that it produces the equivalent of something that works.

These are just ideas. I don’t currently have a need for this facility in my own work, so I can’t afford to invest in testing it. I just got carried away with the implications of an idea today, and here are the results of that.

I’ll start by explaining the nuts and bolts. Using pure functional programming techniques, I’ve defined a handful of static functions, mostly extension methods on pre-existing types, making them very easy to discover and use. To begin with, I’ll leave out a detail to do with exception handling, and then add it in as an afterthought, as it makes things a little messier.

Jeffrey’s AsyncEnumerator class is effectively a consumer of a sequence of integers. The sequence is generated by a function that the user writes, taking advantage of the yield return keyword. They yield a count of 1 for each asynchronous operation that they start:

     stream.BeginWrite(outputData, 0, outputData.Length, ae.End(), null);

    yield return 1;

    stream.EndWrite(ae.DequeueAsyncResult());

In the above snippet (taken from Jeffrey’s TcpClient example), a single write is made. Characteristically, there are three steps:

Call a BeginXXX API to launch the asynchronous operation. Such operations always require a callback function, which is provided by calling AsyncEnumerator.End.
Yield the value 1 (because only one operation has been launched in this case).
Call an EndXXX API to finish the operation. The AsyncEnumerator.DequeueAsyncResult is used to obtain some data associated with results of the operation.

The integers so yielded are interpreted as requests to wait for that number of asynchronous operations to complete. So to do three operations in parallel, you would begin three asynchronous calls, and then yield return 3. When your function got back control, the three calls would all have completed. However, they may of course complete in any order, so when the results are dequeued some care may need to be taken in matching the results up with their corresponding EndXXX functions, because they may be of different types (e.g. a stream operation and a WebRequest).

Using Linq’s Select function, we can easily convert between sequence types. This means that we can provide a way for the user to write a function that yields a sequence of some other kind, such that it can still be plugged into AsyncEnumerator.

The elements of the new kind of sequence are called activities. Although most user need not be aware of this, they are in fact functions, defined by this delegate:

    public delegate int Activity(AsyncEnumerator asyncEnum);
  

An activity launches one or more asynchronous operations, and returns how many it has launched, making it perfect to fit AsyncEnumerator’s requirements. So we can easily convert a sequence of these activities into the kind of sequence that AsyncEnumerator likes to get:

    public static void Execute(this AsyncEnumerator asyncEnum, 

                                       IEnumerable<Activity> activities)

    {

        asyncEnum.Execute(activities.Select(activity => activity(asyncEnum))

                                    .GetEnumerator());

    }

In other words, we simply produce a sequence of integers by calling each activity in the input sequence. Then as a final step, get the IEnumerator<int> of the sequence and pass it to the intrinsic AsyncEnumerator.Execute function. By providing this as an extension method, it’s as convenient to use as its intrinsic cousin.

How can we compose a set of activities to make a single activity that causes all the activities in the set to execute in parallel? By defining a higher-order function that does it for us:

    public static Activity Parallel(params Activity[] list)

    {

        return asyncEnum => list.Sum(activity => activity(asyncEnum));

    }

Again, the implementation is trivial thanks to Linq. Our composite activity has to return the sum of the return values of the activities on the input list, so it’s the perfect fit for the Sum function, which adds together the values produced by a function executed for each item in a sequence.

Finally, we need a higher-order function to allow us to easily define an activity. This one’s a little more mind-bending, but still pretty short. Crucially, it is much easier to use than it is to fully understand, and even then most users do not need to use it directly.

    public static Activity Pair(Action<AsyncCallback> begin, AsyncCallback end)

    {

        return asyncEnum => // action accepts an AsyncEnumerator 

        {

            begin(result => // callback accepts a result

               {

                   end(result); // pass on to the user's handler

                   asyncEnum.End()(result); // and to AsyncEnumerator

                   asyncEnum.DequeueAsyncResult(); // we don't need this

               });

            return 1;

        };

    }

It pairs together two functions. The first one, begin, is responsible for launching the asynchronous call. To do this, it needs a callback function that it can pass to whatever asynchronous API it calls. The second one, end, will run when the call completes, and (as you will see if you look up the definition of the standard AsyncCallback delegate) accepts an IAsyncResult object.

So the Activity function returned by Pair will call the begin function, and pass it a function to serve as the callback for the asynchronous API. That function is defined by the inner lambda. It calls onto three things:

Firstly, the end function (whatever that may be) so that the result of the call can be interpreted.
Secondly, the callback supplied by AsyncEnumerator. This is crucial, as it ensures that the thread pool is asked to execute another step through of the sequence of integers.
Finally, the AsyncEnumerator.DequeAsyncResult function, although the result is discarded. This is because we have already passed the result to the end function. But we should still call this function once for each call that is made, so that the queue doesn’t needlessly grow in length.

That’s all we need as a basis. But for maximum convenience for most users, we can add extension methods for the most commonly used asynchronous call types. For example, writing to a stream:

    public static Activity RequestWrite(this Stream stream, byte[] buffer, 

                                        int offset, int size)

    {

        return Pair(

            callback => stream.BeginWrite(buffer, offset, size, callback, null),

            result => stream.EndWrite(result));

    }

This is a higher order function – it makes an Activity function, using the handy Pair function to tie together the two halves of the operation. But it can be called directly on a Stream object. If so called, it does not actually do anything; the return value must be passed on via yield return.

So how does code look using this whole technique? Let’s look back at that real example again. The function starts with this signature:

    private static IEnumerator<Int32> Process(AsyncEnumerator ae, 

                                              String server, 

                                              String message) 

    {

Then in the body of the function there are triplets of lines like this:

    stream.BeginWrite(outputData, 0, outputData.Length, ae.End(), null);

    yield return 1;

    stream.EndWrite(ae.DequeueAsyncResult());

By contrast, the alternative way of working enabled by these new functions begins by declaring the function like so:

    private static IEnumerable<Activity> Process(String server, 

                                                 String message)

    {

The first thing to note (aside from the obvious change to the return type) is that there is no need to pass in an AsyncEnumerator object, even though it interoperates with one automatically. The code to write to the stream looks like this:

    yield return stream.RequestWrite(outputData, 0, outputData.Length);
  

The triplet of lines has been boiled down to a single line, which appears just like a non-asynchronous call but with yield return in front of it.

Because the helper extensions are higher order functions, the user doesn’t need to even be aware that they’re using functional programming, or that an Activity is a function. They just make a method call that appears to do what they want, although they prefix it with yield return.

What about parallel activities running at the same time? Loosely inspired by another of Jeffrey’s examples, this function obtains results from two website simultaneously:

    private static IEnumerable<Activity> ProcessAllAndEachOps()

    {

       yield return Async.Parallel(

                WebRequest.Create("http://www.google.com").RequestResponse(true, response =>

                    Console.WriteLine("Bytes from Google: " + response.ContentLength)),

                WebRequest.Create("http://www.microsoft.com").RequestResponse(true, response =>

                    Console.WriteLine("Bytes from Microsoft" + response.ContentLength))

           );

       Console.WriteLine("All the operations completed.");

    }

The Parallel function we saw defined above takes care of composing a set of activities into a new activity that will launch all of them to run in parallel.

The end result appears so simple that it is worth going through an exercise of “expansion” to see how this alternative way of working must produce the same results as the original way. Hold onto your hats…

Here’s the nice and easy way it looks to the typical user:

    yield return stream.RequestWrite(outputData, 0, outputData.Length);
  

Let’s substitute in the definition of RequestWrite:

    yield return Async.Pair(

        callback => stream.BeginWrite(outputData, 0, outputData.Length, callback, null),

        result => stream.EndWrite(result));

Then the definition of Pair, in two stages to make it easy to follow. Firstly, keeping the definitions of begin and end separated out:

    yield return asyncEnum => // action accepts an AsyncEnumerator 

    {

        Action<AsyncCallback> begin =

                  callback => stream.BeginWrite(outputData, 0, 

                                outputData.Length, callback, null);

        AsyncCallback end = result => stream.EndWrite(result);

        begin(result => // callback accepts a result

        {

            end(result); // pass on to the user's handler

            asyncEnum.End()(result); // and to AsyncEnumerator

            asyncEnum.DequeueAsyncResult(); // we don't need this

        });

        return 1;

    };

Then finally substituting those definitions into their places:

    yield return asyncEnum => // action accepts an AsyncEnumerator 

    {

        stream.BeginWrite(outputData, 0, outputData.Length, 

            result => // callback accepts a result

            {

              stream.EndWrite(result); // pass on to the user's handler

              asyncEnum.End()(result); // and to AsyncEnumerator

              asyncEnum.DequeueAsyncResult(); // we don't need this

            }, null);

        return 1;

    };

Now we can see what’s really happening. The statement yields a function that calls BeginWrite on the stream and then returns 1. BeginWrite requires a callback, and we build one for it. In the normal way of using AsyncEnumerator as seen in Jeffrey’s example, the callback is provided by calling AsyncEnumerator.End, but here we effectively wrap that in a lambda so we can do other things as well. First we call EndWrite on the stream (which may throw an exception, but I’ll deal with that in a moment), then we call on to the callback returned by AsyncEnumerator.End, and finally we do the housekeeping of discarding one IAsyncResult instance from AsyncEnumerator’s internal inbox.

Then this whole function will be executed by the Execute extension method. Some more substitution will make this clearer. Here’s the expression we use to generate the kind of IEnumerable<int> that the intrinsic Execute method requires:

    activities.Select(activity => activity(asyncEnum))
  

So each activity is called in turn to produce integers, and the result is the same as if the return value of the activity was being yielded directly. In other words, continuing our expansion (now supposing we are in a function that is yielding integers having been passed the parameter asyncEnum):

    stream.BeginWrite(outputData, 0, outputData.Length,

        result => // callback accepts a result

        {

            stream.EndWrite(result); // pass on to the user's handler

            asyncEnum.End()(result); // and to AsyncEnumerator

            asyncEnum.DequeueAsyncResult(); // we don't need this

        }, null);

    yield return 1;

It is now clear what the only actual differences are. Compare with Jeffrey’s original code (I’ll repeat it here one more time to save you scrolling up and down the page).

    stream.BeginWrite(outputData, 0, outputData.Length, ae.End(), null);

    yield return 1;

    stream.EndWrite(ae.DequeueAsyncResult());

There, the End() callback causes the function to resume executing after the operation finishes, and the next line of code is the call to stream.EndWrite. Working the new way, stream.EndWrite is called from within the callback itself. It also has the correct IAsyncResult ready to use.

Also, immediately after calling the function returned by End(), the result is removed from the inbox by calling DequeAsyncResult. This places an additional thread-safety constraint on AsyncEnumerator, because previously it looks like the inbox is only accessed by one thread at a time. But by looking at the code of AsyncEnumerator in Reflector, I can see that it takes out a lock before accessing the queue, so this should be fine.

So what are the limitations of this new approach? The main one is the lack of flexibility in exception handling. With the original raw approach, you are free to place a try/catch around either the BeginXXX or EndXXX calls (although you can’t place one such handler around both calls, due to a limitation of the yield return implementation.)

In the new approach, the best we can do is to allow any exceptions to propagate out of the IEnumerator<int> sequence generator. In other words, if the BeginXXX or EndXXX calls throw an exception, then it is just as if they were to throw uncaught exceptions in the original approach.

To achieve this, we need to make a further change. The reason is that the EndXXX call is made in the context of a thread that is running due to the fact that an asynchronous call has completed. We do not control that thread. Rather than bothering it with an exception, we need to transfer the exception into the context of whichever thread is executing our function.

To achieve this, first we have to catch the exception. The user’s callback is executed in the inner lambda in Pair, so that’s where we need a try/catch block:

    public static Activity Pair(Action<AsyncCallback> begin, AsyncCallback end)

    {

        return asyncEnum => // action accepts an AsyncEnumerator 

        {

            begin(result => // callback accepts a result

            {

                try

                {

                    end(result); // pass on to the user's handler

                }

                catch (Exception e)

                {

                    asyncEnum.Cancel(e);

                }

                asyncEnum.End()(result); // and to AsyncEnumerator

                asyncEnum.DequeueAsyncResult(); // we don't need this

            });

            return 1;

        };

    }

Note that we make use of a handy feature of AsyncEnumerator where we stash the exception inside it by calling Cancel. We then continue as normal, calling on to AsyncEnumerator’s callback, which means that the iteration will resume. What does this mean?

It means that when iteration resumes, the first thing we need to check for the cancellation, retrieve the exception and throw it. Unfortunately, this means we need to mess up our nice simple Execute function. If you refer to where I defined it above, you’ll see that I originally used Select to do all the looping and yielding. But this doesn’t allow us to perform the exception check immediately after resuming from the yield return. We need to write out the equivalent of Select in “long hand” so we can insert the extra code:

    public static void Execute(this AsyncEnumerator asyncEnum, 

                               IEnumerable<Activity> activities)

    {

        asyncEnum.Execute(AdaptEnumerator(asyncEnum, activities));

    }

    private static IEnumerator<int> AdaptEnumerator(

           AsyncEnumerator asyncEnum, Enumerable<Activity> activities)

    {

        foreach (Activity activity in activities)

        {

            yield return activity(asyncEnum);

            object x;

            if (asyncEnum.IsCanceled(out x) && (x is Exception))

                throw (Exception)x;

        }

    }

The private AdaptEnumerator function serves as the equivalent of Select, except that it checks for an exception to throw immediately following resumption after the yield return. This means that after the asynchronous action completes with an error, no further code executes in the underlying function that yields the Activities.

Like I say, I have only written this and done the above analysis on it, not really tested much. If you want to give it a try, be my guest:

http://www.earwicker.com/downloads/async.zip

Please let me know if you find any ridiculous bugs or design flaws, or even if it works. It’s just a source file containing all the functions (just 150 or so lines of code), so it could be added to any project already using AsyncEnumerator, or built into a separate class library.

Asynchronous Sockets with Yield Return of Lambdas

2008-12-05T14:13:00.002Z

Update: More in-depth stuff about this

I just watched this video of Jeffrey Richter demonstrating his AsyncEnumerator class:

http://channel9.msdn.com/posts/Charles/Jeffrey-Richter-and-his-AsyncEnumerator

The key idea is the realisation that yield return takes care of turning a single function into a continuation that can be resumed under the control of some other code, but still provides a natural way to write procedurally. This is just what is needed to manage asynchronous communication. Great stuff.

But I had an idea while watching it. His code seems to still place some burden on the caller to know about the details of asynchronous socket programming - how to specify a callback, etc.

Instead, why not hide those details. The trick is to use yield return to pass back lambda expressions containing the work to do asynchronously.

Here's a quick sample - look at this first, to see how easy it is to use. It's important you see that first, because unless you're into functional programming, the behind-the-scenes stuff may seem confusing.

     /* Trivial example of a protocol - send a byte containing the payload

     * length, followed by that many bytes of data.

     * 

     * This server just sends back the same data in the same way.

     */

    static IEnumerable<AsyncIOPipeAction> HandleMyClient()

    {

        // Start by reading a byte from the client

        byte[] singleByte = new byte[1];

        yield return pipe => pipe.Read(singleByte, 0, 1);

        // That byte tells us how much to read next

        int inputPayloadLength = singleByte[0];

        byte[] inputPayload = new byte[inputPayloadLength];

        yield return pipe => pipe.Read(inputPayload, 0, inputPayloadLength);

        // Send same thing back again

        yield return pipe => pipe.Write(singleByte, 0, 1);

        yield return pipe => pipe.Write(inputPayload, 0, inputPayloadLength);

    }

As you can see, this function doesn't actually get passed a socket to work on. And yet it has these suspiciously convenient-looking calls on to a pipe object. Where does that pipe object come from and what is it?

Note how the whole function returns IEnumerable<AsyncIOPipeAction>, so it produces actions to be called somehow. Those actions are delegates:

    public delegate void AsyncIOPipeAction(IAsyncIOPipe pipe);
  

That pipe object supports this interface:

/* Example of an interface with operations that are either synchronous 
 * or asynchronous depending on the context in which they are called.
 */ 
public interface IAsyncIOPipe
{
    void Read(byte[] buffer, int offset, int size);
    void Write(byte[] buffer, int offset, int size);
}

You could follow the same pattern with any facility that supports asynchronous usage, but here I just provide two obvious operations on a socket.

So in the client-handling function, whenever you want to make use of the socket, you do a yield return to hand off some code that can be called back to. Your code must accept a pipe (which is just what you wanted). Then it can call a method on it.

The implementation IAsyncIOPipe is then very simple indeed:

    class SocketPipe : IAsyncIOPipe

    {

        private readonly Socket _socket;

        private readonly IEnumerator<AsyncIOPipeAction> _actions;

        public SocketPipe(Socket socket, 

                          IEnumerable<AsyncIOPipeAction> actions)

        {

            _socket = socket;

            _actions = actions.GetEnumerator();

            Step();

        }

        private void Step()

        {

            if (!_actions.MoveNext())

                return;

            _actions.Current(this);

        }

        private void Callback(IAsyncResult result)

        {

            _socket.EndReceive(result);

            Step();

        }

        public void Read(byte[] buffer, int offset, int size)

        {

            _socket.BeginReceive(buffer, offset, size, 

                                 SocketFlags.None, Callback, this);

        }

        public void Write(byte[] buffer, int offset, int size)

        {

            _socket.BeginSend(buffer, offset, size, 

                              SocketFlags.None, Callback, this);

        }

    }

The constructor is passed a bunch of actions to be carried out asynchronously. It doesn't actually care how that collection of actions is implemented. But of course we can call HandleMyClient to produce a suitable collection.

SocketPipe starts the ball rolling immediately, by starting the enumeration and then calling Step. This executes the first portion of code in the function up to the first yield return, after which we get control back. We then just execute the lambda giving it a pipe to work on - our implementation, in fact.

This means that when the lambda calls Read or Write, we can simply begin the right kind of asynchronous operation on our concealed socket, and we take care of specifying the callback. All our callback has to do is end the asynchronous operation and run the next Step.

Exercises for the reader:

There isn't much consideration given to error handling, mainly because I never even looked at the asynchronous socket APIs until just now, so I'm not sure where it needs to go. It should be possible to put error handling into this approach without putting any mess in the application code (e.g. HandleMyClient).
It should be possible to launch multiple asynchronous calls on multiple objects, where that makes sense (I can't see how it does in this simple example, but it might if you have multiple sockets for some reason). The lambda would need to be passed multiple parameters, one for each object currently "in play", and the management object would need to ensure that all outstanding asynchronous calls had completed before it called Step again.

Solution zip file is here:

http://www.earwicker.com/downloads/asyncsockets.zip

COIL and COILettes

2008-11-19T14:58:00.002Z

Douglas Crockford started a minor war when he observed that JavaScript's object initialisation syntax provides a neat way to persist hierarchical data, maybe more suitable to some situations than XML.

Since C# 3.0 we've had a similar facility in C#. This means an opportunity for another war.

I've started to see little object initialisation trees appearing in my code, and they start to look like a declarative internal DSL. I should post a real example some time. Anyway, this can only mean one thing: we need a snappy name for these things.

JSON stands for JavaScript Object Notation, and it sounds sort of like the name Jason, which makes it catchy. So we need a four letter acronym that starts with CS (for C-Sharp) where you pronounce the first letter as a syllable and it all sounds like a person's name. This immediately lead me to:

CSIL (pronounced "Cecil" in the American way):

C-Sharp Initialisation Language.

Sadly somebody already used that for something else.

Ah well, it was just too perfect.

But not to be discouraged, I relaxed the rules so it just has to be a four letter acronym that sounds like a word, and went for:

COIL (pronounced "coil", amazingly):

C# Object Initialisation Language.

The beauty of this becomes apparent when you consider that we also need a way to describe those little islands of COIL that appear embedded in our C# programs.

They are called COILettes.