Paul Batum

Advanced Distributed Systems Design with Udi Dahan

2010-02-07T23:01:00.000+11:00

I spent last week in Melbourne for a 5 day training course on distributed systems, run by Udi Dahan. I’ve been a fan of Udi’s work for a while now, so when I discovered that he was on his way to Australia I jumped at the chance to be immersed in his approach to designing scalable and reliable distributed systems. Let me tell you – I was not disappointed. I found Udi’s course to be very challenging – not in terms of difficulty, but rather that it was full of ideas that challenged my preconceptions. I was also very impressed with Udi’s presentation and communication skills. He really knows the material and has an amazing ability to give helpful, informative answers to really dumb questions :)

The course was focused on a few key ideas:

Service oriented architecture
Message based systems
Command / query responsibility segregation
Domain models

If you’d like a more detailed breakdown of the course content, Udi has provided an overview on his website.

I’ve tried to understand SOA before and struggled with the abstractness of the concept. I guess part of my difficulty has always come from the fact that I still approach the world with a “developer” mindset – I’ve never really bought into the concept of a non-coding architect and sometimes I struggle to understand the meaning and implications of an idea if I can’t see the actual effect on the code we write.

Thanks to Udi, I now have a basic understanding of what SOA means. I am comfortable with the idea of identifying business capabilities and describing them as services that consist of business components, which in turn consist of autonomous components that are individually deployable. I’m also comfortable with the idea of these autonomous components communicating with each other via a message bus using a combination of asynchronous request-reply and publish-subscribe. I am not yet sure how well my understanding will map to the existing literature on SOA, as I got the impression from some of the other students that Udi’s version of SOA was somewhat different to the SOA they had read about. My impression of SOA is that it is a slippery subject, where only the most abstract and vague definitions are widely accepted. That said, I can see a great deal of value in the analytical process and technical approach that Udi taught us.

Having skimmed Enterprise Integration Patterns, I was already familiar with the idea of message based systems and the advantages of temporal decoupling before I began the course. But Udi’s coverage of the topic helped fill in large gaps and also gave me a great deal of appreciation for the power and simplicity of his open source .NET based service bus, NServiceBus. My co-worker Malcolm nearly did a backflip when he saw how easy it is to begin using NServiceBus alongside WCF.

Command / query responsibility segregation (CQRS) is about recognising the difference between queries and commands as part of system architecture, and designing completely different paths for handling the two types of operations. Going into the course, I thought I was comfortable with the idea as I’d watched a number of videos on the topic from Greg Young, and had read a number of blog posts. It turned out that Udi had his own take on CQRS that I did not pick up on when reading his posts on the topic. Speaking of Udi’s posts on the topic of CQRS, I highly recommend this one if you’d like to learn more.

So how was Udi’s version of CQRS different to what I expected? One example immediately comes to mind. A necessary part of CQRS is some sort of persistent view model to facilitate the queries, and a transactional data model to facilitate the commands. So far, so good. Udi then introduced the idea that there may be some relationships that are only recorded in the persistent view model, and not in the transactional model – if later on you need that data in your transactional store, then backfill it with an ETL from your view model! Boy did that raise some incredulous looks, especially from yours truly! “What happened to my single source of truth?” I cried.

Udi also had some interesting ideas about domain models. In particular, we went into quite a bit of detail on the idea of aggregates, and how to ensure consistency. Has it ever occurred to you that perhaps there is something wrong with loading a Customer, and then lazily loading their Orders at some later point? What happens if one of the Orders are modified by another process, after the Customer is loaded but before the Orders are lazily loaded? Now the model loaded into memory is inconsistent! Even if your optimistic concurrency will protect you in most of these scenarios, its entirely possible that you’re updating some other object based on logic that has operated on your inconsistent snapshot. This problem seemed obvious once it was pointed out, but it had never occurred to me before.

There were so many interesting discussions and points of contention over the 5 days, this post has barely begun to skim the surface. It really was an eye opening experience for me, and some serious food for thought. If you ever get the opportunity to attend Udi’s course, don’t hesitate. Its worth it!

Now that I’ve finally managed to get something written down on the course, I’ll let myself read some of the summaries written by other attendees.

Reacting to the Reactive Framework: Part 8

2009-11-18T22:00:00.001+11:00

Today I caught wind of some news that was bound to rouse me from my blogging slumber. The Reactive Framework, now known as Reactive Extensions (or Rx for short) has been released on DevLabs. The good news is that this release includes versions for .NET 3.5, .NET 4 Beta 2 and Silverlight 3, and documentation. The bad news is that at this stage, the documentation is pretty sparse - single sentence summaries and zero examples. Certainly, the summaries will help developer make sense of the impressive range of extension methods available on IObservable. For example, the comment on the rather cryptically named Amb - Returns the observable sequence that reacts first - makes its purpose quite clear, even if it doesn’t help explain the name. However the same cannot be said for all the cases, such as Dematerialize - Dematerializes the explicit notification values of an observable sequence as implicit notifications. Perhaps that will make sense once I understand the difference between explicit and implicit notifications, but its unlikely that the documentation (in its current form) will help me understand this. No matter - this intermediate release is certainly welcome and I now look forward to diving back in to Rx with at least some clue of what things are supposed to do :)

If you are interested in the Reactive Extensions I recommend you check out the team blog. The announcement post has plenty of links for you to click and learn more. I also recommend Matt Podwysocki’s series of Rx posts. Also, don’t forget that now Rx is on DevLabs, there’s a dedicated forum.

Reacting to the Reactive Framework: Part 7

2009-08-11T17:55:00.000+10:00

The demo application for today allows the user to experiment with a couple of the mechanisms that I tried for part 6. As you may recall, I wanted an IObservable<int[]> that would return the three selections made from three groups of radio buttons, and only begin returning values once a selection had been made from all three. The demo app allows you to switch between using SelectMany, ForkJoin and CombineLatest and observe how the behavior changes:

The first approach I tried was SelectMany - I’ll use the query comprehension syntax as it is much more readable than calling the SelectMany extension method directly:

from s1 in choiceControl1.OptionSelections
from s2 in choiceControl2.OptionSelections
from s3 in choiceControl3.OptionSelections
select new[] { s1, s2, s3 }

This syntax might be readable, but its also a little misleading. It looks very uniform, like it wouldn’t matter which order you wrote those three ‘from’ statements in. But if you are familiar with LINQ statements like this one, you will know that the ordering IS important. To observe this, activate the SelectMany option in the app above, and then make your selections in reverse order i.e. select an option from group 3, then group 2, then group 1. Notice how you don’t get a selection readout? What’s actually happening here is that the selections made in groups 2 and 3 are ignored until a selection is made in group 1. Then the selections made in group 3 are ignored, until a selection is made in group 2. Then finally selections from group 3 will trigger the observable and raise a result. I could go into more detail on what’s happening here, but is there much point? Its obvious that this implementation is not at all close to the desired result. Lets move on.

When I came across the signature for ForkJoin, I thought I had found what I was looking for:

public static IObservable<TSource[]> ForkJoin<TSource>(params IObservable<TSource>[] sources);

It converts many IObservable<T>’s into one IObservable<T[]>, which is exactly what I want. The bad news is that it only works once. Go ahead and try ForkJoin in the sample app – the status text will update once a selection has been made from all three groups, but it will not update again as the selection continues to change. It did occur to me that perhaps I could use ForkJoin and somehow re-subscribe each time it fires, but I was reluctant to go down that path because it doesn’t feel like a functional (as in functional programming) solution.

The demo app for today uses CombineLatest in the same way as in my previous post:

choiceControl1.OptionSelections
  .CombineLatest(choiceControl2.OptionSelections, (i, j) => new[] { i, j })
  .CombineLatest(choiceControl3.OptionSelections, (array, k) => new[] { array[0], array[1], k }))

This works fine, though its not pretty. I’ll keep my eye out for a better solution, but before I finish up today I want to look at the code behind today’s demo app:

<StackPanel Margin="20">
    <TextBlock Text="Combining Example" HorizontalAlignment="Center" Margin="10" />
    <StackPanel Orientation="Vertical" HorizontalAlignment="Left">
        <TextBlock Text="Select a means of combination:" />
        <RadioButton Name="rbSelectMany" Content="Use SelectMany" />
        <RadioButton Name="rbForkJoin" Content="Use ForkJoin" />
        <RadioButton Name="rbCombineLatest" Content="Use CombineLatest" />                               
        <TextBlock Text="Select an option from each group below, and then experiment with changing your selections." TextWrapping="Wrap" Margin="0,10,0,0"  />
    </StackPanel>            
    <StackPanel Orientation="Horizontal" HorizontalAlignment="Center" >
        <SilverlightApp:ChoiceControl Name="choiceControl1" Heading="Group 1"/>
        <SilverlightApp:ChoiceControl Name="choiceControl2" Heading="Group 2"/>
        <SilverlightApp:ChoiceControl Name="choiceControl3" Heading="Group 3"/>
    </StackPanel>
    <TextBlock Name="statusText" Text="Status Text" TextAlignment="Center"></TextBlock>
</StackPanel>

public MainPage()
{
    InitializeComponent();

    IObservable<IObservable<int[]>> observerSelections = Observable.Merge(
        Observable.FromEvent<RoutedEventArgs>(rbSelectMany, "Checked")
            .Select(_ => from s1 in choiceControl1.OptionSelections
                         from s2 in choiceControl2.OptionSelections
                         from s3 in choiceControl3.OptionSelections
                         select new[] { s1, s2, s3 }),
        Observable.FromEvent<RoutedEventArgs>(rbForkJoin, "Checked")
            .Select(_ => Observable.ForkJoin(choiceControl1.OptionSelections, choiceControl2.OptionSelections, choiceControl3.OptionSelections)),
        Observable.FromEvent<RoutedEventArgs>(rbCombineLatest, "Checked")
            .Select(_ => choiceControl1.OptionSelections
                            .CombineLatest(choiceControl2.OptionSelections, (i, j) => new[] { i, j })
                            .CombineLatest(choiceControl3.OptionSelections, (array, k) => new[] { array[0], array[1], k }))
        );

    IDisposable subscription = null;
    observerSelections.Subscribe(observer =>
                                 {
                                     if (subscription != null)
                                         subscription.Dispose();

                                     choiceControl1.ClearAll();
                                     choiceControl2.ClearAll();
                                     choiceControl3.ClearAll();
                                     statusText.Text = string.Empty;

                                     subscription = observer.Subscribe(UpdateSelectedOptions);                                                                               
                                 });
}

private void UpdateSelectedOptions(int[] values)
{
    statusText.Text = string.Format("Option {0}, Option {1}, Option {2}",
                                    values[0], values[1], values[2]);
}

If you recall in the previous post, I was using the Observable.Merge method to glue three separate events together into one observable, and today I’m using the same technique on the radio buttons that let you swap between the different implementations. The difference in this case is that instead of simply returning an integer, I’m returning an IObservable<int[]>, so the result is an IObservable<IObservable<int[]>>. I then subscribe to this so that each time the selected implementation changes, the existing subscription is disposed, the selections are cleared and a new subscription is instated.

What do you think? Am I being too clever for my own good here? Is an IObservable<IObservable<T>> taking it too far? Let me know in the comments!

The code for this post has been tagged in my github repository.

Reacting to the Reactive Framework: Part 6

2009-08-09T02:42:00.000+10:00

Before I dive into today’s code, there are two things worth mentioning:

If you haven’t already, make haste to Jafar Husain’s blog. Jafar is posting truly interesting examples of using the Reactive Framework - none of the ‘hello world’ fare I’m peddling here.
I mentioned in my previous post that I was having trouble using System.Reactive.dll with non-silverlight projects. Jb Evain has the goods on how you might get around this if you were so inclined. For now I’ll stick with Silverlight as its well suited for including interactive demonstrations in my blog posts.

Today I want to look at combining events using the Reactive Framework (Rx). Here is the demo app for today: (Once again I will remind readers using RSS readers to view this post in a proper browser window so you can see the embedded Silverlight app.)

The idea behind this example is that I am not interested in the selections until an option has been selected from all three groups. From then on, I’d like to be informed whenever the selection changes. This application consists of three instances of a user control, one for each group. Here is the relevant markup and code for the user control:

<StackPanel Margin="20">
    <TextBlock Text="{Binding Heading}" Margin="5" />
    <RadioButton Name="optionButton1" Content="Option 1" />
    <RadioButton Name="optionButton2" Content="Option 2" />
    <RadioButton Name="optionButton3" Content="Option 3" />
</StackPanel>

public ChoiceControl()
{
    InitializeComponent();

    OptionSelections = Observable.Merge(
        Observable.FromEvent<RoutedEventArgs>(optionButton1, "Checked").Select(_ => 1),
        Observable.FromEvent<RoutedEventArgs>(optionButton2, "Checked").Select(_ => 2),
        Observable.FromEvent<RoutedEventArgs>(optionButton3, "Checked").Select(_ => 3)
        );
}

public IObservable<int> OptionSelections { get; private set; }

As you can see, I am creating IObservables from the Checked events of the radio buttons. I’m using the Select method to make observables that simply return the index, and I’m merging those together into one IObservable<int>. So if the user checked option 1, then option 2, then option 3, the OptionSelections would call OnNext on its subscribed observers with values 1, 2 and 3 respectively.

As I mentioned before, this app has 3 instances of this user control:

<StackPanel x:Name="LayoutRoot" Margin="50" Background="Azure" Width="400">
    <StackPanel Orientation="Horizontal" HorizontalAlignment="Center" >
        <SilverlightApp:ChoiceControl Name="choiceControl1" Heading="Choice 1"/>
        <SilverlightApp:ChoiceControl Name="choiceControl2" Heading="Choice 2"/>
        <SilverlightApp:ChoiceControl Name="choiceControl3" Heading="Choice 3"/>
    </StackPanel>
    <TextBlock Name="statusText" TextAlignment="Center"></TextBlock>
</StackPanel>

Now somehow I want to subscribe to the OptionSelections from each control, in such a way that I don’t see any results raised until an option from all three groups have been selected. After a few failed attempts, I stumbled upon this solution:

public MainPage()
{
    InitializeComponent();

    string formatString = "Option {0}, Option {1}, Option {2}";

    var selections = choiceControl1.OptionSelections
        .CombineLatest(choiceControl2.OptionSelections, (i, j) => new[] { i, j })
        .CombineLatest(choiceControl3.OptionSelections, (array, k) => new[] { array[0], array[1], k });

    selections.Subscribe(values => statusText.Text = string.Format(formatString, values[0], values[1], values[2]));            

}

I’m using the CombineLatest extension method, but it will only combine two IObservables so I have to use it twice. The first call returns an IObservable<int[]>, where the array contains two elements. I then combine that with the option selections from choiceControl3, again returning an IObservable<int[]>, this time with all 3 selections. The final step is simply to subscribe to the resulting observable and display the message.

