crem: compositional representable executable machines
State machines are a typical abstraction in pc science. They can be utilized to symbolize and implement stateful processes.
My curiosity in them stems from DomainDriven Design and software program structure. With this weblog publish I’d like to clarify why I believe that state machines are an incredible instrument to specific and implement the area logic of functions.
Furthermore, I’d wish to current crem
, a brand new Haskell library to construct state machines, and clarify why Haskell performs an necessary position in making crem
particular.
The origin: AreaPushed Design and state machines
In case you are aware of Area Pushed Design, and Event Storming specifically, you might have most likely already seen the next image:
What I at all times appreciated about it’s that it not solely explains the that means and the position of the totally different sticky word colors for use in the course of the Occasion Storming workshop, nevertheless it additionally hints at a sure model of software program structure. Concepts like CQRS and Event Sourcing play a powerful (if not important) position in such programs.
As I defined in additional element in this blog post, we are able to view the above image as a diagram composed of three stateful processes:

aggregates
(the yellow stickies) obtaininstructions
(the blue stickies) and emitoccasions
(the orange stickies). They’re crucial a part of your area logic, the place the invariants of your system are checked. 
projections
(the inexperienced stickies) propagate the data contained within theoccasions
to thelearn fashions
(i.e. the model of your area mannequin optimized for studying, in a CQRS structure), which might then be queried by the customers. 
insurance policies
(the purple stickies), also referred to assagas
orcourse of managers
, describe the reactive logic of a system (every time ... occurs, then do ...
). They obtainoccasions
as inputs and emitinstructions
.
These three course of collectively can absolutely describe an software area. Due to this fact, discovering a great way to encode these stateful processes could possibly be extraordinarily useful when implementing the area of your mission.
As you may suspect from the introduction, I’ll argue that state machines are in actual fact what we’re searching for right here. There are two primary motivations for this:

State machines are compositional, that means that it’s simple to mix a number of machines into extra advanced ones. This permits working domestically on smaller parts, and solely when these are prepared, combining them into extra advanced artefacts.

State machines admit a graphical representation, which actually assist when documenting and discussing their supposed or present behaviour.
How will we mannequin state machines?
If we’re to make use of state machine to encode parts of our software area, we then want a very good knowledge construction to encode state machines in order that we are able to leverage their theoretical benefits (compositionality and representability).
For those who check out the classical definition of a Mealy machine, it’s simple to translate it right into a Haskell knowledge kind like the next:
knowledge Mealy state enter output = Mealy
{ initialState :: state
, motion :: state > enter > (state, output)
}
The kind variables state
, enter
and output
are respectively the kinds of the attainable states, the out there inputs and the outputs of the machine. initialState
is, unsurprisingly, the worth of its preliminary state, of kind state
. The motion
operate describes easy methods to compute the output
and the following state
, given the enter
and the present state
.
Machines
For those who seek for a Mealy knowledge kind within the Haskell ecosystem, you’ll stumble throughout the machines
library. Their definition is as follows:
newtype Mealy enter output = Mealy
{ runMealy :: enter > (output, Mealy enter output) }
It says that, given an enter
, the machine will produce an output
and a brand new machine, which might then be utilized in future iterations. The unfoldMealy
operate permits us to go from the earlier model with the specific state to this one.
The primary distinction with respect to our earlier definition is that now we don’t have a sort variable to explain the state area. Because of this to retrieve any details about the present state, we must cross that as a part of the output. Alternatively, this model makes composition a lot simpler, and actually this new Mealy
kind is an occasion of Category
, Profunctor
, Strong
, Choice
and plenty of extra which we might not have the ability to implement for the primary model.
These kind courses grant us entry to sequential composition:
(.) :: Mealy b c > Mealy a b > Mealy a c
parallel composition:
(***) :: Mealy a b > Mealy c d > Mealy (a, c) (b, d)
and different composition:
(+++) :: Mealy a b > Mealy c d > Mealy (Both a c) (Both b d)
Such a knowledge kind is nice for compositionality. Alternatively, as soon as we construct a Mealy
machine, there’s nothing else we are able to do however run it. The one option to extract info on its internals is to run it. Specifically, we free the theoretical capability to generate a graphical illustration of the machine itself.
Recovering a graphical illustration
For a given state machine we are able to outline a directed graph of the allowed transitions, the place now we have a vertex for each attainable state, and an edge from a state a
to a state b
if there’s an enter which strikes the machine from state a
to state b
. We’ll name such a graph the Topology
of the machine.
What we want to do is so as to add the Topology
to the definition of a machine. This is able to grant us two advantages.
 It permits us to test whether or not a transition is legitimate.
 It permits us to extract it and use it to supply the graphical illustration of the machine we’re after.
