Safe IO on the Xbox 360 in F#

... or how computation expressions can help you write concise, clean and exception-safe code.

The XNA framework offers a number of APIs to access files. The Storage API, described on MSDN, is a popular one.

All seasoned XBLIG developers know that this API has a number of pitfalls that are not always easy to avoid. Here are those that come to my mind:

1. Files can only be accessed after getting access to a storage device, which requires interaction with the user as soon as more than one storage device (hard-disk, memory unit, usb stick...) is available. As all of the steps cannot be performed within a single iteration of the update-loop, this forces the programmer to spread the steps over multiple iterations.
2. Attempting to get a storage device while the guide is open results in an exception. The guide is a graphical interface to the console's "operating system" which is available at any time.
3. At most one storage container may be in use at any time (a storage container is a collection of files, it can be seen as a directory).
4. The user may at any time remove a storage device, which results in exceptions being thrown while accessing the device.
5. File access is quite slow. In order to keep the GUI responsive, games must perform IO asynchronously.

Attempting to use the XNA API as it is almost invariably leads to bugs. I would say storage-related crashes are among the top 3 reasons games fail peer review. EasyStorage is a popular C# component that simplifies safe IO in games. In this article, I describe an alternative component written in F#.

Let us look at each pitfall and consider ways to avoid them.

Problem 1: Getting a storage device asynchronously

A simple popular solution consists of requesting the storage device, which is an asynchronous operation, and busy-wait until the operation completes when the user chooses a device.

let getUserStorageDevice player = task {
    let! async_result = doOnGuide(fun() -> StorageDevice.BeginShowSelector(player, null, null))
    do! waitUntil(fun() -> async_result.IsCompleted)
    let device = StorageDevice.EndShowSelector(async_result)
    return
        if device = null then
            None
        else
            Some device
}

This function takes a PlayerIndex and returns an Eventually computation expression (which I call a task). doOnGuide is another task which I describe shortly hereafter. Busy-waiting occurs in "do! waitUntil" on the third line.

Problem 2: Avoiding GuideAlreadyVisible exceptions

Whenever you want to open the guide to ask the user to choose a device, to show a message box, send a message to a friend, open the virtual keyboard, you must check whether Guide.IsVisible is false. Even if it is, you have to surround your call to the guide with a try...with block, as GuideAlreadyVisibleException may be thrown. It may surprise beginners, but so is the case, as I have experienced during peer review of Asteroid Sharpshooter.

let rec doOnGuide f = task {
    do! waitUntil(fun() -> not Guide.IsVisible)
    let! result = task {
        try
            return f()
        with
        | :? GuideAlreadyVisibleException ->
            do! wait(0.5f)
            let! eventually_some_bloody_result = doOnGuide f
            return eventually_some_bloody_result
    }
    return result
}

doOnGuide is a recursive function which repeatedly busy-waits until Guide.IsVisible is false. Then it tries to execute the provided function f. If GuideAlreadyVisibleException is thrown, it is caught, discarded, and doOnGuide calls itself again after waiting a short while. This additional wait for half a second is not strictly necessary, I put it there mostly because the idea of raising one exception per update cycle disturbed me a bit.

I don't find this repeated get-rejected-and-retry particularly pleasing to the eye, but if you have seen it's "hacked-the-night-before-sending-to-peer-review" variant in C#, you'll probably find my version decently pretty.

Problem 3: At most one storage container opened at any time

The solution is again pretty simple in principle: keep track in a central place whether a storage container is already opened. If it is, busy-wait until it isn't.

type Storage() =
    let is_busy = ref false
    member this.DoTitleStorage(container_name, f) = task {
            do! waitUntil(fun () -> not !is_busy)
            try
                is_busy := true

                let! result = doInContainer device container_name f
                return result
            finally
                is_busy := false
    }

Class Storage is the class that coordinates access to storage devices. Only parts of the class relevant to problem 3 are shown here.

The first line of method DoTitleStorage busy-waits until is_busy becomes false. When this happens, it goes ahead and immediately sets is_busy to true again. Readers concerned about race conditions and multiple waiters proceeding into the critical section unaware of each other may rest reassured: multiple tasks are picked and executed one a time using cooperative multi-tasking. True concurrency and its pitfalls are out of the picture.

