Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch.embedded > #25771 > unrolled thread

Do you use FSMs or HSMs?

Back to article view | Back to comp.arch.embedded

Contents

  Do you use FSMs or HSMs? pozz <pozzugno@gmail.com> - 2017-02-06 10:43 +0100
    Re: Do you use FSMs or HSMs? Don Y <blockedofcourse@foo.invalid> - 2017-02-06 03:20 -0700
    Re: Do you use FSMs or HSMs? Dave Nadler <drn@nadler.com> - 2017-02-06 06:38 -0800
    Re: Do you use FSMs or HSMs? "QL" <80499@EmbeddedRelated> - 2017-02-06 08:56 -0600
      Re: Do you use FSMs or HSMs? Don Y <blockedofcourse@foo.invalid> - 2017-02-06 12:13 -0700
      Re: Do you use FSMs or HSMs? jim.brakefield@ieee.org - 2017-02-06 16:52 -0800
        Re: Do you use FSMs or HSMs? Don Y <blockedofcourse@foo.invalid> - 2017-02-06 18:11 -0700
        Re: Do you use FSMs or HSMs? Les Cargill <lcargill99@comcast.com> - 2017-02-06 23:32 -0600
      Re: Do you use FSMs or HSMs? pozz <pozzugno@gmail.com> - 2017-02-07 10:39 +0100
    Re: Do you use FSMs or HSMs? John Speth <johnspeth@yahoo.com> - 2017-02-06 09:17 -0800
      Re: Do you use FSMs or HSMs? Tom Gardner <spamjunk@blueyonder.co.uk> - 2017-02-06 18:03 +0000
        Re: Do you use FSMs or HSMs? Don Y <blockedofcourse@foo.invalid> - 2017-02-06 11:56 -0700
          Re: Do you use FSMs or HSMs? Tom Gardner <spamjunk@blueyonder.co.uk> - 2017-02-06 20:34 +0000
            Re: Do you use FSMs or HSMs? Don Y <blockedofcourse@foo.invalid> - 2017-02-06 14:19 -0700
              Re: Do you use FSMs or HSMs? Tom Gardner <spamjunk@blueyonder.co.uk> - 2017-02-06 22:12 +0000
                Re: Do you use FSMs or HSMs? Don Y <blockedofcourse@foo.invalid> - 2017-02-06 15:29 -0700
                Re: Do you use FSMs or HSMs? Phil Hobbs <pcdhSpamMeSenseless@electrooptical.net> - 2017-02-08 12:15 -0500
                  Re: Do you use FSMs or HSMs? Tom Gardner <spamjunk@blueyonder.co.uk> - 2017-02-08 23:52 +0000
                    Re: Do you use FSMs or HSMs? Phil Hobbs <pcdhSpamMeSenseless@electrooptical.net> - 2017-02-08 19:59 -0500
                Re: Do you use FSMs or HSMs? Steve Watt <steve.removethis@Watt.COM> - 2017-02-17 00:30 +0000
                  Re: Do you use FSMs or HSMs? Tom Gardner <spamjunk@blueyonder.co.uk> - 2017-02-17 00:44 +0000
              Re: Do you use FSMs or HSMs? Clifford Heath <no.spam@please.net> - 2017-02-07 10:12 +1100
                Re: Do you use FSMs or HSMs? Les Cargill <lcargill99@comcast.com> - 2017-02-06 23:36 -0600
                  Re: Do you use FSMs or HSMs? George Neuner <gneuner2@comcast.net> - 2017-02-07 03:15 -0500
                    Re: Do you use FSMs or HSMs? Les Cargill <lcargill99@comcast.com> - 2017-02-10 17:41 -0600
                  Re: Do you use FSMs or HSMs? Clifford Heath <no.spam@please.net> - 2017-02-07 19:56 +1100
                    Re: Do you use FSMs or HSMs? Paul Rubin <no.email@nospam.invalid> - 2017-02-07 01:30 -0800
                      Re: Do you use FSMs or HSMs? Clifford Heath <no.spam@please.net> - 2017-02-07 20:42 +1100
                        Re: Do you use FSMs or HSMs? Paul Rubin <no.email@nospam.invalid> - 2017-02-07 02:46 -0800
                          Re: Do you use FSMs or HSMs? Clifford Heath <no.spam@please.net> - 2017-02-08 00:27 +1100
    Re: Do you use FSMs or HSMs? Paul Rubin <no.email@nospam.invalid> - 2017-02-06 18:35 -0800
      Re: Do you use FSMs or HSMs? Don Y <blockedofcourse@foo.invalid> - 2017-02-06 21:50 -0700
      Re: Do you use FSMs or HSMs? Les Cargill <lcargill99@comcast.com> - 2017-02-06 23:39 -0600
        Re: Do you use FSMs or HSMs? Paul Rubin <no.email@nospam.invalid> - 2017-02-06 23:20 -0800
          Re: Do you use FSMs or HSMs? Les Cargill <lcargill99@comcast.com> - 2017-02-10 17:47 -0600
            Re: Do you use FSMs or HSMs? Paul Rubin <no.email@nospam.invalid> - 2017-02-10 16:11 -0800
              Re: Do you use FSMs or HSMs? Les Cargill <lcargill99@comcast.com> - 2017-02-11 15:43 -0600
    Re: Do you use FSMs or HSMs? Les Cargill <lcargill99@comcast.com> - 2017-02-06 23:24 -0600

