Friday, November 28, 2008

Predictable random for testing

In my Haskell RPG game, the results of actions are random: I use the standard random generator to simulate the throw of a dice in a table top RPG.
However for writing unit tests that is not ideal, since I would like to be able to test the outcome of an action for a given result of the dice. I didn't
want to clutter the code (even if using a State monad) with something used only for testing, so I experimented with IORef and a custom Test Generator.

First of all, we need a data type to store our non random random generator. It will store a list of results and the index it's at in that list. It's
basically a circular list, so that when we reach the end we start again. If the list is one element long, then the same result will be given for all
dice throws:

data TestGen = TestGen [Int] Int


mkTestGen is just a helper function to initialise the index to 0

mkTestGen l=TestGen l 0


This is the real magic: I thought you needed to pass around an IORef as any other variable to be able to read its results, but in fact this is not necessary,
if somewhat of a kludge:

testGen :: IORef (TestGen)
{-# NOINLINE testGen #-}
testGen=unsafePerformIO (newIORef (mkTestGen []))


This means that testGen is initialized only once as a TestGen with an empty list, no matter how many time it's called. It seemed to work in ghci even
without the NOINLINE pragma. Don't ask me why. So, given a simple setter function:


setTestGen l=do
writeIORef testGen (mkTestGen l)


We can specify what we want as the random generator. If we have an empty list, we use the standard random generator, otherwise we return the current element
in the list, and increment the index, going back to zero if we overrun the list:


randomInt ::(Int,Int) -> IO (Int)
randomInt (l,h)=do
(TestGen list ix)<-readIORef testGen
if null list
then getStdRandom (randomR (l,h))
else do
let e=list!!ix
let ix'=ix+1
let ix''=if ix'==(length list)
then 0
else ix'
writeIORef testGen (TestGen list ix'')
if e<l || e>h
then error (printf "%d not in range (%d,%d)" e l h)
else return e


And this works, amazingly:


setTestGen [2]
l<-replicateM 3 (randomInt (1,6))
assertEqual ("l is not 3 2s") [2,2,2] l
setTestGen [2,3,4]
l<-replicateM 4 (randomInt (1,6))
assertEqual ("l is not 2,3,4,2") [2,3,4,2] l
setTestGen []


(Notice how I reset the test generator to standard at the end by passing an empty list).

So now I can test my code with predictable results, that will be still random in production use.
Oops, already found a bug on the first test written with that technique!

7 comments:

Joeri van Eekelen said...

The "clean" way to accomplish this isto rewrite your code to use any kind of StdGen (perhaps using a State StdGen a), and either run that code with

getStdRandom (runState program)

to get a result in IO, or with

evalState program (mkStdGen 1)

to get a pure result, which uses '1' as seed. You can change this seed, of course.

Joeri van Eekelen said...

Or even better, check out

http://hackage.haskell.org/cgi-bin/hackage-scripts/package/MonadRandom

Which basically is a wrapper around the interface of System.Random and the State thingy of my previous comment.

BlackMeph said...

I was just wondering why you didn't just throw your list into an array, and use some array tools - after all, you're using your generator more like an array than like a list. :)

Anonymous said...

type TestGen = [Int]

mkTestGen l = if null l then l else cycle l

(e:list') <- readIORef testGen
writeIORef testGen list'

Tim said...

As the others have commented, this is not very Haskell-ish. Haskell has infinite lists so you don't need to have mutable index-based cycling. To turn [1, 2, 3, 4] in to an infinite repetition of that sequence just do:

cycle [1, 2, 3, 4]

You could either just assume the list is infinite or run cycle on it again to be sure - if it's already infinite then it will never cycle anyway.

Also, the use of IO is unnecessary and unfortunate. What if you want to use this in pure code? unsafePerformIO calls are like rabbits. One may seem like a fairly safe thing but it only takes one more interacting with the first and suddenly you're drowning in them.

What you really want to do is add an instance of RandomGen which simply takes results from a list. Your random number generator type may as well be the list itself:

instance RandomGen [Int] where
next (x:xs) = (x, xs)
split g = (g, g)

You can now use a list of Int values as a random number generator. Of course this only generates integers - to generate more complex structures requires knowledge of how they're generated. That's going a bit too far - you would then perhaps want to look at another method of testing.

Ryan Ingram said...

Check out MonadPrompt on hackage; you write your game using a "prompt" to export its actions, and then an interpreter to embed those actions in an interface.

The benefit is that the game itself becomes pure; you can write unit tests that use a pure implementation for the RNG.

See http://www.haskell.org/pipermail/haskell-cafe/2008-April/041983.html for some links to sample code.

JP Moresmau said...

Thank you all for your comments!! I learned an awful lot!

1. Yep, I overlooked cycle, simplifies the code nicely
2. My goal was not to change my original code, but I realize now that StdGen being a pseudo random generator, it's obtaining the instance that needs to be done in IO, getting the numbers is actually pure. So yes, I should probably keep the RandomGen in my State and have pure functions for my actions.
3. One thing with seeds and RandomGen instances: giving the lists of numbers doesn't mean you'll get these numbers, because randomR transforms the number obtained from the call to next. So I've adapted my code so that it calls next itself, and if the number retrieved is not in the requested range, I call randomR. This is not that elegant and means production code that uses StdGen will require to calls for each number, but it's a step forward!