Adder as a state machine

In my previous post I wrote about a, probably rather naïve, approach to constructing state machines in Haskell. I ended it with a saying that the pattern matching of Haskell makes it rather simple to manually write the step function required to create a working state machines. Hopefully this post can convince you I’m right.

The vehicle I’ve chosen is a very simple machine capable of reading two integers and adding them. In slightly more detail it’s a machine that:

  1. reads a total of three parts, two integers followed by a plus sign (+)
  2. each part is separated by whitespace
  3. on errors the machine resets and starts over

The signals (a.k.a. the output alphabet) is the following type

The events (a.k.a. the input alphabet) is simply Char. The states are

where the names hopefully are self explanatory. The type of the machine is then

The machine itself can then be written like this:

That’s rather simple and easy to read I find. Though I’m not sure it scales too well to much larger machines. I’ve not really used any DSLs to create large machines either, so I don’t know how well any method scales ;)

To do a bit of exploratory testing it’s handy to create the following function

Using that function it’s easy to check if the machine works as intended.

> calculate "56 67 +"
CalcNothing
CalcNothing
CalcNothing
CalcNothing
CalcNothing
CalcNothing
CalcResult 123

So far so good. What about the behaviour on errors?

> calculate "5a6 67 +"
CalcNothing
CalcError (ReadFirst 5) "Bad format"
CalcNothing
CalcNothing
CalcNothing
CalcNothing
CalcNothing
CalcResult 73

That looks good enough to me. Though there is (at least) one detail of how the machine works that might be surprising and hence should be fixed, but I’ll leave that as an exercise for the reader ;)

As I mentioned in the previous post I’ve been using this method for writing state machines to implement two different protocols. For the IO I used conduit which means I had to turn the state machine into a conduit. I’ll write about that in a later post though.

⟸ Simple state machines in Haskell State machine with conduit ⟹

Tobias Florek

Have you considered using Ed Kmett’s machines library?

Magnus Therning

@Tobias Yeah, I did have a brief look at it, and spent some time failing to find some documentation on it. AFAIU I could use it as a replacement for conduits, but I kind of like conduits and know a little about how to use it already. So, for now I’ve left machines on my list of modules to have a look at.

Tobias Florek

I was confused when I wrote the comment. Have you had a look at Ed Kmett’s folds library? It supports many different machines, e.g. a Mealy machine.

Magnus Therning

@Tobias No, I haven’t had a look at it, but now I have yet another thing on my list of Haskell stuff to take a look at. Thanks for the tip.

Leave a comment