technology from back to front

QuickChecking imperative code

[Haskell](http://www.haskell.org)’s [QuickCheck] http://www.cs.chalmers.se/~rjmh/QuickCheck/) is a very neat tool for automated testing. One specifies *properties* that one would like a program to satisfy, and *generators* for test data, usually involving some form of randomisation. QuickCheck then uses the generators to produce test cases and check the properties against them.

The original QuickCheck was designed to test *purely functional* code only. However, the project I am working on contains a fair amount of imperative code, most of it performing operations on a database. Is it possible to employ QuickCheck for testing this code?

The [Testing Monadic Code With QuickCheck](http://www.cs.chalmers.se/~rjmh/Papers/QuickCheckST.ps) paper explorers several approaches for QuickChecking programs that aren’t purely functional. The one that fits my application bestproceeds by defining the the following:

1. A data type representing the actions that can be performedby the program:

data Action = Reset
| Intervals User Interval
| NewInterval User Interval Task
| ClearInterval User Interval
| ModifyTask User Interval Task Task
deriving (Eq, Show)

So in this example there are five possible actions, parameterised by instances of the `User`, `Task`, and `Interval` data types which are part of the API I am testing:

2. A notion of *observation*, i.e. what kinds of things can be observed by running programs:

type ObservationC = Maybe [(Task, [Interval])]

Most of the API calls return `Nothing`, and one, `Intervals` returns a
list of `(Task, [Interval])` instances.

3. A `perform` function that takes a sequence of actions, performs it, and returns all the observations made along the way:

performC :: Database -> [Action] -> IO [ObservationC]
performC db [] = return []
performC db (act : acts) =
liftM2 (:) ((transaction db . execC db) act) (performC db acts)

execC :: Database -> Action -> IO ObservationC
execC db act =
case act of
Reset -> reset db >> return Nothing
Intervals u i -> intervals db u i >>= (return . Just)
NewInterval u i t -> newInterval db u i t >> return Nothing
ClearInterval u i -> clearInterval db u i >> return Nothing
ModifyTask u i t t’ -> modifyTask db u i t t’ >> return Nothing

Here `reset`, `intervals` etc are the functions of the API I am
testing.

4. An *abstract model* of the desired program behaviour. The details are unimportant here, so I am omitting the associated code.

5. A notion of observation for the abstract model:

type ObservationA = Maybe [(Task, [[Tick]])]

6. A `perform` function that takes the same kind of sequence of actions defined above, performs it on the abstract model, and returns all the observations made along the way.

performA :: AbstractModel -> [Action] -> [ObservationA]
performA m = snd . mapAccumL execA m

execA :: AbstractModel -> Action -> (AbstractModel, ObservationA)
execA m act =
case act of
Reset -> aReset m
Intervals u i -> aIntervals m u i
NewInterval u i t -> aNewInterval m u i t
ClearInterval u i -> aClearInterval m u i
ModifyTask u i t t’ -> aModifyTask m u i t t’

Here `aReset`, `aIntervals` etc are the functions in the abstract model which correspond to the functions of the API I am testing.

7. QuickCheck generators to produce sequences of actions. In our case this involves generators for the `User`, `Task` and `Interval` types, and for `Actions` constructed from these. This is all very straightforward, so I am omitting the details.

8. A property that calls the `perform` functions defined above to execute the action sequence in both the real implementation and the abstract model, and then compares the resulting observation traces. The latter requires a function to map concrete observations to abstract observations.

prop_Test =
forAll actions $ \acts -> performOnC acts == performOnA acts

performOnC actions = map abstractObservation $ unsafePerformIO $
withDb (\db -> performC db actions)

performOnA = performA M.empty

abstractObservation :: ObservationC -> ObservationA
abstractObservation Nothing = Nothing
abstractObservation (Just tis) =
Just $ map (\ (t, is) -> (t, map intervalTicks is)) tis

Notice that I had to resort to `unsafePerformIO` since QuickCheck currently does not provide an easy mechanism to test programs in the IO monad. According Koen Claessen, one of the authors of QuickCheck, this is due to change though.

With the above in place we can get QuickCheck to test for observational equivalence of our implementation and the abstract model. Tests can fail because the implementation is incorrect, the abstract model is incorrect, or both. So the testing strategy is to run the tests, fix the bugs, rinse and repeat. In my application I managed to track down half a dozen corner case bugs this way. The test
code is less than two hundred lines of well-factored Haskell code that is easy to understand and keep up-to-date as the implementation
evolves.

by
matthias
on
20/07/06
 
 


9 − = five

2000-14 LShift Ltd, 1st Floor, Hoxton Point, 6 Rufus Street, London, N1 6PE, UK+44 (0)20 7729 7060   Contact us