When is a State Machine not a State Machine?

Started by MaxMaxfield 4 years ago12 replieslatest reply 4 years ago712 views

Suppose we have a loop() function in an Arduino sketch (program) that looks like the following:

void loop()
    digitalWrite(PinLed, HIGH);
    digitalWrite(PinLed, LOW);

Even though we don't have any named states per se, would this still be classed as a state machine in that it does alternate between two states or conditions with the LED being On or Off?

If it's not a state machine, what is it? 


[ - ]
Reply by QLJuly 27, 2020

Hell No! The code you are showing is NOT a state machine. In fact, it is an antithesis of a state machine.

My whole recent presentation at the Embedded Online Conference uses this exact Arduino-Blink example to explain the difference between the sequential, blocking code (like your Blink) and event-driven, non-blocking code that can become a state machine. BTW, The aforementioned presentation also explains the concept of a state machine.

But here quickly, the main difference is how the context is preserved between events.

In a sequential code, every blocking call represents explicit waiting for a given event. Unblocking then represents the delivery of that event. In a sequential code then the expected sequence of events is hard-coded. In the Blinky code, you have two hard-coded TIMEOUT events (each corresponding to the delay() call). Between the events, the context is preserved on the call stack. When the call unblocks, you pick up exactly where you left off, so you know what to do. For example, after the first delay(), you known that its time to turn the LED off. and after the second delay, you turn the LED on.

In contrast, truly event-driven code does not block. The code has to process every event to-completion (RTC -- Run-to-Completion processing) and then, after each event, the code returns back to the event-loop. The context then cannot be preserved on the call stack, because the stack is unwound after each call.

So, in event-driven code the context must be preserved differently, typically in some static (or global) variables. The ad hoc, "manual context management" typically uses a bunch of variables and flags that "remember" the history of the system. Then you have many layers of IFs and ELSEs, where the flags and variables are tested and set. This is also known as "spaghetti" or BBM (Big Ball of Mud).

And here is where state machine comes in. A state machine is a very effective way of remembering the relevant context between events in the form of state. Specifically, "remembering" the context, means remembering only the current state (in one state-variable) instead of many variables.

So, to call a piece of code "state machine", it must have at the very least a few properties, such as: (1) a clearly identifiable, central "state variable" (could be encapsulated inside a class) which indicates the currently active state, (2) clear rules of changing the "state variable", which are called "state transitions", and (3) it should be possible to depict the operation of the code in a state diagram. The code presented in the OP does not have any of these properties, and therefore it cannot be called a "state machine".

[ - ]
Reply by MaxMaxfieldJuly 27, 2020
"No! The code you are showing is NOT a state machine. In fact, it is an antithesis of a state machine."

Don't hold back -- tell me what you really think LOL.

While I admire your enthusiasm, I'm not sure I agree with your reasoning. I don;t dispute the facts that delay() is a blocking function truly event-driven code doesn't block, but I don't see how this determines whether the classic blinky sketch is a state machine or not.

I agree with everything you say about a classic state machine being "a very effective way of remembering the relevant context in the form of state," but I don't see why this prevents the blinky sketch from being an inefficient form of a state machine.

I was wondering whether it might be regarded as an "implicit" implementation of a state machine as opposed to an "explicit" implementation.

It's also interesting reading the other replies below. I will have to mull on this some more.

[ - ]
Reply by QLJuly 27, 2020

Of course, you can hold the viewpoint that "everything is a state machine". The CPU is a state machine... The universe is a state machine (perhaps an "implicit" one)

But, I think that it is more productive to use somewhat narrower understanding, in which terms, like "state machine" actually mean something...

As to other responses supporting your viewpoint, it seems to me that there is a difference between the actual structure of the code and how it could be perhaps transformed. I certainly don't see the "PinLedON" and "PinLedOFF" states in the code. Do you? By that reasoning every piece of code could be understood as something else, because it could be transformed into something else.

[ - ]
Reply by MaxMaxfieldJuly 27, 2020
"Of course, you can hold the viewpoint that 'everything is a state machine'."

Are you calling my dear old mother a state machine? LOL

