Text on FSM

On 3/10/2023 4:48 AM, Robert Roland wrote:
> On Fri, 10 Mar 2023 09:54:23 +0100, pozz <pozzugno@gmail.com> wrote:
> 
>> There will be a time when the programmer would simply draw one or more
>> state-machines and click a button to generate the full working code in
>> whatever language.
> 
> When I went to school, 30 or so years ago, we did have such a program.
> I am not able to remember its name, though.

You can use regex "compilers" to deal with DFAs.

The problem with all of these approaches is they add another "tool" to
the development process -- and another opportunity for the developer
(who only uses the tool for a *portion* of a project) to make mistakes
in its application.  The more capable and expressive the tool, the
more knowledge is required of the developer to exploit its capabilities.

[E.g., if you had to construct an arbitrary regex, could you do so
with the knowledge you have committed to memory?  Would a reference
answer all of the questions you *might* have about your particular
pattern?]

Instead (IMO), you want something that lets a developer use a technology
without reliance on a particular tool (that may not be well-supported
or may have latent bugs that haven't yet been tickled).

As such, understanding the technique is more important than finding a tool
that may )or may not) address your needs.  ("I want to write in Eiffel.
Does your tool output Eiffel source?"  Next week it may be some other
/langue du jour/)

On 3/10/2023 9:39 AM, Don Y wrote:

> The problem with all of these approaches is they add another "tool" to
> the development process -- and another opportunity for the developer
> (who only uses the tool for a *portion* of a project) to make mistakes
> in its application.  The more capable and expressive the tool, the
> more knowledge is required of the developer to exploit its capabilities.
> 
> [E.g., if you had to construct an arbitrary regex, could you do so
> with the knowledge you have committed to memory?  Would a reference
> answer all of the questions you *might* have about your particular
> pattern?]

By way of example, what does this:
     ^0*(1(00)*10*|10(00)*1(00)*(11)*0(00)*10*)*0*$
do over the set of binary integers?

[assuming *I* haven't botched it!  I should test it...]

Hello again!

Thank you all very much for your valuable inputs! I have A LOT of reading to do!

I'm not a professional developer, like most of you (I guess). I'm just a "gizmo" builder, serving mainly my own research and my colleagues. I don't have access to professional development tools. My background is in physics, although I took a few electronics courses in college. I took courses on embedded systems, usually called "microprocessor in physics" and the like, but the emphasis of these courses tended to be on the digital part and not so much on the computational aspects of the thing. That is why I usually get lost on the jargon of computer science and know very little of data structures and things like that..... 

My first contact with FSM was many years ago when I was finishing my PhD. I had to implement a FSM on a FPGA and, of course, I was late, so I pick an example somewhere and just implemented, without really knowing what I was doing....

Now I would like to finally understand a little better how these things work.

Also, the sort of things that I build, usually have some type of "controller" in it, and usually talk to a PC via serial interface. This, it seems to me, could to be well modeled by a FSM. I understand that this representation might bring additional issues, as it was mentioned by Don Y, but my main goal here is to go one step further from the clumsy programming that I've been doing for the past few years into a bit more formal representation of the problems.

I also have some questions about synchronization of several FSM, but this is a subject for a feature post.

Cheers,
jmariano    

On Friday, March 10, 2023 at 11:39:57 AM UTC-5, Don Y wrote:
> On 3/10/2023 4:48 AM, Robert Roland wrote: 
> > On Fri, 10 Mar 2023 09:54:23 +0100, pozz <pozz...@gmail.com> wrote: 
> > 
> >> There will be a time when the programmer would simply draw one or more 
> >> state-machines and click a button to generate the full working code in 
> >> whatever language. 
> > 
> > When I went to school, 30 or so years ago, we did have such a program. 
> > I am not able to remember its name, though.
> You can use regex "compilers" to deal with DFAs. 
> 
> The problem with all of these approaches is they add another "tool" to 
> the development process -- and another opportunity for the developer 
> (who only uses the tool for a *portion* of a project) to make mistakes 
> in its application. The more capable and expressive the tool, the 
> more knowledge is required of the developer to exploit its capabilities. 

While you're last statement is true, I do not think it is a valid argument against
adding another tool to the development process. In a work (not hobby)
environment, I expect good management and teams to make considered
choices about what tools to apply. If a tool is feature rich and well documented,
then the knowledge should be available (either in you head or in the manual)
to make the job easier.

> 
> [E.g., if you had to construct an arbitrary regex, could you do so 
> with the knowledge you have committed to memory? Would a reference 
> answer all of the questions you *might* have about your particular 
> pattern?] 

Yes.
When I have done a lot of regex work I kept a quick reference card handy.
> 
> Instead (IMO), you want something that lets a developer use a technology 
> without reliance on a particular tool (that may not be well-supported 
> or may have latent bugs that haven't yet been tickled). 

Being tool agnostic is an ideal goal. In a practice, you must pick some
specific tools to get the work done within schedule, budget, and quality constraints.

If you want portability of design then that should be an explicit fourth constraint.
Most projects select tools with the additional LONG TERM constraint of
support throughout the life of the product or product line.
> 
> As such, understanding the technique is more important than finding a tool 
> that may )or may not) address your needs. ("I want to write in Eiffel. 
> Does your tool output Eiffel source?" Next week it may be some other 
> /langue du jour/)

