I often encounter many problems when I have to implement a "behaviour" in a microcontrollor. For example, I have some analog/digital inputs and some user commands. Based on that, the logic should set some outputs (digital or analog). Most of the time you (the developer) must understand what is the good behaviour of the machine, because noone is able to describe it in a good way. I usually heard the sentence: when the user presses the ON button, you switch on the engine. After some short implementation, you understand that the engine should be on only if the interlock input is closed. And so on... I think the best method to describe a machine behaviour is a state-machine, mainly a hierarchically state-machine (HSM). Do you agree? My post here is to understand if you really use HSMs to describe the beahviour of the system you are coding and how do you implement them in C or C++ (or whatever).
Do you use FSMs or HSMs?
Started by ●February 6, 2017
Reply by ●February 6, 20172017-02-06
On 2/6/2017 2:43 AM, pozz wrote:> I often encounter many problems when I have to implement a "behaviour" in a > microcontrollor. For example, I have some analog/digital inputs and some user > commands. Based on that, the logic should set some outputs (digital or analog). > > Most of the time you (the developer) must understand what is the good behaviour > of the machine, because noone is able to describe it in a good way. I usually > heard the sentence: when the user presses the ON button, you switch on the engine. > After some short implementation, you understand that the engine should be on > only if the interlock input is closed. > And so on... > > I think the best method to describe a machine behaviour is a state-machine, > mainly a hierarchically state-machine (HSM). Do you agree? > > My post here is to understand if you really use HSMs to describe the beahviour > of the system you are coding and how do you implement them in C or C++ (or > whatever).*Always*. They act as a sort of "application specific language" to codify behavior in a high level form. I always implement them with an interpreter that takes a "current state" and some number of "input variables", along with a set of tables defining the transitions from each potential "current state" to other "next states" (along with "action routines" to be executed when the transition is made. The manner in which the tables are encode varies based on what I expect the needs of the machine being modeled to be. For example, to accept a decimal value from a "digit source" (which could be a keypad or a character stream received from a UART) I might code a little machine: STATE IDLE ; prompt and default value are displayed, here, and the FIRST digit is expected CASE "CLEAR" GOTO IDLE EXECUTING no_op() CASE '0' GOTO ENTRY EXECUTING first_digit() CASE '1' GOTO ENTRY EXECUTING first_digit() ... CASE '9' GOTO ENTRY EXECUTING first_digit() CASE "ENTER" GOTO CHECK EXECUTING completed() ORELSE GOTO same EXECUTING complain() STATE ENTRY ; first digit has been entered, prompt and default value have been removed CASE "CLEAR" GOTO IDLE EXECUTING restore_default() CASE '0' GoTO DIGITS EXECUTING accept_digit() CASE '1' GOTO DIGITS EXECUTING accept_digit() ... no_op() return first_digit() accumulator() = digit; remove_prompt(); printf("%s: %d", shortened_prompt, accumulator) return accept_digit() accumlator = 10 * accumulator + digit; printf("%s: %d", shortened_prompt, accumulator) return complain() beep() return restore_default() accumulator = default_value; printf("%s: %d", long_prompt, accumulator); return ... Obviously, another encoding might support a syntax like: STATE ENTRY ; first digit has been entered, prompt and default value have been removed CASE "CLEAR" GOTO IDLE EXECUTING no_op() CASE '0' THRU '9' GOTO ENTRY EXECUTING first_digit() ... CASE "ENTER" GOTO CHECK EXECUTING completed() ORELSE GOTO same EXECUTING complain() How you acquire "inputs" is also variable. You can force each input to appear in a particular "variable" that the FSM interpreter polls (different variables for different FSM's -- one interpreteer can handle multiple FSM's). I prefer having a LIST of "input variables" that the FSM interpreter examines sequentially. Individual "tasks" can then maintain their own "variables" without having to coordinate a SHARED variable among many competing tasks. E.g., the "keypad" task can have a "key_detected" variable that is LISTED in those variables consumed by the above FSM. The example suggests this variable would be a char -- though there is no requirement that it be so. The task responsible for polling and debouncing keystrokes from the keypad can watch the "key_detected" variable and, any time it is found to be "empty" (NUL, by convention), can place the next enqueued keystroke into that variable. It can then continue scanning/debouncing the keypad while queuing subsequent keystrokes until the "key_detected" variable is "not busy". The FSM interpreter can then, by convention, CLEAR any variable that it has acted upon to remove the stimulus from subsequent FSM iterations AND "signal" the producer task that the consumer (the FSM!) has processed the previous "event/datum" and is ready for another FROM THAT DATA SOURCE. [This opens up lots of hacks -- like allowing a stimulus to be propagated to the next state -- by NOT clearing it!] Note that you can also deviate from conventional FSM implementations by supporting "special" next state codes (e.g., "same" refers to the *current* state -- don't transition to another state, just stay here!) The number of variations in syntax and mechanisms is far too many to enumerate here -- as are the encodings for the "state tables" illustrated above. But, the point is, you can cleanly codify the behavior of an algorithm without resorting to lots of spaghetti code and conditionals.
Reply by ●February 6, 20172017-02-06
On Monday, February 6, 2017 at 4:43:26 AM UTC-5, pozz wrote:> My post here is to understand if you really use HSMs to describe the > beahviour of the system you are coding and how do you implement them in > C or C++ (or whatever).I often use FSMs but not formal HSMs. Make sure you read Miro Samek's "Practical Statecharts in C/C++" Never found a framework that fit nicely with my projects though I read about lots of them, so seems like I keep redoing this. Probably I should look at Miro Samek's latest open source offerings... Let us know what you end up using this round, Best Regards, Dave
Reply by ●February 6, 20172017-02-06
Let me start with the full disclosure: I'm the author of the book "Practical UML Statecharts in C/C++, 2nd Edition" and I run a company called Quantum Leaps that makes open-source state machine software frameworks and a free state machine modeling tool. The company website is: http://www.state-machine.com So, yes, I also strongly believe that hierarchical state machines (a.k.a. UML statecharts) combined with event-driven programming are the best way to go when it comes to developing real-time embedded software. From my two decades of experience, however, I see that the biggest obstacle in adopting state machines is the required paradigm shift from sequential programming based on blocking (like blocking on a semaphore or a time delay in a traditional RTOS or a "superloop") and the event-driven programming based on run-to-completion event processing without blocking (like in a state machine). Anyway, if you are seriously interested in (hierarchical) state machines for embedded real-time systems I would recommend to start with the key concepts: http://www.state-machine.com/doc/concepts.html You might also wish to try the free state machine modeling tool called QM, which allows you to draw hierarchical state machine diagrams and automatically generate production-quality C or C++ code from them: http://www.state-machine.com/qm Miro Samek www.state-machine.com --------------------------------------- Posted through http://www.EmbeddedRelated.com
Reply by ●February 6, 20172017-02-06
> I think the best method to describe a machine behaviour is a > state-machine, mainly a hierarchically state-machine (HSM). Do you agree?FSM models are my #1 considered method for documenting required behavior. But it's not always the best way. Some requirements sets just don't lend themselves well to FSM diagrams. I find that sometimes I'll sketch a FSM and then find out it's just too simple or too linear. ON the flip side, I've had project for which I'd have an extremely simple FSM documented and later it's starts to get elaborate and useful as new requirements emerge. JJS
Reply by ●February 6, 20172017-02-06
On 06/02/17 17:17, John Speth wrote:>> I think the best method to describe a machine behaviour is a >> state-machine, mainly a hierarchically state-machine (HSM). Do you agree? > > FSM models are my #1 considered method for documenting required behavior. But > it's not always the best way. Some requirements sets just don't lend themselves > well to FSM diagrams.Precisely. A good engineer knows which tools to use/avoid for each job.> I find that sometimes I'll sketch a FSM and then find out > it's just too simple or too linear. ON the flip side, I've had project for which > I'd have an extremely simple FSM documented and later it's starts to get > elaborate and useful as new requirements emerge.Precisely. A large part of engineering is being able to demonstrate which part of an design implements each part of the specification. A good implementation of an FSM enables you to easily see exactly what will happen when any event occurs in any state. That can be very difficult with if-then-else clauses.
Reply by ●February 6, 20172017-02-06
On 2/6/2017 11:03 AM, Tom Gardner wrote:>> I find that sometimes I'll sketch a FSM and then find out >> it's just too simple or too linear. ON the flip side, I've had project for which >> I'd have an extremely simple FSM documented and later it's starts to get >> elaborate and useful as new requirements emerge. > > Precisely. > > A large part of engineering is being able to > demonstrate which part of an design implements > each part of the specification. > > A good implementation of an FSM enables you > to easily see exactly what will happen when > any event occurs in any state. That can be very > difficult with if-then-else clauses.Exactly. IME, they are excellent for representing UI actions along with other formal "protocols". They allow you to verify by inspection that all possibilities are addressed and addressed in the manner intended -- without having to count nesting levels of conditionals, etc. "Will this 'if' cover this condition in ALL states? Or, does it only apply to some subset of the states, based on where it is syntactically anchored?" I'd *not* use one to implement a floating point package...
Reply by ●February 6, 20172017-02-06
On 2/6/2017 7:56 AM, QL wrote:> So, yes, I also strongly believe that hierarchical state machines (a.k.a. > UML statecharts) combined with event-driven programming are the best way > to go when it comes to developing real-time embedded software. > > From my two decades of experience, however, I see that the biggest > obstacle in adopting state machines is the required paradigm shift from > sequential programming based on blocking (like blocking on a semaphore or > a time delay in a traditional RTOS or a "superloop") and the event-driven > programming based on run-to-completion event processing without blocking > (like in a state machine).The two aren't mutually exclusive. So, silly to limit yourself to that mindset. And, a "machine" doesn't have to be a cohesive, monolithic block of code easily recognizable as "something special". It can, instead, be coded "in-line" if the environment supports seemless redefinition of program (task) entry points; the "current state" is then effectively encoded in the "saved entry point" which is explicitly changed each time you explicitly command it (yield()/reschedule()) In this way, you can undertake lengthy operations without resorting to a preemptive MTOS/RTOS to ensure you aren't monopolizing the processor as well as doing the same in a fully preemptive environment.
Reply by ●February 6, 20172017-02-06
On 06/02/17 18:56, Don Y wrote:> On 2/6/2017 11:03 AM, Tom Gardner wrote: >>> I find that sometimes I'll sketch a FSM and then find out >>> it's just too simple or too linear. ON the flip side, I've had project for which >>> I'd have an extremely simple FSM documented and later it's starts to get >>> elaborate and useful as new requirements emerge. >> >> Precisely. >> >> A large part of engineering is being able to >> demonstrate which part of an design implements >> each part of the specification. >> >> A good implementation of an FSM enables you >> to easily see exactly what will happen when >> any event occurs in any state. That can be very >> difficult with if-then-else clauses. > > Exactly. IME, they are excellent for representing UI actions > along with other formal "protocols". They allow you to verify > by inspection that all possibilities are addressed and > addressed in the manner intended -- without having to > count nesting levels of conditionals, etc. > "Will this 'if' cover this condition in ALL states? Or, > does it only apply to some subset of the states, based on > where it is syntactically anchored?" > > I'd *not* use one to implement a floating point package...Yes, but... They are very neat way of implementing parsing an ascii string and turning it into a floating point number. Each input character is an "event", and the states are things like "skipping leading whitespace, parsing before decimal point" etc. An "E" transitions from "parsing before decimal point" or parsing after decimal point" to "parsing exponent", and transitions to "error" elsewhere. E&OE, of course :)
Reply by ●February 6, 20172017-02-06
On 2/6/2017 1:34 PM, Tom Gardner wrote:> On 06/02/17 18:56, Don Y wrote: >> On 2/6/2017 11:03 AM, Tom Gardner wrote: >>>> I find that sometimes I'll sketch a FSM and then find out >>>> it's just too simple or too linear. ON the flip side, I've had project for >>>> which >>>> I'd have an extremely simple FSM documented and later it's starts to get >>>> elaborate and useful as new requirements emerge. >>> >>> Precisely. >>> >>> A large part of engineering is being able to >>> demonstrate which part of an design implements >>> each part of the specification. >>> >>> A good implementation of an FSM enables you >>> to easily see exactly what will happen when >>> any event occurs in any state. That can be very >>> difficult with if-then-else clauses. >> >> Exactly. IME, they are excellent for representing UI actions >> along with other formal "protocols". They allow you to verify >> by inspection that all possibilities are addressed and >> addressed in the manner intended -- without having to >> count nesting levels of conditionals, etc. >> "Will this 'if' cover this condition in ALL states? Or, >> does it only apply to some subset of the states, based on >> where it is syntactically anchored?" >> >> I'd *not* use one to implement a floating point package... > > Yes, but... > > They are very neat way of implementing parsing an ascii > string and turning it into a floating point number.Different problem -- and one that could be "automated" with a simple grammar/lex/yacc. You'd find it hard to apply it to performing multiplications, divisions, etc. in a way that was anywhere near as efficient as the underlying instruction set! [An FSM effectively gives you a new "language" layered atop the native instruction set via any intermediate languages]> Each input character is an "event", and the states are > things like "skipping leading whitespace, parsing > before decimal point" etc. An "E" transitions from > "parsing before decimal point" or parsing after > decimal point" to "parsing exponent", and transitions > to "error" elsewhere. > > E&OE, of course :)In a similar vein, using it to parse "messages" in some arbitrary syntax. There, it makes it relatively easy to add new "message options" without having to rewrite a bunch of spaghetti code. *Or*, buffer an entire message before it can be parsed. I've often used it to decode barcode labels at higher levels. I.e., use procedural mechanisms to process the "raw video" into "characters"; then a FSM to decide which sequences of characters are representative of valid messages. In my implementations, an "action routine" (transition routine) can perform a test on the data and then simulate a GO/NOGO event that is the *only* "event" processed in the succeeding state. It can then redirect the machine to the correct next state based on some (possibly complex) computation performed on "embedded" data (e.g., verifying a checksum is not something that you would encode into the normal state transitions; instead, compute it in the CHECK state and then act on that GO/NOGO event in the DISPATCH state that immediately follows) At the same time, input from keypads, mains power detectors, UART character streams, etc. can continue, being buffered until the machine opts to examine them, again (based on the significant events defined for THIS particular state). Allowing inputs to simultaneously arrive from multiple sources WITHOUT enforcing an ordering on them external to the FSM lets you cascade machines, have machines talking to each other while operating concurrently, implement co-routine machines, etc. It's just like designing synchronous hardware.
