Haskell: How to test a (reactive) FSM with quickcheck?

Question

I wrote a finite state machine module for a little soccer game I'm currently working at. It provides an interface for setting up an FSM (basically its states and transitions). For each state, you can provide functions that will be fired on entry and exit or while the FSM remains in the same state, these functions then return some messages. It also provides a reactive interface (Yampa) that yields the time-varying state and collects the messages that occur over time. The code is here Data/FSM.hs.

I am looking for a good approach to test this module. Since it is pure, I thought about giving quickcheck a try. I am not experienced with quickcheck, so any tip would be appreciated! My basic understanding so far: one would provide some functions that build up FSMs more or less randomly, and then run some (again more or less random) transitions on them. But I can't quite see how to build a test that way...

Vial

Well, what sort of tests do you want to write? What properties or behaviors need to be verified? – Volunteer

Well, maybe the problem is I don't really know... For something simple like "for every valid fsm, any finite list of transitions leads to either a state 'Nothing' or state 'Just s' where s is a state in fsm", ok. But more complicated stuff like "for every valid fsm and list of (time-varying) transitions and perceptions, every message collection along the transition path should be picked up", I wouldn't know how to formalize this. I would know how to set up unit tests for that, but with quickcheck I'm a bit lost. – Vial

The link is dead (patch-tag.com/r/martingw/Rasenschach/snapshot/current/content/…) and there's no archive that I can find – Crabber

@icc: It's been a while :-) - fixed the link. – Vial

Nigh on 5 years to the day :) – Crabber

Answer 1

First of all, QuickCheck is arguably best suited for verifying broad, general properties. Given arbitrary data of some type, perform some operations, then use a predicate to ensure the result has some property relative to the input. Things involving precise details of step-by-step behavior might not work as well in this style, and you shouldn't feel obligated to do everything in QuickCheck!

That said, based on the more complicated example you gave in a comment, have you considered simply generating expected output along with the FSM and inputs? If you can produce a desired result that you know is correct by construction, you can then run the FSM on the input and compare the actual result with the constructed version.

It might help if you avoid thinking of the QuickCheck properties as testing a function on some input, but rather as checking whether one or more values satisfies some predicate expressed in terms of the function being tested. This collection of values (which may include multiple inputs, outputs, whatever is necessary) is what's actually being generated randomly by QuickCheck.

Volunteer

So probably a mix is the best approach: test for a specific result for a specific fsm and input with HUnit for step-by-step situations, and quickcheck for more generic properties? – Vial

@martingw: I think a mix is the best default approach, yeah. I'm pretty sure there's even stuff on Hackage providing unified test harnesses for HUnit, QuickCheck, and maybe other stuff. I'd probably argue that QuickCheck should be preferred when possible, but it works best when all you're testing is that you get from A to B, not the details of the route taken. – Volunteer