Exactly why an abstracting tool that is more focused on the design is better than
a specific tool.

State machine design tools are a good example. With a graphic design tool,
it is much easier to spot missing states or incorrect transitions. It can be
clear enough that even end users can understand and point out flaws or
enhancements. I don't think the particular output language is the point here.

BTW, lots of your earlier comments match closely to what I would have posted.
This one just struck me are being a little too idealistic.

Ed

On 3/10/2023 11:10 AM, Ed Prochak wrote:
>> The problem with all of these approaches is they add another "tool" to
>> the development process -- and another opportunity for the developer
>> (who only uses the tool for a *portion* of a project) to make mistakes
>> in its application. The more capable and expressive the tool, the
>> more knowledge is required of the developer to exploit its capabilities.
> 
> While you're last statement is true, I do not think it is a valid argument against
> adding another tool to the development process. In a work (not hobby)
> environment, I expect good management and teams to make considered
> choices about what tools to apply. If a tool is feature rich and well documented,
> then the knowledge should be available (either in you head or in the manual)
> to make the job easier.

You have to decide if the effort to learn (and remain "current")
the tool offsets the advantages gained by using it.  I see lots
of developers who "almost" know how to use something.  IMO, this
is worse than *not* knowing hot to use it (or, not *having* the
tool) because it breeds a false sense of confidence in their
efforts.

>> [E.g., if you had to construct an arbitrary regex, could you do so
>> with the knowledge you have committed to memory? Would a reference
>> answer all of the questions you *might* have about your particular
>> pattern?]
> 
> Yes.
> When I have done a lot of regex work I kept a quick reference card handy.

The qualifier on that last statement is the issue.  What about
when you HAVEN'T done work with a tool for some period of time?
Will you admit to yourself that you likely need a "refresher"?
Or, will you stumble along and *hope* it "comes back to you"?
Error-free?

E.g., are multidimensional arrays stored in row or column major order?
There are too many "little details" like this that only stay fresh
in your mind with "frequent refreshing".

[I write a lot of formal documentation.  Yet, I'll be damned if I can
remember the shortcut for "non-breaking hyphenation" -- despite using
it dozens of times on any given document!  (tomorrow, I'll look it up,
again!)]

>> Instead (IMO), you want something that lets a developer use a technology
>> without reliance on a particular tool (that may not be well-supported
>> or may have latent bugs that haven't yet been tickled).
> 
> Being tool agnostic is an ideal goal. In a practice, you must pick some
> specific tools to get the work done within schedule, budget, and quality constraints.
> 
> If you want portability of design then that should be an explicit fourth constraint.
> Most projects select tools with the additional LONG TERM constraint of
> support throughout the life of the product or product line.

I've made a lot of money addressing the needs of clients who banked on
a set of tools, only to discover that they were "no longer supported"
(e.g., doesn't run unde new version of OS, requires hardware that PCs no
longer include, etc.)

You don't realize this is a legitimate design issue until you get
bitten by it.  And, at that time, the time and $$$ available are
seldom what you'd need.

>> As such, understanding the technique is more important than finding a tool
>> that may )or may not) address your needs. ("I want to write in Eiffel.
>> Does your tool output Eiffel source?" Next week it may be some other
>> /langue du jour/)
> 
> Exactly why an abstracting tool that is more focused on the design is better than
> a specific tool.

What better than a human brain?

> State machine design tools are a good example. With a graphic design tool,
> it is much easier to spot missing states or incorrect transitions. It can be
> clear enough that even end users can understand and point out flaws or
> enhancements. I don't think the particular output language is the point here.

But you can use a pencil and paper (or drawing program) to make
such a diagram and "see" the same missing states/incorrect transitions.
The tool just automates binding the design to a particular implementaion.

> BTW, lots of your earlier comments match closely to what I would have posted.
> This one just struck me are being a little too idealistic.