Note the finesse about using finally to reset is_busy. We are not quite sure of what f will do in the container. Should it do something nasty and get surprised by an uncaught exception, the storage component won't be left in an unusable state. Doing proper clean-up and recovery in traditional asynchronous programming using events and callbacks can be difficult. Actually, the difficult part is to remember to do it when the code is turned "inside out".

Problem 4: Uncaring users yanking storage devices at inappropriate times

The only solution here is to sprinkle your code with try...with and checks for StorageDevice.IsConnected. Again, the availability of try...with in computation expressions makes it relatively painless in F#. See problem 2 above for a code example.

Problem 5: Asynchronous file operations

I haven't tackled this problem yet, mostly because I have only dealt with very small files so far (score tables and user settings). I will leave this for another post, if the need arises.
The only point I wanted to mention is that programmers should be wary of simultaneous progression in the GUI and asynchronous IO. Typical tricky situations include users quitting the game while data is being saved, triggering new IO while previous IO operations are still ongoing. For these reasons, it is advisable to limit the responsiveness of the GUI to showing a "please wait" animation, and busy-waiting until IO finishes.

Wrap-up

That's all for now. Complete code is available in XNAUtils. It's still work in progress, but it's already usable. It can be interesting to compare to an earlier attempt I did at dealing with the storage API, using state machines. The previous attempt is both longer in lines-of-code and harder to read. I think it's a lot easier to convince oneself or detect bugs in the newer version using Eventually computation expressions and cooperative multi-tasking.

Cooperative multitasking using the Eventually workflow

In cooperative multitasking at most one task executes at any time. In order for another task to execute, the task currently in control must explicitly pause itself. The scheduler keeps track of which task is executing, which tasks are ready to be executed and which are blocked or sleeping.

This form of multitasking lacks concurrency, which makes it easy for multiple tasks to synchronize and communicate. On the downside, it is not suitable for improving performance of cpu-bound computations.

I have implemented a cooperative-multitasking "operating system" consisting of a scheduler and a couple "system calls" which I believe will make it easier for me to develop the menu systems of my future games. In this article I describe the design and API of this light-weight operating system.

The scheduler

The scheduler is implemented in class Scheduler in CoopMultiTasking.fs, where these methods are available:

• AddTask: A task is an Eventually<unit> computation expression, and can be added to the scheduler using this method. The task won't execute until method RunFor is called. A task is removed from the scheduler after it completes.
• HasLiveTasks indicates if the scheduler has at least one task which hasn't completed.
• RunFor executes all ready tasks for a specified amount of time. Typically, this should be 1/60 for a game running at 60 frames per second, but any value will do. It is for instance possible to "fast-forward" execution by passing durations that exceed the amount of real time that has passed. See "Simulated time vs real time" below for details.

The system calls

Class Environment makes it possible for tasks to interact with the scheduler to control their execution and spawn sub-tasks.

• Spawn allows a task to add a sub-task to the scheduler. The scheduler returns an instance of TaskController which can be used to instruct the sub-task to complete early and to wait for the sub-task to complete early. Spawn does not actually take a task, but a function which takes a reference to a Boolean and returns a task. The Boolean indicates when the task should kill itself. See "Killing sub-tasks" below form more information.
• SpawnRepeat is a variant of Spawn which executes a sub-task in a loop. It returns a TaskController which can be used to interrupt the loop. Unlike Spawn, this method expects a task. The sub-task should be very short, as an iteration of the loop cannot be interrupted.
• Wait causes the task to wait a specific duration. Note that this duration does not correspond to real time, but to durations as passed to RunFor.
• Yield causes the task to stop executing, but remain ready for execution. If another task is ready, the scheduler executes it, otherwise the task continues executing.
• WaitNextFrame causes the task to stop executing until the next time the scheduler's RunFor is called.
• WaitUntil takes a function with signature unit -> bool. The task is paused until the function returns true. The function is first evaluated in the current frame without waiting, then once per call to RunFor. Note that the first evaluation of the function is preceded by an implicit call to Yield.

Simulated time vs real time

The time inside this environment, which I call simulated time, does not correspond to real time. Simulated time passes every time RunFor is called by the amount of time specified to RunFor.

Even if you always pass to RunFor the amount of real time that has passed, the amount of time tasks wait is not coupled to real time. This is due to RunFor never sleeping, even when all tasks are waiting. Instead, it directly advances the simulated time.