This solution of combining once into an array of two elements and then combining again into an array of three doesn’t seem particularly elegant, but so far I haven’t managed to find anything better. Perhaps I could write a version of CombineLatest that takes more than two observables and hides this ugliness? Its probably not necessary – there’s a good chance that the perfect method already exists, and I’ve just missed it.

In my next post, I’d like to demonstrate some of the failed attempts I made before I found CombineLatest. This demo will give me a chance to create my first IObservable<IObservable<T>>, which I’ve been itching to do :)

Today’s code has been tagged in my github repository.

Reacting to the Reactive Framework: Part 5

2009-07-26T17:34:00.000+10:00

It appears to have gone mostly under the radar, but the Reactive Framework is now out in the wild. The latest release of the Silverlight Toolkit includes System.Reactive.dll, mostly to facilitate the testing of the controls found within the toolkit. Jafar Husain broke the news earlier this week with this excellent post.

Today I want to do a demo that is very similar to the previous demos I’ve done, but of course this time I’ll be using the real Reactive Framework rather than my crappy attempt at implementing it that I’ve inflicted upon you in earlier posts. So far my experiments with using System.Reactive.dll with windows forms have not compiled properly so I’ll switch to using Silverlight for my examples. For now I will continue to focus on exposing button click events as an IObservable. Here is the code:

IObservable<Event<RoutedEventArgs>> clicks = Observable.FromEvent<RoutedEventArgs>(button1, "Click");

int count = 0;
clicks.Subscribe(() => count++);

IObservable<string> messages = from c in clicks
                               select string.Format("Clicked {0} time{1}", count, count > 1 ? "s" : "");
messages.Subscribe(s => button1.Content = s);

And here is the application:

If you are in a RSS reader, you probably won’t be able to see the embedded Silverlight app above. Pop this post out into its own browser tab so that you can revel in the glory of a button that tells you how many times its been clicked!

Lets take a look at what this code is doing. The first step is to convert from an Event to an IObservable:

IObservable<Event<RoutedEventArgs>> clicks = Observable.FromEvent<RoutedEventArgs>(button1, "Click");

The Observable class defines a large swath of extension methods for creating and manipulating IObservables. This overload of the FromEvent method is simple to use, but unfortunately it makes use of a magic string (“click”). There is another overload for FromEvent that allows us to do the same thing with compile-time safety, but it is more verbose. I’ve wrapped it in an extension method:

public static IObservable<Event<RoutedEventArgs>> GetClicks(this Button button)
{
    return Observable.FromEvent((EventHandler<RoutedEventArgs> genericHandler) => new RoutedEventHandler(genericHandler),
                                routedHandler => button.Click += routedHandler,
                                routedHandler => button.Click -= routedHandler);
}

This overload takes three functions as arguments. One to convert from a generic event handler (EventHandler<T>) to the specific event handler that the Click event uses (RoutedEventHandler). The conversion is straightforward, because the two event handlers have the same signature. The other two functions add and remove the handler. This extension method can be used like so:

IObservable<Event<RoutedEventArgs>> clicks = button1.GetClicks();

It would not surprise me if we eventually see extra libraries that define many of these extension methods for us. Ideally they would be unnecessary, and we could simply write:

IObservable<Event<RoutedEventArgs>> clicks = button1.GetObservableEvent(b => b.Click);

But unfortunately the dreaded “The event 'System.Windows.Controls.Primitives.ButtonBase.Click' can only appear on the left hand side of += or –=” message rears its ugly head. Perhaps in C# 5 the story will be different.

Moving on, the code initializes a count variable and subscribes an increment function to the clicks:

int count = 0;
clicks.Subscribe(() => count++);

You’ll notice that I am simply passing an Action to the Subscribe method, rather than an IObserver. The Reactive Framework won’t force you to use an IObserver if all you want to do is call a function when a new event occurs.

Finally, the code converts the stream of click events into a stream of messages and subscribes to it:

IObservable<string> messages = from c in clicks
                               select string.Format("Clicked {0} time{1}", count, count > 1 ? "s" : "");
messages.Subscribe(s => button1.Content = s);

There are lots of other ways in which to rewrite today’s example code. This version is very short and still quite readable:

int count = 0;
button1.GetClicks().Select(x => ++count)
    .Subscribe(() => button1.Content = string.Format("Clicked {0} time{1}", count, count > 1 ? "s" : ""));

Or I could implement IObserver:

public class CountingButtonObserver : IObserver<Event<RoutedEventArgs>>
{
    private int _count = 0;
    public Button Button { get; set; }

    public void OnNext(Event<RoutedEventArgs> value)
    {
        _count++;
        Button.Content = string.Format("Clicked {0} time{1}", _count, _count > 1 ? "s" : "");
    }

    public void OnError(Exception exception) {}
    public void OnCompleted() {}
}

And use it like so:

button1.GetClicks().Subscribe(new CountingButtonObserver{ Button = button1});

Well, that’s probably enough for today. I’m going to continue to explore the Reactive Framework and see what interesting things I can find. Oh, and let me know if you come across any documentation for it – so far I haven’t found any and it can be quite a struggle to make sense of the various extension methods that are available.

I’ll be pushing my experiments with the Reactive Framework to a github repo.

Reacting to the Reactive Framework: Part 4

2009-07-19T19:29:00.000+10:00

This post is part 4 in a series.

About a week ago another video on the Reactive Framework went up, this time on Channel 9. It was an enjoyable video, though I found it tricky to follow in parts because my understanding of monad theory is virtually non-existent and the discussion does get abstract/theoretical in places. It did however give me a much better understanding of the basic Reactive Framework interfaces (IObserver<T> and IObservable<T>), which meant I had some work to do get my implementation up to scratch!

Side note: I think I started this series badly by getting too complicated too fast, so I’m going to use this as an opportunity to start again.