Have you looked at Harel charts?  For *complex*/layered machines?
I suspect revisiting one that you managed to *coax* together at
the start of a project a year or two later (maintenance) would
leave you wondering what all of the cryptic notation means.

Would you admit ignorance and "play it safe" -- and expect to have
time to refamiliarize yourself with it BEFORE trying to make
changes?  Or, would you proceed with a false set of confidence
and *hope* you don't break anything along the way?

Because we all KNOW that we have more than adequate time to
devote to "doing it right", right?  :>

[This is why I push the "idealistic" because in practice is far from it]

On Friday, March 10, 2023 at 12:51:33 PM UTC-5, jmariano wrote:
> Hello again! 
> 
> Thank you all very much for your valuable inputs! I have A LOT of reading to do! 
> 
> I'm not a professional developer, like most of you (I guess). I'm just a "gizmo" builder, serving mainly my own research and my colleagues. I don't have access to professional development tools. My background is in physics, although I took a few electronics courses in college. I took courses on embedded systems, usually called "microprocessor in physics" and the like, but the emphasis of these courses tended to be on the digital part and not so much on the computational aspects of the thing. That is why I usually get lost on the jargon of computer science and know very little of data structures and things like that..... 
> 
> My first contact with FSM was many years ago when I was finishing my PhD. I had to implement a FSM on a FPGA and, of course, I was late, so I pick an example somewhere and just implemented, without really knowing what I was doing.... 
> 
> Now I would like to finally understand a little better how these things work. 
> 
> Also, the sort of things that I build, usually have some type of "controller" in it, and usually talk to a PC via serial interface. This, it seems to me, could to be well modeled by a FSM. I understand that this representation might bring additional issues, as it was mentioned by Don Y, but my main goal here is to go one step further from the clumsy programming that I've been doing for the past few years into a bit more formal representation of the problems. 
> 
> I also have some questions about synchronization of several FSM, but this is a subject for a feature post. 

This is a very simple topic, that can be made as complicated as you wish.  It would be good to work through an example of yours, but until you provide one, here's a traffic light. 

Assume there are separate timers and that inputs from sensors are all processed to be "clean". This is a pseudo language rather than any specific language.  Because Google Groups does not preserve multiple spaces, I'm using underlines for indentation.  The states are EW_GREEN, EW_YELLOW, NS_GREEN, NS_YELLOW.  The inputs are EW_CAR, NS_CAR and the timer done indicators.  Outputs are NS_RED_light, NS_YELLOW_light, NS_GREEN_light, EW_RED_light, EW_YELLOW_light, EW_GREEN_light, and the timer start signals.  This intersection has more traffic in the NS direction, so that direction gets the green light until it times out (longer time than the EW time) or after a minimum delay, an EW car is detected.  

cur_state CASE 
__ NS_GREEN OF
____ IF (NS_LONG_TIMER_done OR (NS_SHORT_TIMER_done AND EW_CAR_detected) ) THEN
______ cur_state <= NS_YELLOW;
______ NS_GREEN_light <= OFF;
______ NS_YELLOW_light <= ON;
______ NS_LONG_TIMER_enable <= OFF;  
______ NS_SHORT_TIMER_enable <= OFF;  
______ YELLOW_TIMER_enable <= ON;  
____ ENDIF ;
__ ENDOF ;

__ NS_YELLOW OF
____ IF (YELLOW_TIMER_done) THEN 
______ cur_state <= EW_GREEN;
______ NS_YELLOW_light <= OFF;
______ NS_RED_light <= ON;
______ EW_RED_light <= OFF;
______ EW_GREEN_light <= ON;
______ YELLOW_TIMER_enable <= OFF;  
______ EW_TIMER_enable <= ON; 
____ ENDIF ;
__ ENDOF ;

__ EW_GREEN OF
____ IF (EW_TIMER_done) THEN
______ cur_state <= EW_YELLOW;
______ EW_GREEN_light <= OFF;
______ EW_YELLOW_light <= ON;
______ EW_TIMER_enable <= OFF; 
______ YELLOW_TIMER_enable <= ON;  
____ ENDIF ;
__ ENDOF ;

__ EW_YELLOW OF
____ IF (YELLOW_TIMER_done) THEN
______ cur_state <= NS_GREEN;
______ EW_YELLOW_light <= OFF;
______ EW_RED_light <= ON;
______ NS_RED_light <= OFF;
______ NS_GREEN_light <= ON;
______ YELLOW_TIMER_enable <= OFF;  
______ NS_LONG_TIMER_enable <= ON;
______ NS_SHORT_TIMER_enable <= ON;
____ ENDIF ;
__ ENDOF ;
 ENDCASE ;

