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!

An example of inheritance gone wrong

In an earlier post entitled Why inheritance for code reuse should be avoided I pointed out that the key problem was conforming to the Liskov Substitution Principle.

Although I guess there is nothing controversial in what I wrote, I fear I probably did not convince anyone who wasn't already convinced.

Today at work, I had the pleasure of being hit by a bug that is a wonderful example of inheritance gone wrong.

Let me give a bit of context. Once upon a time there was an application that allowed viewing and editing a database in a nice and user-friendly somewhat buggy GUI. As it was felt the application could be user-friendlier and more stable, additional development efforts were planned to improve it. This logically led to the decision of distributing what was a stand-alone file-oriented program over a server-client architecture.

In case you hadn't noticed, I'm being a bit sarcastic, but the fact is that the original plans for the application included extensions to a server-client architecture, and the source code was cleanly organized in modules, keeping the GUI and the database separated by a middle layer.

When moving to the new architecture, it felt natural to turn the middle layer into a web service. This required all data types in the API of the middle layer to be serializable so that they could be sent over the net between the client (the GUI) and the server. This was fairly easily achieved using WCF and DataContract.

[DataContract]
class Item {
   [DataMember]
   public int Data { get; set; }
}

Today, I opened a bug report with an unexpected exception stating that a type named "...Dialog+GuiItem" could not be serialized. Indeed, I could recognize the "Item" part, which was serializable thanks to DataContract, but the GUI component most certainly wasn't! What was going on there?

Looking at the definition of Item, I could see it was a fairly simple type GuiItem augmenting a simple data-type (called Item) with GUI thingies.

class GuiItem : Item {
   public Gui SomeGuiStuff;
}

The problem is, the GUI-augmented type couldn't provide all features the basic type did: It could not be sent over the net.

In the first version of the software, passing the GUI-augmented instance to the middle layer was not a problem. The middle layer expected a basic Item or anything that can be implicitly converted to such an item. As long as all passing of arguments occurs within the same process, no additional effort or processing was needed.

class MidLayer {
   public void DoSomething(Item item);
}
...
void OnClick(GuiItem item) {
  midlayer.DoSomething(item); // Fine, GuiItem is also an Item.
}

In the new version, passing arguments is a significantly more complex operation involving doing a deep dump of the content of the instance, streaming over the net, and summoning a new instance stuffed with the dump on the other side of the wire. This only works for types which are purely data-oriented. Inject any kind of "live" resource in there, and you are out of luck.

[WebService]
class MidLayer {
   [WebMethod]
   public void DoSomething(Item item);
}
...
void OnClick(GuiItem item) {
  midlayer.DoSomething(item); // Exception: can't serialize GuiItem!
}

The solution was simple enough, simply include the basic Item as a member of the GUI-augmented type, and provide a getter to easily send it from the GUI to the server.

class GuiItem {
   Item item;
   Item Item {
      get {
         return item;
      }
   }

   public Gui SomeGuiStuff { get; set; }
}

void OnClick(GuiItem item) {
  midlayer.DoSomething(item.Item); // Fine again.
}

When inheriting from a type, you don't just get its nice features, but also its responsibilities.

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.

Why inheritance for code reuse should be avoided

The question of when to use inheritance and when not to has been asked many times. I have noticed answers can be put in one of three categories:

1. Use as much as you can. It's a convenient way to maximize code reuse with very few keystrokes. Actually, this answer is seldom explicitly given, but if I judge by the code I see, this is a wide-spread opinion.

2. There are situations when inheritance is appropriate, and situations when it isn't. Namely, inheritance is appropriate to express IS-A relationships.

3. Never use it for the purpose of code reuse. Some take it even further and say never use it at all. Inheritance is flawed by design.

Throughout my life as a programmer, I have gone through all of these stages, in order. I think most of the controversy focuses on inheritance for the purpose of code reuse, and I'll start with that.

Inheritance for the purpose of code reuse
The first answer is easy to discard, as explained in this answer on the programmers stackexchange. Systematically using inheritance quickly leads to excessively large objects. The author of the code probably won't see this as a problem at first, and may indeed be oblivious to the problem. Unfortunately, this makes it very easy to fall into this trap.

