ANN: Roguestar-

Roguestar is a science fiction roguelike game written using Haskell and OpenGL.  It is in the early stages of development.  At this time, it is not a winnable game.

$ cabal install roguestar-engine
$ cabal install roguestar-gl
$ ~/.cabal/bin/roguestar

– or –

$ git clone
$ cd roguestar
$ git checkout
$ make install

New gameplay features:

  • Melee combat, sundering and disarming attacks
  • Weapons can sometimes overheat or explode
  • Gateway teleportation between planets
  • Use material-spheres to craft new tools
  • Use material-spheres to heal
  • Tab-completion of typed commands
  • Compass directions to significant artifacts
  • “Jump” short distances by teleporting

New objects:

  • Chromalite material spheres
  • Metallic material spheres
  • Gaseous material spheres
  • Energy sabres and fleurets
  • Gateways
  • Monoliths

New graphics features:

  • Randomly generated sky spheres and landscapes
  • Unique fractal trees
  • Zoom-in/zoom-out

Changes under the hood:

  • Major re-write of the RSAGL FRP architecture
  • Multi-threaded 3D scene assembly and rendering
  • Multi-threaded, anticipatory engine
  • Various OpenGL performance improvements

For more information, links to the manual and git repository, visit

Check it out!

A Brutal Introduction to Arrows

Imagine being killed by a bow and arrow. That would suck, an arrow killed you? They would never solve the crime. "Look at that dead guy. Let’s go that way." — Mitch Hedberg

I seem to be one of the few people who absolutely adores arrows. I thought it might be helpful if I provided some insight to the advanced-level newbies regarding the practical use of arrows in Haskell. Plenty has already been written about what arrows are in category theory, how to implement the Arrow typeclass, and how to use the special arrow syntax. I want to talk about why I occasionally wake up in the morning thinking, "Maybe I could solve this problem using arrows!"

This article is just to share an extremely simple, intuitive and concrete example of an arrow. I’m not going to get into all the crazy amazing things arrows can do. I just want to show that they can do at least one cool useful thing.

Arrows are closely related to monads. For example, both arrows and monads can be used to capture side-effecting operations.

Monads have the kind * -> *, indicating a side-effecting operation with a single output type, and a binding operation m a -> (a -> m b) -> m b. The input to a monadic operation is provided via a pure function. Arrows, on the other hand, have a kind * -> * -> *, indicating a side-effecting operation with a single input type and a single output type, and a binding operation a b c -> a c d -> a b d.

When binding monads, it’s obvious from the type signature that the subsequent side-effecting operation does not even exist until after the output of the previous operation becomes available. It cannot, because it depends on the previous output and because we can inject any pure function to construct the subsequent operation based on completely arbitrary criteria.

When binding arrows, the subsequent side-effecting operation exists before execution begins.

All monads are arrows, but not all arrows are monads, and this observation is pertinent to their implementation in Haskell, but I’m going to restrict this article’s discussion to "interesting arrows," specifically, arrows that aren’t monads because they don’t implement ArrowApply. Interesting arrows are basically monads without flow control: you can’t generally choose what side-effecting actions to perform based on things you learn during the execution of the arrow.

This is why arrow-notation creates two scopes. Between the <- -< symbols, only values that were in scope before execution of the Arrow are in scope. Outside the <- -<, values that appear during the execution of the Arrow are also in scope.

For example, we (you and I) might have a monad that allows us to perform certain dangerous operations, like overwriting files. In a monadic context, we can not anticipate what any particular instance of the monad will choose to do. We might write a very complicated installation script that accesses many files. Do we have permission to write to all of those files? Do the files we want to read even exist? Do we access an infinite number of files?

Do we ever write to /dev/nuclear_missiles?

We would like to know the answers to these questions before running the installation script, otherwise we could be interrupted and leave the system in a chaotic state. Even if we could recover from an error, we would still be wasting the user’s time, which is the opposite of the thing that computers are for.

But if we implemented our IO environment using an arrow, we could anticipate all of the side-effecting operations, even have a list of files to be overwritten before the operation begins.

In our new file IO arrow, it will be impossible to read the name of a file from a file, and then write to that file dynamically, because all file names must be specified at the time the arrow is bound. That’s a pretty onerous restriction, but we can always add new operations later, if we need them.

Our arrow needs a list of accessed files and an IO action. The list of file paths is going to take the form of a monoid, while the sequence of IO actions will take the form of a Kleisli arrow.

data IORWA a b = IORWA [FilePath] (a -> IO b)

We need a category instance.

instance Category IORWA where

Implementing id is easy. Id accesses no files, so we give an empty file list. Return is the simplest monadic action that type checks.

id = IORWA [] return

The bind operation requires that we concatenate two lists of file paths, and bind the IO actions. (This is a little annoying, but note that the (.) operator specifies the preceding action second and the subsequent action first.)

(IORWA sa actionA) . (IORWA sb actionB) = IORWA (sa ++ sb) (\x -> actionB x >>= actionA)