This all starts with a coherent description of the functions of the state machine, then a diagram.  Once you have the diagram, it's a very simple process to turn it into the above coding style. 

In an HDL, the above code would be in a process that runs when any of the specified inputs changes.  Essentially, it's a data flow design.  But I don't know how you would trigger that in something like C.  I suppose you have interrupts from changes of the inputs, as well as timer interrupts.  Each of these are events that can trigger the above code to run.  

-- 

Rick C.

-- Get 1,000 miles of free Supercharging
-- Tesla referral code - https://ts.la/richard11209

On 3/10/2023 10:51 AM, jmariano wrote:
> My first contact with FSM was many years ago when I was finishing my PhD. I
> had to implement a FSM on a FPGA and, of course, I was late, so I pick an
> example somewhere and just implemented, without really knowing what I was
> doing....
> 
> Now I would like to finally understand a little better how these things
> work.

Remember, a microprocessor based system *is* a FSM.  The "state"
is the union of all of the bits of storage in the product.  The
"machine" transitions between states (i.e., alters some of those
bits) based on opcodes and sensed/stored values.

In the current context, an FSM is a much simpler machine with
(usually) less state and fewer I/Os.

Once you start *thinking* in terms of state machines (states),
many problems become more easily conceptualized.

For (trivial) example, assume you have some buttons/switches
that you are monitoring (keyboard?).  Unless wetted, most
mechanical switches bounce as they move from one "state"
to another (open<->closed).

Debouncing such switches is a common activity.  Typically,
you "see" a change (closed->open or open->closed) and
start a timer (implicit or explicit) that allows you to
ignore any "bouncing" in the immediate future as a known
consequence of this characteristic of the switch(es).