The second answer begs for an answer to the question "what is an IS-A relationship?". I find that all IS-A relationships can be expressed as HAS-A, and vice-versa. Taking the usual example of cars, we can say a car has four wheels, and it is a four-wheeled vehicle. A car has an engine, and it is an engine-powered vehicle. Which is the correct way of expressing relationships between cars and their components?

Instead of relying on IS-A vs HAS-A, one can use the Liskov Substitution Principle (LSP), as pointed out in this other answer.

Informally, the principle states that if B inherits from A, then B must be usable in all places where A is used.

This is a bit of a loose definition, and even the more formal definition by Barbara Liskov and Jeanette Wing stated below invites further questions.

Let q(x) be a property provable about objects x of type T. Then q(y) should be provable for objects y of type S where S is a subtype of T.

What is the proof system assumed here? What kind of sentences can be expressed? Do the axioms include knowledge about the program?

Informally, how should "usable" be interpreted in the informal statement of the principle?

I don't think there is a single fit-all answer to this question. There are a number of aspects to consider, which all affect the initial development time and degree of maintainability of a software project.

Language Semantics.
Note that a language which allows to query the concrete type of an object makes it impossible to meet the LSP.

let f (x : A) =
    match x with
    | :? B -> failwith "Failing!"
    | _ -> x.DoSomething()    

Obviously, an instance of B cannot be used with f, as it would cause the program to behave differently as when provided with instances of A (or some other subtype of A).

Notion of equivalence.
That instances of B can be used instead of A means that the behavior of the software when B is used is "observably equivalent" to that of the software when A is used.

There are different levels of strictness regarding equivalence. Including internal state in the observable behavior is a bad idea, as this forbids method overriding and polymorphism.

Even limiting oneself to "user-visible events" may be too limiting, as this closes the door to plug-ins that extend or modify functionality.

In the end, I think a popular but very weak notion is whether the program crashes or not. And even that may be too strong, as it's probably acceptable for instances of B to work where instances of A crash (OK, that's nit-picking).

Scope.
Does "all places where A is used" refer to the places as they exist in the current form of the software, in the current and expected future forms, or in all possible forms?

There is a bit of overlap with the first aspect. When assuming the scope is limited to the current state, and if no concrete type tests on instances of A are made anywhere, then meeting the LSP seems feasible.

Assuming the second alternative (current and expected future forms) requires either a clear idea of what the future looks like, or a coding standard prohibiting the use of all language constructs potentially incompatible with the LSP.

If you are designing a library or framework to be used by other parties you don't control, you are condemned to the last option, "all possible forms". Unless you have a low level of ambition on the notion of equivalence, the LSP is impossible to meet in this setting.

There may well be other aspects I haven't thought of, but I hope I made it clear that the LSP isn't quite as simple as it may seem at a first glance. Using inheritance only "when it conforms to the LSP" often equates to "never" if one really cares about the LSP. Moreover, it requires an understanding of the principle itself as well as clearly identifiable decisions on all the points mentioned above, two conditions which are not met that often out-there-in-the-real-world.

Note that it's possible and indeed desirable to specify limitations on language features, equivalence and scope on a per-type basis. Doing it on a project-wide level would probably make it impossible to respect the LSP.

Inheritance limited to interfaces
My standing on the question of inheritance when limited to interfaces is not quite clear yet. I can't quite put my finger on the exact problem yet, so I'll leave it to another day to express my thoughts in details on the subject.

Shortly, it seems to me this kind of inheritance brings little, if anything at all, over composition. The argument of the "keystroke minimality" applies only to subtyping between interfaces, which I have had little practical use for so far.

Alternatives to inheritance
Composition is often cited as the right way to take advantage of code reuse. To put it mildly, mentioning it often fails to trigger the enthusiasm of proponents of inheritance for code reuse. It's easy to understand why:

type A =
   ...
   member this.DoSomething1() = ...
   ...
   member this.DoSomething15() = ...

type OhForGodsSake_B =
   let an_a : A = ...
   member this.DoSomething1() = an_a.DoSomething1()
   ...
   member this.DoSomething15() = an_a.DoSomething15()

type WhatABreeze_B() =
   inherit A()

Indeed, there is something to be said for the second approach. I wish F# had some way to achieve the conciseness of inheritance through composition, but that's not the case. This may be an oversight, or may be by design. As Matthieu M. writes in his answer, forcing verbosity can be beneficial:

