NOTE: There is a lot of code in this article, as it is repeated and iteratively added. The final version is just 28 lines near the end, but I think you should read the whole thing anyway.
Once upon the time I needed to implement state machine. To not reinvent the wheel I reviewed what’s available: Windows Workflow Foundation, Appccelerate.StateMachine, bbv.Common.StateMachine, Stateless, SimpleStateMachine, Solid.State, and StateMachineToolkit. Windows Workflow Foundation was just scary, apart from the fact that State Machine is not available in .NET 4.0. It didn’t look lightweight either.
None of the others satisfied my requirements either:
- Events should be able to carry data - for example, hypothetical event
KeyPressedshould also carry information which key has been actually pressed;
- States should be able hold data - for example, state collecting key presses (let’s call it
EnteringText) should be able to hold a list of keys pressed so far;
- Guard statements should have access to both current state and event - for example,
KeyPressedevent may cause transition to different state depending which key has been pressed;
- Transition rules should be implemented outside states - states should be more like POCO/DTO object with no logic in them;
I’ve implemented it in C#, and I’m relatively happy with it, and you can find it on GitHub. As an exercise I implemented it for Kotlin as well, also on GitHub. Then I had to implement one for work, in Java this time.
I decided that maybe it’s time to do something for F# community, and implement nice functional State Machine Construction Kit. I dropped the “transition rules should be implemented outside states” requirement as it was adding some messy reflection code.
To make it more F#y and functional I started with fundamental question: what is the
state? What is its essence?
It is actually a function which will take an
event and produce new state:
This would actually not compile, because it would create infinite recursive type alias, but:
will do just fine.
Actually it would be a little but nicer if it would be possible to return
State option to handle termination:
…but, I decided to make it rather with explicit state case:
So we have transitive state (
State (Some state)) and terminal state (
Please note, that we could add more cases, for example:
but this would introduce some complexity which I don’t want in this example, but you are more than welcome to introduce yourself.
So, let’s go back to my State Machine Construction Kit. We already have a state but we also need a function to fire events and transition from state to state, let’s call it
feed, we feed a state with event. It’s actually almost done as state is a transition function:
For this example I will use some trivial state machine handling opening and closing doors:
So we have
…and have two states:
closed. The states themselves are functions which take events and produce new states:
Let’s define an initial state, a let’s say it is
Now we can send
Open event to it and store new state:
Please note, that to handle sequence of events easily, the only thing you need to is to use
For my personal use I actually created a class to encapsulate mutability. It is, of course, still there but hidden:
What about context (data shared by all states) and state’s state (state internal data) you might ask? By the power of closures and currying there is nothing special to implement. For example, let’s imagine a door state machine which makes sounds (with injected sound emitter) and can be locked or unlocked when closed (state’s internal data):
Note, there is a
sound function passed and all states have access to it and this is your context. Additionally
closed state has a
locked ‘property’ and behaves differently depending on the value is this property (cannot be opened when closed, and needs to be unlocked first). You can call it substate if you want.
What if I don’t like mutable variables and I want my state machine to be an actor / agent? Let’s just wrap it:
So, the full module, already a little bit bloated with helper functions, is:
I can run this now with:
I have to admit. I failed. There is no such thing as State Machine Construction Kit for F#, at least not the one worth releasing, in short, there is just a function:
but I just can’t put it on GitHub. Maybe gist?