When do you recognize the switch as being in the new
(physical) state?  Do you signal the transition as
being detected as soon as you see the physical state differing
from your current model of that state ("I think it's open
but now I see a closure...")?  Or, do you wait until you
are *sure* that the switch will actually settle in that
new physical "condition" (avoiding the use of "state")?

If you model this as a set of *four* FSM states:
- switch IS open
- switch IS closed
- switch opening
- switch closing
you can better think through how you want to handle that
bit of information -- and when.

In the "IS" states, when you sense the physical state of the
switch as being different from your current assessment, you
can transition to the corresponding "*ing" state after starting
a timer.  While in that transitional state, you ignore the
physical switch and just wait for the timer to expire.
At that point ("timer_expired") you can examine the switch's
physical state and, if it has returned to the original state,
choose to *ignore* this bit of noise.  Or, if it has settled in the
"other" state, you can enter that "IS" state and repeat the process
from the other vantage point.

Now, you are free to decide which transition(s) to emit the
"switch_activity" event.  Or, change them, even if you opt
for an asymetric signaling scheme (i.e., signal open-close
as soon as detected but only signal close->open after the
timer has expired and you are sure the switch HAS opened)

> Also, the sort of things that I build, usually have some type of
> "controller" in it, and usually talk to a PC via serial interface. This, it
> seems to me, could to be well modeled by a FSM. I understand that this
> representation might bring additional issues, as it was mentioned by Don Y,
> but my main goal here is to go one step further from the clumsy programming
> that I've been doing for the past few years into a bit more formal
> representation of the problems.

Make up some simple problems and draw the state diagrams.

How would you accept inputs of the ten digit keys, decimal, clear
and enter to accept a valid decimal number?  (note you can't have
two decimal points -- but, you aren't required to have *any*!)

As you are designing the state machine, you have to face decisions
like:
- does CLEAR remove the last entered keystroke?  Or, does it
   discard *all* accumulated keystrokes?
- what if the user doesn't type ANY digits but just hits ENTER?
- what limits the number of digits that can be typed?  Can you
   handle the value 1092039572397013710293014038402938402938402?
   (if not, how do you deal with that possibility?)

Do you issue a prompt to the user before accepting the keystrokes?
Does this prompt remain visible WHILE the user is entering those
digits?  (what if you have a *single-line* display?)  Did you
remember to reemit the prompt if the user clears the entry?  etc.

> I also have some questions about synchronization of several FSM, but this is
> a subject for a feature post.

A *feature* post!  Yay!  "Let's go out to the lobby, let's go out to the
lobby, lets' go out to the lobby, and have ourselves a snack!"

:>

The synchronization problem exists even with a single machine...
because there's usually other stuff going on in the product
that the FSM will have to interact with.  So, the "outputs"
may have side effects -- that are important.

E.g., if pressing a button (after it has been debounced!!)
is supposed to start a motor, does the FSM need to
know that the motor has actually *been* started?  I.e.,
did the "action" that was invoked on the "button debounced"
transition actually turn on the motor?  Or, did it simply
set up something that will actually do that?  In the latter
case, what assurance do you have that the next time the FSM
"runs" (i.e., examines inputs) that the code that turns the
motor on will actually have executed?

[I design my state machines so that the machine "clears"
an input/event when it has processed it.  This acts as
a signal to whatever *posted* that event that the event
has been "consumed.  E.g., a keyboard handler can maintain
a queue of keystrokes and simply block, waiting for the
"most recently SIGNALED keystroke" to be consumed by the
FSM.  When it sees that feedback, it can place the next
keystroke (event/input) as the "most recently SIGNALED
keystroke" and sleep, again.]

[[I also believe in promoting all major forks in an
algorithm to first class events/decision states.
E.g., when I've accepted a set of keystrokes and
need to verify that the value entered is correct
(in an acceptable range), I move from the last digit
accumulating state -- on detecting ENTER -- to a
"decision state".  The action performed on detecting
ENTER is check_for_valid_value().  EVENTUALLY, an
indication of the validity of the entry is signalled
(as an *event*) to the FSM.  So, sitting in the
decision state, it has only two ways to progress
based on those synthetic events:  VALID_VALUE or
INVALID_VALUE.  This makes it easy for a developer to
see 1) that the value *is* checked 2) how the value is
handled if good vs. bad.  The alternative is to bury
these tests amongst a bunch of semicolons so the
developer has to hunt for them]]

On 3/10/2023 12:10 PM, Don Y wrote:
> Because we all KNOW that we have more than adequate time to
> devote to "doing it right", right?  :>
> 
> [This is why I push the "idealistic" because in practice is far from it]

To be fair, I work with lots of different clients/projects so
there's no "established" toolset that I can embrace.  And I
can't always coerce the client to purchase/adopt the tools that
I've found effective.  Hence the need to "understand the
technology" so I can leverage whatever tools I'm *allowed*
to use.  :-/

OTOH, it makes for a much greater variety of assignments!  :>

On Friday, March 10, 2023 at 12:51:33 PM UTC-5, jmariano wrote:
> Hello again! 
> 
> Thank you all very much for your valuable inputs! I have A LOT of reading to do! 
> 
> I'm not a professional developer, like most of you (I guess). I'm just a "gizmo" builder, serving mainly my own research and my colleagues. I don't have access to professional development tools. My background is in physics, although I took a few electronics courses in college. I took courses on embedded systems, usually called "microprocessor in physics" and the like, but the emphasis of these courses tended to be on the digital part and not so much on the computational aspects of the thing. That is why I usually get lost on the jargon of computer science and know very little of data structures and things like that..... 
> 
> My first contact with FSM was many years ago when I was finishing my PhD. I had to implement a FSM on a FPGA and, of course, I was late, so I pick an example somewhere and just implemented, without really knowing what I was doing.... 
> 
> Now I would like to finally understand a little better how these things work. 
> 
> Also, the sort of things that I build, usually have some type of "controller" in it, and usually talk to a PC via serial interface. This, it seems to me, could to be well modeled by a FSM. I understand that this representation might bring additional issues, as it was mentioned by Don Y, but my main goal here is to go one step further from the clumsy programming that I've been doing for the past few years into a bit more formal representation of the problems. 
> 
> I also have some questions about synchronization of several FSM, but this is a subject for a feature post. 
> 
> Cheers, 
> jmariano

Hi jmariano,
You are clearly on the right path. FSM are useful in many situations.
With a physics background you will get it soon.
You can consider time as an input for synchronization. Or a messaging system.
If you would like help on your software design, feel free to email me.

My career went from physics to software, which I've done for about 40 years.
Enjoy and good luck.
   Ed

On Thu, 9 Mar 2023 14:17:14 -0800 (PST), jmariano
<jmariano65@gmail.com> wrote:

>Does anyone know of a nice text on finite state machines and their
>software implementation on embedded systems? 
>
>I'm looking for some theoretical background and design methodology. A
>few examples of "C" implementation would be a nice but not really
>needed. I'm not looking for a recipe or code but for a more formal
>explanation on the workings of FSM.
>Thanks
>jmariano

If you *really* want the theory, you can take a look at Hopcroft and
Ullman's "Intro To Automata Theory, Languages And Computation".

It's available free as an ebook from
https://archive.org/details/HopcroftUllman_cinderellabook/mode/2up


Be aware that there is little/no code in this book - it's theory only
and you will need to figure out how to implement.

Good luck!
George