[It] means that at least a couple keystrokes are needed for each method, and suddenly people begin to think about whether or not it's such a great idea to reuse this "fat" class for just a small piece of it.

I would add that this would also force the author of B to think about whether all 15 DoSomething() methods really are needed in B, or if it's enough to provide just a few of them.

By the way, should the methods in B have the same name as their counter-parts in A? If A is "VehicleWithWeels", and "B" is "Airplane", it makes sense to expose "VehicleWithWeels.Brake" as "Airplane.BrakeWithWheels", as airplanes have different means of braking. It's easy to miss that subtle point when using inheritance.

All-in-all, I don't think I should value my laziness and comfort over cleaner code, at least not in a professional setting. Still, I can't help being lazy... Programming isn't all about writing clean code, it's about having fun too.

When dealing with implementation relationships between concrete types and interfaces, I am happy with seeing it as "HAS-A" kind of relationship, or more precisely (and verbosely) "OFFERS-FUNCTIONALITY-AS-SPECIFIED-BY-INTERFACE". This can be achieved in two ways in F#:

// Explicit implementation
type B1 =
   ...
   interface A with
      method this.DoSomething() = ...

// Composition using object expressions
type B2 =
   ...
   member this.AsA() =
      { new A with
           member x.DoSomething() = ... // Note "x" vs "this". "this" refers to B2.
      }

The first approach can be used when it's clear B1 can only provide A in one single sensible way at all times, the second approach is more general and flexible. One might wonder if the second approach shouldn't always be preferred. Where do extremes end? ;)

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.

Reference-counting just isn't enough and actually is harmful

I recently came across a blog entry titled "Why Garbage Collection is not Necessary and actually Harmful".

I used to share the same opinion in my C++ days, when I used to think no better language could be written. A few years later, I have drastically changed my opinion on the subject. I am not going to address all points made against garbage collection, and instead will focus on one issue: The claim that reference-counting is a viable alternative.

Reference-counting is an automatic memory management system where memory allocated to an object is freed when the object is no longer referred to. C++ makes it relatively easy to replace pointers by wrappers that act like pointers, with the addition that reference counts in objects are automatically increased and decreased, as wrappers are created and destroyed.

Reference-counting by itself is flawed as it does not account for cycles. The aim of automatic memory management is to deallocate memory when it is no longer reachable from the program. Reference-counting deallocates memory when it is no longer reachable from reference-counted objects. These two coincide only in the absence of cycles (and provided a number of other conditions are met, e.g. all reference-counted objects are referenced through wrappers)

Edaqa says:

simple reference counting also covers the vast majority of memory management needs. Sweeping collection has a distinct feature of being able to resolve cyclic dependencies. That is when A points to B and B points to A. Reference counting cannot manage this in the general case.

Obviously if you have such a feature you will make use of it. I don’t see however that cyclic dependencies are a significant obstacle in most programs. Such object relationships can normally be resolved, or significantly mitigated, by one of a number of other techniques.

I strongly object to the claim that cyclic dependencies are not a significant obstacle in most programs. It may be so in version 1.0 of a program, but even that is stretching it. A reference-counting based memory recollection can introduce enough chaos into a software product that early retirement may be needed earlier than expected.

Potential cyclic dependencies are hard to detect.

It might seem at first that it should be possible and easy to detect cycles when looking at the class diagram. In practice, detecting loops involving more than 3 steps is in my experience tricky. Maybe not when you first design your classes, but when you or someone else alters it later. A developer who does not have the entire class diagram at his disposal or in his mind simply cannot know whether an addition can introduce cycles or not.

Actual cyclic dependencies are harder to detect.

Cycles at the class level are not necessarily problematic. There are moreover very common. Consider for instance the usual definition of lists:

template<typename T>
struct Node<T> {
   T data;
   struct Node<T>* next;
};

Although it is in theory possible to create a cyclic list, this should never happen in any run of the program. How does one convince oneself that this is indeed the case? The problem is solved for lists through the use of a safe API, but home-made more complex types seldom offer such an API.

There is no easy way to deal with cycles.

In order to avoid memory leaks, cycles must be broken in one way or another. This involves manually decreasing the count of an object, or simply not accounting for a reference.

