Do you use FSMs or HSMs?

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.
>


It's always dangerous to generalize, but anything I can easily
make non-blocking I will.

Some FSM oriented systems use an "actor" model where actors can be 
threads or even pseudothreads[1], communicating with sequential
message passing.

[1] looks like a thread, but may not map to an O/S thread.

-- 
Les Cargill

Les Cargill <lcargill99@comcast.com> writes:
> It's always dangerous to generalize, but anything I can easily
> make non-blocking I will.

Ok, you prefer to handle the event dispatch manually, with callbacks or
a switch around the protocol state.  I know some people find that
intuitive but I've never gotten the hang of it.

> Some FSM oriented systems use an "actor" model where actors can be
> threads or even pseudothreads[1], communicating with sequential
> message passing.

Yes, that's what I'm used to doing under the covers.  Each thread waits
for some action while appearing to block, and moves forward when the
action occurs.  Erlang is designed for programming in this style and
some very complex, highly reliable systems (phone switches) have been
programmed in it.

On Mon, 6 Feb 2017 23:36:01 -0600, Les Cargill
<lcargill99@comcast.com> wrote:

>Clifford Heath wrote:
>
>> 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.

Every NFA is equivalent to some DFA, and either can be mechanically
translated into the other.  However the DFA version, in general, will
have many more states: in the (theoretical) worst case, equal to the
size of the power set of states in the NFA.

But such explosive growth is very rare.  In practice, the majority of
elements in the power set of NFA states will represent either unwanted
or redundant operations.


>> 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.

Not "less formal" per se if you are concerned about correctness.
However, in general, NFA are easier to specify and to understand.  

Any particular state of the equivalent DFA may be simultaneously
representing multiple states of the NFA.  Consequently, the
transition/acceptance rules in the DFA may be extremely complex -
perhaps even incomprehensible to mere mortals.


George

On 07/02/17 16:36, Les Cargill wrote:
> 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 didn't mention determinism. Why did you?
I said "FSA", meaning Finite State Automaton.

>> 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.

"FA" means Finite-state Automaton to me. What does it mean to you?

It certainly does not mean "non-finite-state", which is what
you need to process irregular grammars (things Yacc can do that
a regular expression cannot). That's what I mean by "unbounded state".

Clifford Heath <no.spam@please.net> writes:
>> This is where NFA shine - they're less formal than DFA.
> "FA" means Finite-state Automaton to me. What does it mean to you?

DFA = deterministic finite automaton.  For any node and symbol, there's
at most one edge labelled with that symbol coming out of the node.
E.g. if you are in state 15 and the next input symbol is X, go to state
37.

NFA = non-deterministic finite automaton.  Nodes can have more than one
outgoing edge labelled with the same symbol.  I.e. if the next input
character is X, go to states 23 and 94 at the same time.  You can
simulate it by keeping track of which subset of the states you might be
in, or else convert it to a DFA whose nodes represent subsets of the
nodes of the original NFA.

This is all classical compiler stuff.  There's a chapter about it in the
Dragon Book if anyone still reads that.

https://en.wikipedia.org/wiki/Dragon_Book

Il 06/02/2017 15:56, QL ha scritto:
> 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

Yes, I know your book and your QP/C implementation, mainly your QEP 
processor (the implementation of state machines).

I think it's the only well-designed HSM implementation in C.


> 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).

Yes, I agree with you. I always try to reduce all my project to a fully 
event-driven machine, but it's very difficult.

Many parts of the project can be represented and implemented in a simple 
and efficient way with an HSM. However for me it's difficult to 
implement other parts with an HSM with an event-driven only paradigm.

Example. If the engine must be off when an interlock is open, I put the 
following code in the superloop:
    if (interlock_is_open()) engine_off();
In this way I am *sure* this happens. With an event-driven approach, I 
have to create two different signals: INTERLOCK_OPEN, INTERLOCK_CLOSED. 
I have to be sure the INTERLOCK_OPEN signal is processed and lead to the 
switching off of the engine.

I usually tend to avoid blocking tasks. When I face it, I try to split 
it in sub-tasks... a state-machine. However it's difficult for 
communication protocols (I2C, RS485, ...) and/or third-parties libraries 
(GUI).


> 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

On 07/02/17 20:30, Paul Rubin wrote:
> Clifford Heath <no.spam@please.net> writes:
>>> This is where NFA shine - they're less formal than DFA.
>> "FA" means Finite-state Automaton to me. What does it mean to you?
>
> DFA = deterministic finite automaton.

You missed the point again. Determinism is not the point.

"Finite" in "finite state" is the point. You cannot parse
non-regular grammars using finite state. That's why we
have yacc as well as lex.

> "Finite" in "finite state" is the point. You cannot parse non-regular
> grammars using finite state. That's why we have yacc as well as lex.

I don't see what you're getting at.  You asked what the two
abbreviations meant and I explained.  Yes you need a stack to do what
yacc does, etc.

On 07/02/17 21:46, Paul Rubin wrote:
>> "Finite" in "finite state" is the point. You cannot parse non-regular
>> grammars using finite state. That's why we have yacc as well as lex.
>
> I don't see what you're getting at.  You asked what the two
> abbreviations meant

No, I didn't, go back and check. I asked Les C:

"FA" means Finite-state Automaton to me. What does it mean to you?

I specifically did not mention D nor N, other than to point out
that Les describing determinism was not relevant to my point
about the limitations of *finite* state machines of any form.
Relevant to me, because as I said "a lot of problems I face
require unbounded state." An NFA doesn't help with that.

> and I explained.

Thank you. It wasn't necessary, but thanks anyway.

Clifford Heath.

On 02/06/2017 05:12 PM, Tom Gardner wrote:
> 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.
>
>
Discharge a big cap into it.  If it still works, it's software. ;)

Cheers

Phil Hobbs

-- 
Dr Philip C D Hobbs
Principal Consultant
ElectroOptical Innovations LLC
Optics, Electro-optics, Photonics, Analog Electronics

160 North State Road #203
Briarcliff Manor NY 10510

hobbs at electrooptical dot net
http://electrooptical.net