Here are the relevant interface definitions (I haven’t specified any covariance or contravariance for these types because I am still using C# 3.):

public interface IObservable<T>
{
    IDisposable Subscribe(IObserver<T> observer);
}

public interface IObserver<T>
{        
    void OnNext(T item);
    void OnDone();
    void OnError(Exception e);
}

Hopefully the expected interaction between these two interfaces is relatively self-explanatory. There are a few differences between this pair of interfaces and what I had in the previous posts:

Rather than passing a callback function to the Subscribe method (previously called ‘Attach’) an IObserver is passed. As you would expect, the OnNext(item) method is called on the subscribed observer when the IObservable has a new result.
The Subscribe method returns an IDisposable. When it is disposed, the IObserver is unsubscribed.
When the IObservable has finished (no more results), each of the IObservers are notified using OnDone().
If the IObservable encounters an error, the IObservers are notified using OnError(e).

The task today is to capture the stream of MouseDown events on a button as an IObservable<MouseEventArgs>, and then convert that into an IObservable<string> representing messages to be written to a text box. When the MouseDown event occurs, the text box should be updated accordingly. We can start by obtaining a IObservable<MouseEventArgs> like so:

IObservable<MouseEventArgs> mouseEvents = button1.GetMouseDowns();

GetMouseDowns() is an extension method – its purpose is to wrap the MouseDown event as an IObservable. Its implementation is very simple:

public static IObservable<MouseEventArgs> GetMouseDowns(this Button button)
{
    var wrapper = new EventWrapper<MouseEventArgs>();
    button.MouseDown += wrapper.Handler;
    return wrapper;
}

The EventWrapper class is wired up to the MouseDown event. It has a collection of observers which it notifies when the MouseDown event occurs:

public class EventWrapper<T> : IObservable<T> where T : EventArgs
{
    private readonly ObserverCollection<T> _observers = new ObserverCollection<T>();

    public void Handler(object sender, T eventArgs)
    {
        _observers.NotifyNext(eventArgs);
    }

    public IDisposable Subscribe(IObserver<T> observer)
    {
        return _observers.Subscribe(observer);
    }
}

Lets skip the implementation of the ObserverCollection for now. I’d prefer to move on to converting this IObservable<MouseEventArgs> to an IObservable<string>:

IObservable<MouseEventArgs> mouseEvents = button1.GetMouseDowns();
IObservable<string> messages = from md in mouseEvents
                               select "Mouse down at: " + md.X + "\n";

This works as long as the “Select” LINQ operator has been implemented for IObservable, because the C# compiler converts the above into:

IObservable<MouseEventArgs> mouseEvents = button1.GetMouseDowns();
IObservable<string> messages = mouseEvents.Select( (MouseEventArgs md) => "Mouse down at: " + md.X + "\n");

The following extension method has the appropriate signature:

public static IObservable<TResult> Select<T, TResult>(this IObservable<T> observable, Func<T, TResult> func)
{
    return new SelectObservable<T, TResult>(observable, func);            
}

By calling this method, really what we’re saying is that we want a new IObservable that calls its subscribers when the old IObservable did, but first uses the passed function “func” to convert from the old result type to the new result type. In this case, that function is the lambda expression:

(MouseEventArgs md) => "Mouse down at: " + md.X + "\n"

Lets skip the implementation of the SelectObservable, and instead look at consuming the messages. I’ll subscribe an observer that will update the textbox:

messages.Subscribe(new TextBoxUpdater(textBox1));

Here is the implementation for the TextBoxUpdater:

public class TextBoxUpdater : IObserver<string>
{
    private readonly TextBox _textBox;

    public TextBoxUpdater(TextBox textBox)
    {
        _textBox = textBox;
    }

    private void AppendText(string text)
    {
        Action textboxUpdater = () => _textBox.AppendText(text);
        _textBox.BeginInvoke(textboxUpdater);
    }

    public void OnNext(string s)
    {
        AppendText(s);
    }

    public void OnDone()
    {
        AppendText("Done\n");
    }

    public void OnError(Exception e)
    {
        AppendText("Error: " + e.Message);
    }
}

As you can see, it implements the OnNext, OnDone and OnError methods by writing some appropriate text, though in this simple example, I’m not really using OnDone or OnError. If I run this program now and click the button a few times, I get this:

That wraps it up for today. The code as of this post is available here.

Reacting to the Reactive Framework: Part 3

2009-07-05T15:08:00.001+10:00

In part one of this series, I introduced the Live Labs Reactive Framework and provided a simple example of what can be achieved when using LINQ for reactive programming. In part two I did my best to explain how my example worked. In today’s post I want to extend the example slightly. Just to reiterate, this series is not about using the Live Labs Reactive Framework as it has not yet been released. I’m exploring the idea of a reactive framework using my own implementation.

Here is my example from the previous posts:

Func<MouseEventArgs, int> slowOperation = args =>
{
    System.Threading.Thread.Sleep(3000);
    return args.X;
};

IObservable<int> observable = from md in button1.GetMouseDowns()
                              from x in slowOperation.AsAsyncObservable(md.EventArgs)
                              select x;

The idea behind this code is that the IObservable<int> represents a stream of integers that are the result of capturing the mouse down event on a button, doing some “slow processing” (really just a 3 second sleep) asynchronously, and returning the x coordinate from the mouse down event. You can then attach something to that observable like so:

Action<string> textboxUpdater = s => textBox1.AppendText(s);
observable.Attach(x => textBox1.BeginInvoke(textboxUpdater, "Mouse down: " + x + "\n"));

The attached code updates the textbox as the values bubble up through the IObservable. Unfortunately its a little more complicated than I would like because the update has to be marshalled onto the UI thread – hence the BeginInvoke call. Today I want to modify this example so that the textbox is only updated when the right mouse button was clicked. The MouseEventArgs can tell me which button was clicked, so really this is just a matter of implementing support for where:

IObservable<int> observable = from md in button1.GetMouseDowns()
                              where md.EventArgs.Button == MouseButtons.Right
                              from x in slowOperation.AsAsyncObservable(md.EventArgs)
                              select x;

Well this is a very natural way to express what I want – and the implementation is not too hard. First I create the appropriate extension method:

public static IObservable<T> Where<T>(this IObservable<T> source, Func<T, bool> predicate)
{
    return new WhereObservable<T>(source, predicate);
}

This extension method is just a wrapper call for a class. In this case, its WhereObservable<T> which takes a source IObservable, and a predicate to apply:

public class WhereObservable<T> : IObservable<T>
 {
     private readonly IObservable<T> _source;
     private readonly Func<T, bool> _predicate;

     public WhereObservable(IObservable<T> source, Func<T, bool> predicate)
     {
         _source = source;
         _predicate = predicate;
     }

     public void Attach(Action<T> action)
     {
         _source.Attach(t => { if (_predicate(t)) action(t); });
     }
 }

All I’m doing here is wrapping an inner observable so that I can check to see if the predicate applies before I let the observable event bubble up. That’s all there is to it. My example will now only update the textbox if the right mouse button was clicked.

My work on this project is available on github. To get the code as it was at the time this post was written, use this tag.

Reacting to the Reactive Framework: Part 2

2009-05-31T15:42:00.000+10:00

DISCLAIMER: The code in this post was the result of a big hackfest with the single goal of getting a particular use case working. I am telling you right now that I paid no attention to potential concurrency problems and that if you try to reuse any of this stuff you are just asking for trouble.

In the previous post, I explained how Eric Meijer’s recent Lang.NET presentation on the LiveLabs Reactive Framework piqued my interest. Wondering how the framework works, I decided to have a go at emulating some of the basic functionality it appears to provide. This code demonstrates the functionality I’ve implemented so far:

Func<MouseEventArgs, int> slowOperation = args =>
{
    System.Threading.Thread.Sleep(3000);
    return args.X;
};

IObservable<int> observable = from md in button1.GetMouseDowns()
                              from x in slowOperation.AsAsyncObservable(md.EventArgs)
                              select x;

Action<string> textboxUpdater = s => textBox1.AppendText(s);
observable.Attach(x => textBox1.BeginInvoke(textboxUpdater, "Mouse down: " + x + "\n"));

Today I am going to work my way through the query comprehension you can see here and do my best to explain how I got this working. Perhaps a good place to start would be to convert the query comprehension into a method chain in the same way the C# compiler does for us under the covers. Resharper can do this automatically, which is convenient:

IObservable<int> observable = button1.GetMouseDowns().SelectMany(
                    md => slowOperation.AsAsyncObservable(md.EventArgs), 
                    (md, x) => x
                    );

The first call here is to an extension method called GetMouseDowns:

public static IObservable<EventResult<Button, MouseEventArgs>> GetMouseDowns(this Button b)
{
    var wrapper = new EventWrapper<Button, MouseEventArgs>();
    b.MouseDown += wrapper.Handle;
    return wrapper;
}

So far, this is relatively straightforward. The GetMouseDowns extension method creates an EventWrapper, and wires that EventWrapper up to the MouseDown event on the button. You can see that the wrapper is being returned as an IObservable of an EventResult. Here is the code for these:

public interface IObservable<T>
{
    void Attach(Action<T> action);
}

public class EventResult<TSender, TArgs>
{
    public EventResult(TSender sender, TArgs args)
    {
        Sender = sender;
        EventArgs = args;
    }

    public TSender Sender { get; private set; }
    public TArgs EventArgs { get; private set; }
}

public class EventWrapper<TSender, TArgs> : IObservable<EventResult<TSender,TArgs>>
{
    private List<Action<EventResult<TSender, TArgs>>> _attached = new List<Action<EventResult<TSender, TArgs>>>();

    public void Handle(object sender, TArgs e)
    {
        foreach (var action in _attached)
            action(new EventResult<TSender,TArgs>((TSender)sender, e ));
    }

    public void Attach(Action<EventResult<TSender, TArgs>> action)
    {
        _attached.Add(action);
    }
}

Now there is some really naive code here. What would happen if someone called Attach while we were in the middle of handling the event? It would crash, because the list of actions to be called would be modified while it was being iterated over. In general, the code for the EventWrapper feels bad. I am sure it can be done much better, but it works for now.

So the result of the GetMouseDowns method is an EventWrapper that will call the attached methods when the mouse down event occurs, and this is exposed as an IObservable. SelectMany is then called on that IObservable. This is another extension method:

public static IObservable<TResult> SelectMany<TSource, TCollection, TResult>(this IObservable<TSource> source, Func<TSource, IObservable<TCollection>> collectionSelector, Func<TSource, TCollection, TResult> resultSelector)
{
    return new SelectManyObservable<TSource, TCollection, TResult>(source, collectionSelector, resultSelector);
}

So how on earth did I arrive at this method? Its quite simple actually – I stole its signature from the SelectMany extension method implemented on IEnumerable. The interesting thing about LINQ query comprehensions is that they actually don’t have a dependence on IEnumerable or IQueryable. Instead they depend on the existence of particular methods with the appropriate signature such as Select, SelectMany, Where, GroupBy, etc. By writing these extension methods for IObservable, I can then write query comprehensions against IObservables.

Once its established that my SelectMany borrowed its signature from the appropriate extension method on IEnumerable, there isn’t much more to know about it. You can see that all it simply does is return a SelectManyObservable that wraps the passed arguments. What is the SelectManyObservable exactly? Well, here is the code:

public class SelectManyObservable<TSource, TCollection, TResult> : IObservable<TResult>
{
    private readonly IObservable<TSource> _source;
    private readonly Func<TSource, IObservable<TCollection>> _collectionSelector;
    private readonly Func<TSource, TCollection, TResult> _resultSelector;

    public SelectManyObservable(IObservable<TSource> source, Func<TSource, IObservable<TCollection>> collectionSelector, Func<TSource, TCollection, TResult> resultSelector)
    {
        _source = source;
        _collectionSelector = collectionSelector;
        _resultSelector = resultSelector;
    }

    public void Attach(Action<TResult> action)
    {
        _source.Attach(
            s => _collectionSelector(s).Attach(
                c => action(_resultSelector(s, c))
            )
        );            
    }
}

So this class simply wraps an underlying IObservable, and when methods are attached to the SelecyManyObservable, it actually gets attached to the underlying IObservable. The funny thing about this code is that it practically wrote itself. It was basically a matter of just figuring out how the underlying observable, collectionSelector, resultSelector and attached action related to each other and then calling them accordingly. It felt like solving a 4 piece jigsaw puzzle with only 1 solution.

Before the explanation of the query comprehension is complete, there is one more extension method that requires explanation:

public static IObservable<TResult> AsAsyncObservable<TInput, TResult>(this Func<TInput,TResult> funcToObserve,TInput input)
{
    return new AsyncWrapper<TInput, TResult>(funcToObserve, input);
}

This pattern should look familiar. Its like the SelectMany in that it simply returns a wrapper object that takes all the method arguments as parameters. The signature however, wasn’t borrowed from the framework. The point of this method is to allow the user to convert an anonymous delegate or lambda expression into an IObservable. Now I hope you packed the goggles I mentioned in my previous post, because AsyncWrapper is really nasty:

public class AsyncWrapper<TInput, TResult> : IObservable<TResult>
{
    private List<Action<TResult>> _attached = new List<Action<TResult>>();

    public AsyncWrapper(Func<TInput, TResult> funcToObserve, TInput input)
    {
        funcToObserve.BeginInvoke(input, CompletedCallback, null);
    }

    public void Attach(Action<TResult> action)
    {
        _attached.Add(action);
    }

    private void CompletedCallback(IAsyncResult asyncResult)
    {
        TResult calculatedValue = ((Func<TInput, TResult>) ((AsyncResult) asyncResult).AsyncDelegate).EndInvoke(
            asyncResult);

        foreach (var action in _attached)
            action(calculatedValue);
    }
}

It might not seem so bad, until you look at what the constructor is doing. When the AsyncWrapper is created, it fires off the function to observe. Now when that function completes, the callback will be invoked, and as a result all the attached actions will also be invoked. The reason why this is all so heinous is that the actions will have to be attached AFTER the function to observe is invoked, but before it completes. As a result, I am fairly sure that if we changed the slow asynchronous operation to be much faster, then this code would stop working. Surely a better solution can be found, and I do hope to attend to this later.

So that covers all the code that makes my example work. The nice thing about this approach is the composability. It is convenient to be able to work with enumerables using select, where, etc and the same is true for observables. I am really looking forward to getting my hands on the Reactive Framework code. In the mean time, I’ll continue to experiment. In the next post I’ll extend this example, starting with adding support for ‘where’ operations.

Reacting to the Reactive Framework: Part 1

2009-05-26T22:54:00.001+10:00

Last night I managed to get some code working and I was very excited, but it was far too late to start writing a blog post. Here is the code:

Func<MouseEventArgs, int> slowOperation = args =>
{
    System.Threading.Thread.Sleep(3000);
    return args.X;
};

IObservable<int> observable = from md in button1.GetMouseDowns()
                              from x in slowOperation.AsAsyncObservable(md.EventArgs)
                              select x;

Action<string> textboxUpdater = s => textBox1.AppendText(s);
observable.Attach(x => textBox1.BeginInvoke(textboxUpdater, "Mouse down: " + x + "\n"));

This code is sitting inside a very simple windows form. The form has a button and a textbox. When the button is clicked, a message is written to the textbox about 3 seconds later, relaying the relative X coordinate of the mouse when the button was clicked. The 3 second delay represents some sort of slow asynchronous operation, currently simulated with a simple Thread.Sleep(). Because the slow operation is done on a different thread, we have to use Control.BeginInvoke() to get the textbox to update on the UI thread. GetMouseDowns() is an extension method on Button that helps set the whole thing up by returning an IObservable that is wired to the MouseDown event.

So at this point you might be wondering what this is all about. To get the full story, I encourage you to watch Eric Meijer’s video on the LiveLabs Reactive Framework (direct wmv link). In this very enjoyable presentation, Eric gives us a run down the Reactive Framework, which appears to be a set of libraries that unite various types of “reactive” operations under a common pair of interfaces, IObserver<T> and IObservable<T> which are then integrated into LINQ. I found the presentation to be quite a tease. Erik shows just enough to give you an idea of what the Reactive Framework is all about, but he skims over the implementation details quite lightly. I ended up watching the thing a couple of times, trying to wrap my head around the idea of LINQ query comprehensions (e.g. from x in y select x.ID) operating against non enumerable/queryable types. In particular, I started wondering whether I could implement something like the code from this slide:

As you can see, my code at the top is not too dissimilar from Erik’s code here. Erik’s example is a web page with dictionary suggest on a textbox. When the user enters a character into the textbox, the dictionary suggest runs asynchronously against the input entered so far and when a return value is received it is rendered as html.

There is certainly quite a lot regarding the Reactive Framework that I don’t understand. I’ve been unable to find any resources beyond Erik’s talk – certainly the code doesn’t seem available anywhere. So far I don’t even understand how IObserver fits in. Can YOU see anything that might implement IObserver in the above slide? But in any case, the idea is intriguing, and trying to figure out how to do this myself is teaching me quite a bit about LINQ. In the next post, I’ll do my best to explain how the implementation works. Don’t forget your goggles, this is some pretty hacky code coming up.

A Fluent NHibernate update

2009-04-29T01:20:00.001+10:00

Since James has announced the latest happenings in the ongoing saga of moving Fluent NHibernate to using a semantic model, I thought a companion post might be appropriate.

My first post on the Fluent NHibernate rewrite is as good a place to start as any. In it I explained the limitations of the existing implementation and outlined my strategy for dissolving those limitations. My branch differs from the trunk by separating the fluent interface from the mapping model. The fluent interface manipulates the underlying model, and a family of visitors build a Hbm object graph that represents that underlying model. That object graph is serialized to xml and then passed to NHibernate. This graph consists of classes that are generated from the NHibernate mapping schema, so the serialization step is all automatic and works flawlessly.

The use of the visitor pattern allows for two things. One, the mapping model is not tied to any particular output format. Sure we pass NHibernate xml today, but tomorrow it would be nice to pass it the Hbm object graph directly so it can skip the xml schema validation step. The day after it would be nice to pass it a prebuilt NHibernate.Mapping graph, which is an idea that Tuna Toksoz was exploring from within my branch. Secondly, the visitor implementation allowed for powerful manipulations of the mapping model that would otherwise be difficult. I talked more about the visitor implementation here.

Sure, passing NHibernate its mappings in a format other than xml would be nice some day, but there was another reason why I chose to use a Hbm graph instead of directly writing xml. Basically, its much harder to go off the rails when working with the Hbm objects. One example is that the NHibernate schema is finicky about element ordering and you simply don’t have to worry about this when working with Hbm objects.

As time went on the code base grew, things changed, but slow and steady progress was made. The problem is that slow and steady doesn’t always win the race – specifically in the case where the goalpost is moving as fast or faster than you! This is the classic rewrite problem. I’m sure you are familiar with it – its why all the well respected software professionals tell you that rewriting your app is a fools errand. And don’t get me wrong, I am in agreement here. I approached my work to rewrite Fluent NHibernate as a prototyping exercise - “one possible future” if you will. As the work continued I would discuss our long term goals with James and for a while we found ourselves hoping that we could replace the existing trunk with my branch, if only we could “catch up” to the trunk functionality. Of course this sort of thinking was dangerous, and the consequences are well described in James’s post. My intentions, while good, have lead to a lack of progress on the Fluent NHibernate trunk and this is simply not a healthy place to be.

James asked me whether I could see a way to merge the two code bases. Basically inject my model into the existing guts of the trunk. I told him I couldn’t see a way how, but I encouraged him to try. The problem, I’m sure you’ve already guessed, is that I was too “caught up” in my code and simply not prepared to make sacrifices. This is why James managed something that I could not – he merged my branch into the trunk code under an “integration” branch, with all the existing trunk tests passing. Its not pretty, but I suspect that it represents the best direction to work from. We can now do what the experts tell us to do and refactor, rather than rewrite.

So what were the sacrifices? The main one is the Hbm object graph approach. Fluent NHibernate will only be capable of spitting out xml for the near future. Lets face it, its not a huge loss. Plus I say near future because the visitor implementation survived, so there is no reason why we couldn’t later start retrofitting my Hbm code in. I am yet to take full stock of the “casualties”, but I expect that everything that has been lost in the merge can be regained through a gradual process of refactoring and reintroducing code and ideas from my branch. It will be fun!

Finally I want to use this post as an opportunity to thank James for all his amazingly hard work on this great project. We don’t always see eye to eye but the thing that I often remind myself is that time and again he has proven to me that he has his finger on the pulse of our users and can see how this project can best fulfil their needs. Please keep it up James.

Legacy code: a follow up

2009-04-27T14:26:00.001+10:00

A few weeks back I wrote a post on Working Effectively with Legacy Code, a book by Michael Feathers. At the time I lamented that even though I accepted Michael’s definition of legacy code (code without tests), I wasn’t doing much about it – I hadn’t written any tests at work. Today I wanted to follow up on this because the last two weeks have gone much better – I’ve been writing unit tests. I was given the job of rewriting a particularly hairy module and this was simply too good an opportunity to pass up. I’m not doing TDD yet, and I certainly haven’t written as many tests as I would like, but its a start.

Rather than using a mocking framework, I’ve been hand rolling stubs. I believe that the other developers will have an easier time understanding the tests if I use manual stubs. Mocking frameworks are certainly convenient but as Michael demonstrates in his book, they are not necessary per se. So far I haven’t found this particularly painful and I think its a sound approach for introducing automated unit testing. I must admit that the fact that I am working on a .NET 2.0 project made this decision easier. I learned Rhino Mocks using the .NET 3.5 API and I think I would have a hard time going without the sweetness that lambda expressions provide.

Writing that very first test is a bit of a barrier, but its only a mental one. I was fortunate to have a nice piece of work come along and give me a push. Hopefully it will not be necessary the next time I find myself faced with legacy code – I intend to write that first test without a moment of hesitation. Its all downhill from there.

Working Effectively with Legacy Code

2009-04-13T23:04:00.001+10:00

Today I finished reading Working Effectively with Legacy Code by Michael Feathers. If you are not familiar with this book, you might be wondering if I’ve somehow been roped into maintaining some sort of 10 year old VB6 application -fortunately this is not the case. But I am indeed working on a legacy application – at least, it is legacy by Michael’s rather unique definition. Michael defines legacy code as code that is not under test, specifically unit tests. By Michael’s definition, virtually all of the code I have written during my career was legacy from the day it was born, and when I reflect on it, this seems like a fair statement. Here is a short excerpt from the preface:

Code without tests is bad code. It doesn’t matter how well written it is; it doesn’t matter how pretty or object-oriented or well-encapsulated it is. With tests, we can change the behaviour of our code quickly and verifiably. Without them, we really don’t know if our code is getting better or worse.

It doesn’t matter how clean and refactored my code was – developers that had to maintain it were forced to do so with uncertainty. It is specifically that element of uncertainty that I associate with the legacy code experience.

The book uses a FAQ format, with chapter titles such as:

I need to make a change. What methods should I test?
I can’t get this class into a test harness.
This class is too big and I don’t want it to get any bigger.
I need to make a change but I don’t know what tests to write.

It does a great job of illustrating refactorings that let you break dependencies so you can get the code under test. These refactorings are designed to be performed safely without tests so you can get the tests written and then move on to more significant refactorings. The book also does a great job of tackling the mechanics of writing the tests themselves.

I think the book could have been better named. Ayende says that it should be mandatory reading for people that write code for a living. I agree with him, but the title does not communicate this. In general I found it very readable and relatively quick to get through, and the lessons the book offers are profound.

So the obvious question is whether it has changed the way I’ve been writing code. Well unfortunately, I wrote a bunch of legacy code just last week! By night I revel in the freedom that my unit tests give me as I work on Fluent NHibernate, but by day I continue to work in a manner that Uncle Bob would consider unprofessional. Why?

Unfortunately the book doesn’t have a chapter called “I’m all alone, nobody else is convinced that writing unit tests is worthwhile. Is it worth starting if its just me doing it?”. Nor does it have a “This is just a quick fix for someone else’s broken code, I’ll write tests when the –real- work begins” chapter (its a weak argument but I’ve found it an easy trap to fall into). The closest the book comes is the very last FAQ chapter: “We feel overwhelmed. It isn’t going to get any better”. But at less than 2 pages, it didn’t quite deliver what I needed to hear.

I’m finding it difficult to take that first step and add that 55th project to the solution (yeah…) so I can write some tests. Part of it is procrastination, but part of it is fear. I believe these ideas have value and I don’t want to screw it up. But simply “waiting until the time is right” is the refrain of the procrastinator.

This makes me feel that Working with Legacy Code is a great book, but not an entirely complete package. It gives you the tools and techniques but assumes that the reader can simply read it and run with it. Michael developed these techniques as he worked with teams that heeded his advice and were prepared to follow his lead. A piece of the puzzle is missing because Michael has been the consultant for so long.

Maybe this criticism is unfair. People can write books full of advice, but its up to the reader to start putting that advice into practice. A new work week begins tomorrow, perhaps I’ll add that 55th project before I do anything else tomorrow morning.

Supporting multiple NHibernate versions in Fluent NHibernate semantic model

2009-03-09T16:30:00.000+11:00

My Fluent NHibernate semantic model rewrite is designed to support multiple versions of NHibernate simultaneously. At the moment, I support NH 2.0.1GA and 2.1.0.1001 (this was a trunk snapshot). My goal is to support the latest official release and to keep as up to date with the trunk as possible; time will tell how well this pans out.

The semantic model rewrite makes heavy use of classes that are generated from the NH mapping schema. These classes are all prefixed with Hbm, so I am in the habit of calling them “Hbm*” classes. Here is some example code that builds a HbmKey representation of a KeyMapping:

public override void ProcessKey(KeyMapping keyMapping)
{
    _hbm = new HbmKey();

    if (keyMapping.Attributes.IsSpecified(x => x.Column))
        _hbm.column1 = keyMapping.Column;

    if (keyMapping.Attributes.IsSpecified(x => x.ForeignKey))
        _hbm.foreignkey = keyMapping.ForeignKey;

    if (keyMapping.Attributes.IsSpecified(x => x.PropertyReference))
        _hbm.propertyref = keyMapping.PropertyReference;

    if (keyMapping.Attributes.IsSpecified(x => x.CascadeOnDelete))
        _hbm.SetCascadeOnDelete(keyMapping.CascadeOnDelete);
}

Because the NH mapping schema changes from version to version, the public interface for these classes also changes from version to version. See that “column1” property? Its entirely possible it was called “column” in an earlier version of NH. Obviously, if it were to change back to “column” tomorrow, this code would no longer compile. Given this, how can Fluent NH hope to simultaneously support multiple NH versions? The answer is to put any version specific code in a separate assembly.

Today I will fix a NH2.1 incompatibility that I introduced a few days ago when adding the ability to specify the column name for a property. Here is the code I wrote while working against NH2.0.1:

public override void ProcessProperty(PropertyMapping propertyMapping)
{
    _hbm = new HbmProperty();
    _hbm.name = propertyMapping.Name;

    if(propertyMapping.Attributes.IsSpecified(x => x.IsNotNullable))
        _hbm.SetNotNull(propertyMapping.IsNotNullable);

    if (propertyMapping.Attributes.IsSpecified(x => x.Length))
        _hbm.length = propertyMapping.Length.ToString();

    if (propertyMapping.Attributes.IsSpecified(x => x.ColumnName))
        _hbm.column1 = propertyMapping.ColumnName;
}

The very last line is the one to watch here. You can see its setting the “column1” property. This worked fine against NH2.0.1 but when I ran my rake script to switch over to NH2.1 today, this code no longer compiled - the property is now called “column”. As I mentioned above, my strategy for dealing with this problem is to use version specific assemblies. Here is the Fluent NH solution:

The two “Versioning” projects are where the version specific code goes – they each reference their own version of NHibernate. Each project contains the same set of extensions methods, each method implemented slightly differently depending on the versioning requirements. The two projects share the same namespace and output an assembly with the same name (FluentNHibernate.Versioning) and to the same location. Neither project is included in the default build configuration, so they have to be built explicitly. The act of building one of these versioning projects will make it “active” because the assembly is output to the same location that the FluentNHibernate project is referencing.

With the background out of the way, lets fix the problem with with “column1” property on HbmProperty. First I open the Versioning.NH20 project, find the HbmPropertyExtensions and add an extension method:

public static class HbmPropertyExtensions
{
    ...

    public static void SetColumn(this HbmProperty hbmProperty, string column)
    {
        hbmProperty.column1 = column;
    }
}

I then modify the code to call the extension method:

if (propertyMapping.Attributes.IsSpecified(x => x.ColumnName))
    _hbm.SetColumn(propertyMapping.ColumnName);

I compile the Versioning.NH20 project to make sure its active and run my tests. I already have a test that is verifying this implementation – here it is:

[Test]
public void Should_write_the_attributes()
{
    var testHelper = new HbmTestHelper<PropertyMapping>();
    testHelper.Check(x => x.Name, "test").MapsToAttribute("name");
    testHelper.Check(x => x.Length, 50).MapsToAttribute("length");
    testHelper.Check(x => x.IsNotNullable, true).MapsToAttribute("not-null");
    testHelper.Check(x => x.ColumnName, "thecolumn").MapsToAttribute("column"); <--- HERE
    var writer = new HbmPropertyWriter();
    testHelper.VerifyAll(writer);
}

Because this test verifies that a certain property is written to the correct xml attribute, it works for both versions of NH. Regardless of what the property is called on the Hbm class, its written to the “column” attribute.

The tests all pass, so I switch to NH2.1 using my rake script and move to the Versioning.NH21 project. Again, I add an extension method:

public static class HbmPropertyExtensions
{
    ...

    public static void SetColumn(this HbmProperty hbmProperty, string column)
    {
        hbmProperty.column = column;            
    }
}

This looks almost the same as the code above, but notice that the “1” is gone. I compile the Versioning.NH21 project to make sure its active and run the tests. They all pass!

So far, all the versioning issues I’ve ran into were easily fixed like the one above. Lets hope they are all this simple!

Fluent NHibernate semantic model: Visitors

2009-02-21T17:09:00.000+11:00

My work-in-progress semantic model based version of Fluent NHibernate makes heavy use of the visitor pattern. Currently, the visitor implementation is there to serve two purposes:

Facilitate the construction of a Hbm* representation of the mapping model. Hbm* refers to the set of classes found in the NHibernate.Cfg.MappingSchema namespace that are generated from the NHibernate mapping schema. My version of Fluent NHibernate communicates with NHibernate by serializing the Hbm* representation to xml.
Enable powerful, user-defined conventions that walk the mapping model and make changes. The NamingConvention class is a very simple example of this – it takes mapping model instances and sets their Name property based on reflected data such as the System.Type or the PropertyInfo.

Lets begin by looking at the implementation of AcceptVisitor for the root of the mapping model – HibernateMapping:

public override void AcceptVisitor(IMappingModelVisitor visitor)
{
    visitor.ProcessHibernateMapping(this);

    foreach (var classMapping in Classes)
        visitor.Visit(classMapping);
}

This is reasonably straightforward. The HibernateMapping tells the visitor to first process a HibernateMapping instance, and passes itself as the argument. Then it tells the visitor to visit each of the child classes. What the visitor does when its told to visit a ClassMapping is its business, but what it is likely to do is call AcceptVisitor on the ClassMapping:

public override void AcceptVisitor(IMappingModelVisitor visitor)
{
    visitor.ProcessClass(this);            

    if (Id != null)
        visitor.Visit(Id);

    if (Discriminator != null)
        visitor.Visit(Discriminator);

    foreach (var subclass in Subclasses)
        visitor.Visit(subclass);

    base.AcceptVisitor(visitor);
}

This is similar to the previous AcceptVisitor implementation, but its worth noting that at the end, it calls base.AcceptVisitor(visitor). This is necessary because ClassMapping inherits from a common base class (JoinedSubclassMapping and SubclassMapping also inherit from this base class). Here is AcceptVisitor on ClassMappingBase:

public override void AcceptVisitor(IMappingModelVisitor visitor)
{
    foreach (var collection in Collections)
        visitor.Visit(collection);

    foreach (var property in Properties)
        visitor.Visit(property);

    foreach (var reference in References)
        visitor.Visit(reference);
}

Of course – all class mappings, regardless of how they fit into an inheritance hierarchy, can have collections, properties and references (many-to-ones). Its probably not necessary to follow this any further. The important point is that as long as the visitor calls AcceptVisitor when it is told to visit something, then it will make its way along the entire mapping model. To make life easier, I’ve implemented a DefaultMappingModelVisitor class that does precisely this. It has a whole bunch of code that all looks very similar to this:

public override void Visit(PropertyMapping propertyMapping)
{
    propertyMapping.AcceptVisitor(this);
}

public override void Visit(ManyToOneMapping manyToOneMapping)
{
    manyToOneMapping.AcceptVisitor(this);
}

public override void Visit(KeyMapping keyMapping)
{
    keyMapping.AcceptVisitor(this);
}

.. Many more Visit methods

Now you might be looking at this and wondering why this is necessary. Why can’t we skip this completely, and just have AcceptVisitor implementations that will call AcceptVisitor directly like this:

public override void AcceptVisitor(IMappingModelVisitor visitor)
{
    visitor.ProcessHibernateMapping(this);

    foreach (var classMapping in Classes)
        classMapping.AcceptVisitor(visitor); <--- JUST DO THIS??
}

The answer is that the proposed change will work when you want one single visitor instance to visit the entire mapping model. While this works fine for conventions (as you will see in a moment), it does not work so well for building the Hbm representation. I’ll get to that in a second, but lets first take a look at the simpler case of the conventions. Here is a gutted version of the NamingConvention:

public class NamingConvention : DefaultMappingModelVisitor
{
    public Func<MemberInfo, string> DetermineNameFromMember = info => info.Name;
    public Func<Type, string> DetermineNameFromType = type => type.AssemblyQualifiedName;

    public override void ProcessOneToMany(OneToManyMapping oneToManyMapping)
    {
        if (!oneToManyMapping.Attributes.IsSpecified(x => x.ClassName))
        {
            if (oneToManyMapping.ChildType == null)
                throw new ConventionException("Cannot apply the naming convention. No type specified.", oneToManyMapping);
            oneToManyMapping.ClassName = DetermineNameFromType(oneToManyMapping.ChildType);
        }
    }
}

I’ve removed the majority of its implementation for the sake of brevity. As it currently stands, it will walk the entire mapping model (because it inherits from the aforementioned DefaultMappingModelVisitor), and when it encounters a OneToManyMapping, it will attempt to set its ClassName based on the ChildType property. Its worth noting that the full implementation of the NamingConvention class actually handles naming of many other mappings types, such as ClassMappings, ManyToManyMappings, etc. This means that this visitor completely handles the concern of setting the name of mapping model elements for the entire mapping model. This point is important, because the next example is different. As I mentioned before, this visitor implementation would work fine with the previous simplification of having AcceptVisitor directly call AcceptVisitor on the children. Lets now move on to the process of building a Hbm* representation, and examine why the simplification won’t work so well for this case.

I define an interface for classes that build Hbm:

public interface IHbmWriter<T>
{
    object Write(T mappingModel);        
}

Here is an example implementor, a hbm writer that will handle ColumnMappings:

public class HbmColumnWriter : NullMappingModelVisitor, IHbmWriter<ColumnMapping>
{
    private HbmColumn _hbm;

    public object Write(ColumnMapping mappingModel)
    {
        _hbm = null;
        mappingModel.AcceptVisitor(this);
        return _hbm;
    }

    public override void ProcessColumn(ColumnMapping columnMapping)
    {
        _hbm = new HbmColumn();
        _hbm.name = columnMapping.Name;
        
        if(columnMapping.Attributes.IsSpecified(x => x.IsNotNullable))
        {
            _hbm.notnull = columnMapping.IsNotNullable;
            _hbm.notnullSpecified = true;
        }

        if (columnMapping.Attributes.IsSpecified(x => x.Length))
            _hbm.length = columnMapping.Length.ToString();
        
        //etc

}
}

You’ll notice that this class inherits from NullMappingModelVisitor, which is basically a blank implementation of IMappingModelVisitor. It has all the methods, but none of them do anything. So this visitor ONLY knows how to handle ColumnMappings - if its passed to any other type of mapping, it will do nothing. This is certainly a difference approach to the NamingConvention, which actually knew how to set the name for Classes, OneToMany’s, ManyToMany’s and many other mapping model elements. So why does this difference exist? Basically, the job of generating all the Hbm that NHibernate requires is too big for one class. Creating separate classes for generating the appropriate HBM helps make the job more manageable. These classes can then be composed, like so:

public class HbmIdWriter : NullMappingModelVisitor, IHbmWriter<IdMapping>
{
    private readonly IHbmWriter<ColumnMapping> _columnWriter;
    private readonly IHbmWriter<IdGeneratorMapping> _generatorWriter;

    private HbmId _hbm;

    public HbmIdWriter(IHbmWriter<ColumnMapping> columnWriter, IHbmWriter<IdGeneratorMapping> generatorWriter)
    {
        _columnWriter = columnWriter;
        _generatorWriter = generatorWriter;
    }

    public object Write(IdMapping mappingModel)
    {
        _hbm = null; 
        mappingModel.AcceptVisitor(this);
        return _hbm;
    }

    public override void ProcessId(IdMapping idMapping)
    {
        _hbm = new HbmId();

        if(idMapping.Attributes.IsSpecified(x => x.Name))
            _hbm.name = idMapping.Name;
    }

    public override void Visit(ColumnMapping columnMapping)
    {
        var columnHbm = (HbmColumn) _columnWriter.Write(columnMapping);
        columnHbm.AddTo(ref _hbm.column);
    }

    public override void Visit(IdGeneratorMapping generatorMapping)
    {
        var generatorHbm = (HbmGenerator) _generatorWriter.Write(generatorMapping);
        _hbm.generator = generatorHbm;
    }
}

This hbm writer handles IdMappings. IdMappings include one or more columns and a generator, so this writer composes a IHbmWriter<ColumnMapping> and a IHbmWriter<IdGeneratorMapping>. In this way, the task of creating the hbm representation can be managed by a family of visitors that delegate to each other as required.

Finally now, I can return to the previous point of why all the AcceptVisitor implementations call visitor.Visit(child) rather than child.AcceptVisitor(visitor). The former allows the current visitor to see that a different visitor is passed in when calling child.AcceptVisitor(). You can see some of this happening above, in the override for Visit(ColumnMapping) – it asks the IHbmWriter<ColumnMapping> to write the column. The implementation of that method will call columnMapping.AcceptVisitor(this). Thus, the Fluent NHibernate semantic model has an implementation of the visitor pattern that supports both single visitors that visit the entire graph themselves, and families of visitors that collaborate to get a large job done.

Fluent NHibernate semantic model: AttributeStore

2009-02-08T16:34:00.000+11:00

My work to rewrite Fluent NHibernate using a semantic model continues at a reasonable pace. I will admit there is some unconventional stuff in the code base, and much of it deserves explanation. Today I would like to explain AttributeStore<T> - what it is for and how it works. Lets start by taking a look at the model class for the contents of a collection with OneToMany semantics:

public class OneToManyMapping : MappingBase, ICollectionContentsMapping
{
    private readonly AttributeStore<OneToManyMapping> _attributes;

    public OneToManyMapping()
    {
        _attributes = new AttributeStore<OneToManyMapping>();
        _attributes.SetDefault(x => x.ExceptionOnNotFound, true);
    }

    public AttributeStore<OneToManyMapping> Attributes
    {
        get { return _attributes; }
    }

    public string ClassName
    {
        get { return _attributes.Get(x => x.ClassName); }
        set { _attributes.Set(x => x.ClassName, value); }
    }

    public bool ExceptionOnNotFound
    {
        get { return _attributes.Get(x => x.ExceptionOnNotFound); }
        set { _attributes.Set(x => x.ExceptionOnNotFound, value); }
    }
}

As you can see, I am doing something unusual in some of the getters and setters. Basically, I am storing the values of certain properties in a dictionary, and these values are keyed on the name of the property you use to access them. Its very easy to add new attributes, I use this Resharper live template:

public $ReturnType$ $PropertyName$
{
    get { return $_attributes$.Get(x => x.$PropertyName$); }
    set { $_attributes$.Set(x => x.$PropertyName$, value); }
}

This approach allows me to write code that asks questions about properties beyond simply “what is the value?”. Here is an example from the NamingConvention class:

public override void ProcessOneToMany(OneToManyMapping oneToManyMapping)
{
    if (!oneToManyMapping.Attributes.IsSpecified(x => x.ClassName))
    {
        if (oneToManyMapping.ChildType == null)
            throw new ConventionException("Cannot apply the naming convention. No type specified.", oneToManyMapping);
        oneToManyMapping.ClassName = DetermineNameFromType(oneToManyMapping.ChildType);
    }
}

This convention walks the mapping model, naming mappings based on the assigned Type or MemberInfo. In this example, if the ClassName property for the OneToManyMapping hasn’t been specified explicitly, then the NamingConvention uses the ChildType property to set the ClassName. If the user has set the ClassName themselves, then I don’t want the NamingConvention to overwrite that, so I ask the question “Is the ClassName property specified?”. If the ClassName property was just implemented as an autoproperty, I would probably have to check if it was null. But what if the property was a bool? Make it a nullable bool? Then I would have nasty if(blah.HasValue) code in various places. Yuck!

Here is another example, this time from the class that creates a HbmOneToMany instance based on my OneToManyMapping:

public override void ProcessOneToMany(OneToManyMapping oneToManyMapping)
{
    _hbmOneToMany = new HbmOneToMany();
    _hbmOneToMany.@class = oneToManyMapping.ClassName;

    if(oneToManyMapping.Attributes.IsSpecified(x => x.ExceptionOnNotFound))
    {
        _hbmOneToMany.SetNotFound(oneToManyMapping.ExceptionOnNotFound);
    }
}

This code always sets the @class field on the HbmOneToMany, but it won’t always call SetNotFound. It only calls SetNotFound if the the ExceptionOnNotFound property was specified. The point of this behaviour is to only generate the xml the user desires. It is not mandatory to set the not-found attribute on a one-to-many element, so why write it if the user hasn’t specified it?

As well as being able to ask questions about the properties, I also wanted a convenient way to copy them. The next code sample is the code for OneToManyPart. This class is part of the fluent interface for FluentNHibernate. It builds up information on the collection being mapped, and builds the appropriate collection when ResolveCollectionMapping() is called (obviously the IsInverse property is the only value copied at the moment, but that will change as the supported functionality grows):

public class OneToManyPart<PARENT, CHILD> : IDeferredCollectionMapping
{
    private readonly PropertyInfo _info;
    private readonly AttributeStore<ICollectionMapping> _attributes;

    private Func<ICollectionMapping> _collectionBuilder;

    public OneToManyPart(PropertyInfo info)
    {
        _info = info;
        _attributes = new AttributeStore<ICollectionMapping>();
        AsBag();   
    }

    public OneToManyPart<PARENT, CHILD> AsBag()
    {
        _collectionBuilder = () => new BagMapping();
        return this;
    }

    public OneToManyPart<PARENT, CHILD> AsSet()
    {
        _collectionBuilder = () => new SetMapping();
        return this;
    }

    public OneToManyPart<PARENT, CHILD> IsInverse()
    {
        _attributes.Set(x => x.IsInverse, true);
        return this;
    }

    ICollectionMapping IDeferredCollectionMapping.ResolveCollectionMapping()
    {
        var collection = _collectionBuilder();       
        _attributes.CopyTo(collection.Attributes);

        collection.PropertyInfo = _info;            
        collection.Key = new KeyMapping();
        collection.Contents = new OneToManyMapping {ChildType = typeof (CHILD)};

        return collection;
    }

}

The relevant lines are at the beginning of ResolveCollectionMapping(). Once the collection instance is created, the attributes collected in the _attributes field are copied to the AttributeStore for the new collection instance.

Well that is probably enough examples of why I am using this pattern. Now I want to run through the implementation. Lets start with AttributeStore<T>:

public class AttributeStore<T>
{
    private readonly AttributeStore _store;

    public AttributeStore()
        : this(new AttributeStore())
    {

    }

    public AttributeStore(AttributeStore store)
    {
        _store = store;
    }

    public U Get<U>(Expression<Func<T, U>> exp)
    {
        return (U)(_store[GetKey(exp)] ?? default(U));
    }

    public void Set<U>(Expression<Func<T, U>> exp, U value)
    {
        _store[GetKey(exp)] = value;
    }

    public void SetDefault<U>(Expression<Func<T, U>> exp, U value)
    {
        _store.SetDefault(GetKey(exp), value);
    }   

    public bool IsSpecified<U>(Expression<Func<T, U>> exp)
    {
        return _store.IsSpecified(GetKey(exp));
    }

    public void CopyTo(AttributeStore<T> target)
    {
        _store.CopyTo(target._store);
    }

    private string GetKey<U>(Expression<Func<T, U>> exp)
    {
        PropertyInfo info = ReflectionHelper.GetProperty(exp);
        return info.Name;
    }
}

As you can see, AttributeStore<T> is a generic wrapper for a non-generic class called AttributeStore. The purpose of AttributeStore<T> is to expose get and set methods that take a lambda, and convert that lambda into a dictionary key, and then delegate to an inner attribute store using that dictionary key. Finally, here is the code for the non-generic attribute store:

public class AttributeStore
{
    private readonly IDictionary<string, object> _attributes;
    private readonly IDictionary<string, object> _defaults;

    public AttributeStore()
    {
        _attributes = new Dictionary<string, object>();
        _defaults = new Dictionary<string, object>();
    }

    public object this[string key]
    {
        get
        {
            if (_attributes.ContainsKey(key))
                return _attributes[key];
            
            if (_defaults.ContainsKey(key))
                return _defaults[key];

            return null;
        }
        set { _attributes[key] = value; }
    }

    public bool IsSpecified(string key)
    {
        return _attributes.ContainsKey(key);
    }

    public void CopyTo(AttributeStore store)
    {
        foreach (KeyValuePair<string, object> pair in _attributes)
            store._attributes[pair.Key] = pair.Value;
    }

    public void SetDefault(string key, object value)
    {
        _defaults[key] = value;
    }
}

AttributeStore is just a wrapper for a couple of dictionaries, one for the values that have been specified, and one for the default values. That’s pretty much all there is to it.

I see AttributeStore<T> as a superior alternative to the weakly typed bag of attributes approach that Fluent NHibernate currently uses.There are no magic strings, and its all strongly typed. Its more powerful than just using properties with backing fields, and it requires pretty much the same amount of code. Sure, its much slower, but performance is not really a concern for Fluent NHibernate. I can see myself using this pattern on other projects.

I’m starting to Git it

2009-02-02T09:52:00.000+11:00

For the last week I have been experimenting with Git. Git is a relatively new source code management tool that is set apart from the SCM’s you are likely to be familiar with because it is distributed rather than centralised. I’m not going to sit here and harp on about all the reasons why this approach has merit when there are plenty of resources available that will do a much better job:

Nor am I going to teach you the fundamentals of how git works and how to use it, again for similar reasons:

Today I just want to talk about what I had to do to start using Git effectively for my work on Fluent NHibernate (which is hosted in Subversion on Google Code). Basically, I wanted a local repository for Fluent NH. I wanted to be able to commit smaller chunks of work to the local repository and then commit to SVN once I was happy with it. I also wanted to be able to branch, rollback, view history, etc all without touching the SVN repository. Git gave me these capabilities.

Here are the steps I followed to get up and running with Git and a Google Code hosted project:

Installed msysgit. I installed version 1.5.5 because I heard that the later versions had problems with git-svn (the tool for bridging Git and Subversion). I have no idea if this is actually the case. When installing, I chose the option that added git to my path environment variable. This allowed me to use Git in the windows command line, but there was a hitch. Every time I ran git from the windows command line, it would close the command line. I followed the fix here here to solve it.
Configure git. I set up a SSH key and my details, as described here. I also set the autocrlf option to false – this seems to minimise problems with line endings. To do so I used the command:

git config –global core.autocrlf false
Used git-svn to create a local clone. Initially I ran into some difficulty because I pulled the repository down using http – this caused problems later when I tried to commit and could not authenticate properly. Using https when cloning the repository fixed the problem. Another issue to be aware of when using git-svn is that unlike the rest of Git, git-svn is very slow. I had to leave git-svn working away for over 20 minutes when I first pulled down my branch of Fluent NHibernate. Later I learned that you can tell git-svn to clone a revision rather than the entire repository, so I used this functionality when I pulled the second time (using https instead of http). The command I used was:

git svn clone https://fluent-nhibernate.googlecode.com/svn/branches/pb-rewrite --username "paul.batum" –r234

My Google Code username is “paul.batum”. I was prompted for my password the first time, but then Git seemed to remember it from then on. The –r234 switch specified a particular revision to get. If I was prepared to wait, I would have omitted the flag and pulled the entire history into my local repository, but patience got the better of me.
Added a .gitignore file to specify which types of files should not be tracked by Git. I grabbed the .gitignore file from an a .NET project hosted in GitHub called Machine. I then made a few modifications, copied into my new repository and checked it in:

git add .gitignore
git commit –m “Added ignore file”

You can view my ignore file here.
Worked with the local repository. My git repository was ready to use. I worked on the Fluent NH code for a while, using the git gui (run simply by using the git gui command) to make small commits.
Rebased my local repository against the SVN repository. Before I commit back to the SVN repository, I need to merge any changes that have been made since I cloned the repository. Git offers merge functionality, but it also offers something slightly different called a rebase. In a nutshell, the difference between a merge and a rebase is that a merge will interleave your changes with everyone else’s changes. A rebase will take each of your changes, and apply them all sequentially after everyone else’s changes. You can read a better explanation here. The rebase command was straightforward:

git svn rebase
Checked the state of my repository. I wanted to see what my repository looked like after the rebase. A commit viewer called gitk is installed as part of msysgit, to run it with all branches displayed the command is:

gitk –-all
Commited my changes to the SVN repository. With the rebase complete, my local commits were ready to be pushed to the main repository on Google Code. To commit my changes back to SVN, I ran the following command:

git svn dcommit –-username paul.batum

The dcommit command pushes my commits to the SVN repository one at a time. This means that the rich history that was created locally by my small commits is preserved in the SVN history. There are some options for “squashing” all of the local changes so that they are all represented by a single commit, but I am yet to explore those.

I am still a total Git newbie. But hopefully this guide will save some hair pulling for other windows developers that decide to learn git by using it locally for their SVN hosted projects.

Refactoring Towards the Y Combinator: Part 6

2009-01-12T23:55:00.002+11:00

This is a multi-part series. Part 1. Part 2. Part 3. Part 4. Part 5. Part 6.

This is the final part of my series on the Y combinator. By the end of part 5, the bulk of the work was done. All I have to do today is generalize it, clean it up and make it look pretty. Here is the code from part 5:

public class Solution09 : ISolution
    {
        public Factorial MakeFactorialFunction()
        {
            HigherOrderFunction<Factorial> algorithm = (Factorial f) =>
            {
                return (int x) =>
                {
                    return x < 2 ? 1 : x * f(x - 1);
                };
            };

            SelfApplicable<HigherOrderEvaluator<Factorial>> factorial = (SelfApplicable<HigherOrderEvaluator<Factorial>> self) =>
            {
                return (HigherOrderFunction<Factorial> alg) =>
                {
                    return (int x) =>
                    {
                        return alg(self(self)(alg))(x);
                    };
                };
            };
            return factorial(factorial)(algorithm);
        }
    }

I claimed that the factorial function, as it is defined here, is a version of the Y combinator. Indeed if you take a look at it, you will see that it really doesn’t have anything to do with calculating factorials anymore – that code has long since been moved into the “algorithm” function. But the signature of the function still mentions factorials, specifically the Factorial delegate. To get my definition for the Y combinator into a more usable state, I can replace usages of the Factorial delegate with Func<int,int>. Later on, I’ll be able to define a generic version so it can even be used for functions that take and compute a double, or string, or whatever. However when I make this change, I still need to return a Factorial (because my test harness requires the MakeFactorialFunction method to return a Factorial delegate). To get around this I will use an earlier trick of returning a lambda that can be cast as a Factorial delegate:

/// <summary>    
/// Its possible to make a generic version of the Y combinator for application to functions that take 1 argument and return a value of the same type.
/// Unfortunately we cannot continue to use the Factorial delegate if we want to make this generic version.
/// We rename the functions to better represent their purpose (factorial becomes Y, algorithm becomes factorial).
/// We can't just return Y(Y)(factorial)(x) because that will return a Func<int,int> but this method is supposed to return a Factorial. Although
/// they are basically the same thing, a conversion cannot be made. Therefore I have to return a lambda that calls Y(Y)(factorial)(x).
/// </summary>
public class Solution10 : ISolution
{
    public Factorial MakeFactorialFunction()
    {
        HigherOrderFunction<Func<int, int>> factorial = (Func<int, int> f) =>
        {
            return (int x) =>
            {
                return x < 2 ? 1 : x*f(x - 1);
            };
        };
        
        SelfApplicable<HigherOrderEvaluator<Func<int, int>>> Y =
            (SelfApplicable<HigherOrderEvaluator<Func<int, int>>> self) =>
            {
                return (HigherOrderFunction<Func<int, int>> alg) =>
                {
                    return (int x) =>
                    {
                        return alg(self(self)(alg))(x);
                    };
                };
            };
        
        return x =>
        {
            return Y(Y)(factorial)(x);
        };
    }
}

I can now make Y generic by moving it into its own generic class:

/// <summary>
/// Move Y into its own class.
/// </summary>
public class Solution11 : ISolution
{
    public Factorial MakeFactorialFunction()
    {
        HigherOrderFunction<Func<int, int>> factorial = (Func<int, int> f) =>
        {
            return (int x) =>
            {
                return x < 2 ? 1 : x * f(x - 1);
            };
        };

        return x =>
        {                
            return YCombinator<int>.Y(YCombinator<int>.Y)(factorial)(x);
        };
    }

    private static class YCombinator<T>
    {
        public static SelfApplicable<HigherOrderEvaluator<Func<T, T>>> Y =
            (SelfApplicable<HigherOrderEvaluator<Func<T, T>>> self) =>
            {
                return (HigherOrderFunction<Func<T, T>> alg) =>
                {
                    return (T x) =>
                    {
                        return alg(self(self)(alg))(x);
                    };
                };
            };
    }
}

There is some ugliness with calling Y on itself now, so I add a “ApplyY” helper to the YCombinator class to make this part easier. I let Resharper help me use a more terse syntax for the lambdas, and this is the result:

public class YCombinator<T>
{
    private static readonly SelfApplicable<HigherOrderEvaluator<Func<T, T>>> Y =
        self => algorithm => t => algorithm(self(self)(algorithm))(t);

    public static readonly HigherOrderEvaluator<Func<T, T>> ApplyY = Y(Y);

}

I’ve avoided using the terse lambda syntax up until now because I think it would have made comprehending the individual steps more difficult. I can use ApplyY like this:

return YCombinator<int>.ApplyY(factorial)(10);

Here is my final implementation for this entire exercise, utilizing the above class:

/// <summary>
/// This is the final implementation.
/// The Y combinator has been moved to a separate file. 
/// The factorial algorithm has been pushed to a static member and condensed.
/// </summary>
public class Solution12 : ISolution
{
    private static readonly HigherOrderFunction<Func<int, int>> factorial =
                    f => x => x < 2 ? 1 : x * f(x - 1);

    public Factorial MakeFactorialFunction()
    {
        return x => YCombinator<int>.ApplyY(factorial)(x);
    }

    // Example of using Y without any need for the Factorial delegate:
    public int CalculateFactorialOf10()
    {
        return YCombinator<int>.ApplyY(factorial)(10);            
    }

}

Now lets test my implementation of the Y combinator by using it to calculate Fibonacci numbers:

public static class Fibonacci
{
    private static readonly HigherOrderFunction<Func<int, int>> fibonacci =
        f => x => x < 3 ? 1 : f(x - 1) + f(x - 2);

    public static int Calculate(int nthNumber)
    {
        return YCombinator<int>.ApplyY(fibonacci)(nthNumber);
    }
}

Its horribly inefficient, but it works:

Console.WriteLine(Fibonacci.Calculate(10));

>> 55

So there you have it: the Y combinator implemented in C#, derived via many gradual refactorings. This implementation still has some limitations. For example, it won’t support a recursive algorithm that takes two arguments. You could of course modify the Y combinator class to support this, but because of the strongly typed nature of C#, it seems very difficult to make a definition of Y that could be applied to an algorithm with ANY signature. If you are interested in exploring the code that I provided in this series, you can download it here.

I really enjoyed this exercise and I would definitely encourage other programmers that are weak at functional programming to have a go at it. If you really know this stuff and my clumsy explanations made you cringe, please leave a comment! If you were following along with the series and got lost or stuck at some point, again, please comment! Practice makes perfect, but some constructive criticism can really help too. Thanks!

Refactoring Towards the Y Combinator: Part 5

2009-01-10T21:28:00.001+11:00

This is a multi-part series. Part 1. Part 2. Part 3. Part 4. Part 5. Part 6.

Here is the state of affairs at the end of part 4:

public delegate Factorial HigherOrderFactorial(Factorial factorial);

public class Solution07 : ISolution
{        
    public Factorial MakeFactorialFunction()
    {
        HigherOrderFactorial algorithm = (Factorial f) =>
        {
            return (int x) =>
                {
                    return x < 2 ? 1 : x * f(x - 1);
                };
        };

        SelfApplicable<Factorial> factorial = (SelfApplicable<Factorial> self) =>
        {
            return (int x) =>
            {
                return algorithm(self(self))(x);
            };
        };

        return factorial(factorial);
    }
}

As I mentioned at the end of part 4, the problem with this implementation is that the factorial function creates a closure, capturing the algorithm variable. I fixed a similar problem in step 2 – in this case its fixed by having the factorial function accept ‘algorithm’ as an argument. Unfortunately my first attempt at this will not compile:

SelfApplicable<Factorial> factorial = (HigherOrderFactorial alg, SelfApplicable<Factorial> self) =>
{
    return (int x) =>
    {
        return alg(alg, self(self))(x);
    };
};

return factorial(algorithm, factorial);

Its not that simple, because it breaks the signature of the SelfApplicable delegate. So I will have to define a new delegate. To figure out what to call it, lets take a look at its signature:

public delegate Factorial SomeDelegate(SomeDelegate self, HigherOrderFactorial algorithm);

So it takes itself, and a HigherOrderFactorial, and its returns a Factorial. Well in that case isn’t it fair to say that it is a “higher order evaluator”? Its also self applying, so lets call it SelfApplyingHigherOrderFactorialEvaluator:

public delegate Factorial SelfApplyingHigherOrderFactorialEvaluator(SelfApplyingHigherOrderFactorialEvaluator self, HigherOrderFactorial algorithm);

/// <summary>
/// We can make the algorithm an argument to the factorial function. Unfortunately its not a particularly simple refactoring, because of the
/// self calling nature of the factorial function. We are forced to define a new self applying delegate that accepts the higher order function.
/// </summary>
public class Solution08 : ISolution
{        
    public Factorial MakeFactorialFunction()
    {
        HigherOrderFactorial algorithm = (Factorial f) =>
        {
            return (int x) =>
            {
                return x < 2 ? 1 : x * f(x - 1);
            };
        };

        SelfApplyingHigherOrderFactorialEvaluator factorial =
            (SelfApplyingHigherOrderFactorialEvaluator self, HigherOrderFactorial alg) =>
        {
            return (int x) =>
            {                            
                return alg(self(self, alg))(x);
            };
        };

        return factorial(factorial, algorithm);
    }
}

Phew! I was excited when this one worked – I could smell blood in the air. The body of that factorial function is starting to look pretty close to the Y combinator. Now I don’t know about you, but that factorial function is looking kind of hungry, so lets give it some curry! By currying it, I will have the opportunity to go back to using the SelfApplicable delegate. This is a tricky step, and I’m not quite sure how to break it down. I can start off by looking at the existing signature:

public delegate Factorial SelfApplyingHigherOrderFactorialEvaluator(SelfApplyingHigherOrderFactorialEvaluator self, HigherOrderFactorial algorithm);

I called this thing an evaluator, because it takes a HigherOrderFactorial, and it returns a Factorial. Essentially, it evaluates the higher order function which results in a normal order one. I could create a generic delegate to represent an evaluation operation, but to do so I would need to first create a generic delegate for representing a higher order function. Well that should be pretty straightforward:

public delegate T HigherOrderFunction<T>(T function);

The HigherOrderFunction delegate could be used instead of the HigherOrderFactorial delegate. Here is ‘algorithm’ modified to use the HigherOrderFunction delegate:

HigherOrderFunction<Factorial> algorithm = (Factorial f) =>
{
    return (int x) =>
    {
        return x < 2 ? 1 : x * f(x - 1);
    };
};

Now that I have a generic delegate for higher order functions, I can also create a generic delegate for their evaluation:

public delegate T HigherOrderEvaluator<T>(HigherOrderFunction<T> higherFunction);

Lets try to get comfortable with this before we move on. Lets say I used it like so:

HigherOrderEvaluator<Factorial> evaluator;

Then this is the same as (formatted for clarity):

Func<
    HigherOrderFunction<Factorial>, 
    Factorial
    > evaluator;

Which is the same as:

Func<
    Func<Factorial, Factorial>, 
    Factorial
    > evaluator;

I could expand out those Factorial delegates, but I do not think that is necessary. It would just cause an <int> explosion. Now that the HigherOrderEvaluator is defined and explained, I have the necessary tools to discuss how the SelfApplicableHigherOrderFactorialEvaluator is going to be replaced. Again, to make it easier to eyeball the changes, here it is:

public delegate Factorial SelfApplyingHigherOrderFactorialEvaluator(SelfApplyingHigherOrderFactorialEvaluator self, HigherOrderFactorial algorithm);

This delegate can be retired, because I can use this instead:

SelfApplicable<HigherOrderEvaluator<Factorial>>

BUT! I can only make that replacement if I curry the factorial method, as was discussed before. SelfApplicable only takes one argument, while you can see that the SelfApplyingHigherOrderFactorialEvaluator above takes two. Currying will allow me to reduce it to one argument, so I get to use SelfApplicable. Here is what it looks like:

public delegate T HigherOrderFunction<T>(T function);
public delegate T HigherOrderEvaluator<T>(HigherOrderFunction<T> higherFunction);

/// <summary>
/// Once again, we curry. This time its the factorial function again.
/// Believe it or not, the second function defined here is the Y combinator. Unfortunately, in this form it is specific to the factorial method..
/// </summary>
public class Solution09 : ISolution
{
    public Factorial MakeFactorialFunction()
    {
        HigherOrderFunction<Factorial> algorithm = (Factorial f) =>
        {
            return (int x) =>
            {
                return x < 2 ? 1 : x * f(x - 1);
            };
        };


        SelfApplicable<HigherOrderEvaluator<Factorial>> factorial = (SelfApplicable<HigherOrderEvaluator<Factorial>> self) =>
        {
            return (HigherOrderFunction<Factorial> alg) =>
            {
                return (int x) =>
                {
                    return alg(self(self)(alg))(x);
                };
            };
        };
        return factorial(factorial)(algorithm);
    }
}

I jumped out of my chair when this worked. I did a lap of my apartment, punching at the air. Yes, I am really that lame. ANYWAY…

The function that is still called ‘factorial’ is actually a version of the Y combinator specifically typed for being applied to factorials. In the final post for this series I will make it more general, clean it up, demonstrate it being used for Fibonacci and post the full source code.

Refactoring Towards the Y Combinator: Part 4

2009-01-09T20:25:00.001+11:00

This is a multi-part series. Part 1. Part 2. Part 3. Part 4. Part 5. Part 6.

I finished the previous post with the following code:

public delegate T SelfApplicable<T>(SelfApplicable<T> self);

public class Solution05 : ISolution
{
    public Factorial MakeFactorialFunction()
    {
        SelfApplicable<Factorial> factorial = (SelfApplicable<Factorial> self) => 
        {
            return (int x) =>
            {
                return x < 2 ? 1 : x * self(self)(x - 1);
            };
        };
        
        return factorial(factorial);
    }
}

The next step, as I mentioned previously, is to attempt to remove the self(self) business from the factorial algorithm. The self calling aspect is really a technical concern, while the algorithm is more like business logic – it makes sense to want to separate the two. To do this, I’m going to apply a variation on the Extract Method refactoring. I’ll define the factorial algorithm using a new RecursiveFactorial delegate, and let the existing factorial function call it:

public delegate int RecursiveFactorial(int x, Factorial f);

/// <summary>
/// Lets try to seperate the algorithm definition for factorial from the infrastructure that is applying the recursion.
/// I extract the bit that calculates the factorial as a seperate function, and call it "algorithm". The existing factorial function now calls
/// the algorithm, applying itself to itself as it does.
/// </summary>
public class Solution06 : ISolution
{        
    public Factorial MakeFactorialFunction()
    {
        RecursiveFactorial algorithm = (int x, Factorial f) =>
        {
            return x < 2 ? 1 : x * f(x - 1);
        };

        SelfApplicable<Factorial> factorial = (SelfApplicable<Factorial> self) =>
        {
            return (int x) =>
            {
                return algorithm(x, self(self));
            };
        };

        return factorial(factorial);
    }
}

If you compare the two versions, you should be able to see that I have replaced the “return x < 2…” line of code with a call to “algorithm”, but I left the self(self) part where it was. The two concerns are seperated. But the RecursiveFactorial delegate should look familiar to you. Its sort of like my old friend, the SelfCallingFactorial, except it doesn’t seem to call itself, it just calls the factorial function you pass it. The funny thing is that it IS calling itself. Suprised? Perhaps I can help..

At the last line of the function, I return the result of evaluating the factorial function, passing in itself as an argument. I will try to expand this out by performing substitutions:

           
            // Redefine factorial to use more compact syntax.
            factorial = self => x => algorithm(self(self))(x);

            // This is the line of code to expand.
            return factorial(factorial);

            // Substitute the body of factorial in, replacing the self parameter with factorial
            return x => algorithm(factorial(factorial))(x);            

            // If you look inside, you can see that the line we just substituted has another factorial(factorial). Lets substitute that one too.
            // I will have to rename the integer parameter when I do so, to avoid a clash. I'll call it x1.
            return x => algorithm(x1 => algorithm(factorial(factorial))(x1))(x);

            // Whoops! That pesky factorial(factorial) has appeared again! Substitute, substitute!
            return x => algorithm(x1 => algorithm(x2 => algorithm(factorial(factorial))(x2))(x1))(x);

            // Is there no end in sight?

No, there is not. Doing it this way, it looks like I am stuck in some sort of infinite loop, but this is because I’ve expanded the code incorrectly. The first few substitutions are fine – its when I attempted to expand this line that I made a mistake:

return x => algorithm(x1 => algorithm(factorial(factorial))(x1))(x);

The point to notice about this line is that the factorial(factorial) is inside the body of a lambda, being passed as an argument. It will only be evaluated if x is >= 2. If I called the function this line returns with the argument of 1, then that factorial(factorial) part will never be called. I would like to show you the correct expansion of this line but I struggled to get an expansion that compiled properly. Perhaps it would suffice to say that the next step would be to expand the algorithm call, rather than the factorial call. Hopefully this expansion discussion has illuminated the self calling nature of the solution, but also explained how an infinite loop is avoided.

Getting back on track, the reason why I pointed out that RecursiveFactorial bares some resemblance to SelfCallingFactorial is because I intend to repeat an operation I performed in part 3; I want to apply the currying technique to ‘algorithm’. I will define yet another delegate to represent the curried version of algorithm and call it HigherOrderFactorial. Why “higher order”? Because the curried version accepts a Factorial function and returns a Factorial function – it operates on functions rather than operating on integers:

public delegate Factorial HigherOrderFactorial(Factorial factorial);

/// <summary>
/// Apply the currying techinque again, this time to algorithm, we arrive at a higher order function. 
/// Now algorithm takes a factorial function, and returns a factorial function.
/// </summary>
public class Solution07 : ISolution
{        
    public Factorial MakeFactorialFunction()
    {
        HigherOrderFactorial algorithm = (Factorial f) =>
        {
            return (int x) =>
                {
                    return x < 2 ? 1 : x * f(x - 1);
                };
        };

        SelfApplicable<Factorial> factorial = (SelfApplicable<Factorial> self) =>
        {
            return (int x) =>
            {
                return algorithm(self(self))(x);
            };
        };

        return factorial(factorial);
    }
}

If you take a look at the changes made to ‘algorithm’ in this step, you will see that they are really quite similar to the changes made in Part 3, where the factorial function was curried. Of course, when I modified the signature of ‘algorithm’, I also had to modify the call to it:

This should be really familiar. Go back and reread part 3 if you are not comfortable with this transformation.

The next step is to address the fact that ‘algorithm’ is a captured variable inside the factorial closure. It would be better to pass in the algorithm as an argument to the factorial function. I will tackle this in the next post.

Refactoring Towards the Y Combinator: Part 3

2009-01-08T12:48:00.003+11:00

This is a multi-part series. Part 1. Part 2. Part 3. Part 4. Part 5. Part 6.

I would like to begin this post with an explanation of a technique called currying. Currying is a mechanism that allows a function that takes multiple arguments to be converted to a function that takes only a single argument. I will be using it today, but it would probably be best to look at currying in a simpler context before it is applied to the factorial scenario. I’ve constructed a simple example of currying based on adding two numbers. The inline comments should explain what is going on. Brief disclaimer: currying is another one of those theoretical computer sciency concepts that I’ve understood just enough to get by. If my explanation sucks, please leave a comment so I can fix it.

// The addition function takes two integers, and returns the result of adding them together.
Func<int, int, int> add = (x, y) => x + y;
int five = add(2, 3);

// If you often needed to add two to something, you could explicitly define a function that does so.
// It would only need to take one argument.
Func<int, int> addTwo = x => add(x, 2);
five = addTwo(3);

// Perhaps you also need to add four often. Again, you could make a function for it, and it would only take one argument.
Func<int, int> addFour = x => add(x, 4);
five = addFour(1);

// Now there is some duplication between addTwo and addFour. What if we could make a function, that makes adders?
Func<int, Func<int, int>> makeAdder = (int valueToAdd) =>
{
   return x => add(x, valueToAdd);
};

// Excellent, now we can reconstruct addTwo and addFour using makeAdder
addTwo = makeAdder(2);
addFour = makeAdder(4);

// And use them like before
five = addTwo(3);
five = addFour(1);
          
// Lets compute 6 + 4, by making an adder that adds 6 to numbers, an then passing 4 to it.
int ten = makeAdder(6)(4);

// Well it appears we can now add any two numbers together by using makeAdder. But makeAdder only takes one argument, not two.
// makeAdder is the result of applying currying to the add method.

Here is another way of stating it: if you have a function that takes arguments A and B and returns C, you can create a function that takes argument A, and returns a function that takes argument B and returns C. By calling this function with A, you then call the resulting function with B, and you get C. That is currying. Lets get back to factorials – here is the code the last post finished up with:

public delegate int SelfCallingFactorial(int x, SelfCallingFactorial self);

/// <summary>
/// Creating the factorial method inside the returned lambda resolves the garbage collection problem.
/// This solution does not involve a closure, so its pretty good. But...
/// </summary>
public class Solution03 : ISolution
{
   public Factorial MakeFactorialFunction()
   {
       return (int x1) =>
       {
           SelfCallingFactorial factorial = (int x, SelfCallingFactorial self) =>
           {
               return x < 2 ? 1 : x * self(x - 1, self);
           };

           return factorial(x1, factorial);
       };
   }
}

Its sort of annoying how I have to do all my work inside a lambda. I’ve had to do this for the last few solutions, ever since I introduced the idea of using self calling function. It would be great if the SelfCallingFactorial could return a Factorial (the delegate). That way I could just return the result directly, and I wouldn’t have to deal with the fact that I have two integer parameters running about (x and x1). This change can be achieved by using currying. Its somewhat tricky so I will do it in two steps. The first step is to perform the currying operation, making as few changes as possible, the second step will clean up, simplify and generalize. Here is the first part:

public delegate Factorial SelfCallingFactorial2(SelfCallingFactorial2 self);

/// <summary>
/// Apply a technique called currying. Now the self calling factorial function returns a factorial delegate.
/// </summary>
public class Solution04 : ISolution
{
   public Factorial MakeFactorialFunction()
   {
       return (int x1) =>
       {
           SelfCallingFactorial2 factorial = (SelfCallingFactorial2 self) =>
           {
               return (int x) =>
               {
                   return x < 2 ? 1 : x*self(self)(x-1);
               };
           };

           return factorial(factorial)(x1);
       };
   }
}

I had to modify the SelfCallingFactorial delegate. It no longer accepts an integer, instead it returns a Func<int,int> which I replaced with the Factorial delegate. You will notice I stuck a 2 on the end of the name, this is just to avoid clashes with previous delegate. This will get cleaned up in a second. Once the delegate was modified, I had to change the factorial function, and then its invocation. A side-by-side comparison might help:

Do you see how the sections in the boxes follow the same pattern, where instead of there being two arguments, there is just one argument, and then the result is invoked with the second argument?

Step two of this change is to take advantage of what I gained in step one. Now that the self calling factorial function returns a Factorial delegate, I don’t need to wrap the entire thing in a lambda – I can just return the result directly. I can also change the SelfCallingFactorial2 delegate to be generic. Ideally I could use it for other recursive algorithms such as Fibonacci. While I’m in cleanup mode, I want to rename the delegate to “SelfApplicable”. By doing this, I’ve changed the terminology somewhat – I’m using “applicable” instead of “calling”. I’ve done this because the delegate doesn’t actually “know” what the function is doing with the self argument. Its probably calling it, but perhaps its just inspecting its members? What the delegate can say is that the function is definitely applying itself to itself, because it takes itself as an argument, after all. This change also gets me closer to the code I’m aiming for in Mads’ post. So here is the result of applying these changes:

public delegate T SelfApplicable<T>(SelfApplicable<T> self);

/// <summary>
/// We can generalize the previous delegate to work with any function, and create SelfApplicable<T>.
/// I wish I could constrain T to be a delegate type but unfortunately it is not supported.
///
/// Because we removed the integer argument from the function, we no longer have to nest the entire body in
/// a lambda as we did in the previous step.
/// </summary>
public class Solution05 : ISolution
{
   public Factorial MakeFactorialFunction()
   {
       SelfApplicable<Factorial> factorial = (SelfApplicable<Factorial> self) =>
       {
           return (int x) =>
           {
               return x < 2 ? 1 : x * self(self)(x - 1);
           };
       };
      
       return factorial(factorial);
   }
}

Pretty neat huh! My only complaint with this code is that my factorial algorithm has this yucky self(self) business. Ideally I could refactor this out, so that the factorial algorithm is as readable as possible, and the tricky self calling nonsense is somewhere else. I shall pursue this in the next post.

Refactoring Towards the Y Combinator: Part 2

2009-01-06T11:42:00.003+11:00

This is a multi-part series. Part 1. Part 2. Part 3. Part 4. Part 5. Part 6.

Lets get started with discovering the Y combinator. To start off, I came up with the most straightforward recursive implementation of the factorial function I could think of, restricting myself to anonymous methods (or more specifically, lambdas):

public delegate int Factorial(int x);

/// <summary>
/// This is the cheating way. Define a variable and use a closure on that variable.
/// Its cheating because it only works in an impure language.
/// </summary>
public class Solution01 : ISolution
{
    public Factorial MakeFactorialFunction()
    {            
        Factorial factorial = null;
        factorial = (int x) =>
        {
            return x < 2 ? 1 : x * factorial(x - 1);
        };
        
        return factorial;
    }
}

I define a delegate for the Factorial function – it takes an int, returns an int. I could have used Func<int,int> but believe me, as this gets more complicated, you’ll be glad I introduced the delegate. I also define a MakeFactorialFunction() method, which is intended to be used as so:

var s1 = new Solution01();
Factorial f = s1.MakeFactorialFunction();
int factorialOf10 = f(10);

You can mostly ignore the Solution01 and ISolution stuff, they are just artefacts from the testing harness I set up. Lets focus on the code that matters:

Factorial factorial = null;
factorial = (int x) =>
{
    return x < 2 ? 1 : x * factorial(x - 1);
};

return factorial;

In this code, I call factorial recursively by utilizing a closure. The body of the lambda expression refers to a variable that lies outside the scope of the lambda; that variable is ‘factorial’. You might have noticed, my code comment above states that I consider this implementation to be “cheating”. This is because I reassign the value of factorial. First it is null, then it is a lambda expression. Perhaps you are wondering why I bother reassign it? Why not just do it like this:

Factorial factorial = (int x) =>
{
    return x < 2 ? 1 : x * factorial(x - 1);
};

I am afraid this won’t work, the compiler identifies this as an error, “use of unassigned local variable ‘factorial’”. This is why I use the extra step of declaring factorial to be null. Now I said before that reassigning the factorial variable is cheating. Why? The Y combinator is much more relevant to the functional programming paradigm than it is to the imperative paradigm – functional programming has a concept called “purity”, which means no side effects, and no variables (no variables with varying values, that is) . For the purposes of this exercise, it will be helpful to limit myself to pure operations. The reassignment of the factorial variable is a impure operation. So how to get rid of it?

My next attempt:

public delegate int SelfCallingFactorial(int x, SelfCallingFactorial self);

/// <summary>
/// We can remove the impurity by having the factorial function accept a reference to itself, so it can call itself.
/// We can't just return this implementation because it doesn't match the Factorial signature, so we have to return
/// a lambda that calls it. Unfortunately, doing so will create a closure and as a result, as long as a reference
/// to the result of MakeFactorialFunction method is held, the Solution2 instance will not be garbage collected.
/// </summary>
public class Solution02 : ISolution
{
    public Factorial MakeFactorialFunction()
    {
        SelfCallingFactorial factorial = (int x, SelfCallingFactorial self) =>
        {
            return x < 2 ? 1 : x * self(x - 1, self);
        };

        return x =>
        {
            return factorial(x, factorial);
        };
    }
}

Okay, so what has happened? Rather than having the factorial function call itself by utilizing the variable, we could pass a reference to the factorial function as an argument to itself. I modify the Factorial delegate to accept an instance of itself, and call it a SelfCallingFactorial instead. You can see that delegate definition at the top. I then define ‘factorial’ similarly as before, but this time I have a ‘self’ parameter which I can invoke as the recursive step. When it is invoked, I have to pass two arguments: the value I want to calculate the factorial of, and another self reference. Try to think of the ‘self’ parameter as a manually implemented equivalent of the ‘this’ keyword in normal C#, but for functions. The ‘this’ keyword allows code inside an object to obtain a reference to that object, similarly, my ‘self’ parameter allows code inside a function to call that function!

The result of this trick is that I have successfully removed the impurity - there is no reassignment in this solution. However we are not finished yet: unfortunately, I cannot simply return ‘factorial’ after it has been defined, because it is a SelfCallingFactorial, and the MakeFactorialFunction method is supposed to return a Factorial. Instead I have to return a lambda that will execute my SelfCallingFactorial. This creates another closure, again, on the ‘factorial’ variable. As mentioned in the code comment, the instance of Solution02 used to create the factorial function will stay in scope as long as the factorial function stays in scope, because the returned factorial function holds a reference to the ‘factorial’ local variable defined in the MakeFactorialFunction() method. Fortunately, this is easy to fix:

/// <summary>
/// Creating the factorial method inside the returned lambda resolves the garbage collection problem. 
/// This solution does not involve a closure, so its pretty good. But...
/// </summary>
public class Solution03 : ISolution
{
    public Factorial MakeFactorialFunction()
    {
        return (int x1) =>
        {
            SelfCallingFactorial factorial = (int x, SelfCallingFactorial self) =>
            {
                return x < 2 ? 1 : x * self(x - 1, self);
            };

            return factorial(x1, factorial);
        };
    }
}

Solution03 is just a very minor revision on Solution02. All I had to do was move the code that defines the SelfCallingFactorial inside the returned lambda expression (if you look at the code above, you will see that it was previously outside). Now when a Solution03 instance is used to construct a FactorialFunction, that instance will be free to be garbage collected while the result, the factorial function, can continued to be used. Now please don’t get me wrong, I know that this garbage collection ‘issue’ is quite irrelevant – I am actually just using it as an excuse to get the code closer to my satisfaction. I am not exactly sure why I want it this way – it just seems neater.

So, where to go from Solution03? It seems pretty good, and we are still nowhere near the Y combinator. In the next instalment, I will start making the code a little more general, with the eventual goal that the same technique might be applied to other recursive algorithms (such as Fibonacci).

Refactoring Towards the Y Combinator: Part 1

2009-01-04T12:05:00.002+11:00

This is a multi-part series. Part 1. Part 2. Part 3. Part 4. Part 5. Part 6.

Sometimes I wish that I had studied computer science rather than software engineering at university. The software engineering degree was much more practical, and as a result there is a bunch of interesting computer science theory out there that I am yet to be exposed to. In an effort to make some tiny progress on this front, this Christmas break I decided to spend a few days exposing myself to a lovely little thing called the Y combinator.

What is the Y combinator exactly? Basically, its a mechanism that can be used to call functions recursively, even if your programming language does not support recursion, as long as it does have support for first class functions (e.g. you can pass one function to another as an argument). It is extremely unlikely that you will find a use for it in your day to day work as a programmer, but I found learning about the Y combinator to be a worthwhile exercise nonetheless simply because it made my head hurt in a good way.

I found three particularly useful resources for learning about the Y combinator. These were:

Recursive Lambda Expressions by Mads Torgersen
The Y Combinator by Mike Vanier
The Why of Y [PDF] by Richard Gabriel

Just reading through them, they all managed to lose me at some point. The Y combinator is really a functional programming concept, so programmers such as myself that were crippled at a young age by being first exposed to an imperative language like Basic will really struggle with it. It was clear that the only way I was really going to understand it was roll up my sleeves and write some code.

Mads’ post uses C#, and it had enough code to give me a clear goal. I would start with the most basic implementation of a recursive method I could, and try to slowly refactor it towards the final Mads code. This turned out to work very well, but I probably would not have succeeded without the help of the other resources, especially The Why of Y. Both Mike and Richard use Scheme (a dialect of Lisp), but fortunately I have watched enough SICP lectures to be able to follow it at a basic level. In the Why of Y, Richard provides an example derivation of Y, and I was able to successfully translate each of his steps to the appropriate C#. I promise you, there will be no Lisp code in any of the posts in this series.

So what does the Y combinator look like? Well here is the definition I ended up with:

SelfApplicable<HigherOrderEvaluator<Func<T, T>>> Y =
   self => algorithm => t => algorithm(self(self)(algorithm))(t);

HigherOrderEvaluator<Func<T, T>> ApplyY = Y(Y);

Here is my definition for the factorial function:

HigherOrderFunction<Func<int, int>> factorial =
               f => x => x < 2 ? 1 : x * f(x - 1);

And here is the usage:

public int CalculateFactorialOf10()
{
   return YCombinator<int>.ApplyY(factorial)(10);
}

What’s the phrase you’re looking for? How about: “My eyes! The goggles do nothing!”

Even now when I look at it, I struggle to make sense of it. This is the compressed version, but in my opinion even a far more verbose version is still difficult to comprehend. I understand this code by understanding the steps I followed to arrive at it, and hopefully by the end of this series of posts, so will you.

One Year

2009-01-04T10:00:00.001+11:00

Its been one year since I started this blog, so I figured a reflective post might be appropriate.

What went right in 2008:

I made a dramatic change to my free time habits. I did significantly more reading and programming, and spent much less time playing videogames.
I read a bunch of software related books cover-to-cover. Probably more than in all previous years combined.
I involved myself in an open source project.

What went wrong:

I started many things, finished few. I played with lots of stuff but didn’t deliver a whole lot.
I didn’t learn javascript or ruby. At least, not to the point where I can write idiomatic code in either language.
I failed to deliver a worthwhile MVC based web application.
I made very little progress in the area of algorithms and data structures.

Rereading my posts from a year ago, it is quite evident that my year did not proceed quite as I intended. However, I am not disappointed - I learned quite a bit about my own capabilities and study habits. My career goal changed – while Google is very alluring, I recognise that Microsoft would probably be an awesome place for me to work and a better fit. I have concluded that my focus on the Microsoft stack is not a bad thing. From my perspective, there are lots of exciting things in the works for the Microsoft stack:

Microsoft will be, for the first time ever, providing and fully supporting a proper functional programming language: F#.
The introduction of the DLR promises to foster a healthy ecosystem of dynamic programming languages, with IronPython and IronRuby at the forefront.
Spec# has been transformed into a code contract library with compiler support and will be part of the .NET 4.0 release.
Windows Azure, Microsoft’s cloud computing platform, could make a significant impact on the .NET development ecosystem over the next few years.
Oslo, simply because it could help push domain specific languages into the mainstream. I am sceptical about much of what Oslo promises, but I think better tooling and raising awareness of what DSLs can offer is a good thing.

In the next few years I will be able to explore functional languages, dynamically typed languages, code contracts, cloud computing and domain specific languages all within the .NET platform. There is an immense amount for me to learn (this list, obviously, is nowhere near enumerating all of it), so why not go with the path of least resistance and learn what I can within the MS stack?

I hope to do a better job this year of actually finishing things. My study habits are still a long way off being optimal.

A Fluent NHibernate rewrite

2008-12-09T17:39:00.000+11:00

A little less than 6 months ago I joined the Fluent NHibernate open source project. More recently I’ve struggled with fielding feature requests and partial patches, and I believe that the source of my difficulty has been the structure of the Fluent NHibernate codebase. In my opinion, the fundamental problem with the code is a lack of separation of concerns. Lets take a look at some excerpts from the ClassMap class:

public virtual IdentityPart Id(Expression<Func<T, object>> expression, string column)
{
    PropertyInfo property = ReflectionHelper.GetProperty(expression);
    var id = column == null ? new IdentityPart(property) : new IdentityPart(property, column);
    AddPart(id);
    return id;
}

This Id method is part of the fluent interface. You can see it takes an expression and does some reflection to convert that expression into a format that can be used to configure NHibernate.

public XmlDocument CreateMapping(IMappingVisitor visitor)
{
    if (String.IsNullOrEmpty(TableName))
        TableName = visitor.Conventions.GetTableName.Invoke(typeof(T));

    visitor.CurrentType = typeof(T);
    XmlDocument document = getBaseDocument();
    setHeaderValues(visitor, document);

    foreach (var import in imports)
    {
        import.Write(document.DocumentElement, visitor);
    }

    XmlElement classElement = createClassValues(document, document.DocumentElement);
    writeTheParts(classElement, visitor);

    return document;
}

This CreateMapping method generates the eventual output that will be fed to NHibernate: an XmlDocument.

The fact that these two methods exist in the same class is a prime example of why I have found the code base increasingly difficult to work with. There is no seperation between the function of specifying the mapping (by calling into the fluent interface) and generating the mapping (writing an xml document). It becomes difficult to reason about the capability of the library as the public interface consists of a big pile of lambda goo. Thinking more ambitiously, if you wanted to develop an alternative fluent api while continuing to utilize all the existing infrastructure provided by Fluent NHibernate, you would find it very difficult indeed.

So, what to do? Hell, if your a programmer you shouldn’t have to ask that question! The same thing we always want to do when the old code base starts to feel clunky. Throw it all out and start from scratch! Ok, rarely is this actually a good idea but that is the nice thing about doing open source on your own time – you can do whatever the hell you want.

Well what should the code base actually look like? Chad Myers had the answer, so I rolled up my sleeves and went to work. That was a couple of weeks ago. Today I hit a milestone - I was able to successfully configure NHibernate for a simple 3 entity scenario, using an API that looks just like the existing Fluent NHibernate API but actually utilizes a model that constructs an object graph of Hbm* instances (these are classes provided by NHibernate that are generated from the mapping schema) and then serializes that graph to xml. Hitting this milestone meant that it was time to share my work, so I committed my version as a branch. I included a decent chunk of notes in the commit message and don’t intend to repeat them all here, so I recommend you review the log if you would like to know more.

So what does this rewrite actually look like?

First of all, here is the tiny demonstration domain that I have been using so far:

Now here is the fluent mapping that I managed to get working today:

private class ArtistMap : ClassMap<Artist>
{
    public ArtistMap()
    {
        Id(x => x.ID);
        Map(x => x.Name)
            .WithLengthOf(50)
            .CanNotBeNull();
        HasMany<Album>(x => x.Albums)
            .AsSet()
            .IsInverse();
    }
}

private class AlbumMap : ClassMap<Album>
{
    public AlbumMap()
    {
        Id(x => x.ID);
        Map(x => x.Title)
            .WithLengthOf(50)
            .CanNotBeNull();
        References(x => x.Artist);
        HasMany<Track>(x => x.Tracks)
            .AsSet()
            .IsInverse();
    }
}

private class TrackMap : ClassMap<Track>
{
    public TrackMap()
    {
        Id(x => x.ID);
        Map(x => x.Name)
            .WithLengthOf(50)
            .CanNotBeNull();
        Map(x => x.TrackNumber);
        References(x => x.Album)
            .CanNotBeNull();
    }
}

Look familiar? It should if you are a Fluent NHibernate user or developer! To demonstrate the flexibility of the rewrite, I implemented a very small subset of the existing fluent interface. That implementation was put in a completely separate assembly, to demonstrate that the core of Fluent NHibernate is not tied to any specific fluent api. If you wanted to, you could map a class unfluently, using the core model like so: (this example only maps Album)

var root = new HibernateMapping();

var classMapping = new ClassMapping
   {
       Name = typeof (Album).AssemblyQualifiedName,
       Id = new IdMapping("ID", new IdColumnMapping("ID"), IdGeneratorMapping.NativeGenerator)
   };
root.AddClass(classMapping);

var titleMapping = new PropertyMapping("Title") {Length = 50, AllowNull = false};
classMapping.AddProperty(titleMapping);

var artistMapping = new ManyToOneMapping("Artist");
classMapping.AddReference(artistMapping);

var trackMapping = new SetMapping
   {
       Name = "Tracks",
       Key = new KeyMapping(),
       Contents = new OneToManyMapping(typeof (Track).AssemblyQualifiedName)
   };
classMapping.AddCollection(trackMapping);

You could then serialize the underlying Hbm graph and this is the result:

But of course, doing it that way sucks. This project is called Fluent NHibernate after all! You don’t even have any strong typing on the properties! I can’t see anyone using the core model directly. Its designed to be a base for fluent api’s to build on.

The core model is still in a rough state. At the moment it has very little functionality other than to wrap the Hbm* classes. However I expect this will change. One of the many issues that need addressing is that of support for conventions – I expect the conventions implementation will require the model to be richer, to accept Type and PropertyInfo instances rather than awful strings. But don’t worry! It won’t get too rich – you won’t see any Expression<Func<T, Object>> hanging off the model – that stuff belongs in the fluent interface.

I am really quite excited about how the seperation between the mapping model and the fluent interface could be leveraged. The DDD fanboi in me would love to see a fluent interface that allows you to describe your aggregate structure in addition to mapping to NHibernate.

No visitors!

2008-11-03T04:55:00.000+11:00

I am sure that most programmers managed to learn some specific design patterns before they even knew what design patterns were. This is certainly true for myself – and while I cannot say what my first design pattern was, I can tell you about the first one I remember learning: the Visitor pattern. I was midway through a university class on object oriented programming and in my spare time I was writing a turn based puzzle game in C# that involved daggers and goblins and dragons and doors and keys and whatnot. Now to make the thing work, I was doing something that felt very wrong. I was writing lots of switch statements that described the interactions between the different objects. I experimented, looking for better solutions using overloading and overriding, but none of it seemed to work. I asked my lecturer for help, and of course this is where I learned about visitor. Initially I was elated, but in time my opinion changed: visitor is this ugly bloated thing, designed to get around the lack of double dispatch support in most object oriented languages. Its a hack, a workaround. As with arguably all design patterns, its a trick to deal with limitations in the language.

So today I was watching this video that goes into more detail on the new C#4 features and something was said about runtime overload resolution that flicked a switch in my brain and suddenly I realised a fact that I am sure was mindblowingly obvious to people much smarter than I: the C#4 dynamic keyword supports double dispatch. If you are prepared to take the performance hit and just want to get something up and running, you can forget the visitor pattern. Lets look at an example based on the sort of thing I was trying to do years ago with my little game:

class Entity
{
    public string Name { get; set; }
    public string GetGreeting(Entity e)
    {
        return "...";
    }
}
class Foo : Entity
{
    public string GetGreeting(Foo f)
    {
        return string.Format("Hi there {0}! Beware, there may be evil Bars nearby!", f.Name);
    }

    public string GetGreeting(Bar b)
    {
        return "Curse you! I hate all Bars!";
    }
}
class Bar : Entity
{
    public string GetGreeting(Bar b)
    {
        return string.Format("Greetings {0}! Have you seen any evil Foos lately?", b.Name);
    }

    public string GetGreeting(Foo f)
    {
        return "The Foos are a scourge on this planet! Take this!";
    }
}
class StaticIntroducer
{
    public void Introduce(Entity e1, Entity e2)
    {
        Console.WriteLine("{0} is introduced to {1} by the StaticIntroducer...", e1.Name, e2.Name);
        Console.WriteLine("{0} says: \"{1}\"", e1.Name, e1.GetGreeting(e2));
        Console.WriteLine("{0} says: \"{1}\"", e2.Name, e2.GetGreeting(e1));
    }
}
class Program
{
    static void Main(string[] args)
    {
        Entity f1 = new Foo { Name = "BobFoo" };
        Entity f2 = new Foo { Name = "JohnFoo" };
        Entity b1 = new Bar { Name = "JerryBar" };
        Entity b2 = new Bar { Name = "SamBar" };

        var introducer = new StaticIntroducer();
        introducer.Introduce(f1, f2);
        introducer.Introduce(f1, b1);
        introducer.Introduce(b1, b2);

        Console.ReadLine();
    }
}

It outputs the following:

BobFoo is introduced to JohnFoo by the StaticIntroducer... BobFoo says: "..." JohnFoo says: "..." BobFoo is introduced to JerryBar by the StaticIntroducer... BobFoo says: "..." JerryBar says: "..." JerryBar is introduced to SamBar by the StaticIntroducer... JerryBar says: "..." SamBar says: "..."

Clearly, it does not work as intended. The code I’ve written makes some sort of sense, but its not correct. If you look at the Introduce method, you can see that it takes two entities. As a result, the call to GetGreeting will be resolved at compile time to Entity.GetGreeting(Entity e) and no polymorphism will occur. You cannot fix the problem by simply making the methods virtual and overrides, as the overriden versions take different arguments. Redeclaring the GetGreeting methods using the new operator also does not help. If you are facing this problem with C# 3 or earlier, its time to apply the visitor pattern. I won’t do that here, there are plenty of examples of Visitor on the web.

But if you are using C#4, its time for dynamic to come to the rescue. Here is a slightly different implementation of an Introducer:

class DynamicIntroducer
{
    public void Introduce(dynamic e1, dynamic e2)
    {
        Console.WriteLine("{0} is introduced to {1} by the DynamicIntroducer...", e1.Name, e2.Name);
        Console.WriteLine("{0} says: {1}", e1.Name, e1.GetGreeting(e2));
        Console.WriteLine("{0} says: {1}", e2.Name, e2.GetGreeting(e1));
    }
}

The ONLY thing I have changed is the signature. The parameters are now typed as dynamic rather than Entity. I plug this introducer in and this is the output:

BobFoo is introduced to JohnFoo by the DynamicIntroducer... BobFoo says: Hi there JohnFoo! Beware, there may be evil Bars nearby! JohnFoo says: Hi there BobFoo! Beware, there may be evil Bars nearby! BobFoo is introduced to JerryBar by the DynamicIntroducer... BobFoo says: Curse you! I hate all Bars! JerryBar says: The Foos are a scourge on this planet! Take this! JerryBar is introduced to SamBar by the DynamicIntroducer... JerryBar says: Greetings SamBar! Have you seen any evil Foos lately? SamBar says: Greetings JerryBar! Have you seen any evil Foos lately?

It works! How? Well, once you are using the dynamic type, overload resolution occurs at runtime rather than compile time, and is done using the runtime types of the arguments rather than the compile time types. My nice, succinct code that describes the different interactions now works just how I intended. But at what cost? Putting the possible performance problems aside, we have made the code more fragile. If someone passes a non-Entity to the Introduce method, we’ll get a runtime error! Well this is actually a trivial fix that only occurred to me while writing this post:

public void Introduce(Entity e1, Entity e2)
{
    Console.WriteLine("{0} is introduced to {1} by the DynamicIntroducer...", e1.Name, e2.Name);
    Console.WriteLine("{0} says: {1}", e1.Name, ((dynamic)e1).GetGreeting(e2));
    Console.WriteLine("{0} says: {1}", e2.Name, ((dynamic)e2).GetGreeting(e1));
}

The only method call that actually needs to be dynamic is GetGreeting, so we can change the method signature back to as it was before and just introduce a cast to dynamic for the GetGreeting invocation. Much better. There is one more thing I would like to try to do: hide the need for GetGreeting to be invoked dynamically from the caller. The crude way is to use a static method, but I’m not a fan of that. Tomorrow I will see if there is an elegant way to approach it.