In reality, I would say that a CPU is indeed a super-complex state machine in that it maintains an internal state that is depended on both current inputs and previous sequences of inputs.

But I know what you mean. It's like when people try to say that CPUs are ASICs or ASSPs -- that's true in one sense, but it really serves only to confuse the issue.

I'm glad I raised this question because -- taking all of the responses into account -- it seems that my inability to define what is and is not a state machine is a shared experienced -- I am not alone (hurray! :-)

[ - ]
Reply by QLJuly 27, 2020

Yes, I'm also glad that this issue came up. This is just an example of a bigger issue of the fuzzy terminology of our discipline. The other terms causing constant misunderstandings are: "RTOS", "blocking", "event", "asynchronous", "run-to-completion", "polymorphism", to name just a few...

[ - ]
Reply by MaxMaxfieldJuly 27, 2020
"This is just an example of a bigger issue of the fuzzy terminology of our discipline."I'm guessing you aren't a fan of Fuzzy Logic LOL
[ - ]
Reply by KocsonyaJuly 27, 2020

Well, I think you can call it a state machine, if you really want, but it's a bit of a stretch. It's a state machine as much as this

for ( int i = 0 ;; i = ( i + 1 ) % 10 ) putc( i + '0' );

is a 10-state state machine. It has output, it has a set of states and it moves between the states depending on its current state and that of its non-existent inputs. The lack of inputs could facilitate a nice debate on whether this is conceptually a Moore or a Mealy machine.

You could also drag probability theory into it, by calling it a discrete time Markov chain, with the transition probabilities all being 1 and 0.

Personally, I'd just call it an infinite loop.

[ - ]
Reply by PedroMBMachadoJuly 27, 2020

In the limit yes. The def. of FSM is "Finite state machine (FSM) is a term used by programmers, mathematicians, engineers and other professionals to describe a mathematical model for any system that has a limited number of conditional states of being.". 

In the example above you have 2 states (i.e. PinLed ON and PinLedOff) and the conditions to stay in that state (i.e. delay) and the condition to change to the next stage. Furthermore, one is able to identify clearly in which state the machine is.

[ - ]
Reply by cprovidentiJuly 27, 2020

I much prefer this (Pedro's) response, and would take it one step further.

A (finite) state machine is a mathematical construct, and as such is represented via mathematical notation (e.g., a state transition matrix or diagram).

What you have shown is C source code that (almost certainly, given the context) implements a state machine that specifies the desired behavior of the LED.

Or if said formal specification of the LED behavior does not exist (i.e., you implemented the code directly), then one way of describing how the code should (or does) operate would be via a state machine.

I mention this to highlight some of the differences between the mathematical representation (i.e., the state machine) and the implementation thereof (the software running on the target hardware). E.g., transitions between states occur instantaneously in the mathematical representation, but this rarely (if ever) is the case in the implementation. Another way to implement said state machine might be on an FPGA (or CPLD), in which case the implementation might be written in VHDL, not C. The state machine itself does not depend on how it's implemented.

[ - ]
Reply by jmford94July 27, 2020

I would say that it is.  The 2 states are LED_LO and LED_HIGH.  Not a very efficient use of CPU cycles, but it gets the job done.  

[ - ]
Reply by waydanJuly 27, 2020

I would argue that this code describes a state machine with the two states you have indicated: LED_OFF and LED_ON.

The transitions between the states are triggered by timeout events, i.e. each delay call.

This example is fairly simple, but if you identify it as a state machine, it might make it easier to map it to a mental model and rewrite it in any number of forms that suit your needs.



[ - ]
Reply by CustomSargeJuly 27, 2020

Well, I suppose at a minimalist view, yes. 

I think of state machines as a set of outputs controlled by a structured set of inputs.

I designed a light controller that has a given state parameter format that defines what the outputs do. Naming the product / mfgr would be poor forum etiquette (but we sell a Lot of them).

An up sized version is pending, it has both fixed state parameters and logical conditional inputs. Both are state machines, since a given parameter set, at evaluation time, sets outputs. Think of a traffic signal with a turn lane that only gives a turn arrow if a sensor loop "sees" a vehicle.

So yes, just as a square is a subset of rectangle.   G.H. <<<)))