Making Lambdas and Iterators Play Nicely Together

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?

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

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:

1. 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.
2. 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.
3. 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).
4. 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?

Displaying a nested evaluation tree from Expression<Func<bool>>

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

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

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:

3
1
4
4
1
3

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

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

Ora Stories

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:

• C# Regions Considered Harmful
• C# Regions Suck
• Just say No! to C# Regions
• C# Regions... When to use them?

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:

• Using Regions to Improve Code Readability
• Make Use of #regions When Developing C# .net Code

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#

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.