Tasks which are waiting for durations exceeding the frame time wake up during the correct frame. Within a frame, tasks wake up in the correct order, in accordance to their amount of time left before waking up.

Killing sub-tasks

It is not possible to forcibly kill a sub-task. Instead, a notification mechanism using a reference to a Boolean cell is used. It is the responsibility of the sub-task to test this cell often enough that excessively long delays after requesting termination do not occur. I realize this may not be a popular design decision, as this forces one to sprinkle the code of tasks with checks for termination requests. The rationale behind this decision is that uncontrolled termination can leave an application in an incorrect state. I don't feel strongly about that point, though.

The Eventually workflow

The F# specification gives an example of custom workflow in its section on computation expressions. I have extended it as shown below:

type Eventually<'R> =
    | Completed of 'R
    | Blocked of float32 * (unit -> Eventually<'R>)
    | BlockedNextFrame of (unit -> Eventually<'R>)
    | Running of (unit -> Eventually<'R>)
    | Yield of (unit -> Eventually<'R>)

An Eventually computation can be in one of the following states:

• Completed, in which case the state includes the result of the computation.
• Blocked, when the computation is paused, and the state contains the amount of time remaining before it resumes.
• BlockedNextFrame, when the computation is paused for a short while, until the start of next frame. The meaning of "next frame" is up to the scheduler, which is described in an upcoming article
• Running, which indicates the computation is ready to proceed.
  
• Yield, when the computation is willing to pass control to another computation which is in state Running, if any. Otherwise, the computation is ready to proceed.
  

All states but the first one, Completed contain a function value which when executed produces a new state. It represents the work that the computation can perform "in one block" before returning control to the scheduler. When that happens, the scheduler updates the state of the computation.

Although it is possible to build computations "manually" using this discriminated union, F# makes it possible to do so conveniently using a subset of F# extended with a few keywords, namely yield, yield!, return, return!, let! and do!. The meaning of these keywords is up to the designer of the custom workflow, but they have an expected behaviour which should be respected.

yield and yield! are used to produce values in sequences. The second variant allows to insert sequences from other sequence expressions. Here I use sequence expression as a synonym for "a computation expression used to produce sequences". Below is an interesting example (from the F# Programming wikibook).

let allEvens = 
  let rec loop x = seq { yield x; yield! loop (x + 2) }
  loop 0;;

loop is a function which takes an integer x and returns a sequence expression which when evaluated produces the integer, followed by the result of a recursive call to loop using x+2. In clear, this will produce x, x+2, x+2+2, x+2+2+2..., one value at a time. Note the difference between yield and yield!: the first produces a single value, the second produces the values of another sequence expression.

let! allows to "nest" computation expressions. In other words, a computation expression can "call" another computation expression. I'm being pretty vague here, so let's look at an example using asynchronous computations (also from the wikibook).

let extractLinksAsync html =
    async {
        return System.Text.RegularExpressions.Regex.Matches(html, @"http://\S+")
    }
 
let downloadAndExtractLinks url =
    async {
        let webClient = new System.Net.WebClient()
        let html = webClient.DownloadString(url : string)
        let! links = extractLinksAsync html
        return url, links.Count
    }

return and return! are used for the final results of a computation expression. The example above uses return. My guess is return! should behave as

let! x = ...
return x

I am not quite sure if return is meant to have imperative semantics, i.e. discarding the remainder of a computation when encountered. My attempts to use such C-like semantics have not succeeded yet.

Going back to my library, XNAUtils, I have written a computation builder which is used to turn computation expressions (code between curly brackets) into state machines that can be executed in a controlled manner. The builder takes the form of a class with methods are called at selected places in a computation expression. A builder allows to override the meaning of certain keywords and specify the effect of the special keywords I listed above. The code is in CoopMultiTasking.fs

let rec bind k e =
    match e with
    | Completed r ->
        Running(fun () -> k r)
    | Running f ->
        Running(fun () -> f() |> bind k)
    | Blocked(dt, f) ->
        Blocked(dt, fun () -> f() |> bind k)
    | BlockedNextFrame f ->
        BlockedNextFrame(fun () -> f() |> bind k)
    | Yield f ->
        Yield(fun () -> f() |> bind k)

...

type TaskBuilder() =
    member x.Bind(e, f) = bind f e
    member x.Return(r) = result r
    member x.Combine(e1, e2) = combine e1 e2
    member x.Delay(f) = delay f
    member x.Zero() = result ()
    member x.TryWith(e, handler) = tryWith e handler
    member x.TryFinally(e, compensation) = tryFinally e compensation
    member x.While(cond, body) = whileLoop cond body
    member x.For(xs, body) = forLoop xs body
    member x.Using(e, f) = using e f

let task = TaskBuilder()

The module-level variable task can be used to create instances of Eventually. I have provided a few helpful tasks that can be used to wait a fixed amount of time, wait until next frame, give control to another task:

// Wait a fixed amount of time.
let wait dt =
    Blocked(dt, fun () -> Completed())

// Wait until next frame, i.e. next call to Scheduler.RunFor
let nextFrame () =
    BlockedNextFrame(fun() -> Completed())

// Stop executing, let some other task execute, if any is ready. Otherwise, we get control back.
let nextTask () =
    Yield(fun() -> Completed())

// Wait until a specified condition is true.
// nextTask is always called, then the condition is checked.
// If it's false, we wait until next frame, check the condition,
// call nextTask if it's not true, and so on...
let waitUntil f = task {
    let stop = ref false
    while not !stop do
        do! nextTask()
        if f() then
            stop := true
        else
            do! nextFrame()
            stop := f()
}

waitUntil uses a while loop, it could have used recursion too. I initially refrained from using recursion in all code meant to be executed on the Xbox 360, because tail calls are not available on this platform. On second thoughts, I don't think that's a problem, as the kind of recursion that would appear inside of tasks is of the loose kind. Recursive calls a interrupted by calls to nextTask and nextFrame, which should prevent the stack from overflowing.

Although I have not had any use for synchronization between tasks yet, I have provided two functions to that effect:

// Lock, can be used for mutual exclusion.
// Locks should not be shared across instances of Scheduler.
type Lock() =
    let mutable locked = false;

    member this.Grab() =
        task {
            do! waitUntil (fun() -> not locked)
            locked <- true
        }

    member this.Release() =
        task {
            locked <- false
            do! nextTask()
            ()
        }

// A blocking channel which can be used for cross-task communication.
// Note that sending blocks until the message is received.
type BlockingChannel<'M>() =
    let mutable content = None
    let mutable flag_send = false
    let mutable flag_receive = false

    member this.Send(m : 'M) =
        task {
            do! waitUntil (fun () -> not flag_send)
            content <- Some m
            flag_send <- true
            do! waitUntil (fun () -> flag_receive)
            flag_send <- false
            content <- None
        }

    member this.Receive() =
        task {
            do! waitUntil (fun () -> flag_send)
            let ret = content.Value
            flag_receive <- true
            do! waitUntil (fun () -> not flag_send)
            flag_receive <- false
            return ret
        }

Cooperative multi-tasking makes synchronization between tasks easy, as there is no concurrency involved.

That's all for this time, in the next article I will describe how multiple tasks are executed by a single scheduler.

How to spread a computation over multiple update cycles

Let us consider a simple example: We want to implement an animation effect which can be used for "press start screens", among other things. The animation can be decomposed into three phases:

1. Fade-in effect where the text "press start" appears from the void. To achieve that, the text is rendered with full transparency initially, then gradually goes to fully opaque. This effect should be short, e.g. half a second.
2. Blinking effect. The text is rendered alternating between fully transparent and opaque. We don't want to alternate between the two modes every frame, as that would be two fast. The text should be rendered opaque for half a second, then transparent (or not rendered at all) for half a second, and so on...
3. Fade-out effect, which is triggered when the player presses the start button. It's similar to the fade-in effect, but in reverse.

The game update loop

The XNA framework, just as most other frameworks, encourages the developer to build their game in a specific way. The main function, which is implemented by the framework, repeatedly calls a function Update provided by the developer, followed by a call to another function Draw, also provided by the user. The combine execution time of these two functions should not exceed the amount of time separating two frames, which is about 16ms for a game running at 60 frames per second.
In this context, implementing computations that need to span over multiple frames is a bit tricky. Not very complicated, and all experienced game developers can do that during their sleep. Nevertheless, I always found that annoying enough that it has often stopped me from implementing a cool animation that would have made my application look so much more professional.

Imperative code

For a moment, let us forget about the game loop and write some simple imperative code.

let sleep time dt exit =
    let t = ref 0.0f
    let dt = int (dt * 1000.0f)
    while !t < time && not !exit do
        System.Threading.Thread.Sleep(dt)

let fade_time = 0.5f   // half a second
let blink_time = 0.25f

let alpha = ref 0.0f
let is_visible = ref true

            
let run dt goto_fade_out =
    let t = ref 0.0f
    while !t < fade_time do
        alpha := !alpha + dt / fade_time
        t := !t + dt
        sleep dt dt (ref false)

    while not !goto_fade_out do
        is_visible := true
        sleep blink_time dt goto_fade_out
        is_visible := false
        sleep blink_time dt goto_fade_out

    let t = ref 0.0f
    while !t < fade_time do
        alpha := !alpha - dt / fade_time
        t := !t + dt
        sleep dt dt (ref false)

Implementation using a state machine

Back to reality (where the game update loop rules), one way to break a computation over multiple update cycles is to use a state machine. Transitions are taken every cycle. Our state machine could have four states: FadeIn, BlinkOn, BlinkOff, FadeOut. It would have the following transitions: FadeIn to FadeIn, FadeIn to BlinkOn, BlinkOn to BlinkOff, BlinkOff to BlinkOn, BlinkOn to FadeOut, BlinkOff to FadeOut. While in FadeIn and FadeOut, the state machine maintains a single float representing the degree of transparency of the text. This can be implemented in F# using discriminated unions, as shown below.

type States =
    | FadeIn of float32        // 0.0 -> 1.0
    | Blink of bool * float32  // On/Off, Time left before transition
    | FadeOut of float32       // 1.0 -> 0.0

let fade_time = 0.5f   // half a second
let blink_time = 0.25f

let initial = FadeIn 0.0f

let update dt goto_fade_out state =
    match state with
    | FadeIn k ->
        let delta_k = dt / fade_time
        let k = k + delta_k
        if k > 1.0f then
            Blink (true, blink_time)
        else
            FadeIn k

    | Blink (b, t) ->
        if goto_fade_out then
            FadeOut 1.0f
        else if t <= dt then
            Blink (not b, blink_time)
        else
            Blink (b, t - dt)

    | FadeOut k ->
        let delta_k = dt / fade_time
        let k = max (k - delta_k) 0.0f
        FadeOut k

Implementation using continuations

To an imperative programmer, functional programmers can seem a bit special. They like to do things in a complicated, twisted way. The method I will now show may appear unnecessarily complex, but it has its benefits, as we shall see.

type States =
    | Transparent of float32 * (bool * float32 -> States)
    | Blinking of bool * (bool * float32 -> States)

let fade_time = 0.5f   // half a second
let blink_time = 0.25f

let rec updateFadeIn alpha (_, dt) =
    let delta_alpha = dt / fade_time
    let alpha = alpha + delta_alpha
    if alpha > 1.0f then
        Blinking (true, updateBlinking true blink_time)
    else 
        Transparent (alpha, updateFadeIn alpha)

and updateBlinking is_visible remaining (goto_fade_out, dt) =
    if goto_fade_out then
        Transparent (1.0f, updateFadeOut 1.0f)
    else if remaining >= dt then
        Blinking (is_visible, updateBlinking is_visible (remaining - dt))
    else
        Blinking (not is_visible, updateBlinking (not is_visible) remaining)

and updateFadeOut alpha (_, dt) =
    let delta_alpha = dt / fade_time
    let alpha = max (alpha - delta_alpha) 0.0f
    Transparent (alpha, updateFadeOut alpha)

let initial =
    Transparent (0.0f, updateFadeIn 0.0f)

let update state x =
    match state with
    | Transparent (_, cont) | Blinking (_, cont) -> cont x

What I did here was move the guts of update into the state itself. A state now includes a function which when called returns a new state (which itself includes a function which when called... you get the idea).

Strengths and weaknesses of each approach

The first method I exposed looks nice and easy to understand, but it won't work as it is. The problem is that it retains full control of the execution. There is not update function which can be called every cycle to update the state.

A solution consists of executing this code on a separate thread, but that brings problems of its own. Access to shared data between the main thread which does the rendering and the update thread is one of them, another is stopping/continuing the update thread.

The second method has only one problem, it becomes hard to read and maintain when the number of states grows. It's perfectly viable for simple animations, but it can't be used for the top level of the application (which can itself be seen as some sort of animation, the complex and interactive kind).

Statistics show that the third method will cause 95% of the population of programmers to get headaches. You'll it's actually very close to the second method, once you get the idea. I'm sure motivated programmers can train themselves to master this technique, but in this context, it's pointless.

The only reason I showed the third technique is to introduce features of F# called computation expressions and custom workflows. These features make it possible to write code using an extended subset of F# usual syntax and have it processed and executed in a manner controlled by the programmer. Understanding continuations is required in order to implement new custom workflows, but it's not necessary to take advantage of existing workflows.

These features are described in the F# specification. There is also a chapter in the F# wikibook. Tomas Petricek has some articles (1 2) on his blog.

Untying the game update loop

In a video game, what do the menu system, an AI agent and an animated HUD component have in common? They are all a pain in the neck to implement over the game update loop.

The difficulty arises from the gap between the concept and the code implementing it. For instance, a menu system is pretty simple to specify:
1. Identify the controller which is used to control the game,
2. Show the main menu
3. Wait for the user to select an entry
4. Depending on the entry, remove the menu and show another screen, which may be another menu, or the game itself.

The game update loop requires that we split up these few steps into tiny little chunks that fit in 16ms time slices. This requires the programmer to introduce variables to keep track of where the program currently is and where it's headed:

type GameState =
| PressStartFadeIn of ...
| PressStartWaitButtonPress of ...
| PressStartFadeOut of ...
| MenuFadeIn of ...
...

let update(gt : GameTime) =
  state <-
    match state with
    | PressStartFadeIn ...

The problem with this approach is that the workflow which was so obvious in the specification is now hidden in a state machine. This approach using state machines is common when implementing simple AI agents and animations.
When dealing with the menu system, another objected-oriented approach is often preferred, with a class per screen type. Transitions from one screen to another are implemented using events and handlers, or hard-coded into the screens themselves. For instance, the press start screen takes care of creating and showing the menu screen when it hides itself. In any case, figuring out the order in which screens come and go by reading the code is not trivial.

Ideally, one would like to program the steps using that sort of code:

while not exit_requested do
  let press_start_screen = new PressStartScreen()
  press_start_screen.Show()
  let player = press_start_screen.GetPlayer()
  press_start_screen.Hide()

  let menu_screen = new MenuScreen()
  menu_screen.Show()
  let entry = menu_screen.GetEntry()
  menu_screen.Remove();
  match entry with
  | Play -> play(); showScores()
  | Scores -> showScores()

Happily, F# makes this possible thanks to so-called computation expressions. I am not going into details in one single post, so for now I will simply refer you to the code I have written. It's all in XNAUtils my library for development of games for the Xbox 360.
I have developed a custom workflow and its associated builder TaskBuilder. There is a class which takes care of executing a set of tasks in type Scheduler. Here are some animations demonstrating how it's used. Another example, from the PressStartScreen:

// This task is chopped in blocks and each block is executed by the scheduler each frame (see Main.Update())
    let press_start_task = task {
        // subtask that makes the "press start" text blink. Executes concurrently
        let blinker =
            sys.Spawn(anim.Task)

        // Task to check if a button is pressed. Sets player when that happens.
        let player : PlayerIndex option ref = ref None
        while (!player).IsNone do
            for p in all_players do
                let state = GamePad.GetState(p)
                if state.IsConnected
                    && (state.Buttons.Start = ButtonState.Pressed
                        || state.Buttons.A = ButtonState.Pressed) then
                    player := Some p
            do! nextFrame()

        // Stop blinking
        blinker.Kill()
    
        // To be nice, wait until the blinker is done.
        // Depending on the blinking period, this could take long as we only check for the kill flag once per blink.
        do! sys.WaitUntil(fun () -> blinker.IsDead)

        // Return the index of the player that pressed start.
        return
            match !player with
            | Some p -> p
            | None -> failwith "Unreachable"
    }

All of this is put together in a sample application. Be sure to take a look at the main code.