Avoid Duplicating Code

It’s great that so many C# and VB.NET developers are taking advantage of LINQ. Unfortunately, using LINQ can encourage you to misuse lambdas. Consider the following simple example:

var results = from x in 0.Through(10)

              select x * x;

Square is a useful utility function. It shouldn’t be defined as a lambda because that ensures code duplication instead of reuse. It’s more obvious using extension method-syntax:

var results =

    0.Through(10)

    .Select(x => x * x);

The problem is that in versions of C# prior to 4.0, it is painful to define Square as a reusable method because Select is a function with multiple generic parameters. You are forced to painfully specify the type parameters or use an unnecessary lambda:

//specifying the generic types

var results =

    0.Through(10)

    .Select<int, int>(Math.Square);

//using an unnecessary lambda

var results =

    0.Through(10)

    .Select(x => Math.Square(x));

Even in C# 4.0, the query syntax retains the unnecessary lambda problem:

var results = from x in 0.Through(10)

              select Math.Square(x);

Fortunately, the extension method syntax is fixed in 4.0:

var results =

    0.Through(10)

    .Select(Math.Square);

Avoid Multi-Line Lambdas

It’s easy to recognize that Square should not be a lambda, but some functions are less obvious:

IEnumerable<Ninja> MakeFearsomeFightingTeam(SecretOoze ooze,

                                           IEnumerable<Turtle> turtles,

                                           Pizza pizza)

{

    return 

        turtles

        .Select(turtle =>

        {

            var transformed = ooze.Transorm(turtle);

            transformed.Say("Cowabunga!");

            transformed.Eat(pizza);

            return transformed;

        });

}

You should avoid writing multi-line lambdas like this where possible. In this case, it makes the code harder to read, especially if you add another operation after the Select. It’s difficult to understand what the lambda is doing upon first glance. Also, there’s a good chance that you will want to reuse the behavior of the lambda elsewhere in your program.

IEnumerable<Ninja> MakeFearsomeFightingTeam2(SecretOoze ooze,

                                            IEnumerable<Turtle> turtles,

                                            Pizza pizza)

{

    return

        turtles

        .Select(turtle => Ninjaify(ooze, pizza, turtle));

}

Ninja Ninjaify(SecretOoze ooze, Pizza pizza, Turtle turtle)

{

    var transformed = ooze.Transorm(turtle);

    transformed.Say("Cowabunga!");

    transformed.Eat(pizza);

    return transformed;

}

The named instance method gives a description to the behavior that was in the multi-line lambda, and the Select statement is more readable. The sacrifice is that Ninjaify has to take extra arguments because it cannot rely on closure. There is also no guarantee that the definition of Ninjaify will remain close to where it is used as you add more code. Additionally, C#’s syntax requires that you use an unnecessary lambda to pass the turtle argument to Ninjaify. The answer is to use a locally defined method:

IEnumerable<Ninja> MakeFearsomeFightingTeam3(SecretOoze ooze, 

                                            IEnumerable<Turtle> turtles,

                                            Pizza pizza)

{

    Func<Turtle, Ninja> Ninjaify = 

        turtle =>        

        {

            var transformed = ooze.Transorm(turtle);

            transformed.Say("Cowabunga!");

            transformed.Eat(pizza);

            return transformed;

        };

    return

        turtles

        .Select(Ninjaify);

}

Like a lambda, the locally defined method uses closure to avoid redefining variables, and it has the readability benefit of being defined near to where it is used. Since it is a named method, it provides a useful description of it’s behavior, and it doesn’t disrupt the flow of your Select method. It’s the best of both worlds. The only downside is that it can’t be called outside the scope of the MakeFearsomeFightingTeam3 method.

Unfortunately, C# requires you to write the full type signature for the function. The compiler will fail with a “cannot assign lambda expression to implicitly-typed local variable” if you try to use the var keyword. This is a real pain for more complicated signatures, and it limits you from using locally defined methods to their full potential.

Going Further With F#

In F#, the type signature problem goes away:

    let MakeFearsomeFightingTeam4 ooze turtles pizza =
        let ninjaify turtle =
            let transformed = ooze.Transform(turtle)
            transformed.Say("Cowabunga!")
            transformed.Eat(pizza)
            transformed

        turtles
        |> Seq.map ninjaify

Here, you can see the benefit of F#’s type inference system and functional programming roots. The behavior of the code is retained, but the extraneous type signature is not required.

F# also fixes the problem of requiring an unnecessary lambda for named methods outside the scope of the MakeFearsomeFightingTeam4 method. Automatic currying makes it easy to pass the arguments that would be captured by closure:

    let MakeFearsomeFightingTeam5 ooze turtles pizza = 
        turtles
        |> Seq.map (Ninjaify ooze pizza)

In Summary

• Use lambdas for one line, single use functions
• Prefer locally defined functions to multi-line lambdas, but be wary of complicated type signatures in C#
• If a function is reusable, move it to the appropriate class or module, and use it instead of a lambda or locally defined function
• Use F# to avoid messy type signatures and unnecessary lambdas

Today, I was in the process of creating a branch of Elevate to support .NET 4.0 when I came across a subtle, but breaking change in the Enumerable.Count function. The following code works in .NET 3.5, but fails in .NET 4.0 Beta 2:

[TestClass]

public class CountBug

{

    public class MyIList : IList<int>

    {

        public MyIList()

        {

            GetEnumeratorWasCalled = false;

            CountWasCalled = false;

        }

        //...non-relavent IList members excluded for this post...

        public bool GetEnumeratorWasCalled { get; set; }

        public IEnumerator<int> GetEnumerator()

        {

            GetEnumeratorWasCalled = true;

            return null;

        }

        public bool CountWasCalled { get; set; }

        public int Count

        {

            get

            {

                CountWasCalled = true;

                return 0;

            }

        }

    }

    [TestMethod]

    public void CountBehavior()

    {

        var list = new MyIList();

        Assert.AreEqual(0, list.Count());

        Assert.IsTrue(list.CountWasCalled);

        Assert.IsFalse(list.GetEnumeratorWasCalled);

    }

}

The Enumerable.Count method in .NET 4.0 Beta 2 fails to recognize that MyIList implements ICollection<T>, so instead of returning the .Count property, it calls the MyIList’s GetEnumerator() method and walks every item in the list to determine the count. In .NET 3.5, MyIList is identified as an ICollection<T> implementer and the .Count property is correctly used.

It’s also worth noting that it does not seem to be possible to create a MSTest test project in Visual Studio 2010 Beta 2 that targets .NET 3.5. It will silently upgrade any of your .NET 3.5 test projects to .NET 4.0 even if you select 3.5 as the target framework when creating a project!

I’ve filed the following bugs on connect, so hopefully they get resolved soon!

https://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=514122

[update: I initially posted a link to the wrong bug. The above link has been corrected.]

https://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=514130

Last week, I led a jam about F# at the Ann Arbor Study Group. One of my SRT Solutions coworkers, Ben Barefield, asked a question that warrants further discussion. After I introduced the forward pipe (|>) operator, Ben asked the following:

In F# programming, do you design functions so the last argument is one that you intend for users to pass via the forward pipe operator?