The problem here is which link to choose in the cycle? Obviously, the link must be part of the cycle. Finding a candidate can be difficult by itself for the reasons mentioned above, and there is another restriction. The candidate link must never be a potential member of a cycle-free path for any run of your program, or you might end up deallocating objects that are still in use.

Update (May 2012): Jon Harrop in the comments point out there are languages that prevent creating cycles, and there are algorithms to detect and collect cycles. In this post I was mostly focused on C++ and the traditional ways of doing ref-counting, namely using shared_ptr.

Conclusion

The real problem with reference-counting and avoiding cycles is that there is no good way to convince oneself of the absence of bugs through static analysis or inspection of source code. Absence of cycles is a dynamic property of program runs, and is therefore difficult to analyse. Testing might help, but to my knowledge, few write and maintain test cases specifically for the purpose of validating reference counting.

What makes matters worse is that it's very easy to mistake reference-counting pointer wrappers for substitutes to classic pointers. Systematically using the wrappers often ends up introducing memory leaks. Fixing them introduces dangling pointers.

Mark-and-sweep is no silver bullet, but at least it's a bullet aimed in the right direction.

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.

Is that a cloud, or is it a storm?

I was recently forced to spend some time at a hospital due to a bowel inflammation. The inflammation is due to a chronic disease whose cause is still unknown. It's also not clear whether there are non-surgical treatments to completely cure the disease. I won't go into details in this post, suffices it to say the event has distracted me a bit from my usual focus on games, Xbox360 and XNA.

Let me start with a few words about nutrition journals. Although there is little scientifically established information about the link between food types and inflammations of the digestive tract, many patients report that specific diets do help. The problem is that there does not seem to be any single diet that fits all.

It is therefore important for each individual to assess the effect of each food type on one's digestive system. Any good programmer knows it: before you optimize, you need to measure. The same goes for nutrition. Before doing changes to one's regime, it is important to keep track of what goes in and, well, what comes out.


The difficulty is that keeping such a journal requires discipline, as it's best to record that information as soon as meals are eaten, and directly after visits to the bathroom.

This is were mobile devices and the net comes into the picture. Smart phones make it easy to fill in the journal. The journal itself is probably best kept on a central server (in the "cloud") in order to be accessible from anywhere at any time through any device.

All of this is a good excuse for me to start having fun with WebSharper and F#, of course. WebSharper makes it possible to design web applications entirely in F#. The client code is compiled into javascript and executed in the browser.

The recent panic about .NET and Silverlight being dropped from Windows 8 is interesting in many aspects. .NET developers are reluctant to switch to javascript, a feeling I share and understand. The current tendency however seems to use javascript as a virtual machine targeted by a range of nicer technologies. Examples include F# through WebSharper, XNA, emulators... I for one rejoice in Microsoft's adoption of open standards.

But do I? I see Windows 8 as an attempt to regain control over the Web. What place will have competing web browsers (Firefox, Google Chrome, Opera...) in the new operating system when it includes it's own browser as a mandatory component? If the web view of Windows 8 succeeds in pushing out other browsers, Microsoft will be free to invent new technologies, forcing others to play catch up. Are we getting back to the Windows 98 and "optimized for IE6" days?

Happily, I don't see that happening. Non-Microsoft smart phones and tablets have conquered large portions of territory once owned by Microsoft and Intel. Hopefully HTML5+js will gain adoption and proper support across all platforms.

Note that the irrelevance of platform-specific technologies such as Silverlight applies to others as well. Why keep making iPhone and Android apps when you can make a web app instead? Are the specificities of GUIs compelling arguments to redevelop client apps multiple times? Will users be willing to pay for apps when free web apps become ubiquitous?

We can turn to the PC platform to find hints of answers. The computing power they offer still has no equivalent in the cloud, and demanding applications such as development tools, CAD and video games will always feel best at home on a PC. I expect those applications to keep being developed using a mix of native and VM-based languages and frameworks.

Is there a similar place on the smart phone? Applications requiring unrestricted access to the mobile's resources come to my mind. This includes media players, games, device management... I expect however that a very large eco-system based on "silly apps" will soon disappear, possibly in a very sudden manner.

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.

My next project: WorldConquest

I started working on a new project during the 2010 Christmas break. It's a turn-based strategy game whose working title is WorldConquest. The final title will differ, as there already are quite a few strategy games with identical or similar names.

The game is loosely based on a game for Atari ST written by Alois Felber from WisiSoft games in 1992.

