On 06/02/17 21:19, Don Y wrote:> 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!Yes, and I didn't spot that "loonie idea" was being considered.> 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.Having architected and implemented soft-realtime telecom billing systems, I can only agree :)> It's just like designing synchronous hardware.Oh, indeed. I like playing a game with people that think there is a difference between hardware and software: get them to try to provide a test to distinguish one from the other. They always fail. It is best played in a pub, with a few pints, after work.
Do you use FSMs or HSMs?
Started by ●February 6, 2017
Reply by ●February 6, 20172017-02-06
Reply by ●February 6, 20172017-02-06
On 2/6/2017 3:12 PM, Tom Gardner wrote:>> It's just like designing synchronous hardware. > > Oh, indeed. > > I like playing a game with people that think > there is a difference between hardware and > software: get them to try to provide a test to > distinguish one from the other. They always fail. > > It is best played in a pub, with a few pints, > after work.My preference is for designing hardware. And, synchronous circuits are hands-down easier to design/debug. So, FSM's are almost /de rigueur/. To me, it's only natural to use the same design techniques when it comes to software. It also makes debugging easier ("things only change on -- FSM -- clock edges" :> ). Some folks opt for *huge* tables that enumerate all inputs for all current_states and declared next_states. Rarely is this necessary (it's often a gross inefficiency -- in space). The big advantage to software FSM implementations is that you can implement all sorts of mechanisms that would be costly or impractical to implement in hardware, at the same level of abstraction. (e.g., specifying a "next_state" of PREVIOUS_STATE!) For newbies, the concept is usually a little unsettling. They're looking for "the code" and, instead, their seeing an abstract description of a machine with smatterings of code around the edges. ("How can you CALL a FSM???" "Why not?!" :> ) But, I've yet to find someone who didn't ultimately embrace the technology; its just too damn intuitive not to!
Reply by ●February 6, 20172017-02-06
On 07/02/17 08:19, Don Y wrote:> 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.Lex is a language for describing a regular expression, which it implements by turning it *into* an FSA. You don't need yacc to parse FP numbers. Such parsers are for handling languages that require unbounded state, not finite state. I'm also enthusiastic in using FSAs where appropriate, but a lot of problems I face require unbounded state. In either case, I tend not to do them long-hand - there are good domain-specific languages to generate the code. Clifford Heath.
Reply by ●February 6, 20172017-02-06
On Monday, February 6, 2017 at 8:56:45 AM UTC-6, QL wrote:> 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]> Anyway, if you are seriously interested in (hierarchical) state machines ]> for embedded real-time systems I would recommend to start with the key ]> concepts: Not entirely enlightened on hierarchical state machines. Gather that the lower level state "inherits" from the higher level state. E.g., unless over-ridden, the lower level state defaults to the actions of the higher level state? Side issue: in communications many states use a timer to have a time-out action, and the methodology/diagrams accommodate this?
Reply by ●February 6, 20172017-02-06
On 2/6/2017 5:52 PM, jim.brakefield@ieee.org wrote:> On Monday, February 6, 2017 at 8:56:45 AM UTC-6, QL wrote: >> 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 > > ]> Anyway, if you are seriously interested in (hierarchical) state machines > ]> for embedded real-time systems I would recommend to start with the key ]> > concepts: > > Not entirely enlightened on hierarchical state machines. Gather that the > lower level state "inherits" from the higher level state. E.g., unless > over-ridden, the lower level state defaults to the actions of the higher > level state? > > Side issue: in communications many states use a timer to have a time-out > action, and the methodology/diagrams accommodate this?In my implementations, you can "call" (bad choice of terms but it is something to which a programmer can easily relate!) a "state table" as if it had been inserted into the current state table, "in line" (though it doesn't incur the expected space penalty). [likewise, common data entry FSMs "shared" in a larger UI FSM] So, you take these common things and wrap them in a "pseudo state (table)" and then reference (CALL) it from every state in which it should apply (which might not be ALL states!) E.g., I will embed power fail handling in such a pseudo table and add it to every state that CAN support power fail handling (some might not be designed to tolerate that exception). Likewise, power *recovery* in the same pseudo table (each maintaining a separate FSM orthogonal to the FSM in question and interacting with it in the applicable "transition routines")
Reply by ●February 6, 20172017-02-06
pozz <pozzugno@gmail.com> writes:> 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 looked up HSM in Wikipedia and see it's UML-speak for nested state machines. I don't see exactly how it applies to the calculator example but I've preferred to use multiple communicating processes with the appearance blocking operations, rather than explicit state machines. Of course you can simulate that with an event dispatcher and coroutines, or alternatively do it with an RTOS and tasks. I suppose there is overhead compared to a FSM or HSM approach, but on the big processors I use, it hasn't been an issue.
Reply by ●February 7, 20172017-02-07
On 2/6/2017 7:35 PM, Paul Rubin wrote:> pozz <pozzugno@gmail.com> writes: >> 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 looked up HSM in Wikipedia and see it's UML-speak for nested state > machines. I don't see exactly how it applies to the calculator example > but I've preferred to use multiple communicating processes with the > appearance blocking operations, rather than explicit state machines. Of > course you can simulate that with an event dispatcher and coroutines, or > alternatively do it with an RTOS and tasks. I suppose there is overhead > compared to a FSM or HSM approach, but on the big processors I use, it > hasn't been an issue.IME its not the space/time efficiency but, rather, the conciseness of expression. Designing/debugging an algorithm ("machine") with a state diagram is *so* much easier to sort out what is happening -- and what ISN'T, that should! There are tools that can take diagramatic representations and convert them to code. But, they make assumptions about the implementation that constrain your solution space. Using the design concept without committing to a particular implementation style is where the biggest wins lie. [And, there are "mechanical" ways that you can reduce the complexity of state machines once you've settled on one that works] However, just approaching the problem in a way that lends itself to this sort of visualization makes a huge difference vs. trying to trace paths through code (in potentially different process containers or on different physical processors). It also lends itself to having others (Manglement) review the (planned) behavior without requiring them to understand the latest implementation language, modeling language, etc.: "What if a power fail event is signalled while I'm OVER HERE? How is it handled if the user stalls his interaction at this point -- which doesn't RECOGNIZE the event until after he has done X, Y or Z?"
Reply by ●February 7, 20172017-02-07
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? >It all depends. This being said, I do like state machines, mainly because they lend well to comprehensive unit/regression test suites and have some advantage in coverage measurement. Hierarchical may or may not help that much.> 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 have implemented them in multiple languages and programing paradigms. -- Les Cargill
Reply by ●February 7, 20172017-02-07
jim.brakefield@ieee.org wrote:> On Monday, February 6, 2017 at 8:56:45 AM UTC-6, QL wrote: >> 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 > > ]> Anyway, if you are seriously interested in (hierarchical) state machines > ]> for embedded real-time systems I would recommend to start with the key > ]> concepts: > > Not entirely enlightened on hierarchical state machines. > Gather that the lower level state "inherits" from the higher level state.A state of the higher level state can be another state machine.> E.g., unless over-ridden, the lower level state defaults to the actions of the higher level state? >Probably, but events may resolve to the higher level state machine. I am biased by the way ObjecTime/Rational did this.> Side issue: in communications many states use a timer to have a time-out action, and the methodology/diagrams accommodate this? >To my knowledge they all do. -- Les Cargill
Reply by ●February 7, 20172017-02-07
Clifford Heath wrote:> On 07/02/17 08:19, Don Y wrote: >> 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. > > Lex is a language for describing a regular expression, > which it implements by turning it *into* an FSA. > > You don't need yacc to parse FP numbers. Such parsers > are for handling languages that require unbounded state, > not finite state. >Just to be pedantic :), it's deterministic vs. non deterministic FA. Deterministic FA are equivalent to regular expressions. NFA are not, and very often, NFA are what we use for program control flow.> I'm also enthusiastic in using FSAs where appropriate, > but a lot of problems I face require unbounded state.This is where NFA shine - they're less formal than DFA.> In either case, I tend not to do them long-hand - there > are good domain-specific languages to generate the code. > > Clifford Heath.-- Les Cargill