My first response was a tentative “yes”, but I felt like that put too much focus on the forward pipe operator. After some reflection, I think a better answer is to follow this more general best practice:

In F# programming, prefer ordering function arguments from least varying to most varying.

Normally, you’ll see this discussed in the context of currying and partial application, but I think that it is equally important when considering the forward pipe operator. Let’s take a look at some examples of each.

Currying and Partial Application

We’ll start with the Seq.reduce function. The signature for this function is:

Seq.reduce : ('T -> 'T -> 'T) -> seq<'T> -> 'T

The F# documentation states that reduce is used to “Apply a function to each element of the sequence, threading an accumulator argument through the computation.” In practice, reduce is used to compute a single value from a sequence of values. For example:

> Seq.reduce (+) {0..5};;
val it : int = 15

Here, the computation starts with the first two elements of the sequence, 0 and 1. Reduce applies the addition function to these elements to return 1. This is now our current “state” which we carry over into the next step of computation. Reduce will grab the next element in the list, 2, and call our addition function with that argument and our current state of 1 to produce 3. This process continues until we get our result of 15.

Now that we know how reduce works, observe that the arguments are structured from least varying to most varying. When viewed from the standpoint of currying this is handy because it allows us to create useful residual functions through partial application:

> let mySum<'a> = Seq.reduce (+);;

val mySum<'a> : (seq<int> -> int)

> mySum {0..5};;
val it : int = 15

The |> Operator

In F#, it’s common to rewrite the first example from above using the forward pipe operator:

> {0..5}
   |> Seq.reduce (+);;
val it : int = 15

This compatibility with the forward pipe operator also comes naturally as a result of ordering arguments from least varying to most varying. Because the last argument is the one that is most likely to vary, it follows that it is also the argument that we are most likely to pass via the forward pipe operator.

First of all, thanks to all of you who have taken the time to look at Elevate. We have received a lot of excellent feedback. Most of it has been positive, and all of it has been extremely helpful. We didn’t expect to get this much feedback in such a short time, so we’ve been a little behind on providing good support for community involvement. Today, we took a couple steps to fix that problem.

First, we created a Google Group. We’d love to get feedback from you there. You can join here: http://groups.google.com/group/ElevateProject

Second, on the main CodePlex page (http://elevate.codeplex.com), we have added a road map and suggested practices for submitting patches.

Thanks again for all of the feedback we received so far!

Some of the feedback that we’ve received about Elevate has to do with Option types and how they are different or similar to Nullable types in C#. Luke Hoban does a great job of describing some of the differences here:

http://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=470052

If you’ve played around with Option types in F# or another functional language, you should be able to easily understand his argument, but if you haven’t been exposed to Option types before, you’re probably a bit confused as to how they differ from Nullable types. I’ll do my best paraphrasing and cross language explanation here to help you bridge that gap.

In Theory…

In theory, both Option types and Nullable types can be used to accomplish similar goals. Both model calculations that may or may not return a value. For Options and Nullables, an instance either represents a concrete value, or the lack of a value. Let’s take a look at a some examples.

Nullable types in C#:

[Test]

public void Nullables()

{

    int? nullableWithValue = 10;

    Assert.IsTrue(nullableWithValue.HasValue);

    Assert.AreEqual(10, nullableWithValue.Value);

    int? nullableWithoutValue = null;

    Assert.IsFalse(nullableWithoutValue.HasValue);

}

Option Types in F#:

let optionWithValue = Some 10

Assert.IsTrue(optionWithValue.IsSome)
Assert.AreEqual(10, optionWithValue.Value)

let optionWithoutValue = None

Assert.IsFalse(optionWithValue.IsSome)

Note that in F#, it’s common to combine Option types with a technique known as pattern matching, which is beyond the scope of this post. Most F# programmers probably wouldn’t use the fields that I demonstrated in the sample code, but they are provided in case you do want to use them.

Option Types with Elevate:

[Test]

public void OptionTypes()

{

    Option<int> optionWithValue = Option.Some(10);

    Assert.IsTrue(optionWithValue.IsSome);

    Assert.AreEqual(10, optionWithValue.Value);

    Option<int> optionWithoutValue = Option<int>.None;

    Assert.IsFalse(optionWithoutValue.IsSome);

}

In Practice

In practice, things don’t quite work out the way you’d like. For example, consider a “TryFind” function. This function, given a sequence of elements and a predicate, returns the first element where the predicate returns true, or “no element” if the predicate is not matched. In F#, this is written as “Seq.tryFind”. Let’s take a look at an example usage.

let numbers = [0..10]
let five = numbers
           |> Seq.tryFind ((=) 5)

Despite the F# syntax, this should be easy for most programmers to understand, but let’s see what this looks like in C# using the (just added) TryFind function in Elevate.

[Test]

public void TryFind()

{

    var values = 0.Through(10);

    Option<int> result = values.TryFind(x => x == 5);

    Assert.IsTrue(result.IsSome);

    Assert.AreEqual(5, result.Value);

}

Those of you familiar with LINQ will recognize that this looks very similar to the overload of .First that accepts a predicate. The difference is in the case where the predicate does not match any element in the sequence. Instead of throwing an exception, TryFind will return None.

[Test]

public void TryFindOnFailure()

{

    var values = 0.Through(10);

    Option<int> result = values.TryFind(x => x == 20);

    Assert.IsTrue(result.IsNone);

}

Now that we’ve gone over the usage of TryFind, let’s focus on how we might implement it. Here’s how we currently do it in Elevate (minus a few exception checks).

public static Option<TSource> TryFind<TSource>(this IEnumerable<TSource> source,

                                               Func<TSource, bool> predicate)

{

    var results = source.Where(predicate).GetEnumerator();

    if (results.MoveNext())

    {

        return Option.Some(results.Current);

    }

    else

    {

        return Option<TSource>.None;

    }

}

Now, let’s say that we want to implement TryFind using Nullable types instead of an Option type. You’ll notice right away that there’s a problem. Nullable types only work for structs. TryFind needs to be able to return values of any type, not just value types, so right away, we’re stuck.

There’s one other, slightly more insidious problem, though. Say that we were able to create Nullable types for classes. Our implementation for TryFind would look similar to what we have above for Option types. We would return null when no item in the input sequence was matched, otherwise we would return a value, but consider the following example.

IEnumerable<string> items = Seq.Build("Alpha", "Beta", "Gamma", null);

string result = items.TryFind(item => item == "Delta" || item == null);

Here, our result value would be null, but we wouldn’t know if null meant that no item was found, or that null was the string value that we matched. It’s a subtle and somewhat contrived example, but it does show one more way in which Option types help to clean up the code.

The Bottom Line

To sum things up, Option types and Nullable types are similar in theory, but in practice, they accomplish different goals. In general, I find that using Option types makes for cleaner code and helps to communicate the intent of algorithms more clearly. In Elevate, we use Option types in a few places where Nullable types would not be reasonable. Although these aren’t use cases that you may touch on everyday, it’s definitely good to have the option (no pun intended) to use whatever method makes the most sense for your situation, and that’s why we offer Option types in Elevate.

The past few weeks, a few other SRT Solutions developers and I have been working on a new open source library called Elevate. We went public with the source on CodePlex this weekend, and although we’re still in the early stages of development, I already rely on many of the functional programming features of the library in my day to day coding. So, without further ado, I’d like to formally announce the Elevate project.

What Is Elevate?

Let’s face it, no library has it all, and the BCL is no exception. If you’re anything like me, then you occasionally find yourself re-writing some utility methods over and over again for each project that you work on. Even though you know it’s wrong, you probably re-invent the wheel from time to time for “simple” things. Maybe you carry around your own “MyUtilities.cs” file from project to project. Either way, in the back of your mind, you know that there has to be a better way.

For C++ programmers, this void is filled with Boost. Boost contains a lot of functionality that is missing from the C++ STL for one reason or another. It’s a great library for C++ development. But what about us poor C# developers?

That’s where Elevate comes in. Elevate is a Boost-like library for .NET. Our goal at SRT Solutions is to capture the things that we think are missing from the BCL and put them in Elevate so that we can share them between our project groups and the rest of the world. By devoting some of our weekly learning time to add these common bits of code to Elevate, we can save ourselves, our clients, and hopefully other .NET developers time and money.

What do we have so Far?

We can’t add everything overnight, so to start off, we’re focusing on functional programming concepts. We’ve already taken some of the more useful methods and classes from languages like F#, Ruby, and Haskell and added them to our own collection of useful C# utilities. Here are some of the highlights below:

Building sequences:

[Test]

public void MixingAndMatching()

{

    //if you have a couple sequences of values

    var first = Seq.Build("alpha", "beta");

    var second = Seq.Build("delta", "epsilon");

    //you can combine them along with some other values to create a new sequence

    var result = Seq.Build(first, "gamma", second, "zeta");

    var expected = Seq.Build("alpha", "beta", "gamma", "delta", "epsilon", "zeta");

    Assert.AreEqual(expected, result);

}

[Test]

public void Through()

{

    //if we want to easily generate a sequence of incrementing numbers,

    //we can do it like this

    IEnumerable<int> numbers = 1.Through(15);

    var expected = Seq.Build(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15);

    Assert.AreEqual(expected, numbers);

}

“LINQ Extensions”:

[Test]

public void SelectWithIndex()

{

    //given a sequence of values

    var values = 10.Through(50, 10);

    //we can apply a selector function to each element based

    //on the element's value and it's index

    var result = values.SelectWithIndex((index, value) =>

                                             value / (index + 1));

    var expected = Seq.Build(10, 10, 10, 10, 10);

    Assert.AreEqual(expected, result);

}

[Test]

public void Chunk()

{

    //given a sequence

    var sequence = 1.Through(20);

    //we can split the sequence into a sequence of "chunks" that

    //are each a specific length

    var chunks = sequence.Chunk(5);

    var expectedChunks = 

        Seq.Build<IEnumerable<int>>( 

            1.Through(5).ToList(),

            6.Through(10).ToList(),

            11.Through(15).ToList(),

            16.Through(20).ToList());

    Assert.AreEqual(expectedChunks, chunks);

}

[Test]

public void Select2()

{

    //given two sequences

    var one = 0.Through(5);

    var two = 2.Through(12, 2);

    //we use Select2 to walk the sequences in parallel and apply a

    //selector function

    var result = one.Select2(two, (elementFromFirst, elementFromSecond) => 

            elementFromFirst * elementFromSecond);

    var expected = Seq.Build(0, 4, 12, 24, 40, 60);

    Assert.AreEqual(expected, result);

}

[Test]

public void PatternMatchingWithFunctions()

{

    //given a value

    var value = "alpha";

    //we can start a pattern match like this

    var result = value.Match()

        //causes the pattern match to return "empty" if value is null or empty

        .With(string.IsNullOrEmpty, stringValue => "empty")

        //match any string containing "a"

        .With(stringValue => value.Contains("a"), stringValue => "contains a!")

        .EndMatch();

    Assert.AreEqual("contains a!", result);

}

[Test]

public void EasierTuplePatternMatching()

{

    //given a tuple

    Tuple<string, int> tuple = Tuple.Create("Da Bears", 2);

    //We can avoid having to specify the arguments explicitly for the

    //match portion of the predicate like this

    var result = tuple.Match()

        .WithSecond(1, (teamName, wins) => wins + 1)

        .WithFirst("Da Bears", (teamName, wins) => wins)

        .EndMatch();

    Assert.AreEqual(result, 2);

}

Option Types:

[Test]

public void OptionTypesCanContainValues()

{

    //given a value

    var value = 10;

    //we can wrap it in an option type like this

    Option<int> option = Option.Some(value);

    Assert.IsTrue(option.IsSome);

    Assert.IsFalse(option.IsNone);

    Assert.AreEqual(10, option.Value);

}

[Test]

public void MultipleOpertionsWithOptionTypes()

{

    //say we have a few functions that may or may not return a value.

    Func<int, Option<int>> divideIfEven = value =>

        ((value % 2) == 0) ? Option.Some(value / 2) : Option<int>.None;

    Func<int, Option<int>> subtractIfDivisibleByThree = value =>

        ((value % 3) == 0) ? Option.Some(value - 3) : Option<int>.None;

    Func<int, Option<int>> multiplyIfOdd = value =>

        ((value % 2) != 0) ? Option.Some(value * 2) : Option<int>.None;

    //we can chain these operations together like this:

    Option<int> result =

        divideIfEven(36)

        .Select(subtractIfDivisibleByThree)

        .Select(multiplyIfOdd);

    //the result of one carries on to the next to yield the expected result

    Assert.IsTrue(result.IsSome);

    Assert.AreEqual(30, result.Value);

}

These are just a few samples of the things you can do with Elevate, but there is a lot more to play around with in the actual library. Hopefully, you’re convinced that there are already a number of interesting functional programming features.

Moving Forward

If you’re interested in the above samples, head on over to http://elevate.codeplex.com and check out the source. All of the above samples are copied right out of the “Elevate.Guide” test project. We wrote this project with the goal that someone who has no experience with Elevate can get up and running quickly just by reading through it.

Over the next few weeks, I will try to post about some of the features in Elevate in more detail. If you’re a C# programmer interested in functional programming, a functional programming guru who wants to see examples of functional programming in C#, or simply someone interested in seeing cool and useful language extensions, stay tuned for more detailed posts.

Finally, we would love to hear any feedback (good or bad) and any feature requests that you might have. There are a number of ways to get in contact with us. You can submit comments below, start a discussion or submit a review on the CodePlex page, send an email through CodePlex, or send me a tweet (my username is ChrisMarinos on CodePlex and twitter). Also, speaking of Twitter, be sure to follow @elevateproject for updates!

Update: Check out our GoogleGroup at http://groups.google.com/group/ElevateProject!

During CodeMash this past January, I had the opportunity to talk with Chris Smith about F#. One of the things that he considered to be a sweet spot for the language was programming “in the small”. At the time, I didn’t completely agree with his claim, but after writing more F# and functional C# code, I see where he was coming from.  Programming in the small is an important part of developing software, and it is an area where F# excels.

What is programming in the small?

Brian McNamara of the F# team has a great post where he describes how functional programming impacts code in the “large”, “medium”, and “small”. His post is well worth a read if you know a little bit about functional programming, but for those of you coming from a C# or Java background, I’ll summarize here. Programming in the small is the code that goes inside a method body. As Brian puts it, this is the code that actually “does stuff”. In this context, programming in the medium is code at the class/interface/module level, and programming in the large is code that spans multiple classes and interfaces. For the rest of this post, I’m going to focus on the programming in the small, but it’s good to put everything in context.

How does functional programming improve the code you write in the small?

Before we dive into F#, let’s start with techniques for programming in the small that are more familiar to C# developers. Consider the following code to square a list of numbers:

            IList<int> values = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

            IList<int> squaredValues = new List<int>();

            for (int i = 0; i < values.Count; i++)
            {
                squaredValues.Add(values[i] * values[i]);
            }

In the C/C++ days, we were stuck with this. Although this is a simple algorithm, you can see that there is significant amount of overhead describing things that we shouldn’t have to bother with. Instead of saying “square each item in the list” we have to say “Make a new list. Then with each number from zero to the number of items in the list, index into the list with this number and square that value. Finally add that number to the new list”.

C#, like many languages,  gives us a better way to express this algorithm:

            var values = Enumerable.Range(0, 10);

            IList<int> squaredValues = new List<int>();

            foreach (int value in values)
            {
                squaredValues.Add(value * value);
            }

With a foreach loop, we can see that the code gets better.  Now we say “Make a new list. Then for each element in the input list, square it and add it to the new list”.

Now let's take a look at a solution that uses a functional approach. No, we’re not going to write F# code yet. Instead, we’re going to write a LINQ query. We’re doing this because LINQ uses some of the functional techniques that makes F# great at programming in the small.

            var values = Enumerable.Range(0, 10);

            var squaredValuesQuerySyntax = from value in values select value * value;

Now our code says “for each value in the list, square it” which is exactly what we were trying to describe in the first place. Even for this trivial example, we wrote less, cleaner code to solve our problem.

Now for F#. The last snipped of C# code is almost the same as what we would write in F# once we re-write our LINQ expression to use extension method syntax:

            var squaredValuesExtensionMethodSyntax = values.Select(value=>value*value);

Now, here is the equivalent F# code:

      let values = [0..10]

      let results = values |> Seq.map (fun value -> value * value)

In F#, we use the let keyword instead of var, the map function instead of Select, and the |> operator instead of using an extension method. Other than that, the flow of our code is the same as we did with LINQ.

The Story So Far

So, the question is, what makes the functional code above better?

The key observation is that the above code separates the looping algorithm from the squaring algorithm. It’s like we used dependency injection, but it happened at the method level- in the small, instead of at the class level.

Most programmers know that duplicating code is a bad practice, but while coding in imperative languages, many of us ignore that advice when writing loops. Loops are considered to be idioms, and somehow get a free pass from the Don’t Repeat Yourself rule.

Functional languages take a different approach. Instead of constantly re-writing for the same chunks of “simple” loop logic, they use small, single purpose functions to capture the common looping code. The advantage of this approach is twofold. First, you write less code to express looping constructs. Second, you can easily glue these small functions together to perform more complicated operations. It’s the same technique that makes the *nix and PowerShell terminals so powerful.

Going  Further With F#

We’ve seen how using functional techniques can improve C# in the small, but what makes F# better at programming in the small? This question would take a book to answer, but here are a few reasons:

-Better library support. F#’s Seq module is far more robust than LINQ and offers many extra “glue” functions to help you stitch your code together.

-Better compiler support. Consider the following example:

        public static int Square(int value)
        {
            return value * value;
        }

        public void ProblemsWithTypeInference()
        {
            var values = Enumerable.Range(0, 10);

            var results = values.Select<int, int>(Square);
        }

We want to say values.Select(Square) without having to specify the type arguments. After all, the compiler has enough information to infer the types. Unfortunately, in C#, the code will not compile if we omit the generic type parameters. In F#, this code looks like this:

let Square x = x * x

let GoodTypeInference =
    [0..10]
    |> Seq.map Square

Aside from not having to specify the type of the map function (F#’s equivalent of Select), we didn’t have to specify the type anywhere else either. The F# compiler simply infers the types of each variable or method. This makes code inside the method body extremely concise and easy to work with.

-Functional constructs including option types, discriminated unions, pattern matching, and much more. If you’re coming from a C# background, you probably don’t know a lot about these constructs, but they truly separate F# from C# and were designed specifically to aid the functional style that makes programming in the small better. A few hours spent learning about even a few of these F# language features is well worth the time invested.

First thing’s first. If you’re interested in an in depth description of the changes to F# in the 2010 beta and the May CTP, look no further than this post by Don Syme. Clearly, the F# team has been busy:

http://blogs.msdn.com/dsyme/archive/2009/05/20/visual-studio-2010-beta1-with-f-is-now-available-plus-matching-f-ctp-update-for-vs2008.aspx

After parsing the above notes and spending a little time with the new version of F#, here are my early impressions.

The Good

Vastly Improved Visual Studio Integration

The September CTP version of F# featured some Visual Studio integration, but it was very buggy. The Error List often contained false positives after compiling a project. Errors from background compilation were lacking as well. With the new release, both Visual Studio 2008 and 2010 Beta 1 see huge improvements in both of these areas.

With the new release, the difference has been night and day. Background compilation updates the error list swiftly, and all the errors that I’ve seen so far have been legitimate. Better Visual Studio integration was a clearly a big, if not the biggest goal of this release, and the good news is that the F# team seems to have nailed it.

There is still some work to be done before I’d say that the environment is ideal, but it’s great to have these improvements since this was an area of weakness in the September CTP release. I need a good reason to play with the updated debugger integration, but the team has indicated that there are some improvements there, too.

Performance

Although it’s not getting as much attention as, this is one of the most notable changes in this release. According to Don Syme’s post, sequence expressions, tail calls, and other areas should see increased performance. I haven’t had time to crunch numbers, but I have already observed a big performance increase when running Paint Wars. With the previous CTP release, I was only able to crunch about 75 blobs at one time. With no other changes to the code besides updating to use the new CTP, I’m able to crunch at least twice as many. Thanks to these performance improvements, I’m looking forward to finally being able to finish the F# version of Paint Wars.

I suspect that most of the performance gains come from this tidbit from Don Syme’s post:

“Sequence expressions are now compiled to state machines, instead of as a collection of API calls.  This results in improved performance of F# code which works with seq.  Many of the Seq.* lib0rary functions also have improved performance as a result of this change”

Since the Seq library functions form the backbone of a lot of the F# code that I write, I’m definitely excited about this change.

Standard Library Naming Conventions

Performance improvements are nice, but I am also really happy about (most) of the name changes to the F# Standard Library. Prior to these changes, it was unclear what the best practices for naming were. Should the .NET guidelines be followed? If so, why doesn’t the F# library follow them? Now, the picture is starting to get a little bit clearer.

Per Don Syme’s blog:

“The naming conventions adopted for the F# library are as follows:

o All .NET and F# OO code uses PascalCase according to existing .NET guidelines

o The F# functional programming operators such as List.map are for use in F# internal implementation code. This kind of code uses camelCase for operator names

o Underscores should not be used except for the Module.to_type and Module.of_type pattern. In Beta1 you will only see underscores for this pattern “

Although these changes might not seem that exciting, I think that it is really important to see consistency across the standard library since it has such a large influence on the way the F# community writes code.

Support for custom numeric types (123X, 1.0R, etc.)

This looks pretty cool. I’d like to look into this in more depth and blog about it later. I’m not sure that there are a ton of uses for this, but it seems like a feature that could be abused in a good useful fun way.

Miscellaneous Small (but good) Improvements 

These are some other things that I thought were good additions, but they don’t warrant much discussion:

• #light as default – Good. Almost all F# code I’ve ever seen began with #light
• Support for calling and exposing .NET ParamArray parameters (‘params’ in C#) – This is convenient. It was annoying to have to package values up as arrays so that they would work with params array functions.
• F# uses .NET 4.0 tuple, BigInt, Lazy types – Also good. It’s the correct thing to do.

The Bad

No Seq.Parallel

The addition of Array.Parallel functions is exciting. Unfortunately, for some reason, the same functionality was not provided for Seq. It would definitely be nice to see the F# team provide a Seq.Parallel that integrates with the Parallel Extensions in .NET 4.0. Writing F# style wrappers over PLINQ functions is straightforward to do, but it should be a part of the Standard Library. I imagine that this will happen soon, though.

Renaming _right to Back

In short, Fold_right and Scan_right have been renamed to FoldBack and ScanBack. Fold and Scan are the “_left” variants.

I won’t dwell on this one since it is a matter of personal preference, but I don’t like it at all. I understand why the change was made. “Back” might even be a better way to describe the behavior of these functions. The problem is that the “right/left” naming of these functions was already well defined and established in the functional world. This looks like one of those cases of Microsoft trying to make something less confusing to the average Joe that results in lots of parenthetical comments and ultimately more confusion.

No New PowerPack Release

This one stinks because I was relying on the SI module for units of measure in Paint Wars. Unfortunately, the September CTP version of the Power Pack can’t be used since binaries are not compatible between the two releases. I ended up having to copy and paste the SI module into my project from the CTP source.

I would wager that a new Power Pack release is not far off. However, considering that the Power Pack is supposed to release more frequently than the core library, it is irritating that a new Power Pack not included in this release.

Update: The PowerPack has been released for 2010 Beta1 http://www.microsoft.com/downloads/details.aspx?FamilyID=e475a670-9596-4958-bfa2-dc0ac29b4631&displaylang=en

Still Can’t Click and Drag To Reorder Files in Solution Explorer

This is a minor oversight, but with all the work to better integrate F# with Visual Studio, I was hoping the team would catch this one. To reorder .fs files in the Solution Explorer, you still have to right click and select “move item up” or “move item down” (remember, in F# projects, file order matters). I was recently reminded of how nice it would be to be able to click and drag to reorder files when I discovered that “Add Existing Item” adds files to the bottom of the project. I had to do the right click, “move item up” dance about 15 times. Minor, yes. Annoying, definitely.

The Ugly

Difficult to work with same project in both 2010 and 2008 CTP

The PaintWars solution contains an XNA project which doesn’t appear to be compatible with Studio 2010 Beta 1. Before I realized this, I tried to open the solution in the 2010 beta which upgraded my .fsproj. When I tried to open the same project in Visual Studio 2008, I ran into problems since the FSharp.Core assembly was pointed at the 4.0 version and the compiler was switched to the 4.0 version as well. This is not a bug, but it’s worth warning that you have to stick with either the 2008 version or the 2010 version unless you want to maintain two .fsproj files.

Remove References to System.Threading If Using the June CTP of the Task Parallel Library

This isn’t F# specific, but since many people use F# for parallel processing, I figured that I should mention this. If you had a project that used the June 2008 CTP of the Task Parallel Library, be sure to remove the reference to the System.Threading .dll when you upgrade to .Net 4.0. I was using a couple PLINQ functions, and since PLINQ is now included in the .NET 4.0 core libraries, the F# compiler will complain with overload errors if you don’t remove the reference.

For example, using the IEnumerable.AsParallel() method results in the following, potentially confusing, error:

Error    1    The method 'AsParallel' is overloaded. Possible matches are shown below (or in the Error List window)

Removing the reference to System.Threading, makes everything better. Of course, you have to keep the reference if you’re using Visual Studio 2008

The Bottom Line

Aside from a few minor hiccups, the F# team has done a great job with this new release of F#. Download the May 2009 F# CTP or the Visual Studio 2010 Beta 1 and start playing around with the new F#!

Recently, I’ve been exploring different options for testing in F#. I was pleased to find out that there has been some good work done in this space already:

• Matthew Podowysoki’s Functional Programming Unit Testing series is a great overview of testing in F#.
• The FsUnit project is a specification style testing framework written in F#.
• FsCheck is a port of Haskell’s QuickCheck to F#. QuickCheck is a tool for randomly generating tests.

One of the things that I didn’t find was a good solution for BDD-style testing. I’m not a BDD fanatic, but I am definitely a fan of the extra mile that BDD frameworks go to blend tests and specifications. FsUnit has support for specification style tests, but as a whole, I felt that the project was a too young to be an ideal solution. Plus, I didn’t have the desire to start learning and using yet another testing framework.

Using xUnit.net as a starting point, I decided to try writing my own BDD extension.

Let’s say that I have a two dimensional vector type that I want to test:

    type Vector = 
        { X : float;
          Y : float; }
    module VectorOperations =
        let Add one two =
            { X = one.X + two.X; Y = one.Y + two.Y }

The syntax that I came up with looks like this:

let context = Given "a zero vector, v1," {X=0.0; Y=0.0}

[<BDDFact>]
let VectorAdditon () =
    let outcome = context.With "a vector, v2, of (1,1) added to it" (fun vector -> vector + {X=1.0; Y=1.0})
    outcome.Observe "the result is a new vector = (v1.x + v2.x, v1.y+v2.y)." (fun _ result -> Assert.Equal({X=1.0; Y=1.0}, result))

This syntax is very similar to the syntax that NBehave uses, but I like that it does not rely on a combination of closure and mutable state to pass information from between the “given”, “with”, and “then/assert/observe” portions of the test. I also like that I don’t have to rely on class hierarchies and a bulky testing framework to get the BDD style naming that I want.

Here’s the full implementation:

#light

namespace BDDExtensions

open System
open System.Reflection
open System.Xml
open Xunit
open Xunit.Sdk

module BDDExtensions =
    let mutable Observations = []
    
    type Outcome<'a, 'b>(message, context, result) =
        member this.Observe observationMessage (action:'a -> 'b-> unit) =
            Observations <- (message, (fun () -> action context result)) :: Observations
            
    type Context<'a>(message:string, value) =
        member this.With withMessage func =
            new Outcome<'a, 'b>(String.Concat([|message; "with"; withMessage|]), value, func(value))
         
    let Given (message:string) (value:'a) = new Context<'a>(String.Concat("Given ", message), value)

    
    type BDDCommand(assertion, displayName, info) =
        interface ITestCommand with
            member this.ShouldCreateInstance = false
            member this.Execute testClass = 
                try
                    assertion()
                    new PassedResult(info, displayName) :> MethodResult
                with 
                    ex -> new FailedResult(info, ex, displayName) :> MethodResult
            member this.DisplayName = displayName
            member this.ToStartXml () =
                     let doc = new XmlDocument()
                     doc.LoadXml("<dummy/>")
                     let testNode = XmlUtility.AddElement(doc.ChildNodes.[0], "start")
                     XmlUtility.AddAttribute(testNode, "name", displayName)
                     XmlUtility.AddAttribute(testNode, "type", info.ReflectedType.FullName)
                     XmlUtility.AddAttribute(testNode, "method", info.Name)
                     testNode 
                     
    [<AttributeUsage(AttributeTargets.Method, AllowMultiple = false, Inherited = true)>]
    type BDDFactAttribute() =
        inherit FactAttribute()
        override this.EnumerateTestCommands(info:MethodInfo) =
            info.Invoke(null, null) |> ignore
            Observations
            |> Seq.map (fun (name, assertion) -> new BDDCommand(assertion, name, info))
            |> Seq.cast<ITestCommand>

As displayed in the Vector example above, the first thing that we do is call the Given function. This sets up a Context that takes a function to arrange the test. Next, we call the With method on our Context to perform the operation that generates the result we want to test. Then we check as many conditions as we need by using the Observe function on the Outcome we created. Each outcome adds an action to the mutable Observations list.

When the xUnit framework encounters a BDDFactAttribute on a method, it first executes the method to populate the list of observations. For each observation, we return a BDDCommand. The xUnit framework then executes each command as a separate test case. This causes the command’s action to be executed and any failed assertions to throw errors which the xUnit framework displays in its test output.

Here’s the result. As you can see, the test name is extremely readable:

The code is definitely a little rough around the edges (*cough* mutable static variable *cough*). As always, I was impressed by how few lines of F# code it took to do what I wanted, but I was also impressed by how easy it was to extend xUnit.

F# introduces Record Types and Descriminated Unions to the .NET universe. Although I knew that these types eventually boiled down to reference types, I wanted to make sure that nothing funny was going on behind the scenes when they got instantiated. The results weren’t terribly exciting, but I learned some important things about performance testing along the way.

First Attempt

The first thing I did was create a few basic types:

[<Struct>]
type StructWithImplicitConstructor =
    val x : int
    val y : int
   
[<Struct>]
type StructWithExplicitConstructor =
    val x : int
    val y : int
    new (one, two) = {x = one; y = two}

[<Struct>]
type StructWithObjectConstructor(x:int, y:int) =
    member this.X = x
    member this.Y = y
   
type ObjectWithImplicitConstructor =
    val x : int
    val y : int
   
type ObjectWithExplicitConstructor =
    val x : int
    val y : int
    new (one, two) = {x = one; y = two}
   
type ObjectWithObjectConstructor(x:int, y:int) =
    member this.X = x
    member this.Y = y

type RecordType =
    { x:int;
      y:int }
     
type UnionType =
    | X of int
    | Y of int

Then, I broke out a System.Diagnostics.Stopwatch and started testing how long it took to new up these objects. My first results varied wildly. JITer optimizations and garbage collection behaviors yielded bizarre and inconsistent results. After talking this over with coworkers Bill Wagner and Jay Wren, I made a second pass.

Getting Smarter

This time, I started with a more robust performance testing module:

module PerformanceTesting =
    let Time func =
        let stopwatch = new Stopwatch()
        stopwatch.Start()
        func()
        stopwatch.Stop()
        stopwatch.Elapsed.TotalMilliseconds
        
    let GetAverageTime timesToRun func = 
        Seq.init_infinite (fun _ -> (Time func))
        |> Seq.take timesToRun
        |> Seq.average
        
    let TimeOperation timesToRun =
        GC.Collect()
        GetAverageTime timesToRun
        
    let TimeOperations funcsWithName =
        let randomizer = new Random(int DateTime.Now.Ticks)
        funcsWithName
        |> Seq.sort_by (fun _ -> randomizer.Next())
        |> Seq.map (fun (name, func) -> name, (TimeOperation 100000 func))
    
    let TimeOperationsAFewTimes funcsWithName =
        Seq.init_infinite (fun _ -> (TimeOperations funcsWithName))
        |> Seq.take 50
        |> Seq.concat
        |> Seq.group_by fst
        |> Seq.map (fun (name, individualResults) -> name, (individualResults |> Seq.map snd |> Seq.average))

The above code makes it easy to time operations with greater accuracy. The TimeOperationsAFewTimes function takes a sequence of tuples containing the names of operations to test and the operations themselves. It runs the operations a few times and returns a sequence of tuples that contains the operation names and the average run time for each operation.

There are two important lessons for performance testing to take away from the example. First, the garbage collector is run between tests to make sure that each operation has a clean memory slate. Second, the order that the operations run in is varied between runs in order to help negate the effect of JITer optimizations in our tests.

(As an aside, the TimeOperationsAFewTimes function was really fun code to write. It was one of those moments that made me stop and take notice at the power of the F# language. I realize that the code might be a little difficult to read at first glance, though.)

Results

With the above functions, performance testing became a breeze:

printfn "Starting Tests..."
printfn ""

let tmpRec = {x = 0; y = 50}
 
PerformanceTesting.TimeOperationsAFewTimes 
    [ "RecordType", (fun () -> {x = 1; y = 50}|> ignore)
      "StructWithImplicitConstructor", (fun () -> new StructWithImplicitConstructor() |> ignore) 
      "ObjectWithObjectConstructor", (fun () -> new ObjectWithObjectConstructor(1, 50) |> ignore)
      "ObjectWithExplicitConstructor", (fun () -> new ObjectWithExplicitConstructor(1, 50) |> ignore)
      "StructWithObjectConstructor", (fun () -> new StructWithObjectConstructor(1, 50) |> ignore)
      "StructWithExplicitConstructor", (fun () -> new StructWithExplicitConstructor(1, 50) |> ignore)
      "CreatingUsingWith", (fun () -> { tmpRec with x = 1 } |> ignore)
      "UnionType", (fun () -> X 14 |> ignore)]
|> Seq.sort_by (fun (name, time) -> time)
|> Seq.iter (fun (name, time) -> printfn "%s: %f" name time)

printfn ""
printfn "Press Any Key To Continue..."
      
let tmp = System.Console.ReadKey()

The above code passes a list of tupled names and lamdas to the performance testing functions, sorts them from least to most expensive and prints the results.

Here are the results of a few runs:

Starting Tests...

CreatingUsingWith: 0.001973
StructWithExplicitConstructor: 0.001988
StructWithImplicitConstructor: 0.001992
UnionType: 0.002030
RecordType: 0.002064
ObjectWithExplicitConstructor: 0.002066
ObjectWithObjectConstructor: 0.002081
StructWithObjectConstructor: 0.002092

Press Any Key To Continue...

Starting Tests...

StructWithImplicitConstructor: 0.001407
CreatingUsingWith: 0.001408
RecordType: 0.001423
StructWithExplicitConstructor: 0.001436
ObjectWithObjectConstructor: 0.001438
UnionType: 0.001438
StructWithObjectConstructor: 0.001449
ObjectWithExplicitConstructor: 0.001455

Press Any Key To Continue...

Starting Tests...

RecordType: 0.001365
UnionType: 0.001374
StructWithImplicitConstructor: 0.001380
CreatingUsingWith: 0.001381
StructWithObjectConstructor: 0.001385
StructWithExplicitConstructor: 0.001386
ObjectWithExplicitConstructor: 0.001397
ObjectWithObjectConstructor: 0.001404

Press Any Key To Continue...

The Moral of The Story

The bottom line was that there were not any meaningful differences in the amount of time required to instantiate an object using any of the methods that I tried.

At first, my C and C++ roots were dumbfounded that value types didn’t beat the pants off of everything else. After Thinking critically, I realized that this makes a lot of sense in the managed world because the cost of creating reference types doesn’t include a hefty price for heap allocation.

The other thing that I proved to myself was that Record Types and Discriminated Unions are just as inexpensive to create as any other native .NET type.

This post is the fourth in a series of posts about the code behind PaintWars. In this series, I will be talking about how the design and implementation of the game differed in C# and F#.  Along the way, I'll also be talking about some of the fun and exciting features of the F# language and examine how they can be used to solve practical software problems. For a description of the game, see this post.

In my previous two PaintWars posts, I covered the design of Paint Wars from both an OOP and a functional standpoint. In this post, I'll get practical and combine the two disciplines to produce a real result. We'll use F# to do it because it excels at being multi-paradigm.

We're going to dive right into code. I won't go into details about the syntax here, but the code below forms the basis of all of the interactions in the game.

type IGameObject =
    abstract Id : Id
    abstract Position : Vector
    abstract Attackable : bool
    abstract Color : Color
    abstract Texture : Texture2D
    abstract DrawOffset : Vector
    abstract BoundingObject : BoundingObject option
    abstract Solid : bool
    abstract GetFrame : Time -> Rectangle
    abstract Update : GameState -> GameStateTransform List
    abstract ApplyTransform : GameState-> ObjectTransform -> IGameObject

The first thing that's we define is an interface for game objects. This is similar to the abstract base class that we had in the OOP approach. The most important functions here are the Update and ApplyTransform functions since they are the plumbing for most of the engine. As you can infer from the interface definition, none these functions modify the state of the object.

and ObjectTransform =
    | MoveAbsolute of Vector
    | MoveRelative of Vector
    | ChangeAnimation of Animation
    | GetPickedUp of Color
    | GetPutDown of Vector
    | StartPickingUp
    | StopPickingUp
    | AcquireObject of IGameObject
    | DropChildren
    | TakeDamage of (Color * HitPoints)
    | SetSpawnTicks of int
    | SetPaintRechargeTime of Time
    | Die
    | WaitForNextSpawn

Next we describe the set of transforms that can be applied to a GameObject. I talked about how the transforms work in the last post, but these transforms are used by a GameObject's Update function to produce a new GameObject from an existing one. In the OOP approach, these ObjectTransforms would be Abstract methods on the base object.

and GameState =
    { PlayingArea : Rectangle
      ObjectsById: Dictionary<int, IGameObject>
      Partition : PartitionElement
      Canvas : Canvas
      CanvasState: CanvasState
      PaintList : PaintableGameObject List
      TimeSinceLastState : Time
      Time: Time }

The next thing that we define is the GameState record. This contains the state of the game before and after an update. Most of the members should be self explanatory, The Canvas, CanvasState, and PaintList all deal with how the paint gets drawn on the map, and the Partition member deals with the spatial partitioning algorithm used for collision detection. We'll ignore those for the purpose of this post. Also of interest is the ObjectsByID dictionary. It's mutable for performance reasons, but an immutable container would work if we wanted to stay pure.

and GameStateTransform =
    | AreaOfEffect of (BoundingObject * ObjectTransform)
    | ById of (Id * ObjectTransform)
    | Remove of Id
    | Add of IGameObject
    | Paint of PaintableGameObject

Finally, we define the GameStateTransform type which lists all of the transforms that can be performed on a GameState.

state.ObjectsById.Values
|> ParallelSeq.map (fun gameObject -> gameObject.Update state)
|> Seq.reduce (fun currentList toAppend -> currentList @ toAppend)
|> Seq.fold ApplyTransform state 

Now we get to the fun part. After doing all the hard work of defining the above types and the IGameObject implementors, we can run them with the above code. Let's go line by line to explain exactly what is happening.

|> ParallelSeq.map (fun gameObject -> gameObject.Update state)

This bit of code generates a list of list of GameStateTransforms from the list of objects on the previous state. As described in the last post, we can do this in parallel since none of the generator functions share any mutable state. Note that the ParallelSeq function is just a wrapper around map/select in the Task Parallel Library.

|> Seq.reduce (fun currentList toAppend -> currentList @ toAppend)

This line just transforms the list of lists into a flat list of GameStateTransforms.

|> Seq.fold ApplyTransform state

Lastly, we just apply each transform to the GameState to produce our state for the next frame of gameplay. The ApplyTransform function is defined elsewhere, but as it's name indicates, all it does is apply a GameStateTransform to a Gamestate to produce an updated GameState.

Although there is a lot of other code in the PaintWars project, most of the engine is written out above. It is possible to write in such a small space because F# code can be both terse and multi-paradigm. This combination is also one of the reasons that F# is such a fun language to program in.

I'm taking a post off from the Paint Wars posts, but I think this one is worth it.

Many languages have nice syntactic sugar for creating a sequence of numbers. Usually, the syntax says something like:

The expression "1..5" expands to the list "1, 2, 3, 4, 5".

This syntax lets you do fun things like the below F# code:

for i in 1..5 do
    printfn "%d" i

Like a lot of syntactic sugar, this is simple but powerful. So, how can we get similar effects in C#? Hint:It's very simple with extension methods.

public static IEnumerable<int> Through(this int startValue, int endValue)
{
    int offset;
    if (startValue < endValue)
    {
        offset = 1;
    }
    else
    {
        offset = -1;
    }

    for (int i = startValue; i != endValue + offset; i += offset)
    {
        yield return i;
    }
}

Now, we can write code like this in C#:

foreach(var i in 1.Through(5))
{
    Console.WriteLine(i);
}

Sure, the syntax is not quite as nice as 1..5, but it is not too bad, either.

Don't forget to write extension methods on int, long, and all of the other numeric types to support this. Another obvious addition is an overload that takes an additional argument for "step" (eg. "1.Through(7, 2)" would produce produce the sequence "1, 3, 5, 7").

This post is the third in a series of posts about the code behind PaintWars. In this series, I will be talking about how the design and implementation of the game differed in C# and F#.  Along the way, I'll also be talking about some of the fun and exciting features of the F# language and examine how they can be used to solve practical software problems. For a description of the game, see this post.

It's no secret that most games and graphics intensive applications are written in imperative languages. It's also no secret that until recently, functional languages have only found widespread adoption in academia. That being said, it is not surprising that one of the few examples of writing games in functional languages before Paint Wars was a thesis paper.

With the design exploring relatively uncharted waters, what did the F# design of Paint Wars look like?

Back to the Basics

Functional languages have deep roots in mathematics, so the design of Paint Wars also resembles a series of mathematical equations.

Think of the equation "2 + 3 = 5". One way of breaking down this equation is that "+ 3" is a transform to 2. When we apply this transform to an input of 2, we get an output of 5. Similarly, we can apply a transform of "+ 4" to an input of 5 to get an output of 9.

Now, let's apply this analogy to the game of Paint Wars. We will replace 2 in the "2 + 3 = 5" equation with a game state, and we will replace "+ 3" with a game state transform. Let's say we have a game state of "one blob at position (1,1)" and a transform of "kill all of the blobs at position (1,1)". We can plug this into our equation format and get something that looks like this:

"one blob at position (1,1)" + "kill all of the blobs at position (1,1)" = "no blobs"

This approach to design may seem like a trivial shift from traditional imperative design, but it has powerful implications such as:

• Testing becomes a lot easier. This is because for any given input state and any given transform, we know that the output state will always be the same, just like we always know that adding 3 to 2 equals 5.
• It is much easier to reason about code written in a mathematical style. Basically, it's easier to write code that "gets it right".
• Writing code in this fashion means that some steps in the game loop can be performed in parallel. More on this below.

Getting Practical - The Game Loop

All that math rubbish might sound smart, but it does not make for a complete game loop, so lets fill in the missing pieces. As I talked about in the last post, XNA loops are normally split into an update step and a draw step. In the functional version, we will keep the update and draw steps separate, but we'll split the update into a couple steps.

First, we produce a list of transforms to the game state. This can be done in parallel since the process for generating transforms depends only on an input game state and not on other transforms.

Next, we apply them to the input game state to produce a new game state. We can't go parallel here, since we need the output state of one transform to pass as input to the next.

Once we're done applying all of the transforms, we can pass the final game state to our draw function. After drawing, the input state gets passed to the update function as input to produce the next game state.

To be Continued

What I outlined above is the core of the design, but there are a few details that I glossed over. How do the transforms get generated? How do they get applied? Does this approach work in practice? Where is the code?

I'll have more on all of those questions in the next post where I will talk about meshing ideas from the object oriented and the functional designs.

This post is the second in a series of posts about the code behind PaintWars. In this series, I will be talking about how the design and implementation of the game differed in C# and F#.  Along the way, I'll also be talking about some of the fun and exciting features of the F# language and examine how they can be used to solve practical software problems. For a description of the game, see this post.

For most readers, this post will not be as exciting as future posts about the design of Paint Wars will be, but every story has to start somewhere, and the story of Paint Wars begins with an object oriented design in C#.

The Structure of an XNA Game

This post is not meant to be an introduction to XNA programming, but I will include an extremely brief introduction to the XNA Game loop for our purposes.

As with most game loops, XNA games consist of two important methods: Update and Draw (in reality, there are a few more setup methods, but they don't matter yet). The XNA Framework calls the update function so that the game can progress from one state to another based on player input and whatever game logic is required. This usually happens many times per second. After the update function runs, the draw function is called to render the current game state to the screen. The XNA framework runs a game by continually calling these two functions until the end of the game occurs.

The Model Class

In Paint Wars, most of the update and draw logic is handled in the Model class, which is a container for all of the objects in the game. It's responsibilities include the following:

• Telling all objects in the game to update and draw. Draw order matters, and the Model class handles this.
• Performing collision detection on game objects. The Model class uses basic spatial partitioning to improve the performance of this. I'll go into more detail about this in a future post.
• Providing access to the Canvas, which is the interface for determining the status of the paint on the game board. Again, more on this in the future.

Class Hierarchy

The above diagram shows the class hierarchy for the C# version of Paint Wars. The base class, WorldObject, has abstract methods for common operations such as drawing, updating, moving, and taking damage. WorldObject is considered to be a fat interface because the extra methods (fat) are not needed by some child classes.

This type of design has the advantage of being easy to consume.  When a player presses the nuke button, the Cursor class asks the Model for a list of nearby objects and calls the TakeDamage function on all of the objects. It doesn't matter if the object can actually be damaged. Objects that can be damaged will override the TakeDamage function.  Otherwise, the base class implementation will just "do the right thing".

Similarly, Update and Draw are easy operations for the Model- just iterate the list of WorldObjects, and call either the Update or the Draw function. Polymorphism and Object Oriented Programming 101, right?

Observations

Now that all the busy deign work is out of the way, lets make a few observations about the above OO design:

Pros:

• You don't have to modify the rest of the code to add new types.
• There is no "switch on type" code (if/else blocks or switch statements) that can introduce subtle bugs when new types of objects are added.
• Separation of concerns and encapsulation means that it's easy work in teams (you write BlobObject, I'll write SpawnPoint). It also makes debugging, testing, and maintaining code, a lot less painful.
• Cool diagrams.

Cons:

• Complexity is handled through inheritance. If you want an object to behave differently, you create a subclass and override the appropriate method.  This works well on paper, but in code, it usually becomes difficult to follow.
• There are a lot of classes to worry about. Best practices say that each class belongs in a different file. Without a fancy diagram, it is difficult to see the big picture. A lot of code is wasted on class definitions and plumbing.
• Flexible to a point. Think of a thin wooden rod. It's very flexible if you only apply a little pressure, but if you put too much pressure on it, it snaps. Similarly, the above class hierarchy appears to be very flexible if you have small requirements changes, but if your requirements change drastically, you will be in a world of pain until you rewrite your plumbing.
• A lot of mutable state hidden inside of classes.  Code designed this way will not work in a multithreaded environment without some serious modification.

In the next post, I'll describe the functional/F# design and examine the tradeoffs between the different designs.

At the SRT Solutions booth at CodeMash this year, we will be showcasing Paint Wars, which is a Wii remote controlled game built on the XNA Framework.  The game was originally developed in C# during the Winter of 2007 by Sean Petty, Marshall Weir, and myself as our senior project at the University of Michigan.  During my learning time at SRT Solutions, I rewrote Paint Wars in F# as a learning exercise, and in the coming weeks, I will be blogging about the lessons that I learned while developing the F# and C# versions of the game.

UPDATE: Check out the YouTube video

Paint Wars The Game

Paint Wars is probably described best as a Real Time Strategy game, but it does not fit very well into most video game genres.  It is loosely based on the board game Risk.  A game is played by four people, each of which are assigned a color (Red, Blue, Green, or Yellow).

Players guide an army made up of blobs which are little creatures that move on their own and automatically paint the background with that player's color.  Blobs will move towards enemy blobs and attack them, and also prefer to move towards areas on the background that are of an opposing player's color. 

All players also have a spawn point, which produces more blobs every few seconds.  The more of the background that is painted by a player, the more blobs that they get for each spawn. 

Players can pick blobs up with their cursor and move them around the map, and they can also drop a paint nuke on the canvas every few seconds.  Paint nukes will kill any blobs within a small radius of the cursor, and will also paint the background with the controlling player's color.

Every few seconds, the total amount of each color on the background is calculated.  If the ratio of any one color to the rest of the colors is below a predefined limit, the player corresponding to that color is eliminated.  The last player standing wins the game.

That's it!  I'm looking forward to sharing more about the game and the code behind it in the coming weeks.