State Machine Diagram Considered Harmful		Date	2021-05-06
		Tags

In the grand tra­di­tion of com­puter sci­ence blog­gers, started by Eds­gar Dijk­stra him­self with Go To state­ment con­sid­ered harm­ful, it is time to cri­tique a com­monly used lan­guage fea­ture. This time in UML & SysML (this also ap­plies to simulink, but this is by no means the lim­its of my quib­bles with Mat­lab). SysML has a few be­hav­ioural di­a­gram types: the use case di­a­gram (al­leged­ly), the se­quence di­a­gram, the ac­tiv­ity di­a­gram, the para­met­rics di­a­gram (though they’re con­sid­ered dif­fer­ent for some rea­son?) and the state ma­chine di­a­gram. Af­ter the se­quence di­a­gram, the state ma­chine di­a­gram is prob­a­bly the most used di­a­gram for be­hav­ioural spec­i­fi­ca­tion. In this blog post, I’m go­ing to tell you why that’s bad.

The state ma­chine di­a­gram is (most­ly) a rep­re­sen­ta­tion of the com­puter sci­ence con­cept of a Fi­nite State Au­toma­ton. This is a model of com­pu­ta­tion where the com­puter passes through a num­ber of states. In each state, the com­puter can ac­cept one of a num­ber of pre­de­ter­mined stim­uli which causes the com­puter to tran­si­tion into an­other state. Al­though not tur­ing com­plete, fi­nite state ma­chines can be used as a model for any ter­mi­nat­ing (not run­ning forever) com­pu­ta­tion. There is noth­ing wrong with us­ing FSMs for mod­el­ling be­hav­iour, but their di­a­gram­mat­i­cal rep­re­sen­ta­tion in SysML has a few prob­lems that I shall de­tail be­low. Note that an ac­tiv­ity di­a­gram with cer­tain con­straints ap­plied could also be used to model an FSM.

We can thank Dave Harel at I-Logix for the state di­a­gram who de­vel­oped the no­ta­tion of fi­nite state ma­chines and de­vel­oped a tool for their ex­e­cu­tion, State­M­ate, all the way back in 1987. Even though State­M­ate was con­sid­ered de­funct in 2006, its in­flu­ence is still felt through UM­L/SysML state ma­chine di­a­grams (1997) and Simulink state­flow (2018). The Rhap­sody UML tool, also cre­ated by I-Logix, also has a heavy bias to­wards an­i­ma­tion us­ing state ma­chine di­a­grams, most likely due to I-Logix’s strong pedi­gree with State­M­ate. Since their in­cep­tion, state ma­chine di­a­grams have be­come a sta­ple of spec­i­fy­ing and de­scrib­ing be­hav­iours of soft­ware and sys­tems. This is likely due to the min­i­mal num­ber of lan­gu­gage el­e­ments, their ease of use and the many pro­grams that sup­port their an­i­ma­tion.

The Prob­lems

When spec­i­fy­ing sys­tems, es­pe­cially con­tin­u­ous sys­tems, a sig­nif­i­cant por­tion of func­tion­al­ity usu­ally ends up pure. That is to say that at any point in time, the out­puts of the be­hav­iour can be de­ter­mined en­tirely from the val­ues of the in­put vari­ables at that point in time (ig­nor­ing lag through the sys­tem). We of­ten re­fer to these purely de­fined vari­ables as states of the sys­tem. An ex­am­ple of this could be the On/Off state of a sys­tem. If its in­put volt­age is greater than 5V, then its on, oth­er­wise it is off. The on/off state of the sys­tem is purely de­fined by the in­put volt­age. We call this sort of re­la­tion­ship where the out­put can be de­fined by the val­ue(s) of its in­puts at any point in time a pure be­hav­iour.

Defin­ing your be­hav­iours as pure also comes with cer­tain as­sur­ances: as there is no in­ter­nal state or side ef­fects, if you want to add two num­bers to­geth­er, the sys­tem will do that and only that and will not fire the mis­siles in the way to do­ing it.

Let’s imag­ine what a state ma­chine di­a­gram for a pure sys­tem would look like. To en­sure that the at any point in time, the out­put is en­tirely de­fined by the in­put val­ues, then we need a tran­si­tion from each state to every other state to com­pletely spec­ify a pure func­tion.