The new game will feature the same units as the original game. I am planning improvements of my own, some of which are already implemented.

The original game used square tiles, I will be using hexagonal tiles. Although the new game will be turn-based it will use a simultaneous variant where players plan their moves simultaneously. When all players are ready, orders are executed simultaneously. The game will support on-line and hot-seat multiplayer. I have been thinking about and planning AI from day one. Although my experience in this domain
At this point, I have implemented map generation and some parts of AI, namely path finding. Execution of orders is what I am working on now. Design and basic implementation are done, I am testing and fixing bugs.

I am still open about the platforms I will target. The genre should fit hand-held devices such as smart phones and iPad-style tablets. PC and Mac will probably be first, as these are the only platforms that might have the CPU required to run a rough and slow AI. I would also love to publish on Xbox Live Indie Games, but the prospects are uncertain. On one hand this is a genre that isn't much represented on this market, but on the other hand I am not sure console gamers are the right customer base. Moreover, the .Net platform on Xbox features a poor garbage collector which requires code to be written in a very specific way, and I feel designing and implementing AI is challenging enough as it is. Adding constraints on allocation of temporary objects would add to the difficulty, and "optimising" code to work around the weakness of the garbage collector isn't my idea of fun.
To summarize, the platforms will may include the following, ordered by decreasing order of priority and likeliness:

1. PC / Windows using XNA
2. Mac and PC/Linux using Mono and possibly a port of XNA
3. Windows Phone 7 with XNA; although the garbage collector there currently suffers the same problems as on Xbox, announcements were made during MIX11 that the Mango update would introduce a new ephemeral garbage collector
4. Xbox 360 with XNA if the next update includes improvements to the garbage collector. No announcements have been made, but I'm hoping that Gamefest 2011 will bring positive news.
5. Android using Mono. I have no idea what technical limitations Mono on Android has when it comes to efficiency and garbage collection, but I'm hopeful the Mono team will be working hard to lift whatever limitations there might be. Unlike Microsoft's .Net, it's also easier to see where Mono is heading.
6. iPhone and iPad using Mono would be nice, but it does not seem feasible at this time. F# relies on generic virtual methods for function values, which are a corner stone of functional programming. Unfortunately, restrictions on run-time code generation on iPhone (and I guess iPad) make these hard to support. Sadly, this probably means no support for these platforms.

Although the game itself won't be free software, I will update XNAUtils with whatever reusable code I will write. This includes A* path-finding, a UI framework supporting menus and a network component.

I am planning several iterations, steadily moving toward a Civilization-style strategy game. I will release the source code of old iterations as new ones are published.

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.

"I'll Whack Your Fingers"-Oriented Programming

Every now and then, a question about how to transfer data between game screens pops up on the App Hub forums. The source of the problem is that many try to solve this problem using synchronous programming. This does not work because game screens require interaction with users, which cannot be handled in a synchronous manner without freezing the game.

Although F# gives you tools to solve that problem using e.g. async workflows, most people are using C#.

How do you solve that problem in this language? Usually, people use a combination of events and public fields. This solution is fine, but I just don't like events much. They make bugs tricky to track, because I lose track of where handlers fit in the expected flow of execution of my code. Moreover, the only practical way that I know of to pass data from an event handler to the main code is through a shared variable (which I call "I'll Whack My Own Fingers"-oriented programming).

For this reason, I suggested to use Begin-End-style asynchronous programming. This requires an implementation of IAsyncResult if you want to do it in a nice .NET-ish kind of way. I am not aware of any such implementation (EDIT: Here is one, thanks mausch), so I wrote my own:

/// 
 
  /// An implementation of IAsyncResult that wraps result data. 
  /// 
 
  /// Type of the result data. 
  class AsyncResult<T> : IAsyncResult, IDisposable { 
    public AutoResetEvent signal = new AutoResetEvent(false); 
    public bool isDone = false; 
    public T result = default(T); 
 
    public object AsyncState { 
      get { return state; } 
    } 
 
    public WaitHandle AsyncWaitHandle { 
      get { return signal; } 
    } 
 
    public bool CompletedSynchronously { 
      get { throw new NoneOfYourBusinessException(); } 
    } 
 
    public bool IsCompleted { 
      get { return isDone; } 
    } 
 
    public void Dispose() { 
      signal.Dispose(); 
    } 
  } 

