Understanding variance using functions

Statically typed languages that support parametrized types (generics) and types hierarchies (inheritance) sometimes support covariance and contravariance, concepts which many find confusing.

I think I have finally understood these, thanks to a blog post by Tomas Petricek on the subject.

In this post I'll try to formulate my own understanding, and how I got there using functions instead of classes.

Step 1: values

Let us start easy, with simple values. Consider a base type, for instance IPrintable, and two derived types MyString and MyInt.

I can use a string with any function that accepts a printable object.

type IPrintable =
    interface
    end

type MyInt() =
    interface IPrintable

type MyString() =
    interface IPrintable

// Step 1: simple value
let ``expects an IPrintable``(x : IPrintable) = ()

let n = MyInt()
let s = MyString()

``expects an IPrintable`` n // OK
``expects an IPrintable`` s // OK

Step 2: Parameterless functions

The next step deals with a function that takes another function which doesn't take any parameter and returns an IPrintable. If that's confusing, think of a generic function that creates a new random printable object, then prints it. This function would let the caller be responsible for providing a function which creates the random printable object.

The code below illustrates this, but I've removed the random part. Note also that F# does not support covariance, which forces me to use flexible types.

// Step 2: a function without arguments
// No covariance in F#, see http://msdn.microsoft.com/en-us/library/dd233198.aspx
let ``expects a constructor``(f : unit -> #IPrintable) = ()

let mkInt() = MyInt()
let mkString() = MyString()

``expects a constructor`` mkInt // OK
``expects a constructor`` mkString // OK

Step 3: Functions of a single parameter

Let us now consider a variation of the function described above where the function responsible for creating a random object takes a MyInt (it could be the seed, for instance). Assume I have two functions newRandomMyIntWithSeed and newRandomMyStringWithSeed that both take an IPrintable. Importantly, these two functions are safe to call with any instance of IPrintable. One can imagine that such a function would use the printable representation to generate some number, used as the seed for the random generator.

I can use newRandomMyIntWithSeed and newRandomMyStringWithSeed where a function with signature MyInt -> IPrintable is expected. Notice how the relationship on types for the parameter has been inverted, compared with the case of a value or a return type. This is an example of contravariance.

No code here, but see below for a more complete example.

Step 4: Functions of multiple parameters

It's possible to keep adding more parameters, and currying helps understand which functions are safe to use.
For this last example, I'll switch to another set of types: IScalar and IVector, with their respective implementations Float32 and Vector3. We can imagine there might be other implementations, e.g. Float64 and Vector4. A function which computes the product of a scalar and a vector must return a vector. Using currying, it can also be seen as a function takes a scalar and returns a function which takes a vector and returns a vector.

If I have a function with signature Float32 -> Vector3 -> Vector3, where can I use it?

I can use it where the exact same signature is expected, obviously.

I can use it where a Float32 -> Vector3 -> IVector is expected:

• The final return types match, as shown in step 1.
• The other parameters obviously match.

I cannot use it where a Float32 -> IVector -> Vector3 or a Float32 -> IVector -> IVector is expected. Although the final return types are compatible in either case, the next step in the matching process fails.

A more general function with signature IScalar -> IVector -> Vector3 can be used where a Float32 -> Vector3 -> IVector is expected:

• Vector3 as a simple value can be used anywhere any IVector is expected.
• A function accepting any IVector accepts in particular Vector3, meaning such a function can be used where a function expecting a Vector3 is expected (!), provided their return types match (which was shown above).
• By the same reasoning applied on the first (and only) argument of the function with signature IScalar -> (IVector -> Vector3), we conclude that the more general function can be used.

The code below illustrates this example.

// Step 4: a function with arguments
type IScalar =
    interface
    end

type IVector =
    interface
    end

type Float32() =
    interface IScalar

type Vector3() =
    interface IVector

let prodGeneral (s : IScalar) (v : IVector) : Vector3 =
    failwith "..."

// Interesting: flexible types are needed for the return type (no covariance),
// but not for the parameters (contravariance)
let apply prod (s : Float32) (v : Vector3) : #IVector = prod s v // OK

let k = Float32()
let v = Vector3()
let u = apply prodGeneral k v

Conclusion

I hope that wasn't excessively complex. Other explanations on the subject which I have seen often use container classes instead of functions, which is confusing, as it brings in read-only vs writable and reference-type vs value-type into the picture. Another problem is that using containers tends to mislead readers into thinking that T<B> can always be used where T<A> is expected if B inherits from A. Although that makes sense when T is IEumerable, it doesn't work when T is Action.
Looking at the problem with a functional mindset really helped clarify the picture.

I was a bit disappointed when I first saw F# did not support covariance, but flexible types do the job with very little additional syntax (a single # before the type). I was surprised to notice F# does support contravariance for function parameters, as it's often heard that F# supports neither covariance nor contravariance. That's not quite true, as it turns out.

If functions are powerful enough to model all other types, it may be interesting to see what kind of variance one should expect for unions, tuples, records and eventually classes. That's probably already been done, but it would be an interesting exercise.

Recursive descent parsers using active patterns, part 2

In the previous post, I presented a method to implement a parser relying solely on core F# features, namely active patterns.
In this post, I'll touch on some of advantages and limits of this approach.
Recursive descent parsers are limited to LL(k) grammars, which means that left-recursive grammars cannot be directly handled. It is necessary to rewrite such grammars to remove left recursion.

Consider the common problem of parsing expressions, e.g. Boolean expressions. A typical formulation of the  grammar could be:

Expr := AndExpr | OrExpr | NegExpr | Variable | True | False | "(" Expr ")"
AndExpr := Expr "AND" Expr
OrExpr := Expr "OR" Expr
NegExpr := "~" Expr | Expr

Note there is an ambiguity, as "A AND B OR C" could be parsed as (A AND B) OR C or as A AND (B OR C). In order to lift this ambiguity, priorities can be assigned to rules. Similarly for associativity, allowing to parse "A AND B AND C" as (A AND B) AND C or A AND (B AND C).

Such a grammar, if implemented naively using a recursive descent parser, would loop endlessly on some inputs: The parser would try to match rule AndExpr, which would try to match Expr, which would again try to match AndExpr...

An alternative formulation of the grammar can be used that will generate semantically equivalent results

Expr := OrExpr
OrExpr := AndExpr "OR" OrExpr | AndExpr
AndExpr := NegExpr "AND" AndExpr | NegExpr
NegExpr := "~" AtomExpr | AtomExpr
AtomExpr := Variable | True | False | "(" Expr ")"

Note the hierarchy between Expr, OrExpr, AndExpr, NegExpr and AtomExpr. The left-most rule appearing on an alternative in the right-hand side of each definition is always a "lower" rule: Expr refers to OrExpr, OrExpr to AndExpr, AndExpr to NegExpr, NegExpr to AtomExpr.
AtomExpr refers to the higher rule Expr in "(" Expr ")", but that's OK as Expr does not appear as the left-most rule (the token for a left parenthesis does).

What I like with this formulation is that it captures both associativity and operator precedence within the system of rules.

It is common to split parsers into two stages, using a lexer that processes the input stream in linear time, producing a pre-digested stream of so-called tokens. While this has undeniable advantages when it comes to performance, it prevents composing grammars and rule-specific tokenization. This is why most languages have keywords reserved for future use, and this also explains why you can't use identifiers that are also keywords even in situations where no ambiguity arises.

For these reasons, I personally prefer avoiding the separate lexing stage if performance constraints allow for it.

Regarding performance, it's important to write a recursive descent parser in such a way that decisions on the rule to try can always be done looking at a finite number of tokens.

In the example below, the second implementation performs significantly better:

let (|OrExpr|_|) s =
  match s with
  | AndExpr (e1, Token ("OR", OrExpr(es, s))) -> Some (e1 :: es, s)
  | AndExpr (e, s) -> Some ([e], s)
  | _ -> None

let (|OrExpr|_|) s =
  match s with
  | AndExpr (e1, s) ->
    let rec work s es =
      match s with
      | Token ("OR", AndExpr(e, s)) -> work s (e :: es)
      | _ -> (List.rev es, s)
    let es, s = work s []
    Some(e1 :: es, s)
  | _ -> None

To see what happens, consider the input "~X". This is a "degenerate" OrExpr with a single term. The first implementation will go all the way down through each rule to identify a NegExpr, promoting it to an AndExpr, then will look for "OR", which isn't there. The first match case will therefore fail, and the second will be tried, redoing the work. The same problem exists at all levels in AndExpr, NegExpr and AtomExpr. What makes matters worse is that this kind of "degenerate" case is actually the normal common case in typical expressions.

The second implementation uses the functional equivalent of a while loop, going as far as possible. The trick here is to factorize common prefixes into a single branch, thus avoiding redoing the work in case of a match failure.

An important problem with my simple example code is the lack of error messages. Those are important from a usability point of view, but I'm currently not too sure how to do this with manually-written parsers.

To summarize, using this technique requires some amount of manual work, which is the price to pay for not using smarter parsing frameworks. I wouldn't advise it over using parser generators, but it's interesting nonetheless. I can see it having uses for extremely small grammars, for instance when parsing fragments in a document. Otherwise, go for a parser generator such as fslex+fsyacc or ANTLR (which generates recursive descent parsers), or combinator-based parsers such as FParsec.

Recursive descent parser using active patterns

Today's post isn't specifically about games, but about parsing, which I find is a recurring task in many programming tasks, including game-related tasks.

In F#, the most popular methods for writing parsers are FParsec and fslex/fsyacc. Although parser generators are very useful, I'm always a bit reluctant to depend on third-party software.

In the past I have worked on a development tool for safety-critical systems, which was itself subject to some of the limitations of software for safety-critical systems. In particular, the use of lex and yacc was not accepted.

I fell back on a technique suitable for hand-written parsers, namely recursive descent parsers. I was positively surprised by the inherent simplicity of the method and the clarity of code that resulted.

I was first exposed to the idea of using active patterns for parsing when I read a blog post by Jon Harrop.
Active patterns is a feature specific to F#, and the F# wikibook has a chapter dedicated to them. I'll be using parameterized partial active patterns.

We start by defining a type for the input. The integer denotes the number of lines read so far, the list of strings is the input split at line-breaks.

open System.Text.RegularExpressions

type Stream = Stream of int * string list

A pattern to detect the end of the input, when the list of strings is empty.

let (|EOF|_|) = function
    | Stream(_, []) -> Some()
    | _ -> None

A pattern to detect end-of-lines, by recognizing list of strings which start with the empty string.

let (|EOL|_|) = function
    | Stream(n, "" :: rest) ->
        Some (Stream(n + 1, rest))
    | _ -> None

This pattern eats white space.

let (|OneWS|_|) = function
    | Stream(n, line :: rest) ->
        let trimmed = line.TrimStart()
        if trimmed <> line then
            Some (Stream(n, trimmed :: rest))
        else
            None
    | _ -> None

A convenient pattern to eat sequences of white space and newlines. Note the use of the rec keyword, which allows to refer to the pattern itself in its implementation.

let rec (|WS|_|) = function
    | OneWS (WS s)
    | EOL (WS s) -> Some s
    | s -> Some s

We could also have attempted another variant, where WS uses itself for the first part, which would implement a left-recursive grammar. Unfortunately, this pattern would be useless, as all it would do is raise stack-overflow exceptions.

let rec (|WS1|_|) = function
    | WS1 (OneWS s) -> Some s
    | s -> Some s

My variant of the Regex pattern differs a bit from the one in the wikibook, to avoid re-building Regex objects, which has a non-neglectable cost.

let (|Regex|_|) (regex : Regex) = function
    | Stream(n, line :: rest) ->
        let m = regex.Match(line)
        if m.Success then
            let lineRest = line.Substring(m.Length)
            let values =
                [ for gr in m.Groups -> gr.Value ]
            Some (values, Stream(n, lineRest :: rest))
        else None
    | _ -> None

A sample pattern to illustrate the use of the Regex pattern.

let personRegex = Regex("NAME: (\w+) AGE: (\d+)")
let (|Person|_|) = function
    | WS (Regex personRegex ([_ ; name ; age], s)) -> Some ((name, age), s)
    | _ -> None

A pattern to parse data of a large number of persons. I could have used recursion at the level of the pattern itself, similarly to WS. However, such a pattern would not be tail-recursive, and would cause stack overflows for large numbers of entries.

let (|Persons|_|) s =
    let rec work s persons =
        match s with
        | Person (p, s) -> work s (p :: persons)
        | _ -> (persons |> List.rev, s)
    let persons, s = work s []
    Some (persons, s)

Finally, some utility code to initialize streams, generate one million lines to parse, followed by the parsing itself.

let streamOfLines lines =
    Stream(0, lines |> List.ofSeq)

let streamOfFile path =
    Stream(0, System.IO.File.ReadAllLines(path) |> List.ofArray)

let stream =
    seq { for n in 0..1000000 do
            yield sprintf "  NAME: Anonymous AGE: %d              " (n % 99) }
    |> streamOfLines

#time "on"
match stream with
| Persons (p, WS EOF) -> printfn "Success %A" p
| _ -> printfn "Failed"
#time "off"

Parsing takes about 9 seconds on my PC (18s if I recreate the Regex object repeatedly). I think that's very decent performance.
In a future post, I'll describe how to parse Boolean formulas and expand a bit on the power and performance of this method.

Modular programming for portable F# libraries

I've been battling a few more rounds with F# portable class libraries. Getting them to work on PCs wasn't a walk in the park, but it seems I've got it working at last. Although this particular problem is not the main topic of this post, I expect many will run into the same issue, so I'll dedicate a few lines to its resolution.

The setting

I have a portable F# library which performs some physics calculations. Typical stuff you would expect in a portable library. It's unimaginatively but aptly named PortableLibrary1.

There is also an F# application project to run the simulation in a windows console (as in "text console", no xbox fun involved at this stage yet) application.

The application project refers to the library project.

The problem

The application compiles fine, but crashes when run with an exception stating that some version of FSharp.Core.dll could not be loaded.

The solution

Insert the following lines into the app.config file in the application's project:

<runtime>
  <assemblyBinding xmlns="urn:schemas-microsoft-com:asm.v1">
    <dependentAssembly>
      <assemblyIdentity name="FSharp.Core" publicKeyToken="b03f5f7f11d50a3a" culture="neutral"/>
      <bindingRedirect oldVersion="2.3.5.0" newVersion="4.3.0.0"/>
    </dependentAssembly>
  </assemblyBinding>
</runtime>

Thanks to Brian and his answer on stackoverflow.

We can run portable code on the PC, but the problems I mentioned in my previous post are still there, namely:

1. I can't reference functions and types from Microsoft.Xna.Framework because there is no portable version (that I know of).
2. There are core functions that are not available in the portable core, e.g. Thread constructors.

I will show below a solution to these two problems (my apologies to all bird lovers out there).

Signatures and modules

F# has its origins in ML, and some ML languages (standard ML, Ocaml) offer a module system that separates interfaces (which are called signatures) and implementations (call structures). Unfortunately, the module system of F# isn't as powerful. It's probably difficult, if not impossible, to fully emulate modules in F#. Nevertheless, there may some nice aspects of ML modules that can be imitated in F#.

• The module system distinguishes interfaces and implementations.
• Signatures specify a number of related types and operations operating on them in an abstract way.
• Structures provide a number of concrete types and functions satisfying the specification in the structure they implement.

A signature of vector math could look as shown below:

signature VectorMath
  type V
  val add: V * V -> V
  val dot: V * V -> float32
  val len: V -> float32

In the .NET world, there is something that might play the role of signatures, namely interfaces. The problem is how to express that module VectorMath should have a type V? Interfaces can be used to specify operations, but not nested types. In my solution, I have used generics:

type VectorMath<'V> =
    interface
        abstract Add : 'V * 'V -> 'V
        abstract Subtract : 'V * 'V -> 'V
        abstract Dot : 'V * 'V -> float32
        abstract Scale : float32 * 'V -> 'V
        abstract Len : 'V -> float32
        abstract Len2 : 'V -> float32
        abstract Zero : 'V
        abstract AreEqual : 'V * 'V -> bool
    end

Note that the dimension of the vector type V is not constrained. This signature allows to perform interesting operations on vectors regardless of whether we are working in 2d or 3d.
Operations that depend on the number of dimensions are found in additional signatures:

type Vector2Math<'V> =
    interface
        inherit VectorMath<'V>
        abstract Cross : 'V * 'V -> float32
        abstract UnitX : 'V
        abstract UnitY : 'V
        abstract Create : float32 * float32 -> 'V
    end

type Vector3Math<'V> =
    interface
        inherit VectorMath<'V>
        abstract Cross : 'V * 'V -> 'V
        abstract UnitX : 'V
        abstract UnitY : 'V
        abstract UnitZ : 'V
        abstract Create : float32 * float32 * float32 -> 'V
    end

Modules implementing these signatures are written using any .NET type that can implement interfaces. In F#, discriminated unions do the job. As a side note, I tend to use single-discriminant DUs a lot in my F# code. I see them as C's typedefs the way they should have been.

type XnaVector3Math =
    | XnaVector3Math
    interface PortableLibrary1.Vector3Math<Vector3> with
        member this.Add(v1, v2) = v1 + v2
        member this.Subtract(v1, v2) = v1 - v2
        member this.Scale(x, v) = x * v
        member this.Dot(v1, v2) = Vector3.Dot(v1, v2)
        member this.Cross(v1, v2) = Vector3.Cross(v1, v2)
        member this.Len(v) = v.Length()
        member this.Len2(v) = v.LengthSquared()
        member this.AreEqual(v1, v2) = v1 = v2
        member this.UnitX = Vector3.UnitX
        member this.UnitY = Vector3.UnitY
        member this.UnitZ = Vector3.UnitZ
        member this.Zero = Vector3.Zero
        member this.Create(x, y, z) = new Vector3(x, y, z)

Keep in mind the problem I wanted to solve was how to remove the dependency on the XNA dll from the portable library. The interfaces are part of the portable library, the implementation is in the application's code.
The same method can be used to send missing bits of Thread from the application (which has access to the missing bits) to the portable code.

Using signatures

The code for the physics simulation is shown below, not so much for its value as a physics engine, but to judge of the usability of signatures.

type SystemState<'V> =
    { mass : float32[]
      pos : 'V[]
      speed : 'V[] }

let computeForces (ops : #VectorMath<'V>) state =
    let forces =
        [|
            for mass, pos in Array.zip state.mass state.pos do
                let force =
                    Array.zip state.mass state.pos
                    |> Array.map (fun (mass', pos') ->
                        if ops.AreEqual(pos, pos') then
                            ops.Zero
                        else
                            let relPos = ops.Subtract(pos', pos)
                            let dist = relPos |> ops.Len
                            ops.Scale(mass * mass' / (dist * dist * dist), relPos))
                    |> Array.fold (fun x y -> ops.Add(x, y)) ops.Zero
                yield force
        |]

    forces

let update (ops : #VectorMath<'V>) dt state =
    let inline (.*) k v = ops.Scale(k, v)
    let inline (.+.) v1 v2 = ops.Add(v1, v2)

    let forces = computeForces ops state
    let accels =
        Array.zip state.mass forces
        |> Array.map (fun (mass, force) -> (1.0f / mass) .* force)

    let speeds =
        Array.zip state.speed accels
        |> Array.map (fun (speed, accel) ->
            speed .+. (dt .* accel))

    let positions =
        Array.zip state.pos speeds
        |> Array.map (fun (pos, speed) ->
            pos .+. (dt .* speed))

    { state with
        pos = positions
        speed = speeds }

let initialize (ops : #Vector3Math<'V>) =
    let rnd = new System.Random(0)
    let nextFloat() = rnd.NextDouble() |> float32

    let N = 1000

    let masses =
        Array.init N (fun _ -> nextFloat() * 1000.0f)

    let positions =
        Array.init N (fun _ ->
            let len = nextFloat() * 100.0f
            ops.Scale(len, ops.Create(nextFloat(), nextFloat(), nextFloat())))

    let speeds =
        Array.init N (fun _ -> ops.Zero)

    { mass = masses
      pos = positions
      speed = speeds }

let centerOfMass (ops : #VectorMath<'V>) state =
    let wpos =
        Array.zip state.pos state.mass
        |> Array.map (fun (pos, mass) -> ops.Scale(mass, pos))
        |> Array.fold (fun wpos x -> ops.Add(wpos, x)) ops.Zero

    let mass = Array.sum state.mass
    
    ops.Scale(1.0f / mass, wpos)

Discussion

This approach has a number of problems, compared with traditional F# modules.

1. Additional level of indirection when calling operations. In performance-critical situations, this can matter.
2. Additional ops parameter sprinkled in all functions that use the signature. A bit tiresome to write. Call sites aren't as badly affected, thanks to partial application and currying.
3. Need to specify the signatures. Will I need to duplicate all of XNA's API in signatures?

There are a number of non-problems, i.e. problems that have pretty good solutions:

1. Operator overloading: See update for an example on how to use operators to improve the look of expressions involving vector math.
2. Callers need not pass ops explicitly at each call site, as shown below:

In the library:

let mkModule ops =
    (fun () -> initialize ops),
    update ops,
    centerOfMass ops

In the application:

let initialize, update, centerOfMass = PortableLibrary1.mkModule MyVector3Math
let state = initialize()
let center0 = centerOfMass state

The benefits include:

1. Truly write-once-run-everywhere library code. I should be able to use my library code in a game for Sony devices using the Playstation Suite SDK, or for smart phones (actually, not quite, due to limitations regarding generic virtual methods in Mono).
2. Looser coupling between libraries. It's up to the top level, the application, to specify implementations. That's the right thing to do, since that's the only part that should be aware of the target platform and its  specifics.

Programmers with a background in OOP might wonder why I did not use an interface for the vector type itself, instead of providing an interface for a module. Note that would not really help me here, as XNA's Vector3 and Vector2 don't implement this interface (of which they know nothing). I would need some bridging type anyway.
Providing abstraction on the module-level, as opposed to the "object" level allows to group related types in a module specification. A more complete vector math signature would include matrices and operations that operate on vectors and matrices. The OOP approach forces these operations into one of the vector and matrix types, which I have always found a bit arbitrary.

Units of measure for array indices

In F#, arrays play an important part in optimizing performance-critical parts of your code. This is especially true on Xbox 360, where arrays of value types can help avoid snags due to slow garbage collection. Unfortunately, index out-of-bound exceptions are common when working with arrays. This post shows a little trick to help detect cases where the wrong variable is used as the index.

/// An array whose index has a unit of measure
type MarkedArray<[<Measure>] 'K, 'T> = MarkedArray of 'T[]
with
    member this.Content =
        let (MarkedArray arr) = this
        arr

    member this.First : int<'K> =
        LanguagePrimitives.Int32WithMeasure 0

    member this.Last : int<'K> =
        let (MarkedArray arr) = this
        LanguagePrimitives.Int32WithMeasure (arr.Length - 1)

    member this.Item
        with get (i : int<'K>) =
            let (MarkedArray arr) = this
            arr.[int i]
        and set (i : int<'K>) (v : 'T) =
            let (MarkedArray arr) = this
            arr.[int i] <- v

The interesting bit lies in the definition of this.Item. It allows to access the content of a MarkedArray using the usual array notation arr.[idx]

To illustrate how this is used, imagine you are making an Asteroids clone. You'll probably need arrays for the positions and velocities of the ships (assuming it's a multiplayer game), and similarly for the asteroids. Using units of measures as shown in the previous post will help avoid mixing speeds and positions, but it's still possible to pick a position from the wrong array.

This is the problem that MarkedArray solves, see below.

[<Measure>] type Ship
[<Measure>] type Asteroid

type State =
  { shipPositions : MarkedArray<Ship, TypedVector3<m>>
    shipVelocities : MarkedArray<Ship, TypedVector3<m/s>> 
    asteroidPositions : MarkedArray<Asteroid, TypedVector3<m>>
    asteroidVelocities : MarkedArray<Asteroid, TypedVector3<m/s>> }

let getShipPosition (state : State) (idx : int<Ship>) : TypedVector3<m> =
  state.asteroidPositions.[idx] // Fails: idx has the wrong type, expected int<Asteroid>

Note also that creating marked arrays isn't as tedious as one might fear, thanks to type inferrence

let state' = { state with shipPositions = state.shipPositions.Content |> Array.map f |> MarkedArray }

A small remark to finish off, this is how to iterate over all positions in a marked array, note the 1<Ship> increment:

for idx in state.shipPositions.First .. 1<Ship> .. state.shipPositions.Last do
  ...

By the way, both TypedVector3 and MarkedArray are available in XNAUtils on bitbucket.

Units of measure to the rescue!

Physics can really improve immersion in a game, regardless of how faithful they are to reality. That's why I always enjoyed writing simple physics engine. Even though I have stuck to really simple physics engine, I always end up mixing accelerations and forces. That usually doesn't lead to much trouble in the final result, as masses tend to be constant, and physical properties of game objects are typically chosen after experimentation to maximize fun.

The feeling that there is something wrong with the math in my code is always annoying, though. It turns out F# has a solution for that, called units of measure.

A unit of measure is a type annotation that helps programmers write correct formulas. It's obviously useful for formulas in simulations, whether one is dealing with physics, finances or any other domain where models play an important role.

The code below shows how to declare a unit measure.

/// Position, meters
[<Measure>] type m

/// Time, seconds
[<Measure>] type s

/// Mass, kilograms
[<Measure>] type kg

Units in physics have a certain level of redundancy, one might say. For instance, forces can be expressed in Newtons or in kilograms time meters per squared seconds. Newtons are obviously more convenient to use, but you want that masses multiplied by accelerations be recognized as forces. This is how you capture Newton's law:

/// Force, Newtons
[<Measure>] type N = kg m/s^2

Units of measure can be used with primitive numeric types such as int, float and float32.

let integrateShips (dt : float32<s>) (ships : Ships) ...

dt above denotes a time duration in seconds represented using a 32-bit floating point value. Units of measure can also be applied to complex types. The code below shows the code for a wrapper around Xna's Vector3.

/// A three-dimensional vector with a unit of measure. Built on top of Xna's Vector3.
type TypedVector3<[<Measure>] 'M> =
    struct
        val v : Vector3
        new(x : float32<'M>, y : float32<'M>, z : float32<'M>) =
            { v = Vector3(float32 x, float32 y, float32 z) }
        new(V) = { v = V }

        member this.X : float32<'M> = LanguagePrimitives.Float32WithMeasure this.v.X
        member this.Y : float32<'M> = LanguagePrimitives.Float32WithMeasure this.v.Y
        member this.Z : float32<'M> = LanguagePrimitives.Float32WithMeasure this.v.Z
    end

[<RequireQualifiedAccessAttribute>]
module TypedVector =
    let add3 (U : TypedVector3<'M>, V : TypedVector3<'M>) =
        new TypedVector3<'M>(U.v + V.v)

    let sub3 (U : TypedVector3<'M>, V : TypedVector3<'M>) =
        new TypedVector3<'M>(U.v - V.v)


type TypedVector3<[<Measure>] 'M>
with
    static member public (+) (U, V) = TypedVector.add3 (U, V)
    static member public (-) (U, V) = TypedVector.sub3 (U, V)

This allows to add and subtract vectors with compatible units of measure. It took me some effort to figure out how to handle multiplication by a scalar. First, in module TypedVector:

let scale3 (k : float32<'K>, U : TypedVector3<'M>) : TypedVector3<'K 'M> =
        let conv = LanguagePrimitives.Float32WithMeasure<'K 'M>
        let v = Vector3.Multiply(U.v, float32 k)
        new TypedVector3<_>(conv v.X, conv v.Y, conv v.Z)

Then the type extension:

type TypedVector3<[<Measure>] 'M>
with
    static member public (*) (k, U) = TypedVector.scale3 (k, U)

Note the use of LanguagePrimitives.Float32WithMeasure<'K 'M> to produce a number with a specific unit of measure in a generic fashion.

I have designed the class to reuse Xna's implementation although it wouldn't have been hard to write my own from scratch. The key benefit, on Windows Phone 7, is to take advantage of some fast vector math that's only accessible through Xna's types. The PC and Xbox platforms don't support fast vector math, but who knows, it may come.

Finally, here comes an example of how to use all this:

    let speeds2 =
        Array.map2
            (fun speed (accel : TypedVector3<m/s^2>) ->
                let speed : TypedVector3<m/s> = speed + dt * accel
                speed)
            ships.speeds.Content accels.Content

    let posClient =
        ArrayInlined.map3
            (fun pos speed speed2-> pos + 0.5f * dt * (speed + speed2))
            ships.posClient.Content
            ships.speeds.Content
            speeds2

There is more to be said and written about units of measures, a future post will show how they can be used for safe access of array contents.

Parallel draw-update XNA game component

Video games are often demanding when it comes to computation power, especially simulations and 3d games. The Xbox 360 has 3 cores with two hardware threads each. Of these 2 are reserved for the system, leaving 4 available to the programmer.
This article describes an easy to use custom XNA game component that allows to run computations in parallel with rendering.

The typical game loop is often divided in two steps, update and draw. I suggest a slightly different workflow divided in three steps, two of which run in parallel: update, compute and draw. The traditional update stage is divided in two new steps, update and compute.

In this new setting, update is used for receiving inputs from the player and the network, in the case of an online multiplayer game. Compute is potentially cpu-hungry operation implemented in a purely functional way. Rendering plays the same role as usual.

The code for the entire component fits in little over 100 lines, see below.

namespace CleverRake.XnaUtils

open Microsoft.Xna.Framework
open System.Threading

type IFramePerSecondCounter =
    abstract FramesPerSecond : float

/// An update-able and drawable game component which performs light updates on the main
/// thread, then draws on a separate thread in parallel of more computation-heavy updates.
/// initialize_fun is called when assets are loaded.
/// dispose is called when the component is disposed, and should be used to unload assets.
/// update_fun takes a GameTime and a state, and should produce draw data and computation
/// data.
/// draw_fun takes a game time and draw data and should return nothing.
/// compute_fun takes a game time and computation data and should return a new state.
type ParallelUpdateDrawGameComponent<'State, 'DrawData, 'ComputationData>
    (game,
     initial_state : 'State,
     initialize_fun : unit -> unit,
     update_fun : GameTime -> 'State -> 'DrawData * 'ComputationData,
     compute_fun : GameTime -> 'ComputationData -> 'State,
     draw_fun : GameTime -> 'DrawData -> unit,
     dispose : unit -> unit) =

    inherit DrawableGameComponent(game)

    let mutable state = initial_state
    let mutable draw_data = Unchecked.defaultof<'DrawData>
    let mutable compute_data = Unchecked.defaultof<'ComputationData>
    let mutable gt_shared = GameTime()

    let mutable enabled = true
    let mutable update_order = 0

    let signal_start = new AutoResetEvent(false)
    let mutable kill_requested = false
    let signal_done = new AutoResetEvent(false)

    let do_compute() =
#if XBOX360
        // Set affinity
        // 0 and 2 are reserved, I assume the "main" thread is 1.
        Thread.CurrentThread.SetProcessorAffinity(3)
#endif
        while not kill_requested do
            signal_start.WaitOne() |> ignore
            state <- compute_fun gt_shared compute_data
            signal_done.Set() |> ignore

    let compute_thread = new Thread(new ThreadStart(do_compute))

    // Must be called from the main thread.
    let post_compute_then_draw gt =
        if not kill_requested then
            let state = state
            gt_shared <- gt
            signal_start.Set() |> ignore
            draw_fun gt draw_data
            signal_done.WaitOne() |> ignore

    let mutable frameCounter = 0
    let mutable timeCounter = 0.0
    let mutable fps = 0.0
    let fpsUpdatePeriod = 0.3

    do
        compute_thread.IsBackground <- true
        compute_thread.Start()

    override this.Initialize() =
        base.Initialize()
        initialize_fun()

    override this.Update(gt) =
        if base.Enabled then
            base.Update(gt)
            let draw, compute = update_fun gt state
            draw_data <- draw
            compute_data <- compute

    override this.Draw(gt) =
        if base.Visible then
            base.Draw(gt)
            post_compute_then_draw gt
        else
            state <- compute_fun gt compute_data
        timeCounter <- timeCounter + gt.ElapsedGameTime.TotalSeconds
        frameCounter <- frameCounter + 1
        if timeCounter > fpsUpdatePeriod then
            fps <- float frameCounter / timeCounter
            timeCounter <- timeCounter - fpsUpdatePeriod
            frameCounter <- 0

    
    interface System.IDisposable with
        member this.Dispose() =
            base.Dispose()
            dispose()
            signal_start.Dispose()
            signal_done.Dispose()

    interface IFramePerSecondCounter with
        member this.FramesPerSecond = fps

    member this.FramesPerSecond = fps

    member this.RequestKill() =
        kill_requested <- false
        signal_start.Set() |> ignore

    member this.WaitUntilDead() =
        compute_thread.Join()

    member this.IsDead = not(compute_thread.IsAlive)

To be noted is that this component isn't meant to be extended the usual way which consists in inheriting and overriding. I'm experimenting with staying away from traditional OOP. I'm not sure it's the nicest way to do things, but building a wrapper from which to inherit shouldn't be hard. The OOP way will definitely be more appealing when using this component from C#, so I'll probably have to take this step anyway.

The constructor of the class takes an initial state and an initializing function which shouldn't be mixed. The initializing function is meant for loading assets. The dispose function should undo the effects of the initializing function and should dispose of any disposable asset.

The initial state represents the state of the world when the game starts. This is typically built from a level description when entering a new level, or by loading a previously saved session.

When the game is running, the state is passed to the update function, which isn't so well named, in retrospect. Its role is to prepare data for the compute and draw functions, which are run in parallel. In most cases I expect that ComputationData and State are the same type.

As is common in parallel update/draw scenarios, the draw function renders the state produced by the compute function in the previous frame. This is necessary to avoid race conditions between the compute and draw functions.

I am not yet sure whether I'm happy with my implementation of IDisposable, and this may change if turns out to be impractical or wrong. I've been using this component in a new game I'm working on, and I have been positively surprised. I hope you will find it useful!

Converting FS project files to target Xbox 360

Of interest to anyone using F# and XNA to make games targeting the Xbox 360: I'm working on a script to convert fsproj files for the PC platform to the Xbox platform.

https://bitbucket.org/johdex/xnautils/src/a2cc6e8c7455/WinPc/ConvertFsProj.fsx

It's not 100% ready yet, the converted files need some manual editing before they are usable.

The advantage of using a script over using the project template is that no additional and unnecessary directory is created. It also keeps all project content, no need to re-add all dll references and source files.

Here are some known issues:
- Project references are not automatically updated.
- System.Xml and System.Xml.Serialization and possibly other XNA dlls cannot be added from Visual Studio. It complains that those libs are not compatible with the targeted framework despite the fact that they are.
- You need the custom FSharp.Core.dll and accompanying files for Xbox360 somewhere in your solution. You get them as part of the F# + XNA templates, they are also in XNAUtils/FSharpCore.

Defeating the blank page

Programmers have two ways to approach implementation of complex programs:

Start by building bricks, combine them to build larger bricks, repeat until the brick is actually a house.

Work the other way around.

The second approach is actually the more sensible one for new problems. In general, you know what is the problem you want to solve, not how to solve it. It's therefore easier to write the top-level of an application first.
The obvious problem is: On what do you build the top level?

There is a trick I used in F# that I wanted to share.
Consider the following problem: I want to implement a racing game, which requires multiple data structures to represent the track. In the track editor, the track is basically a curve controlled by a number of points and directions. In the game, the track is a set of triangles used for rendering and simulation. The problem is to convert a track segment defined using the first representation to the second.
A track segment is either linear (it connects two control points), a fork (for the entrance and exit of the pit lane) or a bridge. We can imagine other kinds of segments (+ and T -shaped crossings), but that's enough for a start.
I start with this function:

let triangulate segment =
   match segment with
   | Linear data -> ()
   | Fork data -> ()
   | Bridge data -> ()

It's not doing much, obviously. Let's look at the easy case first. A solution would be to get an ordered set of vertices for one side of the road segment, and another set for the other side.

| Linear data ->
   let leftSide = getLeftSide data
   let rightSide = getRightSide data
   knit triangles leftSide rightSide

This code isn't valid, because getLeftSide, getRightSide knit and triangles aren't defined. Let's add them as parameters to triangulate:

let triangulate getLeftSide getRightSide knit triangles segment =
   match segment with
   | Linear data ->
      let leftSide = getLeftSide data
      let rightSide = getRightSide data
      knit triangles leftSide rightSide

After a few more iterations of this I get the following function:

let triangulate getLeftSide getRightSide getLeftSideOfFork getLeftInner getRightSideOfFork getRightInner intersect glue knit triangles segment =
    let triangulateLinear data =
        let leftSide = getLeftSide data
        let rightSide = getRightSide data
        knit triangles leftSide rightSide

    match segment with
    | Linear data ->
        triangulateLinear data

    | Fork data ->
        let outSide0 = getLeftSideOfFork data
        let inSide0 = getLeftInner data
        let outSide1 = getRightSideOfFork data
        let inSide1 = getRightInner data
        let inSide0, inSide0', inSide1, inSide1' = intersect inSide0 inSide1
        knit triangles outSide0 (glue inSide0 inSide1')
        knit triangles outSide1 (glue inSide1 inSide0')
        knit triangles inSide0' inSide1'

    | Bridge data ->        
        triangulateLinear data.under
        triangulateLinear data.over

The function takes quite a few parameters, maybe too many. I can clean this up later after I have implemented getLeftSide and all other functions.

Notice how far I can get never worrying about types, yet I never need to worry about whether the parts fit together.

This way of writing code has helped me get over a number of situations where I was suffering some sort of "blank page syndrome", not knowing where to start to tackle a complex problem.
Of course, there is no guarantee that the final implementation will keep the same architecture, but at least I'm going forward!

New e-book: FRIENDLY F# with game development and XNA

I received a mail from Giuseppe Maggiore, one of the authors of a new book: FRIENDLY F# with game development and XNA. Giuseppe helped me put together the project templates for F# and XNA on the Xbox 360.

The main subject of the book is the F# language and its various
constructs, but every single chapter is centered around a game-related
problem. Each one of the first 5 chapters describes a problem, shows
and discusses its solution and then discusses in depth the F#
constructs used. The book has a (relatively rare) "problem-solution"
approach where everything is explained because of how well it works in
solving the problem, and not just "because". The 5 problems we present
are:
- a bouncing ball
- the Saturn V rocket
- an asteroid field
- a large asteroid field optimized with quad trees
- a police starship that must fight off a pirate ship attacking a
cargo freighter
In the last two chapters we use XNA to build a 2D and 3D renderer for
two of the samples we have seen. We show the basics of the SpriteBatch
class, the Model class, input management and audio with this powerful
framework. Basically, we cover the most important aspects of XNA in a
simple and succint way.

I had a quick look at the book and I think Giuseppe's description is a fair one. In other words, this is not a book primarily about game programming, but an introduction to F#. Although it touches some advanced topics such as custom workflows, it is not a comprehensive coverage of the language.
All in all, if you are looking for a gentle and quick introduction to the language, and you are interested in game programming, you should definitely check this book.

The book is available on Amazon and Smashwords.

The forgotten control flow construct

There is a truly powerful control flow construct that many programmers have forgotten. It helps implement complex flows that ifs, whiles and matches can't handle. Not even throwing and catching exceptions can measure itself to this construct.

You may wonder what kind of situation would require something that traditional constructs can't handle. Here is an example taken from Go To Statement Considered Harmful: A Retrospective.

int parse()
{
    Token   tok;

reading:
    tok = gettoken();
    if (tok == END)
        return ACCEPT;
shifting:
    if (shift(tok))
        goto reading;
reducing:
    if (reduce(tok))
        goto shifting;
    return ERROR;
}

Let's see how using a while turns out:

type Token = END

type ParseState = Reading | Shifting | Reducing | Accepted | Errored
type Status = ACCEPT | ERROR

let parse gettoken shift reduce () =
    let mutable state = Reading
    let mutable tok = Unchecked.defaultof<Token>
    
    while state <> Accepted && state <> Errored do
        state <-
            match state with
            | Reading ->
                tok <- gettoken()

                if tok = END then
                    Accepted
                else
                    Shifting

            | Shifting ->
                if shift tok then
                    Reading
                else
                    Reducing

            | Reducing ->
                if reduce tok then
                    Shifting
                else
                    Errored

            | Errored | Accepted -> failwith "Invalid state"

    match state with
    | Errored -> ERROR
    | Accepted -> ACCEPT
    | _ -> failwith "Non-final state"

(Note that I have introduced extra parameters gettoken, shift and reduce; I wanted to be able to write concise code that syntactically correct without explicitly defining these functions).

It looks OK, but we had to introduce an extra type, ParseState. There are also some issues with mutability and initialization of tok.

If you have some experience with functional programming, you are probably thinking that recursion is the right tool. I will leave writing a recursive version of parse to the reader, and jump to a slightly different idea that many might have missed.

type Token = END | SOMETHINGELSE

type Status = ACCEPT | ERROR

let parse gettoken shift reduce () =
    let rec do_read() =
        match gettoken() with
        | END -> ACCEPT
        | _ as tok -> do_shift tok

    and do_shift tok =
        if shift tok then
            do_read()
        else
            do_reduce tok

    and do_reduce tok =
        if reduce tok then
            do_shift tok
        else
            ERROR

    do_read()

do_read, do_shift and do_reduce are mutually recursive functions. All recursive calls are in tail position, which makes it possible to avoid stack overflows (on some platforms...).

Here you have it: calls in tail position are basically safe versions of goto.

The fantastic control flow construct that many have forgotten is simply the procedure call. Every programmer uses it a countless number of times every working day, but fear of recursion and stack overflows have kept many from using it in situations where it fits well.

Is it worth it?

In my previous post, I explained why inheritance for code reuse is a bad idea. The blog was a bit on the theoretical side, and I wanted to know if I wasn't sitting in an ivory tower.

For this reason, I have decided to rewrite one of my uses of inheritance by composition. The piece of code in question is the BaseScreen class in XnaUtils.

Before I go any further, I need to give you a bit of context. The user interface of video games is usually composed of screens. The library provides a class called ScreenManager which is responsible for managing stacks of screens, notifying each screen when to load/unload resources such as textures...

I have created an interface named "Screen" which serves as the interface between the framework and the screens in a game. The framework also provides a few screens which can be used in simple games, namely TextScreen, MenuScreen and PressStartScreen.

These screens all share common functionality which I needed to put somewhere to avoid code duplication. In my first version, BaseScreen was an abstract class from which screen implementations inherited, overriding a few key methods to customize rendering.

Differences in ScreenBase

The changes are not very extensive. Abstract methods were replaced by fields. Instead of defining overrides, inheritors set properties using lambdas.

+    let post_drawer : ('T -> unit) ref = ref (fun _ -> ())
...
-    abstract member EndDraw : 'T -> unit
-    default this.EndDraw(_) = ()
-
+    member this.PostDrawer
+        with get() = !post_drawer
+        and set(d) = post_drawer := d

Differences in inheritors

A few "this" had to be replaced by "impl", the name of the variable I have used to hold the instance of ScreenBase.

type PressStartScreen(sys : Environment, fade_in, fade_out, blink) =
-    inherit ScreenManager.ScreenBase<unit>()
+    let impl = new ScreenManager.ScreenBase<_>()
+    let impl_screen = impl :> ScreenManager.Screen

// Task to check if a button is pressed. Sets player when that happens.
let player : PlayerIndex option ref = ref None
while (!player).IsNone do
-            do! sys.WaitUntil(fun () -> this.IsActive)
+            do! sys.WaitUntil(fun () -> impl.IsActive)
for p in all_players do
let state = GamePad.GetState(p)
if state.IsConnected

Boiler-plate code had to be written to implement interfaces Screen and IDisposable, forwarding calls to "impl". As ScreenBase implements these interfaces explicitly, I had to introduce an extra variable "impl_screen" to refer to impl's implementation of Screen. Otherwise, I would have had to use casts in all forwarding code, as shown in the implementation of IDisposable.

+    interface ScreenManager.Screen with
+        member this.ClearScreenManager() = impl_screen.ClearScreenManager()
+        member this.Draw() = impl_screen.Draw()
+        member this.LoadContent() =
+            impl_screen.LoadContent()

+
+    interface System.IDisposable with
+        member this.Dispose() = (impl :> System.IDisposable).Dispose()
+

Advantages of composition and delegation over inheritance

1. Inheritors can reuse code from multiple classes (F# does not have multiple inheritance).
2. The code for ScreenBase is a bit shorter.
3. Inheritors have more control.

Advantages of inheritance over composition and delegation:

1. The "IDisposability" of ScreenBase is implicitly propagated to its inheritors.
2. No risk of errors in delegation.
3. The code for inheritors is shorter.

Conclusion

Although I believe most of the weaknesses of the approach using composition and delegation could be lifted by additions to the F# language, in its current shape, I would not dare to force users of my library to use composition.

The ideal solution is to write my library code to allow users to use the approach they prefer, which I expect would be inheritance in most cases. Providing this approach as the only one is not acceptable, as it would prevent users to reuse features from multiple classes.

OOP without classes in F#

Did you know that F# allows to use some object-oriented features with types that are not classes? This includes methods, dynamic dispatch, open recursion and encapsulation.

Methods are functions or procedures which are tightly coupled to a type of object.

Dynamic dispatch is the ability to execute different implementations of an operation depending on the concrete types of arguments. A special case which often has dedicated syntax is when the operation is a method, and the argument controlling the dispatch is the object itself.

Open recursion makes the object available to its methods through an identifier, typically called this or self.

Encapsulation restricts access to the internal data and operations of an object to a restricted area of the code. Typically this area is the methods of the object itself, F# works at the module level instead.

The code below shows how a vector type can be defined using records.

[< CustomComparison >]
[< CustomEquality >]
type Vector2 =
    private { x : float
              y : float }
with
    // Constructors
    static member New(x, y) = { x = x; y = y }
    static member Zero = { x = 0.0; y = 0.0 }

    // Accessors
    member this.X = this.x
    member this.Y = this.y
    member this.Length = let sq x = x * x in sqrt(sq this.x + sq this.y)

    // Methods
    member this.CompareTo(other : obj) =
        match other with
        | null -> nullArg "other"
        | :? Vector2 as v -> this.CompareTo(v)
        | _ -> invalidArg "other" "Must be an instance of Vector2"

    member this.CompareTo(other : Vector2) =
        let dx = lazy (this.x - other.x)
        let dy = lazy (this.y - other.y)

        if dx.Value < 0.0 then -1
        elif dx.Value > 0.0 then +1
        elif dy.Value < 0.0 then -1
        elif dy.Value > 0.0 then +1
        else 0
        
    // Overrides for System.Object
    override this.ToString() = sprintf "(%f, %f)" this.x this.y
    override this.Equals(other) = this.CompareTo(other) = 0
    override this.GetHashCode() = (this.x, this.y).GetHashCode()

    // Explicit interface implementations
    interface System.IComparable<Vector2> with
        member this.CompareTo(other) = this.CompareTo(other)

    interface System.IComparable with
        member this.CompareTo(other) = this.CompareTo(other)

    interface System.IEquatable<Vector2> with
        member this.Equals(other) = this.CompareTo(other) = 0

The use of private on line 4 makes the representation (not the type itself or its methods) private to the enclosing module (Thanks to Anton for pointing that out in the comments).
Members can access the object through an identifer (this), and open recursion is covered.
Vector2 can be used as one would expect to be able to use an object, as illustrated below.
Dynamic dispatch is exercised by Array.sortInPlace (which calls CompareTo).

let playWithIt() =
    let v = Vector2.New(0.0, 2.0)
    let v2 = Vector2.New(v.y, -v.x)
    printfn "%s and %s have %s lengths"
        (v.ToString())
        (v2.ToString())
        (if (let epsilon = 1e-6 in abs(v.Length - v2.Length) < epsilon)
            then
            "close"
            else
            "different")
        
    let rnd = System.Random()
    let vs = [| for i in 1..10 -> Vector2.New(rnd.NextDouble(), rnd.NextDouble()) |]
    Array.sortInPlace vs
    printfn "%A" vs

I cannot write an entire article about OOP and not mention inheritance. F#-specific datatypes do not support inheritance, but I will try to show in a later post why this is not as big a problem as one might think.

My impressions of F# after three years

It will be soon 3 years that I have been using F# both professionally and privately.

At work, I have used it to implement the simulator module of Prover iLock. This is a complete rewrite of the first version of the simulator, which was initially written in C#. The rewrite was necessary for a number of reasons. As is often the case with the first version of any software, its design did not age well, leading to bugs, excessive memory use and long execution times. I think the main reason was simply that requirements were not clear when the project was started.

The main challenge of this simulator is to support distributed systems where components use different execution models and link protocols. The term "execution model" is a bit specific to the field, namely railway signalling systems. Historically, these systems were implemented using relays. Their modern counter-parts include relays (they are still popular), software which emulates relays (to take advantage of existing field knowledge and practices) and to a lesser extent procedural languages.
The second category include platforms such as VHLC and Microlok, but there are many other similar yet different technologies. Although similar, they all differ slightly in how they handle communication with remote devices, how timers are handled, in what order instructions are executed...

I am happy to report that so far, most of the objectives for the new implementation have been reached or exceeded:

• Adding a new platform takes little effort.
• Memory use has drastically gone down, despite massive use of short-lived arrays to hold state.
• Run-time efficiency is OK, although a bit worse than the first version in some cases. The main reason here is that I made no attempt to perform some of the optimizations that introduced bugs in the first version (maintaining consistency with respect to time when simulating distributed systems is difficult). 
• Few known bugs.

Time will tell how this second version ages, but so far, I haven't needed to spend a lot of time extending or fixing it. Which is a bit sad, as it means I am not spending as much time working with F# as I would like :)

Another important F# module I developed was a bridge translating the C# representation of systems from the main program to the simulator module. This other project is also successful. The main lesson learned is not to reuse data between different software modules. This may sound surprising at first, but the gains of designing data structures that do one thing well outweigh the costs of maintaining similar types which appear to duplicate code. The data structures in the main program are designed to make it easy to build and modify them via a scripting API. The data structures in the simulator are designed for efficiency of simulation.

Defining types in F# is easily done thanks to records and discriminated unions. Translating from one type hierarchy to another is facilitated by pattern matching. I'm inclined to think the lack for these constructs in other languages leads to excessively large and complex data-types, as they try solve multiple problems at once. Although the evils of code duplication are well known, there are also risks associated to excessive code sharing. Getting the right balance in the number of data types requires a flexible and rich family of types, and it's now clear to me that C# is too poor in that respect. Classes and enums are not enough.

I have used F# in a range of projects, mostly game-related. Asteroid Sharpshooter was released in January. Although not a commercial success (168 copies sold so far), it showed it was possible to write games with high performance requirements in F#, despite the weaknesses of .Net on the Xbox 360. I have not gotten a single bug report so far, but this may be due to the small amount of users. Its rating of slightly over 3 stars out of 5 seems to indicate users are moderately satisfied with the game.

I have also developed a "new" way of developing game user interfaces which I think blows the "old" way out of the water. The new way I am referring too allows to write reactive UIs over the game update loop in a simple way, allowing for much faster development and more robust software. The old way either leads to unresponsive interfaces or buggy ones that fail to deal with storage management or any other lengthy processing requiring asynchronous programming. I doubt many programmers without a functional background realize the power of computation expressions in F#.

By the way, I often hear and read that "F# is not good for UI". This is total nonsense. I normally try to express myself in a gentle, moderate, non-controversial way on this blog, so just to emphasize how I feel about this:

"F# is not good for UI" is total nonsense.

There are basically two problems with UI.

1. Lots of boring code to write: widget layout, boiler-plate...
2. Achieving good responsiveness

Point 1 is addressed by tools and code generation, and is actually language-independent. What do I care if automatically-generated code is in C#, IL or F#? As long as I don't have to write it...

Even in the case when I do write the code myself, I don't find C# and F# to differ significantly in that matter. F#'s supported for nested  variable and function definitions help limit the number of members in a class, which avoids one of C# problems, namely over-blown classes with numerous private fields and methods.

Point 2 is solved by F#'s async. In that respect, I wonder how people have been dealing with the problem in C#? BackgroundWorker and threads are not so fun to use.

In all my projects, I think I have noticed two strong differences with developing in a C++-like procedural language:

1. I spend a lot less time debugging. Modulo trivial bugs, functional code that is correctly typed just works out of the box. Any time I went out of the pure functional path to introduce mutability, direct access to items in arrays... I introduced bugs.
2. The relatively low verbosity of F# and its high-level constructs make it easier to implement more complex algorithms. For instance, I could never get my head around Runge-Kutta(4) in C++, implementing it in F# was trivial, all while learning F#.

On the negative sides, I found that Visual Studio's debugger can be difficult to use with F#. In other words, it's good you don't spend a lot of times debugging, because it can be hard to understand what's going on in the debugger. Two of the main issues, I think, reside on the one hand in the fact that a debugger is statement and line oriented, where a functional language is expression-oriented, and on the other hand in a somewhat confusing handling of F# closures and lambdas by the debugger. For instance, debugging code in computation expressions is close to impossible.

That's all for now. If you are decision-taker in your company, and .Net is part of the technologies you use, I think you simply cannot afford not looking at F#. I know every time a new language is introduced, productivity gains are claimed by its inventors.

I did not invent F# and don't work for Microsoft, but I can vouch for the alleged productivity gains. Your mileage may vary, but I don't think it will.

The myths about the risks of introducing F# in your development team

At work we are a couple people who have been using F#. All people who have used it are enthusiastic, yet I was surprised today when I heard a project leader had asked to limit the use of F#.

There is a question on programmers' stack exchange which touches the subject titled "Real world pitfalls of introducing F# into a large codebase and engineering team". I'm quoting:

1) Everyone has to learn F#, and it's not as trivial as switching from, say, Java to C#. Team members that have not learned F# will be unable to work on F# parts of the codebase.
2) The pool of hireable F# programmers, as of now (Dec 2010) is non-existent. Search various software engineer resume databases for "F#", way less than 1% of resumes contain the keyword.

The fear is that maintaining F# code might be difficult because current employees and job applicants lack functional programming skills.

It seems some decision makers are still stuck at the time when C# 1.0, C++ and Java 2 were the languages of choice. Since then, a few things have happened.

Firstly, Python has become hugely popular. Although many were horrified by its use of white space to delimit blocks, it would be difficult to take seriously a programmer who claims he can't adjust to Python's syntax. Some love it, some hate it, but all can write Python code.
Why would the syntax of F# be any harder to adopt?

Secondly, C# has introduced a number of functional programming and other high-level concepts in each new version that has come out. Modern C# programmers are expected to master LINQ to objects, lambdas and yield return. The next version will introduce a specific syntax for asynchronous programming. Would you consider hiring a programmer would admits he knows nothing about these features and is unwilling to learn about them?
F#'s higher order functions, functions as first-class citizen, sequence expressions and asynchronous workflows match directly the modern features of C#. Why would these be harder to use in F# than in C#?

Dear reader, if you are a decision maker, I hope these two simple remarks dissipated your fears. You may be wondering why adopt F# when C# is evolving? You won't hear it from Microsoft, but the fact is that C# is breaking at the seams in its attempts to bring in new constructs. I won't give an exhaustive list, but here are a few examples of the limits of C#:

1. Limits of iterator blocks (yield return). No such restriction in F#.
2. Closures capture variables, not values. In F#, closures capture values, which is in my opinion a much saner design decision.
3. Language-integrated queries are nice, but they don't sound as generic as they actually are. F#'s notion of quotation is more elegant, and makes it easier to see the applicability of LINQ beyond SQL.
4. Although it's nice that C# is "stealing" async from F#, why not introduce the more general concept of custom workflows?

Moreover, F# supports a few data-types that somehow got forgotten when class-based OOP became dominant, namely records and discriminated unions. Together with pattern-matching, they are doing their come-back in the main stream and I have no doubt they will shortly become tools top programmers are expected to master.
 
Now, I'm not saying you should ditch C# and replace it "en masse" by F#. C# has better tooling support, features implicit conversions and a lighter syntax for implicit interface inheritance. I don't think these features are a must-have in all situations, but they can be handy at times.

Adopting all new hyped technologies has its dangers, but if you refrain from getting on with the times because of a few dinosaurs among your developers, your business will eventually go the way of the dinosaurs.

Planing and designing WorldConquest

I have been using fogbugz from FogCreek to plan and track my previous project, Asteroid Sharpshooter. So called "on-demand" installations are free for single developers. I chose fogbugz over other free alternatives because it's the only platform that I know of supporting a time planning process that has been thoroughly thought out, namely evidence-based scheduling (EBS for short).

One of the dev teams at work is also using fogbugz, but we haven't been able to validate the value of EBS, possibly because I'm the only one interested enough in both programming and planning to follow the process in a disciplined way. One of the problems of the method is that it basically requires a waterfall design process, which isn't very popular these days in professional circles.

I am curious to see whether my use of EBS for the development of WorldConquest will validate the nice ideas upon which EBS is built.

My time estimates for implementing simultaneous turns in the game have shown to be wildly off-target. I thought writing to state update function would take 3 hours. I am now reaching 16 hours, and I am still in the testing phase.

It turned out executing orders in parallel can be tricky due to conflicts. For instance, how do you handle a melee attack order and a regular move order. The first order causes the attacking unit to move towards the targeted unit and attack it when it reaches it. But what happens if the targeted unit has an order to move away? The same kind of issues arise for units embarking and disembarking, if the transporting unit moves or is destroyed.

There are quite a few ways to resolve these issues, solving is really just a matter of deciding. Still, having a clear understanding of the design before implementing it is necessary, and I find that using data-flow graphs really helps. I use yED to draw graphs. This tool can redo the layout of graphs all by itself, a feature I cannot live without. It really beats drawing on paper or drawing on screen without automatic layout.

I ended up with the design below:

Boxes are operations, octagons are data. It's not a very complex process, but trying to implement it without a proper design (as I was hoping to do at first) is not an option.
Here is the implementation of the function that puts all parts together:

let update (gs : GameState) (orders : Order[][]) =
    let damages =
        seq {
            for player in 0 .. gs.player_units.Length - 1 do
                let player_id = PlayerId player
                let attacks = extractAttackOrders gs.player_units.[player] player orders.[player]
                yield! computeDamages gs player attacks |> accumulateDamage                
        }
        |> dict

    let getDamages u =
        match damages.TryGetValue(u) with
        | false, _ -> 0.0f
        | true, x -> x

    let gs = applyDamage gs getDamages

    let dead_units = getUnitDeaths gs damages

    let isDead u =
        dead_units.Contains u

    let player_units =
        [|
            for player in 0 .. gs.player_units.Length - 1 do
                let player_id = PlayerId player
                let units = gs.player_units.[player]
                let orders = orders.[player]

                let isThisDead u = isDead(player_id, u)
                let move_orders =
                    extractMoveOrders units player orders
                    |> filterDeadMoveOrders isThisDead

                let early_disembark, late_disembark = extractDisembarkOrders units player orders
                let late_disembark = filterDeadDisembarkOrders isDead player late_disembark
                let disembark_orders = Array.concat [early_disembark ; late_disembark]

                let embark_orders =
                    extractEmbarkOrders units player orders
                    |> filterDeadEmbarkOrders isDead player
                                
                let units = applyMoves move_orders units

                yield
                    units
                    |> growUnitTree embark_orders disembark_orders
                    |> shrinkUnitTree embark_orders disembark_orders
        |]

    { gs with player_units = player_units }

I have found that comprehensions and the pipeline operator |> are very nice tools to process arrays of units.

Using F# scripts for testing and performance measurement

I have just heard about a new project being started by a game developer, NPerformant.

The developer writes

At various times in my “day job/career” I’ve used commercial profilers with varying results, but I don’t want or need to profile the whole application or even a whole library.  I also don’t want to code two solutions into my product in order to let a normal profiler test them side by side in order to remove the loser later.

The problem about creating additional solutions also occurs in testing and when writing small utilities and editors while developing your game.

F# scripts help avoid this issue. You can add number of .fsx files to your project, and executing them using F# interactive (aka fsi) is very easy. For my current game, I have a script to render parts of my engine data using XNA and winforms, and another script to test some of the game logic. I don't know how long I will need these, but the day I lose the use for them, removing them is as easy as removing a single file from your project. Compare that to removing an entire project, which in my case would involve getting out of Visual Studio and using Windows Explorer then TortoiseHg.

Back to the topic of measuring performance, did you know about the #time command you can use in fsi:

> #time "on";;

--> Timing now on

randomTest();;
Real: 00:00:15.761, CPU: 00:00:54.725, GC gen0: 1917, gen1: 2, gen2: 0

Note that you get information about garbage collection too, which is interesting information when developing games for the Xbox 360.

Regarding testing, I just found out yet another case when pattern matching saves the day. In the code extract below, I'm using it to express the expected result of the code being tested.

match gs'.player_units with
    | [| _; [| { health = x } |] |] when x < 1.0f -> true // Injured
    | [| _; [||] |] -> true  // Killed
    | _ -> false

player_units is an array of player units, where players units are represented using arrays of units. My test has an artillery belonging to the first player fire at a helpless infantry of the second player.

The first branch of the pattern matching says: "An array composed of two elements where the first element can be anything, and the second element is a one-element array of units where x is the value of field health, and x is strictly less than 1".

I don't know how I would have written that in C# in a similarly concise fashion.

Informally, my pattern match checks that the unit of the second player was injured or killed.

Asteroid Sharp Shooter: Post-mortem

Introduction

Asteroid Sharpshooter is a game published on the Xbox LIVE Marketplace, under the independent games section.

It is written in F# and C#, using XNA Game Studio 3.1. The game falls in the category of 3d space shooters. Inspired by a classic, Asteroids, the game puts the player in space, in a field filled with rocks. Some of these can be destroyed by shooting at them. The goal of the game is to shoot and destroy a number of rocks. To make things challenging, the controls of the ship are consistent with what you would expect from a ship drifting in space. There is no friction, and the ship does not necessarily point where it's headed. Controlling the ship to collect power-ups and approach asteroids to shoot requires skill. The higher difficulty levels feature enemies in the form of drones that track the player's ship and detonate themselves when they come close enough.

In this article, I present my thoughts about the development process of the game and the reception of the game by players.

Development

The game was written using Visual Studio in C# and in F#. C# is used for the higher levels of the software, which consist of menus, parts of the rendering, loading assets, loading and saving user progress.
Menus use the game state management sample from the App Hub.

Using F#

F# is a good programming language in general, and contributed positively to the development. Features such as discriminated unions and pattern matching are lacking in C#.

Although the game uses multiple threads, it does not use async workflows (these are primarily intended to ease the development of asynchronous code, but they also have interesting properties for parallel programming, as shown in my earlier blog entries).

Some of F# features were at the time not supported on Xbox and resulted in run-time errors: sprintf and async workflows. I haven't had the occasion to try async workflows with the current version of F#, but sprintf now works!

Building the game was tricky before I managed to hack project files.

I initially used the free versions of Visual Studio: the Express edition for XNA Game Studio and C#, Visual Studio Shell for F#. This worked OK, even for debugging, but wasn't as practical of using Visual Studio Pro, which I ended up using at the end. You can use the free editions to try and see if F# works for you, but for regular development, you will probably want to use the Pro edition or higher.

I was a bit worried that using F# on the Xbox might not fully work, and might even be impossible as new versions of XNA or F# are released. Although there have been problems, all could be resolved, and the mix got better or more stable with every new release. Although F# is still not officially supported on Xbox, the fact that Microsoft Research has developed an XBLA game that uses F# sounds positive.

F# uses reference types for most of its data types: lists, tuples, records, classes, discriminated unions, function values, mutable cells (ref). This can cause problems because of the limitations of the current garbage collector on Xbox. I decided to design my code so that garbage collections would have a low latency, and not care too much about how often they would occur. This worked well enough. The game triggers a garbage collection every 6 frames, which each last for 3.5ms. The remaining time was enough to update the physics and render all objects, but a more complex game with more models and more complex class hierarchies could have difficulties.

F# does not allow circular dependencies between types unless they are declared in the same file and marked as mutually dependent. I was aware of this restriction, and it did not cause me any trouble. I started the project with all C# code in one project, and all F# code in another. Toward the end, I started moving reusable code into separate libraries. For my F# code, this was little more work than moving files to a new project and changing namespaces. The task was notably more difficult in C#, as the language supports circular dependencies within assembly bounds. Breaking apart an assembly will require the introduction of interfaces at the bounds. Although F# and C# do not differ on that point, the fact that F# forces you to work that way has benefits the day you want to split your code, in addition to all other benefits that non-circular designs have (better tool support, easier to understand...).

I don't know of any way to declare pass-by-reference parameters in F#, the way you can in C# using the "ref" keyword. In the XNA framework, some methods use passing by reference to save time. Although it is possible to call such functions from F# code, I don't know of any way to declare new functions.
There is however an F# way of avoiding copying large structs when calling functions: use inlining. Last time I checked, it was not fully reliable though, as the F# compiler tends to introduce lots of unnecessary variables in inlined code. Whether the .net CLR notices that and removes these variables isn't clear to me.

Project planning and tracking

I have used a free account on fogbugz to organize my work and keep track of bugs. Although it may seem to be overkill, it allowed me to look at what went wrong when writing this article, as I had a record of most of the bugs. It also simplifies working on a project part-time. During my day job I can focus on my job and forget about the project. When the week-end comes, I can pick up the project where I left it, and start new tasks which were planned but not started.

Obstacles encountered

Although the game state management sample was very helpful to get the menu system up and running in no time, it's not obvious at first how to integrate user interaction forced by the StorageDevice API. One needs to keep track whether a device is selected, whether the user is currently selecting one... The first solution that comes to mind, using Boolean variables isn't maintainable when the number of variables grows. For instance, the device selection screen had to keep track of whether the user was signed in, currently signing in, if a title-specific storage device was chosen, being chosen, whether a user-specific storage device was chosen, being chosen. Mix that with event handlers that may need to display alert boxes, and it becomes tricky. I used handlers to deal with storage disconnection and I/O operation notification.
Even after writing my own version of EasyStorage in F#, cleaning up code, the Update() method of my game object still looked too complicated for its own good:

protected override void Update(GameTime gameTime)
        {
            base.Update(gameTime);

            if (titleStorageLost == GuideStates.Requested)
            {
                if (!Guide.IsVisible) try
                {
                    Guide.BeginShowMessageBox("Storage device disconnected",
                        "The storage device used for scores was disconnected. " +
                        "Scores will not be saved unless a new device is selected. " +
                        "Would you like to select a device now?",
                        new string[] { "Yes", "No" }, 0, MessageBoxIcon.Alert,
                        (result) =>
                        {
                            var choice = Guide.EndShowMessageBox(result);
                            if (choice.HasValue && choice.Value == 0)
                                requestTitleStorage = true;
                            titleStorageLost = GuideStates.None;
                        },
                        null);
                    titleStorageLost = GuideStates.Pending;
                }
                catch (GuideAlreadyVisibleException) { }
            }

            if (titleStorageLost == GuideStates.None && requestTitleStorage)
            {
                storage.RequestTitleStorage();
                requestTitleStorage = false;
            }

            if (titleStorageLost == GuideStates.None && !requestTitleStorage && userStorageLost == GuideStates.Requested)
            {
                if (!Guide.IsVisible) try
                {
                    Guide.BeginShowMessageBox("Storage device disconnected",
                        "The storage device used for player progress was disconnected. " +
                        "Progress will not be saved unless a new device is selected. " +
                        "Would you like to select a device now?",
                        new string[] { "Yes", "No" }, 0, MessageBoxIcon.Alert,
                        (result) =>
                        {
                            var choice = Guide.EndShowMessageBox(result);
                            if (choice.HasValue && choice.Value == 0)
                                requestUserStorage = true;
                            userStorageLost = GuideStates.None;
                        },
                        null);
                    userStorageLost = GuideStates.Pending;
                }
                catch (GuideAlreadyVisibleException) { }
            }

            if (titleStorageLost == GuideStates.None && userStorageLost == GuideStates.None && !requestTitleStorage && requestUserStorage)
            {
                var screens = screenManager.GetScreens();
                if (screens.Length > 0)
                {
                    var topScreen = screens[screens.Length - 1];
                    if (topScreen.ControllingPlayer.HasValue)
                        storage.RequestUserStorage(topScreen.ControllingPlayer.Value);
                }
                requestUserStorage = false;
            }

        }

Since then, I have developed a better way of solving that kind of problem. All this code now becomes:

task {
  do! storage.CheckPlayerStorage
}

Shorter, isn't it? The point is that F# has features that make it possible to compose code using a notation similar to traditional function calls, yet the execution can differ from a traditional call. The idea is so neat that the normally conservative C# design team decided to add a variant of it to the next version of the language.

Back to the post-mortem, another related problem is to deal with screen transitions. There are several approaches: Hard-coding, events and delegates.

Using hard-coding, screen A creates and displays screen B when a certain action is performed.
This requires the class for screen A to know about the class for screen B, and must have the data needed during instantiation of B at hand. I found this approach was not very flexible, and caused me some trouble when I added support for local multiplayer (which wasn't planned from start).

The two other approaches, events and delegates make it easier to forward the data needed to instantiate new screens, as it's typically available in the class which registers the event handler, or creates the delegates which captures the data in question.

All these approaches share the same problem: the transition code is spread out all over the place, making it hard to debug, modify and extend. Of the 50 bugs I registered in fogbugz, 13 involved screen transitions at some level. For a game programmer who is interested in getting the gameplay right, getting 26% extra bugs because of menus is a very frustrating, even if most of those bugs are easy to fix.


Art assets

Asteroid models, ship models and textures were provided by Benoit Roche. The title and menu music is from Partners in Rhyme, sounds from Soundsnap.  The game backgrounds and the box art were done by myself using The Gimp and a tutorial on starfields. When doing sky boxes, it's a good idea to test them on a PC screen. I failed to notice on my TV that the sides of the box had light levels that did not match. Happily, a tester on the App Hub noticed that and reported the problem.

The community on App Hub...

... was very helpful. Thanks to all of you fellow developers for your feedback and suggestions!

Due to my earlier involvement in free software and Linux, I thought that sending your game to playtest early and often was a good thing. While it was, don't expect feedback for every release. Other developers will not test your game time and again every month. Getting comments from other is a motivation boost, but you should not rely on that. I think it's a good idea to send to playtest as soon as your gameplay is done, to see how well it's received. After that, sending updates every time won't get you much feedback. It may actually be better to wait until a new milestone is reached, e.g. menus are done, art is done, game is ready for evil-checklist testing.

Reception of the game

The mix between a classic 2d game and a 3d space shooter was not well received by the market. After five weeks, the game sold 143 copies with a conversion rate of 8.06%
Few reviews were written, most of them judging the game as dull and hard to control. This is what xboxindiegames had to say about the game:

You can't steer, you can't see, you can't aim and you can't shoot. You can avoid this game, though... 

The Yellow Pages from Pencil Shavings sounded more positive:

Looks fantastic and plays well, just a little redundant [...]. Nice game, enjoyable, but lacking variety.

I also registered the game for Dream-Build-Play 2010, but the game did not make it to the best 20.
The game is rated 3 stars of 5 in the American Xbox LIVE Marketplace, which I think is characteristic of well-done but uninspiring games.

Conclusions

Technically, the game was a success and showed the feasibility of using F#. It took me way too much time (about two years), though. I hope I will be able to increase the production rate for my upcoming games.