This is the crux of why I be­lieve that state ma­chine di­a­grams are dan­ger­ous: missed tran­si­tions on a state ma­chine di­a­gram are very hard to spot and can have bad con­se­quences. If a tran­si­tion is missed, any method used to trans­late that into re­quire­ments is go­ing to in­herit that missed tran­si­tion into a medium where its go­ing to be harder to spot. Of course, state ma­chine di­a­grams can be ex­e­cutable, but to spot a missed tran­si­tion, one has to ex­er­cise it with test cases that would cover it. As Eds­gar Dijk­stra fa­mously put it: “Pro­gram test­ing can be used to show the pres­ence of bugs, but never to show their ab­sence!” In the case of pure func­tions, what can we do?

The Path to To­tal­ity

So what would be the best way to to­tally spec­ify a pure func­tion? One could use a truth table. These are par­tic­u­lary good for sim­ple be­hav­iours as a missed re­quire­ment maps to an empty box on the table. Here’s an ex­am­ple of an XOR be­hav­iour:

As the num­ber of in­puts to the func­tion in­creas­es, the num­ber of di­men­sions on the ta­ble re­quired to fully spec­ify the func­tion in­creases to. This makes truth ta­bles un­wieldy for pretty much any func­tion with more than two in­puts. There are, of course, other ways of to­tally spec­i­fy­ing the out­put of a func­tion for pure func­tions. One of these ways is us­ing pat­tern match­ing syn­tax used in some pro­gram­ming lan­guages. Be­low are some ex­am­ples of pat­tern match­ing writ­ten in the lan­guage Idris:

getChar : Int -> Char
getChar 0 = 'a'
getChar 1 = 'b'
...

Be­low is the stan­dard re­cur­sive form of a fi­bonacci num­ber gen­er­at­ing func­tion:

fi­bonacci : Int -> Int
fi­bonacci 0 = 1
fi­bonacci x = fi­bonacci (x-1)

Idris is an es­pe­cially nice lan­guage for writ­ing func­tions in as it also checks for you that your func­tions are to­tal; that an out­put is gen­er­ated for all pos­si­ble in­puts. Note that its not al­ways pos­si­ble to tell whether a func­tion is to­tal or not; its math­e­mat­i­cally proven that there are classes of func­tions that are to­tal and can­not be proven so and vice ver­sa. This is a case of the halt­ing prob­lem that was shown to be un­solv­able by Alan Tur­ing.

Re­quire­ments Au­thor­ing

An in­ter­est­ing out­come of this is the ef­fect that us­ing state ma­chines or pat­tern match­ing has on re­quire­ments au­thor­ing. Stick­ing to the EARS gram­mar of re­quire­ments writ­ing, we find that we re­quire, at most, one re­quire­ment for each pos­si­ble out­put of the sys­tem. How­ever with a state ma­chine di­a­gram, we re­quire at least one re­quire­ment for each tran­si­tion. Guards on the tran­si­tions and the source state be­come the ‘while’ con­di­tions of the re­quire­ment and the trig­ger, if one ex­ists, be­comes the ‘when’ con­di­tion. Have a go at spec­i­fy­ing a sim­ple pure func­tion with at least 3 out­put states us­ing both meth­ods if you need con­vinc­ing.

Be­cause of the pre­vi­ous points, we can con­clude that if a state ma­chine di­a­gram is used to spec­ify a pure func­tion with [n] out­put val­ues, we will end up writ­ing [n!] re­quire­ments. This ar­gu­ment of­ten holds for lines of code too. The rea­son for this is that re­quire­ments au­thors and soft­ware en­gi­neers of­ten write to the struc­ture of the in­put in­for­ma­tion; it is very rare that an en­gi­neer will ab­sorb a state ma­chine di­a­gram, ru­mi­nate on it and then pro­duce a nicely refac­tored piece of work from it. If there is a time pres­sure in­volved or the state ma­chine is com­plex be­yond first-glance com­pre­hen­sion, this prob­lem can be ex­ac­er­bat­ed.

Con­clu­sion: Church & State

De­spite my click­bait ti­tle, I do not ad­vo­cate for full re­moval of state ma­chine di­a­grams from sys­tems en­gi­neer­ing process; in­stead I urge en­gi­neers to take a nu­anced ap­proach to un­der­stand­ing where they’re use­ful and where they’re not the best way to present be­hav­iour. Ab­stract is a rel­a­tive term; al­ways re­mem­ber what parts of re­al­ity your are ig­nor­ing with your mod­el.

Us­ing truth ta­bles and pat­tern match­ing to de­scribe func­tional be­hav­iour is great for defin­ing pure func­tion­al­ity but falls down quickly when the value of a func­tion’s out­put de­pends on a pre­vi­ously stored val­ue. This is the case where state ma­chine di­a­grams truly shine. When­ever you have any sort of mem­ory in a sys­tem, a state ma­chine di­a­gram will help you ex­press it. I’ve found the fol­low­ing ex­am­ples to be very com­mon:

• Sys­tems with Hys­tere­sis; where the math­e­mat­i­cal re­la­tion­ships be­tween vari­ables are dif­fer­ent de­pend­ing on the ‘di­rec­tion of trav­el’ of the over­all sys­tem state.
• Places where you want to in­ter­pret a user mash­ing a but­ton as a re­quest rather than rapid suc­ces­sive changes of mind.
• Any­where where a de­lay is re­quired.
• Any­where where event based be­hav­iours cause a ‘latch­ing’ ef­fect.

The catch is that we must en­sure that our state ma­chines re­main small and com­pre­hen­si­ble to re­view­ers and con­sumers. A 5 storey deep nested state ma­chine with 100 tran­si­tions may an­i­mate as valid against your cus­tomer re­quire­ments but your poor sup­pli­ers are not go­ing to make head nor tail of it. For this rea­son I have put to­gether a few best prac­tice guide­lines for the safer use of state ma­chines in be­hav­ioural mod­els:

Ex­pose the state

De­sign your func­tion­al­ity so that the out­put value of your state­ful func­tions is the state of the func­tion. Model fur­ther be­hav­iour as down­stream func­tions. This will make er­rors in your state tran­si­tions far eas­ier to spot. To see how to stitch the ex­posed states to­gether see my third point of ty­ing be­hav­iour to­gether with ac­tiv­i­ties.

Break up nested or par­al­lelised state ma­chines

This point is an ex­ten­sion of the pre­vi­ous one; if states are nested or are in par­al­lel, which off the states do you ex­pose and how? This ques­tion is eas­ily avoided by dis­al­low­ing nested states and par­al­lel states. This is easy enough to say but some­times there is no other sim­ple way to spec­ify the func­tion­al­i­ty. To an­swer this, we need a sim­ple way to break up larger be­hav­iours into smaller ones us­ing the state ma­chine de­f­i­n­i­tion of their be­hav­iour.

With nested states, the en­com­pass­ing level of states be­comes an “up­stream” be­hav­iours of the state ma­chines nested in­side of them. An­other valid method could be to flat­ten the states by keep­ing only the in­ner­most lay­ers of nest­ing and prepend the names of the mother state to those of the daugh­ter states. Par­al­lel state ma­chines are eas­ily sep­a­rated into dif­fer­ent, in­ter­de­pen­dent be­hav­iours by seper­at­ing down the dot­ted line.

Fol­low­ing these meth­ods of split­ting out a big state ma­chine into a set of smaller in­ter­con­nected state ma­chines is also a great way of cre­at­ing a bro­ken down set of func­tions for al­lo­ca­tions to sub­sys­tems if you’ve de­fined your over­all sys­tem’s be­hav­iour with a state ma­chine. Per­form­ing these meth­ods, how­ev­er, leaves us with an in­ter­est­ing prob­lem: how do we tie these be­hav­iours back to­gether in SysML so that a user can un­der­stand the in­ter­de­pen­den­cies?

Tie it all to­gether with ac­tiv­i­ties

Ac­tiv­ity di­a­grams are my favourite di­a­grams in SysML. This bias is not with­out rea­son; ac­tiv­ity di­a­grams are a great way to con­nect be­hav­iours to­geth­er. I plan to do a blog post about ex­tend­ing the power of ac­tiv­ity di­a­grams in the fu­ture, so for now I will just talk about them in ref­er­ence to state ma­chines. Call be­hav­iour el­e­ments in ac­tiv­i­ties can be used as a way of call­ing out to state ma­chines.

There are no se­man­tics cur­rently in the UML or SysML specs about how a state ma­chine be­hav­iour in­ter­acts with ob­ject flow within an as a called be­hav­iour. In fact, state ma­chines are left out of the xUML stan­dard! Here are a few ex­tra se­man­tics that “make sense” to me to tie these dif­fer­ent rep­re­sen­ta­tions to­geth­er:

• In­ter­pret the state as the RE­TURN value of a «stream» ob­ject flow from the called be­hav­iour. (An­i­ma­tion of this can be achieved in many SysML tools by adding an ac­tion on en­try to a state to set the func­tions out­put.).
• Use ob­ject flow to link state­ful func­tions. This has the added bonus of al­low­ing you to spoof ac­tiv­i­ties with in­ter­nal block di­a­grams if your SysML tool does­n’t sup­port the stan­dard well enough.