At this point, we only have a category, which has only slightly more sophistication than a monoid. To get our tricky arrow syntax, we need to implement arr and first.

instance Arrow IORWA where

Arr, like id, doesn’t touch any files, so we provide an empty file list and inject the function into the arrow.

arr f = IORWA [] $ return . f

First is a little tricky. We’re accepting a side-effecting operation as a parameter, so we need to preserve that operation’s file list.

first (IORWA s action) = IORWA s $ \(x,k) -> do { x' <- action x; return (x',k) }

And we need read/write operations, in which we simply pack the file path parameter into the file list. Notice that we take the file path as a static parameter, but we take the data to write as an input to the arrow.

writeFileA :: FilePath -> IORWA String ()

writeFileA path = IORWA [path] $ \s -> writeFile path s

readFileA :: FilePath -> IORWA () String

readFileA path = IORWA [path] $ \_ -> readFile path

Using our arrow is as simple as exporting a function to the accessed file list and the IO action, as long as we refuse to export any way to corrupt the synchronization between the two fields.

Looking at Control.Arrow and the arrows library on hackage, there are a few things we could add to all this:

  • We could implement ArrowChoice. This would allow us to choose at runtime between accessing two different sets of files. Both possibilities would appear in our static accessible file list, but only one would actually be accessed.
  • We could use a modified ReaderArrow to capture rewriting rules for file paths, e.g., to specify a current working directory. We can’t use ReaderArrow directly, because it would route information through the monadic component of the computation.
  • We could use a WriterArrow to retain a log of all of the data we actually write.
  • We could use an ErrorArrow to recover from file system errors.
  • We could implement ArrowLoop based on the MonadFix instance of IO.
  • We could use the Automaton arrow to implement multi-phase read/write cycles. Perhaps the first phase would be read-only, then we could check the file list again before proceeding to the second phase.
  • We could re-implement what we just wrote in terms of the StaticArrow and Kleisli arrows,
    and get a metric ton of the above for free.

To play with this example, you could always git clone

Composable Blocking Transactions

Background: Software Transactional Memory (STM) is a foundation for atomic composable non-blocking transactions. An STM transaction consists of a set of variables and a monadic sequence of read/write operations on those variables. As the transaction progresses, a transaction table is constructed detailing the specific variables to be modified. At the end of the transaction, either the changes are written atomically (that is, none of the intermediate modifications are visible to the outside world), or the transaction is aborted as though nothing had happened.

Blocking-transactions is an alternative library that implements atomic transactions using locks. This library is strictly less expressive than STM, but does have some advantages.

First, I will demonstrate why such a library is even possible. In order to implement a blocking transaction, we must:

  1. Sort all of the variables that could participate in the transaction.
  2. Sieze a lock on each variable in sorted order.
  3. Perform the transaction.
  4. Release all of the locks.
  5. Notify any waiting threads that the variables have been modified.

Acquiring locks in sorted order guarantees that the program can not deadlock. Acquiring a lock effectively acquires the exclusive right to acquire any greater-ordered locks before any thread that has acquired a lesser-ordered lock.

None of this is possible unless we know the entire set of variables before the transaction takes place. In traditional models of computation, this is impossible. However, arrows provide an environment of restricted flow control in which all computations are either inevitable or in which there is a finite set of branches. The StaticArrow is an example of an Arrow that can do this.

It is also possible to build a monad with similarly restricted flow control. If the side-effectful operations of a monad always return an opaque value (meaning that there is no function that can transform the value or any combination of values into a boolean) then no flow control within the monad is possible.

Such a library has a profound limitation: although we can store a transactional variable inside another transactional variable, we can not retrieve it without considerable contortions. Blocking transactions therefore do not seem to be suitable for working with complex graphs of transactional variables.

On the other hand, the restricted flow control that blocking transactions require presents an unexpected opportunity: transactions can be made inevitably lazy. A lazy transaction completes in the time it takes to entangle the variables in a system of unevaluated thunks. This means that the locks are held for the shortest time possible, but increases the CPU time needed to complete the entire program.

These systems of unevaluated thunks constitute a potentially hazardous memory leak. I choose to write the library in such a way that each variable is forced after the transaction completes, by means of a parallel spark.

This is not the only strategy for evaluating a transaction. We could also choose to:

  • Allow values to be forced within the transaction, but locks could be held while an expensive and unimportant computation completes. We would then want a strategy to release unneeded locks early, but this would add overhead.
  • Sequentially force each variable after the transaction, but this was not efficient in the benchmark.
  • Specify a per-variable strategy for forcing each variable, but this is adds complexity with little apparent benefit.
  • Tolerate the memory leak on the assumption that the caller must manually force the contents of the transaction, but this had catastrophic implications for performance in the benchmark.

Note that the blocking transactions library at the moment is not exception safe.

My implementation is available as a git repository. You can also link directly to the source code and a simple benchmark.

$ git clone