F# For C# Programmers: Programming In the Small

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. [UPDATE: The code will compile without the generic type parameters in C# 4.0. Still, there are a number of other areas where C#’s syntax lags behind F# when using functional techniques.] 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.

Posted in C#, F#, Functional | Leave a comment

Early Impressions – F# in Visual Studio 2010 Beta 1 and May CTP

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.* library 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#!

Posted in F#, Visual Studio | 4 Comments

Writing BDD-Style tests in F# with xUnit.net

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 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:

F# BDD Results

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.

Posted in F#, testing, xunit | Leave a comment

F# Performance Testing: F# Types vs Structs and Classes

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.

Posted in F# | 2 Comments

The Code Behind Paint Wars: Merging Functional and OOP

This post is the fourth in a series of posts about the code behindPaintWars. 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.

Posted in F#, Functional, Paint Wars, SrtInsights | Leave a comment

Beyond LINQ: Sequence Generation in C#

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

Posted in Beyond LINQ, C#, Functional | 5 Comments

The Code Behind Paint Wars: Functional Design

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.

Posted in F#, Functional, Paint Wars, SrtInsights | Leave a comment

The Code Behind Paint Wars: Object Oriented Design

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

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.

Posted in C#, F#, Paint Wars, SrtInsights | Leave a comment

Paint Wars on Display at CodeMash

PaintWars Logo

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 Paint Wars on YouTube]

Paint Wars The Game

 image

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

image

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.

image

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.

image

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.

image

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.

Posted in C#, F#, Paint Wars | Leave a comment

F# Projects – Order Does Matter

It’s common to run into a few simple problems when learning a new programming language. One such problem that I ran into with F# was resolving dependencies within projects.

With the September F# CTP (version 1.9.6.2), it’s pretty easy to handle dependencies on external projects since it is done as it is in C# with the "Add Reference…" context menu item. Dependencies between .fs files within a project behave a bit differently, though. As it turns out, the order that the files appear in the project determines the order that they are compiled in.

For example, lets say that I have the following two files:

SomeLibrary.fs

#light

namespace SomeLibrary

    type SomeType = { foo : int }

Dependent.fs

#light

open SomeLibrary

let deFoo (x:SomeType) = 
    x.foo

If I place Dependent.fs above SomeLibrary.fs in the project as shown below, I get a lovely compile error telling me that "The namespace or module ‘SomeLibrary’ is not defined".

image

However, once you switch the order using the "Move Up" or "Move Down" context menu actions, everything works as expected.

image

Posted in F# | 2 Comments