Saturday, May 15, 2010

Discriminated unions: a powerful tool for implenting state machines

When writing a game using XNA Game Studio, the programmer quickly faces the problem of dealing with persistent data. Typically, a game will need files to store high-scores, game progress, user settings...
On the PC platform, the programmer has two ways of dealing with file I/O: synchronously, which is OK for dealing with small amounts of data, or asynchronously, which is used to avoid leaving the user with an unresponsive application when large files (or large numbers of small files) are read or written.
On the Xbox, the only available option is the asynchronous one. Another odd side of XNA on the Xbox is the fact that programmers cannot decide on which storage device files should be located. If the Xbox on which the game is running has memory cards plugged in, the user must be asked which device (hard disk or memory card) he/she wishes to use.
In other words, performing I/O on the Xbox requires to go through several steps, and all these steps must be spread out over multiple iterations of the game update loop.

This is one of these situations where state machines are very handy. Considering the file I/O example mentioned above, I have designed a state machine with the following states:

- Ready
- Start requesting user storage
- Requesting user storage
- Start sign in
- Signing in
- Start requesting global storage
- Requesting global storage
- Doing I/O
- Failed I/O
- Successful I/O

User storage is used to store user-specific files, e.g. user preferences. Global storage is used for scores.
Some of these states have specific data. For instance, requesting user storage requires an user id.

In C#, state machines can be a bit cumbersome to implement. Typically, one would use an object containing an enum for the state, and all fields needed for each state.
This last part annoys me a bit, as it hides the relation between states and their data. With time, it's easy to lose track of this connection.

In F#, I see two ways of implementing state machines. The more elaborate way uses a custom workflow and an algorithmic representation of the state machine. Actually, presenting workflows as an implementation technique for state machines is a bit clumsy, as it's really the other way around. I'll stop here for now with custom workflows, more on this subject in a later post.
The simpler way for someone who is not too familiar with functional languages and monads consists of using a discriminated union.

type State =
| StartReqTitleStorage
| RequestingTitleStorage
| StartSignIn of PlayerIndex
| SigningIn of PlayerIndex
| NotSignedInInfo
| StartReqUserStorage of PlayerIndex
| RequestingUserStorage
| DoingIO
| FailedIO of (unit -> unit)
| SuccessfulIO of (unit -> unit)
| Ready

Then comes the data type for the storage component.

type Data =
{ state : State
titleStorage : StorageDevice option
userStorage : StorageDevice option }

As an example of a non-trivial operation, here is the code to request user-specific storage.

let requestUserStorage (p : PlayerIndex) data =
match data.state with
| Ready when Gamer.SignedInGamers.[p] = null -> { data with state = StartReqUserStorage(p) }
| Ready                                      -> { data with state = StartSignIn(p) }
| _     -> raise (new InvalidOperationException())

I particularly like the way pattern matching and the "when clause" combine nicely to express the fact that a user must be signed in before user-specific storage can be requested.
Note also how the programmer is forced to handle the erroneous case of calling requestUserStorage when the storage component is not ready.

This style of implementation using immutable data and functions would not feel very C#-ish for someone using this code from C#. This is easily solved by wrapping all the code in a class:

type StorageComponent(game) =
inherit GameComponent(game)

let data = ref { state = Ready ; titleStorage = None ; userStorage = None }

let getDoSet f =
data := f !data

member x.RequestUserStorage(p : PlayerIndex) =
getDoSet (requestUserStorage p)

For the curious, getDoSet is a helper function I introduced to hide some locking mechanism. The implementation shown here is not the one I actually use. I left it here just because I love to pass functions around ;)

The full code is available on bitbucket, as a part of XNAUtils.