Since we’re working with Haskell, we are able to ask ourselves whether or not we need to observe such info on the kind or on the worth degree. Storing it on the worth degree would make it simpler to retrieve, nevertheless it forces us to test whether or not a transition is allowed at runtime, and subsequently take care of a possible failure. Alternatively, storing such info on the kind degree permits us to get a compilation error each time somebody tries to implement an invalid transition! And, given we’re in Haskell, there are methods to demote typelevel info to the worth degree in order that it may be processed there.
Therefore, we are able to strengthen our kind to one thing like:
knowledge Machine
(topology :: Topology vertex)
enter
output
the place the topology is added among the many kind variables.
At this level, to outline a machine, we first must outline a topology
.
$( singletons
[d
exampleTopology :: Topology ExampleVertex
exampleTopology = _
]
)
We’re utilizing the singletons
library, in order that we are able to elevate the exampleTopology
worth to the ExampleTopology
kind, and in a while demote the ExampleTopology
kind again to the exampleTopology
worth.
At this level, we are able to outline a machine, indexing it with our ExampleTopology
kind:
exampleMachine :: Machine ExampleTopology ExampleInput ExampleOutput
exampleMachine = _
An excessive amount of typelevel info makes compositionality more durable
The mixed utilization of the Topology
on the kind degree and of the singletons
library permits us to extract details about the outlined machines, particularly their allowed transitions, with out operating the machine.
Nonetheless, storing the Topology
on the kind degree makes compositionality more durable. Contemplate, for instance, sequential composition:
(.)
:: Machine topology1 b c
> Machine topology2 a b
> Machine ??? a c
What ought to the topology of the consequence be? Even when we all know the reply, this poses two concrete points:
 We have to compute the ensuing topology out of
topology1
andtopology2
on the kind degree. That is far more advanced than doing it on the worth degree.  The presence of the extra kind variable prevents us from implementing a
Class
occasion. Equally, we have to surrender many different helpful kind courses.
Is there a option to get the very best of each worlds; the power to simply compose our machines and, on the similar time, to extract info with out operating them?
We wouldn’t be right here if the reply was no ????
One of the best of each worlds
The very first thing we have to observe, if we need to obtain our purpose, is that having an extra kind parameter was making issues extra sophisticated with respect to composition. Therefore, we begin by defining a sort with solely the enter
and output
kind variables:
knowledge StateMachine enter output the place
With this method, it seems to be like we’re dropping the Topology
info that we tried so as to add on the kind degree. Actually, not all is misplaced, and we are able to get entry to that info by including a constructor which requires a Machine topology enter output
:
knowledge StateMachine enter output the place
Fundamental
:: Machine topology enter output
> StateMachine enter output
We’re mainly saying that we are able to assemble a StateMachine
simply by offering a Machine
. It seems to be like we’re by some means forgetting info whereas we do that. Actually, because of sample matching, we are able to nonetheless entry the Machine
argument and its topology
info!
foo :: StateMachine enter output > a
foo stateMachine = case stateMachine of
Fundamental machine > _
Now we have to tackle compositionality for StateMachine
. The trick we are able to use is add adhoc constructors, one for each composition operation that we need to enable:
knowledge StateMachine enter output the place
...
Sequential
:: StateMachine a b
> StateMachine b c
> StateMachine a c
Parallel
:: StateMachine a b
> StateMachine c d
> StateMachine (a, c) (b, d)
Different
:: StateMachine a b
> StateMachine c d
> StateMachine (Both a c) (Both b d)
At this level we are able to simply implement infix operators:
(.) :: StateMachine b c > StateMachine a b > StateMachine a c
(.) = flip Sequential
(***) :: StateMachine a b > StateMachine c d > StateMachine (a, c) (b, d)
(***) = Parallel
(+++) :: StateMachine a b > StateMachine c d > StateMachine (Both a c) (Both b d)
(+++) = Different
and revel in all of the compositionality we dreamed of.
Because of this encoding, now the accountability of mixing state machines with totally different topologies is shifted away from the constructors of StateMachine
, which are actually properly compositional, to the eliminators of a machine, like operating or rendering it.
Producing a visible illustration of the state area
A generic time period of kind StateMachine a b
can be a binary tree the place each leaf incorporates a Machine topology x y
and each different node corresponds to one of many different constructors, producing a tree like the next:
At this level, we are able to gather all the data that now we have at each node:
 Within the leaves we are able to entry the data saved within the
topology
on the kind degree.  Within the different nodes, we all know how we’re composing the subtrees of machines, and we are able to recursively generate a illustration for the subtrees. This is sufficient to know easy methods to create some fascinating representations of the entire machine.
For instance, given a machine definition implementing the AreaPushed Design structure defined firstly of the publish, we are able to generate a diagram representing the movement of the machine:
It clearly highlights the parts the entire machine is constructed from and, for every one among them, it represents its topology
(the one nontrivial one is the combination
).
Crem
The concepts which I’ve mentioned on this weblog publish have been packaged within the crem
library.
As mentioned above, it permits creating state machines in a compositional means, executing them and producing graphical representations of the state area and the movement of the machines.
Furthermore, it incorporates an considerable degree of documentation, many examples, together with a DDD impressed software and a terminalbased journey sport, and a cool Nix flake setup for native improvement.
Conclusion
Wrapping up, the principle message of this publish is that state machines are a pleasant abstraction which can be utilized in extraordinarily sensible settings to mannequin and construction our functions. They are often composed simply, they usually admit a graphical language to explain and perceive them. crem
is my try at implementing an answer which each preserves these theoretical properties and makes use of them to make your code simpler and extra maintainable.
Nonetheless, crem
is in its early phases and I might very a lot respect it should you tried it out and let me know what you suppose and the way it could possibly be improved in any attainable means, from its documentation to the nittygritty code particulars.
As a closing word, I’d wish to thank all my colleagues who contributed to crem
and helped me to form and polish it.