I have moved!

I've moved my blog
CLICK HERE

Sunday, 8 February 2009

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.

Tuesday, 3 February 2009

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.

Thursday, 29 January 2009

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

1. "Get out of my house".

Monday, 26 January 2009

Linq to C++0x

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.

Tuesday, 16 December 2008

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:

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.

Thursday, 11 December 2008

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.