How can I Implement Statecharts in Haskell?

Question

After having read the excellent book "Practical UML Statecharts in C/C++" by Miro Samek, I am eager to try them out sometime. More recently, I have started to teach myself Haskell and functional programming.

Only a few chapters into my book on Haskell, it struck me that statecharts might be difficult, and even against the grain of Haskell. After all, a large effort goes into creating state-free programs, or at least keeping all impure parts of the code well separated from the pure ones.

When I searched for "Haskell" combined with "statechart" on the net, I found almost nothing! This piqued my curiosity. Haskell is, after all, a reasonably old, general purpose programming language. How could it be that there seems to be virtually no activity related to statecharts?

Several possible explanations were suggested in the Haskell sub-Reddit thread "haskellers thoughts on statecharts", and I hope my short excerpts won't warp the views of any of the authors:

1. /…/ the Haskell community in general is not very active in UI development /…/

2. /…/ The downside of Statecharts is that all that flexibility that they provide make modelchecking (and therefor also model-based testing) harder. /…/

3. /…/ A state machine is a collection of states and transition rules. But for implementation states are redundant, you can work with transition rules alone, which are neatly represented as (a mutually recursive family of) functions. /…/ But Haskell is free from this restriction, so implementing state machine explicitly is usually redundant.

   Hense (sic!), as a Haskeller I don't really need explicit state machine most of time. Functions as first-class citizens and TCO make them an implementation detail at best and unneeded at worst. /…/

4. a. /…/ You're probably more lucky with search-terms like "transition system", "actor model" or "state transducer" in the Haskell ecosystem. /…/

   b. /…/ Functional reactive programming (FRP) and arrows are ways of implementing signal flow in Haskell. /…/

   c. /…/ The State monad transformer can model that. If you have external signals in an intermediate step, you can embed it in a continuation monad. /…/

I allow myself to interpret, and comment this a bit:

1. I find the notion that H. programmers don't use statecharts since they don't do that kind of programming a bit hard to believe. I may be wrong, but I would think the field of application is much broader than just UIs.
2. This argument is slightly above my head. The author perhaps focuses on a certain type of testing, a certain tool. I mean, wouldn't a well-defined set of states, up front, make testing a lot easier, if anything?
3. This is perhaps the most interesting argument, that explicit states would be superfluous in Haskell, and hence the need to code visible state machines. My objection is perhaps unfair, but wasn't the state machine abstraction (or rather, its visible incarnation in code) invented in order to make things clearer and easier to understand? The problem it solves — to make the unspecified, de facto state machine hidden in "ordinary" programs, making decisions based on the value of a large number of poorly organised variables, more visible — isn't this negated by getting rid of the state machine?
4. Could it really be this simple, that statecharts are there, but are simply called something completely different? … or are these better solutions for the same problem, in the world of Haskell, effectively making statecharts genuinely redundant?

Will all this become embarrassingly obvious once I have finished reading the book on Haskell and FP?

Answer 1

You could do it with state charts, but you don't need to because Haskell works at a higher level than other languages, and subsumes the state chart design into code. Here is how you do it. (Note: I'm simplifying this down from a monad transformer version which also handles exceptions, so sorry if I've made any mistakes)

First, you can define a state machine in Haskell like this:

newtype AutoS i o = AutoS {runAutoS :: (o, i -> AutoS i o)}

In other words a state machine consists of its latest output o and a function from an input i to the next state. I've called it "Auto" because these are automata, which is maths jargon for state machines.

Now you could just take a UML state chart and translate it directly into a collection of AutoS values. But there is a better way.

newtype Auto i o a = Auto {runAuto :: (a -> AutoS i o) -> AutoS i o}

This is a variation on the continuation monad. With a conventional monad the result from each step is used as the argument to the next, but in continuations each step gets the next step as a function argument and passes its result to that function. That sounds like a weird way of doing things, but it means that you get access to the "rest of the computation" from within the monad, which lets you do some clever things. But before explaining that, here are the instances. It's worth spending a bit of time meditating on the Monad instance in particular. In all these functions k is the continuation; the parameter representing the rest of the computation.

instance (Functor m) => Functor (Auto i o) where
   fmap f (Auto act) = Auto $ \k -> act (k . f)

instance (Monad m) => Applicative (Auto i o ) where
   pure v = Auto $ \k -> k v
   f <*> v = Auto $ \k -> runAuto f $ \g -> runAuto v (k . g)

instance (Monad m) => Monad (Auto i o) where
   return = pure
   v >>= f = Auto $ \k -> runAuto v $ \x -> runAuto (f x) k

So now we can write actions in Auto. But what can they do? Here is the yield function, which is the only primitive in Auto:

yield :: o -> Auto i o i
yield v = Auto $ \k -> AutoS (v, k)

This is the magic bit. Like before, k is the continuation (i.e. everything that follows this step). Remember that the result of the step (i.e. the result of yield) gets passed to this function. By wrapping it up in an AutoS with the yielded value we are passing that value as the output of the state machine and giving the state machine caller the next state transition.

So now instead of writing a program as a state machine with lots of named states we can just write monadic code. When our monadic code wants to exchange information with the rest of the world it uses yield to send out a value and get a new one in return.

There is an old joke about a mathematician who is asked to capture a lion in a cage. The mathematician gets into the cage, closes the door, and declares (by a geometric inversion) that he is now outside the cage and everything else, lion included, is inside the cage. This continuation monad is a bit like that; your monadic code is like the mathematician; it passes a value into yield and gets a result back out. But from the point of view of the rest of the world the yielded value comes out of the state machine (the cage), and the next state transition goes back in to become the result of yield.

The only other thing you need here is a way to run an Auto action:

startMachine :: Auto i o Void -> AutoS i o
startMachine act = runAuto act $ error "Can't happen: Auto terminated."

This assumes that your state machines have no end state. You get Void from the void package. If you need an end state then it has to have a separate type and that type has to tramp around along with everything else. In the original Cont continuation monad that type is r.

The big advantage of doing this way is that the logic of the state machine is expressed as a sequence of steps just like a normal program. Without the monadic approach all you have is a list of states and transitions, which makes following the logic very hard. Its like reading a program where every line ends in a GOTO. When the code is incomprehensible you have to use a design notation to explain it. State charts are a bit like a flow chart for state machines. By using a monad you can program directly at the state chart level, rendering it irrelevant in exactly the same way that structured programming rendered flow charts irrelevant.

Creating a monad transformer version AutoT is left as an exercise for the student. Hint: newtype AutoS i o m = runAutoS :: m (o, i -> AutoS i o m)}, and then take a look at ContT in the monad transformer package.

Actually you could do this by replacing Auto with Cont. I didn't because I also needed exceptions and ContT doesn't do exceptions. Adding something like proper exception handling is also left as an exercise for the student. Hint: newtype AutoS i o e m = AutoS {runAutoS :: m (o, i -> AutoS i o e m, e -> AutoS i o e m) }

Edit: You mentioned the ease of testing the implementation of a state chart.

Yes, for a sufficiently small value of "test". If you implement a state chart in a conventional language using states indexed by an enumeration then testing that your state transitions match the state chart is indeed trivial. However you still need to verify that the state chart in your design was correct. This is exactly the same problem as verifying that monadic code in Auto is correct because they are both describing the solution at the same level of abstraction.