Did you notice how I made all fields public? I think many a modern programmer would wince when reading this. What if some careless programmer accessed isDone and modified it? Bad things can follow, and surely we should restrict access to these fields using the private keyword.

I like to call this "I'll whack your fingers if you touch this"-oriented programming. Beside "private" and "protected", which were probably invented to tempt stressed programmers to replace them with "public", enthusiasts of this approach enjoy using "sealed" to punish users who might be tempted to reuse your code.

There are better ways to prevent accidental tempering with an object's internal state: access objects via interfaces.

For instance, here is the code for the Begin-End pair of methods that use my AsyncResult:

/// 
 
        /// Open a MessageBoxScreen asynchronously. 
        /// 
 
        /// The screen manager to which the screen is to be added. 
        /// The index of the player who has control, or null. 
        /// The text of the message to show. 
        /// An object which can be used to wait for the request to complete and retrieve the result. 
        public static IAsyncResult BeginShowMessage(ScreenManager sm, PlayerIndex? player, string msg) { 
          var result = new AsyncResult(); 
 
          var screen = new MessageBoxScreen(msg); 
          screen.Accepted += (src, args) => { 
            result.isDone = true; 
            result.result = true; // User accepted the message box. 
            result.signal.Set(); 
          }; 
          screen.Cancelled += (src, args) => { 
            result.isDone = true; 
            result.result = false; // User cancelled the message box. 
            result.signal.Set(); 
          }; 
 
          sm.AddScreen(screen, player); 
 
          return result; 
        } 
 
        /// 
 
        /// Wait for the user to complete interaction with a MessageBoxScreen opened with BeginShowMessage. 
        /// 
 
        /// The object returned by BeginShowMessage. 
        /// Whether the user accepted or cancelled the message screen. 
        public static bool EndShowMessage(IAsyncResult r) { 
          var result = r as AsyncResult; 
          if (result == null) 
            throw new ArgumentException("Wrong type or null", "r"); 
 
          result.signal.WaitOne(); 
          result.Dispose(); 
          return result.result; 
        } 

Note how BeginShowMessage and EndShowMessage return and take respectively an IAsyncResult. Unless users of these methods really want to take risks getting intimate with AsyncResult, there is no risk of tampering. And if they really want to work directly with the inner parts of AsyncResult, why prevent them to do so?

I wonder, what's the point with "private" and "protected" anyway?

UPDATE:

Thinking a bit more on the subject, I think another overused feature resides in non-virtual public methods (and fields). Anything public in the API of a class should belong to an interface, with the exception of constructors and construction helpers (which maybe should be internal to assemblies).

I would however not advise to use abstract data types in all situations. Navigating in the call tree is a good way to learn a new code base, and typically abstract methods defeat this. One could say abstraction through interfaces is a form of obfuscation, as it effectively hides implementations.

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.

Replacing LIVE functionality in XNA 4.0

Although the XNA framework supports multiple platforms, including Xbox and Windows on PC, there are parts that are not available on Windows PC.

One such part is dedicated to interacting with Xbox LIVE, such as gamer profile information, permissions, avatars. (Actually, these parts are available to developers, but not to users). That can be a problem if you want to release your Xbox game to PC. Even if you don't intend a commercial release and only want to distribute your game to your friends and family, they typically don't want to install the full SDK just so that they can run your game.

Before XNA Game Studio 4.0, if you wanted to support the PC platform, you had to write an abstraction layer over these restricted features, or sprinkle your code with #ifdef. There was no way you could replace the implementation of restricted features with your own as the default implementation was embedded into the same DLLs as non-restricted parts of XNA (and you don't want to reimplement these).

The release of XNA Game Studio 4.0 saw a clean-up of the organization of all assemblies. All restricted features are now confined to specific DLLs, which you can replace with your own.

I have started work on my own implementation. My level of ambition is not pretty low, I only intend to achieve the kind of coverage I need for my own code to compile and run. In any case, it's available on bitbucket, so feel free to grab it, modify and extend it to your liking.

I have started with Microsoft.Xna.Framework.Storage, as this is what I use in the code I mentioned in a previous post about safe IO on Xbox. Here are some random observations and small things I learned in the process.