Page 1 of 2  [1] 2  Next page →

#25771 — Do you use FSMs or HSMs?

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

[toc] | [next] | [standalone]

#25774

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.

[toc] | [prev] | [next] | [standalone]

#25776

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

[toc] | [prev] | [next] | [standalone]

#25777

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

[toc] | [prev] | [next] | [standalone]

#25781

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.

[toc] | [prev] | [next] | [standalone]

#25787

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?

[toc] | [prev] | [next] | [standalone]

#25789

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

[toc] | [prev] | [next] | [standalone]

#25793

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

[toc] | [prev] | [next] | [standalone]

#25800

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

[toc] | [prev] | [next] | [standalone]

#25778

> 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

[toc] | [prev] | [next] | [standalone]

#25779

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.

[toc] | [prev] | [next] | [standalone]

#25780

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

[toc] | [prev] | [next] | [standalone]

#25782

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

[toc] | [prev] | [next] | [standalone]

#25783

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.

[toc] | [prev] | [next] | [standalone]

#25784

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.

[toc] | [prev] | [next] | [standalone]

#25785

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!

[toc] | [prev] | [next] | [standalone]

#25804

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

[toc] | [prev] | [next] | [standalone]

#25806

On 08/02/17 17:15, Phil Hobbs wrote:
> 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. ;)

Thus ruling out FPGAs :)

Besides, if it is software, how could you
be sure it worked before the discharge :)

[toc] | [prev] | [next] | [standalone]

#25807

On 02/08/2017 06:52 PM, Tom Gardner wrote:
<sniiiiip>
> Besides, if it is software, how could you
> be sure it worked before the discharge :)
>
Curses, foiled again. ;)

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

[toc] | [prev] | [next] | [standalone]

#25834

In article <Xw6mA.154283$6N1.4638@fx09.am4>,
Tom Gardner  <spamjunk@blueyonder.co.uk> wrote:
>On 06/02/17 21:19, Don Y 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.

"I want to make these 15 changes.  Can I have the changed model working
tomorow and deployable next week?"

OK, FPGAs have a fair shot at it, but most other hardware doesn't.

Mind, the definition of "working" when it comes to software is quite
notably different than it is for hardware.  Nothing quite like
a fresh tapeout because the verification team didn't get enough time.
-- 
Steve Watt KD6GGD  PP-ASEL-IA          ICBM: 121W 56' 57.5" / 37N 20' 15.3"
 Internet: steve @ Watt.COM                      Whois: SW32-ARIN
   Free time?  There's no such thing.  It just comes in varying prices...

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.arch.embedded

csiph-web