Saturday, 24 April 2010

Uncle Bob’s Bowling Kata in Functional C#

During the session on functional programming at OpenVolcano10 this week, Uncle Bob Martin spoke of a particularly elegant functional solution to his bowling game kata. Proposed by Stuart Halloway, the solution regards the bowling game itself as a (potentially infinite) sequence of ‘rolls’ (balls), and then uses some nicely elegant list manipulation to extract ten valid scoring frames from the sequence of balls and calculate the score of the game.

C# and IEnumerable<T> allow you to do some very similar things in .NET – basically, you can define operations in terms of mapping one infinite list to another infinite list, and you don’t have to worry about stack overflows or out of memory errors because, thanks to the wonder of lazy evaluation, nothing is actually allocated or returned until you start asking for the resulting values.

Take a look at this code snippet:

static IEnumerable<Int64> Integers {
    get {
        for (var i = 1; true; i++) yield return (i);
    }
}

If you’re thinking “but that’s just an infinite loop!” – you’re partly right. Yes, it’s infinite, but no, it’s not a loop. The magical yield return operator there actually breaks the loop, and allows you go to infinity (and beyond!)one step at a time. Using the LINQ Take() method, you can easily slice’n’dice this infinite list into useful pieces:

// Calculate the sum of the first 20 positive integers:
var sum = Integers.Take(20).Sum();

// Calculate the product of the first 10 positive integers:
var product = Integers.Take(10).Aggregate((a, b) => (a * b));

By throwing some extensions methods onto Int64, you can use the same approach to filter the list:

public static class ExtensionMethods {
    public static bool IsPrime(this Int64 candidate) {
        if ((candidate & 1) == 0) return (candidate == 2);
        var num = (int)Math.Sqrt((double)candidate);
        for (var i = 3; i <= num; i += 2) {
            if ((candidate % i) == 0) return false;
        }
        return true;
    }
}

// now we’ve defined myInt64.IsPrime(), we can do this:
var primes = Integers.Where(i => i.IsPrime());

We now have a C# variable – primes – that, for all intents and purposes, contains all the prime numbers. If we try to print the entire list, our program will never terminate – but that’s what we’d expect, because the list of prime numbers is infinite. We can, however, do things like printing a list of the first 100 primes:

foreach(var prime in primes.Take(100)) Console.WriteLine(prime);

or calculating the product of the first 50 primes:

var product = primes.Take(50).Aggregate((a,b) => (a*b));

So, what’s all this got to do with bowling? Well – using this approach, we can store the progress of a bowling game as a (potentially infinite?) list of rolls, and by using a couple of useful extension methods on IEnumerable<int>, we can calculate the resulting ten-pin bowling score in a single LINQ statement:

var score = rolls.ToFrames().Take(10).Sum(frame => frame.Sum());

Here’s the supporting extension methods  - which basically capture the scoring quirks of spares, strikes, frames and the other idiosyncracies of ten-pin-bowling. The ToFrames() method is particularly interesting – it’s translated from the cons operator in Lisp/Clojure, and effectively returns a list (the rolls that count towards the current frame), followed by a list of lists (where each list represents a subsequent frame in the game):

public static class BowlingRules {
    public static IEnumerable<IEnumerable<int>> ToFrames(this IEnumerable<int> rolls) {
        yield return (rolls.Take(rolls.BallsToScore()));
        foreach(var frame in (rolls.Skip(rolls.FrameAdvance()).ToFrames())) {
            yield return(frame);
        }
    }

    private static int FrameAdvance(this IEnumerable<int> rolls) {
        return (rolls.IsStrike() ? 1 : 2);
    }

    private static int BallsToScore(this IEnumerable<int> rolls) {
        return (rolls.IsBonus() ? 3 : 2);
    }

    private static bool IsStrike(this IEnumerable<int> rolls) {
        return (rolls.Take(1).Sum().Equals(10));
    }

    private static bool IsSpare(this IEnumerable<int> rolls) {
        return (rolls.Take(2).Sum().Equals(10));
    }

    private static bool IsBonus(this IEnumerable<int> rolls) {
        return (rolls.IsSpare() || rolls.IsStrike());
    }
}

The project – including the unit test from Uncle Bob’s kata translated to NUnit / C# – is up on Google Code if you want to take a look.

Wednesday, 14 April 2010

Dynamic CSS with .less at the TechDays Open Source Evening

image Thanks to all of you who came along to last night’s Open Source .NET evening (and extra thanks to @serialseb for putting the whole thing together!) I think we managed to cover a really great programme of topics – OpenRasta, Ben Hall using Ruby to test ASP.NET projects, Mike Hadlow talking about the Windsor IoC container, Jeremy Skinner presenting his FluentValidation library (and a late apology from Neil Robbins, whose CouchDB talk had to be cancelled after his laptop went into ‘permanent hibernation’ at the last minute… I guess the long cold winter affects laptops as well as people)

I should make one very important clarification: dotLess is NOT my project! The original Ruby project was created by Alexis Sellier and Dmitry Fadeyev, and it was ported to .NET by Christopher Owen, Erik van Brakel and Daniel Hoelbling. Apologies if this wasn’t clear from the presentation – from the questions afterwards, I appear to have inadvertently given the impression I was one of the project contributors. I’m not; I just think it’s an awesome library and wanted to give it a bit of exposure.

You can download the demo code from last night’s talk here:

    http://www.dylanbeattie.net/dot_less_demo.zip 

You should just be able to unzip the whole lot into a folder, bring up LessDemo.sln in Visual Studio and hit “Run” – but let me know if you’re having any problems with it.

The other bits I spoke about in the talk are:

Finally, I’m very excited to see that for the next version of LESS they’re migrating away from server-side Ruby and porting the entire library to Javascript – so you can run it client-side or server-side depending on your setup. Nothing’s officially released yet, but you can get download the latest source from the less.js project on GitHub – definitely a project worth keeping an eye on.