References to record types can't be null. The XNA framework is primarily meant for C#, and it uses null (to the delight of generations of evil peer-reviewers). I initially used records for StorageDevice and StorageContainer, and I had to change to classes when I tried my replacement with existing game code. Even F# classes aren't null-friendly by default, you have to mark classes with a special attribute to change that:

[<AllowNullLiteral>]
type StorageDevice =
    class
        val drive : DriveInfo
        val path : string
        new (d, p) = { drive = d; path = p }
    end 

Separating methods from data in class declarations help avoid circular dependencies. StorageDevice depends on StorageContainer because a method of StorageDevice is used to create instances of StorageContainer. StorageContainer depends on StorageDevice because each StorageContainer is owned by a StorageDevice.
It would seem there is a circular dependency, which in F# must be dealt with explicitly. A simple solution consists of declaring the types as mutually dependent (using "and" instead of "type" for the second type). Another one is to move the definition of StorageDevice.BeginOpenContainer and StorageDevice.EndOpenContainer after StorageContainer.

[<AllowNullLiteral>]
type StorageDevice =
    class
        val drive : DriveInfo
        val path : string
        new (d, p) = { drive = d; path = p }
    end


[<AllowNullLiteral>]
type StorageContainer =
    class
        val name : string
        val device : StorageDevice
        val mutable is_disposed : bool
    
        new(name, dev) = { name = name; device = dev; is_disposed = false }
    end
with interface IDisposable with
        member this.Dispose() = this.is_disposed <- true

type StorageDevice with
    member this.BeginOpenContainer(displayName : string, cb : AsyncCallback, state : Object) =
        let f = new Task<_>(StorageInternals.openContainer(this, displayName), state)

        StorageInternals.doThenMaybeCallback(f, cb)

        f :> IAsyncResult

    member this.EndOpenContainer(result : IAsyncResult) =
        let task = result :?> Task<StorageContainer>
        task.Wait()
        task.Result

Not everything needs to be in a module. By default, each new F# source file starts with

module Module1.fs

You can use "namespace" instead:

namespace Microsoft.Xna.Framework.Storage

If you need F# functions at the root-level (i.e. outside a class or a method), you can start a module right in the middle of your source file:

type StorageContainer =
    class
        val name : string
        val device : StorageDevice
        val mutable is_disposed : bool
    
        new(name, dev) = { name = name; device = dev; is_disposed = false }
    end
with interface IDisposable with
        member this.Dispose() = this.is_disposed <- true


module StorageInternals =
    let checkConnected(dev : StorageDevice) =
        if not dev.drive.IsReady then raise(StorageDeviceNotConnectedException())

type StorageContainer with

    member this.CreateDirectory(dir) =
        StorageInternals.checkConnected(this.device)
        let path = Path.Combine(this.device.path, this.name, dir)
        Directory.CreateDirectory(path) |> ignore 

Windows.Forms.FolderBrowserDialog isn't very useful. I was initially using it to let the user select the StorageDevice and StorageContainer, but it turned out I can't use it in the main thread because it's modal, and I can't use in a separate thread because I can't. Actually, that's not true, I can use a separate thread if I create it myself using some special options. It the end, that's not what I did. I just rolled up my own browser using a TreeView.



How do I create an IAsyncResult? There may be many different solutions, but an easy one that work for me was to use a Task (they implement IAsyncResult).

let f = new Task<_>(StorageInternals.openContainer(this, displayName), state)

F# Asyncs are nice for GUI. The following code shows the browser on the right thread (assuming you can get hold of the Threading.SynchronizationContext of the GUI thread), and disposes of the dialog nicely.

let openContainer(dev : StorageDevice, name) _ =
        let dialog = new FolderBrowser(sprintf "Select container directory [%s]" name, Some dev.path)
        async {
            try
                do! Async.SwitchToContext(gui_context)
                dialog.Show()
                let! _ = Async.AwaitEvent(dialog.Closed)
                return
                    match dialog.Selected with
                    | Some path ->
                        if not(Directory.Exists(path)) then
                            Directory.CreateDirectory(path) |> ignore
                        new StorageContainer(name, dev)
                    | None ->
                        null
            finally
                dialog.Dispose()
        }
        |> Async.RunSynchronously

Playing and testing with your library code is easy, just use an F# script. No need for an extra project building an executable.



That's all for this article. Lots of small interesting details packed in little code.