Text on FSM

Post by jmariano
Hello
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.

FSM are pretty simple. They usually use a directed graph (drawing with circles for states and arrows for transitions between states) to represent the design. It's always a good idea to start with that. Give the sames names, or values and put the inputs on the transitions. When a state is not changing, this should be represented with an arrow from the state back to itself. But it's not important to show these for the code. It does make it clear what's happening. Some states are transitory and do not remain in the same state. This helps you spot when you've missed an input condition.

The inputs to the FSM are the "inputs" (duh) but also the "current state". The FSM calculates "next states" and "outputs". That's a FSM in its simplest form.

The next state always depends on the current state and the inputs. The output can depend on the present state only, or can also change depending on inputs. In that case, I think of the outputs as being part of the "state" of the FSM, but the next state won't depend on outputs. This can be a bit complex, so it may be simpler to start with a FSM where the outputs only depend on the current state.

The code is typically written as a CASE statement on the present state. Within each present state of the CASE, code is written to examine the relevant inputs and decide the next state or possibly also outputs if you are doing that. Your outputs don't have to be calculated in the CASE statement. They can be calculated only on the present state.

That's it in a nutshell. I'm used to hardware, coding in VHDL, but it's the same thing in C or whatever. You just have to watch where you put what code since the order matters in C. In VHDL sections of code all run in parallel, since it's hardware.

Sorry I don't have a reference. I spent a lot of time reading about FSM coding. But most of it was a bit pedantic. For example, the theoretical analysis that was done nearly 100 years ago, resulted in the Mealy vs. Moore classification, depending on if the outputs depend on the inputs or just the present state. I never remember which is which because very few people use either. Instead they use a hybrid where the outputs are calculated in the same case statement, which means they are a cycle late if done with the classical approach.

Whatever. Just pay attention to the timing of your output changes, and if you want to have the next state depend on an output, move that output into part of the state, since that is what it is.

I hope this helped.

--
Rick C.

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

Don Y

2023-03-10 02:11:08 UTC

Hello Does anyone know of a nice text on finite state machines and their
software implementation on embedded systems?

Implementations can vary widely. Do you want to present (current state,
inputs) to a machine and have (next_state, outputs) emitted "immediately"?
Or, is the processing time not critical (e.g., UI's tend to be this type)

Do you want to limit the machine to the "classic" design? Or, add
extensions (e.g., support the notion of "previous_state", "subroutines",
etc.)?

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

In the degenerate case, you build a matrix that is accessed by [state][inputs]
and delivers (next_state, outputs). But, it's obvious that the size of
this structure grows quickly with number of states and inputs. In practice,
often a state may have only a few significant inputs that govern the choice
of next state so the matrix contains lots of redundant entries.

You can unfold the matrix into a series of switch/case statements -- but,
I've found that makes it hard to sort out what's really happening (the
beauty of a state machine is that it is concise).

I prefer representations like:

Case IDLE
On <digit> GoTo ACCEPTING Executing GobbleDigit()
On <clear> GoTo ISSUE_PROMPT Executing ClearValue()
On <enter> GoTo TEST_VALUE Executing CheckLimits()
..

Note that there are only 3 items encoded on each line:
- the input being examined
- the name of the intended next_state
- the action to be performed *in* the transition
As such, this can be encoded in as few as 3 bytes (depending on how
many states, inputs, and actions you need to support)

But, the big advantage is it's concise -- no extra syntactic sugar
to clutter up the page (cuz you want to express the machine in
as little space as possible as it gets harder to chase layers of
case/switch statements with interspersed *actions*)

[There are also UML techniques for their representation and tools that will
parse such descriptions and build the code for you]

In school, Hill & Peterson was our reference (_Intro to Switching Theory and
Logical Design_) but you don't need much "text" to understand the concepts
(assuming you already understand logic).

OTOH, it's worth learning about minimization techniques -- esp if your
approach to the machine's design is /ad hoc/ (ripe for hidden optimizations).

Bill Davy

2023-03-10 08:37:45 UTC

Hello Does anyone know of a nice text on finite state machines and their
software implementation on embedded systems?

Implementations can vary widely. Do you want to present (current state,
inputs) to a machine and have (next_state, outputs) emitted "immediately"?
Or, is the processing time not critical (e.g., UI's tend to be this type)
Do you want to limit the machine to the "classic" design? Or, add
extensions (e.g., support the notion of "previous_state", "subroutines",
etc.)?

In the degenerate case, you build a matrix that is accessed by
[state][inputs]
and delivers (next_state, outputs). But, it's obvious that the size of
this structure grows quickly with number of states and inputs. In
practice,
often a state may have only a few significant inputs that govern the choice
of next state so the matrix contains lots of redundant entries.
You can unfold the matrix into a series of switch/case statements -- but,
I've found that makes it hard to sort out what's really happening (the
beauty of a state machine is that it is concise).
    Case IDLE
On    <digit>        GoTo    ACCEPTING    Executing    GobbleDigit()
On    <clear>        GoTo    ISSUE_PROMPT    Executing    ClearValue()
On    <enter>        GoTo    TEST_VALUE    Executing    CheckLimits()
..
- the input being examined
- the name of the intended next_state
- the action to be performed *in* the transition
As such, this can be encoded in as few as 3 bytes (depending on how
many states, inputs, and actions you need to support)
But, the big advantage is it's concise -- no extra syntactic sugar
to clutter up the page (cuz you want to express the machine in
as little space as possible as it gets harder to chase layers of
case/switch statements with interspersed *actions*)
[There are also UML techniques for their representation and tools that will
parse such descriptions and build the code for you]
In school, Hill & Peterson was our reference (_Intro to Switching Theory and
Logical Design_) but you don't need much "text" to understand the concepts
(assuming you already understand logic).
OTOH, it's worth learning about minimization techniques -- esp if your
approach to the machine's design is /ad hoc/ (ripe for hidden
optimizations).

I went to a course of lectures on (and by) Harel state-charts.

Here is one for text: https://github.com/cepsdev/machines4ceps

There is also
https://www.codeproject.com/Articles/11398/A-Lightweight-Implementation-of-UML-Statecharts-in

Don Y

2023-03-10 10:50:45 UTC

Post by Bill Davy
I went to a course of lectures on (and by) Harel state-charts.
Here is one for text: https://github.com/cepsdev/machines4ceps
There is also
https://www.codeproject.com/Articles/11398/A-Lightweight-Implementation-of-UML-Statecharts-in

The problem I see with using state machines to control processes
is that those processes. however trivial they may APPEAR to be, often have
lots of exceptions that are inherent in their *correct* implementation.

Representing these in the state machine definition IN A WAY THAT DOESN'T
CAUSE THEIR SIGNIFICANCE TO BE LOST (resulting in bugs!) becomes challenging.

Few applications are simple models of DFA -- e.g., the grammar for
a "numerical value". There are invariably other things going on *during*
the processing of that DFA (which has no notion of time even though
the application may be "human driven") that compete with and
potentially override it!

We bought a range, recently. It was less than an hour before I
was able to stumble over a bug in their implementation -- because
the implementer likely ASSUMED each segment of the grammar would
operate essentially without disturbance. So, if the user wanted to
change the temperature setting, this set of states (and state transitions)
*looks* like it will achieve that goal... except it doesn't take
into account that it takes some amount (UNCONSTRAINED!) of time
for the user to perform those steps (generate the events that
are prescribed by it).

And, that while he is faithfully following the prescribed actions,
other "stuff" can be happening. Like, the cook timer expiring
and expecting acknowledgement. Oh, but how do you tell the timer
that THIS "one big single control" activation is intended to acknowledge
that event and *not* a step in the "change temperature" event
sequence?

And, what would happen if one leg of the AC mains "failed" (or
appeared to) during these two overlapping sequences? Would
the display be commandeered to indicate that failure? And,
the acknowledgement of that alert be confused with these
other two competing activities? Some other yet to be
discovered "fault"? How do you express the priority of
those events without makin ghte simple state machine look
overly complex (have I handled the possibility of a partial
AC mains failure at THIS point in the machine? SHOULD I??)

And, what if the cook timer for the *second* oven expired
while all this was happening? Or, the general purpose ("egg")
timer?

There are ways to resolve these problems (DFA hierarchies).
But, it's too easy for the programmer to miss their potential
conflicts, mistakenly thinking he's enumerated all of the input
events, etc. as is required in a "state machine".

pozz

2023-03-10 08:54:23 UTC

Search for Quantum Leaps. Miro Samek has written a very good book about
state-machines for embedded systems with an implementation. However it
isn't free of use, I think. But the book should be now free to download.

Hierarchical state-machines are a very interesting argument for a system
that can be modeled as an event-driven system. An embedded systems can
be usually described as an event-driver system.

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.

Don Y

2023-03-10 11:17:50 UTC

Hierarchical state-machines are a very interesting argument for a system that
can be modeled as an event-driven system. An embedded systems can be usually
described as an event-driver system.

DFA have application besides handling "events". E.g., you can think
of every character/octet in a message as an "event" (even though they all
"appear" as a coherent unit) and use a DFA to parse the content for
validity/meaning.

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.

Robert Roland

2023-03-10 11:48:09 UTC

Post by pozz
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.

--
RoRo

Rick C

2023-03-10 15:20:14 UTC

Post by pozz
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.

The problem these have, like many graphic oriented approaches, is continuing support and version control of the source. I've never worked with a state machine that was so complex it required anything other than a diagram drawn up in your favorite word processor drawing package. Typically, FSM can be decomposed into multiple distinct FSM that are easier to understand, and typically relate to the problem better.

A FSM with 10 states is easy to code. A FSM with 100 states is probably several FSMs, mistakenly combined into one.

--
Rick C.

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

pozz

2023-03-13 15:35:06 UTC

Post by Rick C

Post by pozz
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.

The problem these have, like many graphic oriented approaches, is continuing support and version control of the source. I've never worked with a state machine that was so complex it required anything other than a diagram drawn up in your favorite word processor drawing package. Typically, FSM can be decomposed into multiple distinct FSM that are easier to understand, and typically relate to the problem better.
A FSM with 10 states is easy to code. A FSM with 100 states is probably several FSMs, mistakenly combined into one.

I think the complexity of a FSM is not only related to the number if
states, but also to the transitions/inputs.

It's much simpler to detect errors on a diagram instead on a cryptic
list of switch/case instructions. The great advantage of a diagram is
that it can be read by non-developers: customers, sales man, project
managers and so on.

UML diagrams are there exactly for these reasons.

Now imagine a tool that takes as input the diagram and spits out a fsm.c
without errors.

I know most of FSMs are simple, but most of the time you refuse to solve
a problem with a FSM just because it could be too complex to convert in
code. However, if you had this type of tool, you would consider FSMs for
much more problems.

For example, a simple calculator can be modeled as a FSM: the
transitions are keystrokes. However it isn't a simple FSM, because there
are many subtle details that must be addressed. It is somewhat simple to
make a diagram and solve some problems with arcs, arrows and rectangles,
but it's much more complex to make the same things on a C code.

StateMachineCOM

2023-03-13 15:55:29 UTC

Post by pozz
Now imagine a tool that takes as input the diagram
and spits out a fsm.c

Indeed. Please check out the freeware QM modeling tool:
- https://www.state-machine.com/qm

Automatic Code Generation video:
-

QM is an example of a modern, *lightweight* modeling tool. Older, "high-ceremony" tools have been available since the '90, but they couldn't pull their own weight and didn't catch on. However, things changed since the '90s...

Post by pozz
For example, a simple calculator can be modeled as a FSM: the
transitions are keystrokes. However it isn't a simple FSM...

Interesting that you mention the calculator problem. (I've used it in my "Practical Statecharts" book published back in 2022.) I've also used it in my recent video "State machines as "spaghetti" reducers:

-

It turns out that even the "simple" 4-operation calculator is complex enough to be almost impossible to get right with traditional "improvised" state management. A state machine, on the other hand, is quite manageable.

pozz

2023-03-14 14:44:05 UTC

Post by StateMachineCOM

Post by pozz
Now imagine a tool that takes as input the diagram
and spits out a fsm.c

- https://www.state-machine.com/qm
- http://youtu.be/FHV5vZyECOA
QM is an example of a modern, *lightweight* modeling tool. Older, "high-ceremony" tools have been available since the '90, but they couldn't pull their own weight and didn't catch on. However, things changed since the '90s...

Yes, I know this tool and I like its philosopy. However I understood I
can't use the generated code in closed source projects without a
commercial license.

Post by StateMachineCOM

Post by pozz
For example, a simple calculator can be modeled as a FSM: the
transitions are keystrokes. However it isn't a simple FSM...

- http://youtu.be/fLXxNe4YeJ4

I read your book ;-)

Post by StateMachineCOM
It turns out that even the "simple" 4-operation calculator is complex enough to be almost impossible to get right with traditional "improvised" state management. A state machine, on the other hand, is quite manageable.

*Hierarchical* state-machine is fundamental here to reduce complexity.

Don Y

2023-03-13 16:29:40 UTC

I think the complexity of a FSM is not only related to the number if states,
but also to the transitions/inputs.

Of course. A 0..99 counter can have oodles of states... but the interactions
between them are trivial to the point of being boring.

Interconnectedness is the source of *all* complexity. E.g., the more
modules your code interacts with, the more complex the code is likely to be!

It's much simpler to detect errors on a diagram instead on a cryptic list of
switch/case instructions.

That depends on the problem and how expressive (and intuitive!) the
drawing.

The great advantage of a diagram is that it can be
read by non-developers: customers, sales man, project managers and so on.

See above.

UML diagrams are there exactly for these reasons.
Now imagine a tool that takes as input the diagram and spits out a fsm.c
without errors.

For what *classes* of state machines?

I know most of FSMs are simple, but most of the time you refuse to solve a
problem with a FSM just because it could be too complex to convert in code.
However, if you had this type of tool, you would consider FSMs for much more
problems.

You're already building an FSM when you solve such a problem. Th eissue is
HOW you build it. If /ad hoc/ then it's more likely to contain errors
and be harder for folks to understand -- without digging deep.

For example, a simple calculator can be modeled as a FSM: the transitions are
keystrokes. However it isn't a simple FSM, because there are many subtle
details that must be addressed. It is somewhat simple to make a diagram and
solve some problems with arcs, arrows and rectangles, but it's much more
complex to make the same things on a C code.

A calculator is a toy example.

Imagine, instead, if that calculator (keys + display) also had to
indicate when a key was *stuck*, when the batteries were low
(without a dedicated "low battery" indicator), the current time
of day (and date), implement an "egg timer" functionality as well
as a traditional "alarm", etc.

A calculator is *just* a calculator. Few embedded systems have such
limited -- and "regular" -- functionality.

Imagine being in the middle of a calculation and the display is
commandeered by the alarm function signalling the programmed time
has been reached. The value you had been typing is overwritten
AND your next keystroke is expected (but not guaranteed) to be
an interaction with the "alarm clock" -- acknowledge the alarm,
request an additional 10 minutes, leave it active (but not
monopolizing the display) for later attention, etc.

This condition can persist indefinitely (unless the design
times it out). So, what happens when the battery fails
some time later? Does that message overlay the alarm
message? How do you interact with THAT? And, when you've
"cleared" it, does the alarm display reappear? Do you
even *remember* the calculation that you were making when
this started?

[And let's not get into the possibilities for races because
you hadn't considered how one "process/interaction" could be
interrupted/preempted by another!]

pozz

2023-03-14 14:54:35 UTC

Post by pozz
I think the complexity of a FSM is not only related to the number if
states, but also to the transitions/inputs.

Of course. A 0..99 counter can have oodles of states... but the
interactions
between them are trivial to the point of being boring.
Interconnectedness is the source of *all* complexity. E.g., the more
modules your code interacts with, the more complex the code is likely to be!

Post by pozz
It's much simpler to detect errors on a diagram instead on a cryptic
list of switch/case instructions.

That depends on the problem and how expressive (and intuitive!) the
drawing.

A good diagram is always much more expressive than a good code, for
developers and for non-developers.

Post by pozz
The great advantage of a diagram is that it can be read by
non-developers: customers, sales man, project managers and so on.

See above.

Post by pozz
UML diagrams are there exactly for these reasons.
Now imagine a tool that takes as input the diagram and spits out a
fsm.c without errors.

For what *classes* of state machines?

Hierarchical state-machines (UML state-machines) are fully qualified
monsters.

Post by pozz
I know most of FSMs are simple, but most of the time you refuse to
solve a problem with a FSM just because it could be too complex to
convert in code. However, if you had this type of tool, you would
consider FSMs for much more problems.

This is the reason why a fsm generation tool could help. You don't need
to build with /ad hoc/ approach.

Post by pozz
For example, a simple calculator can be modeled as a FSM: the
transitions are keystrokes. However it isn't a simple FSM, because
there are many subtle details that must be addressed. It is somewhat
simple to make a diagram and solve some problems with arcs, arrows and
rectangles, but it's much more complex to make the same things on a C
code.

A calculator is a toy example.
Imagine, instead, if that calculator (keys + display) also had to
indicate when a key was *stuck*, when the batteries were low
(without a dedicated "low battery" indicator), the current time
of day (and date), implement an "egg timer" functionality as well
as a traditional "alarm", etc.
A calculator is *just* a calculator. Few embedded systems have such
limited -- and "regular" -- functionality.
Imagine being in the middle of a calculation and the display is
commandeered by the alarm function signalling the programmed time
has been reached. The value you had been typing is overwritten
AND your next keystroke is expected (but not guaranteed) to be
an interaction with the "alarm clock" -- acknowledge the alarm,
request an additional 10 minutes, leave it active (but not
monopolizing the display) for later attention, etc.
This condition can persist indefinitely (unless the design
times it out). So, what happens when the battery fails
some time later? Does that message overlay the alarm
message? How do you interact with THAT? And, when you've
"cleared" it, does the alarm display reappear? Do you
even *remember* the calculation that you were making when
this started?
[And let's not get into the possibilities for races because
you hadn't considered how one "process/interaction" could be
interrupted/preempted by another!]

I didn't get your point of these all. There are simple applications and
complex applications, I don't think you need to convince me.

Anyway even a simple application such as a standard calculator can be
complex enough to be implemented as a flat state-machine without any tool.

However the complexity can be managed and reduced on a diagram of a
UML/hierarchical state-machine. After that, click on a build button and
you error-free code is done.

Don Y

2023-03-14 15:39:21 UTC

I think the complexity of a FSM is not only related to the number if states,
but also to the transitions/inputs.

Of course. A 0..99 counter can have oodles of states... but the interactions
between them are trivial to the point of being boring.
Interconnectedness is the source of *all* complexity. E.g., the more
modules your code interacts with, the more complex the code is likely to be!

It's much simpler to detect errors on a diagram instead on a cryptic list of
switch/case instructions.

That depends on the problem and how expressive (and intuitive!) the
drawing.

A good diagram is always much more expressive than a good code, for developers
and for non-developers.

That depends on whether the diagram can express the issues that need to be
expressed, *concisely*.

nest_state := current_state + 1

sure is a lot more descriptive than wading through 99 discrete states
that all *seem* to say the same thing (but you must VERIFY to be sure!)

customers, sales man, project managers and so on.

See above.

UML diagrams are there exactly for these reasons.
Now imagine a tool that takes as input the diagram and spits out a fsm.c
without errors.

For what *classes* of state machines?

Hierarchical state-machines (UML state-machines) are fully qualified monsters.

Your goal, with *documentation* (vs specification) is to educate quickly
and accurately. If "I" have to understand nuances of a presentation
before the *real* meaning is apparent, then "I" will likely miss some
detail and likely not know it (for some group of "I").

E.g., in Limbo, there are two ways to make an assignment:

foo := 2
foo = 2

Is the latter a typographical error? (No, the former instantiates and
types the variable in addition to making the assignment; the latter simply
does the assignment)

This is the reason why a fsm generation tool could help. You don't need to
build with /ad hoc/ approach.

But if the tool doesn't build the *entire* state machine portion of the code,
then what good is it? If it just generates a skeleton and relies on the
developer to "flesh it out", then it's just a labor saver and still leaves
the application vulnerable to design omissions.

For example, a simple calculator can be modeled as a FSM: the transitions
are keystrokes. However it isn't a simple FSM, because there are many subtle
details that must be addressed. It is somewhat simple to make a diagram and
solve some problems with arcs, arrows and rectangles, but it's much more
complex to make the same things on a C code.

A calculator is a toy example.
Imagine, instead, if that calculator (keys + display) also had to
indicate when a key was *stuck*, when the batteries were low
(without a dedicated "low battery" indicator), the current time
of day (and date), implement an "egg timer" functionality as well
as a traditional "alarm", etc.
A calculator is *just* a calculator. Few embedded systems have such
limited -- and "regular" -- functionality.
Imagine being in the middle of a calculation and the display is
commandeered by the alarm function signalling the programmed time
has been reached. The value you had been typing is overwritten
AND your next keystroke is expected (but not guaranteed) to be
an interaction with the "alarm clock" -- acknowledge the alarm,
request an additional 10 minutes, leave it active (but not
monopolizing the display) for later attention, etc.
This condition can persist indefinitely (unless the design
times it out). So, what happens when the battery fails
some time later? Does that message overlay the alarm
message? How do you interact with THAT? And, when you've
"cleared" it, does the alarm display reappear? Do you
even *remember* the calculation that you were making when
this started?
[And let's not get into the possibilities for races because
you hadn't considered how one "process/interaction" could be
interrupted/preempted by another!]

I didn't get your point of these all. There are simple applications and complex
applications, I don't think you need to convince me.

The point is that most (embedded) applications are much more substantial than
a limited domain calculator.

I drew parallels in the calculator example to the oven example I posted
elsewhere. It *appears* to be a simple application:
- press big button to wake up display
- turn to select cooking mode
- press big button to make that choice
- turn to select cooking temperature
- press button to make that choice
- turn button to select next action (cook, specify time, etc.)
- perform that step
Repeat for the second oven.

Ah, but, while you are specifying the temperature for the second
oven, the cook timer for the first oven may expire (because you started
to specify the second oven's temperature and then dashed off to remove
the toast from the toaster).

Now what? Do you reply to the query (from the first oven) asking if
you want to shut the oven off or leave it on? Or, do you continue
trying to specify the temperature for the second oven -- which is your
memory of your most recent interaction with the oven?

The calculator is a closed box. Nothing interacts with it other than
the user. It can wait forever for the user to perform the next
action (keypress) without fear of having its resources re-assigned
to some other activity.

If, in the example I posted, the calculator had to indicate battery
failures, expired timers, etc. then it's considerably more involved
in its design. This needs to be expressible in the state machine in
a way that makes the correctness (or not) of the design apparent
to the designer.

[My oven fails this test! So, whatever tools the multi-BILLION dollar
corporation that designed it used were inadequate for the task.]

Anyway even a simple application such as a standard calculator can be complex
enough to be implemented as a flat state-machine without any tool.
However the complexity can be managed and reduced on a diagram of a
UML/hierarchical state-machine. After that, click on a build button and you
error-free code is done.

Niklas Holsti

2023-03-14 16:49:26 UTC

Post by pozz

Post by pozz
I think the complexity of a FSM is not only related to the number if
states, but also to the transitions/inputs.

Of course. A 0..99 counter can have oodles of states... but the
interactions
between them are trivial to the point of being boring.
Interconnectedness is the source of *all* complexity. E.g., the more
modules your code interacts with, the more complex the code is likely to be!

Post by pozz
It's much simpler to detect errors on a diagram instead on a cryptic
list of switch/case instructions.

That depends on the problem and how expressive (and intuitive!) the
drawing.

A good diagram is always much more expressive than a good code, for
developers and for non-developers.

In my experience, diagrams that describe all the details of the code, as
would be required for generating the code from the diagram, are usually
much too complex to comprehend easily ("visually"). They tend to be
mazes where one can perhaps trace out some significant paths with a
careful finger, unless too many lines cross at one point.

To get a good, visually graspable diagram, IME one must almost always
simplify and elide details. And then such diagrams are very good entry
points into the code, if one has to read the code to get a complete
understanding.

I remember one case where the SW for the central computer of a satellite
was generated from state-and-message diagrams by an automatic
"model-based design" tool. In graphical form, the diagrams covered
numerous A4 pages and each page had several cryptically labelled
inter-page links for messages coming from other pages and going to other
pages. It was very difficult to get any kind of overall understanding of
the SW.

I admit that there are some domains -- for example, servo-control
systems -- where it is possible to generate significant amounts of code
from readable diagrams, eg. SIMULINK diagrams. But I don't think it
works well for most code in embedded systems.

Don Y

2023-03-10 16:39:46 UTC

Post by pozz
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/)

Don Y

2023-03-10 17:02:23 UTC

Post by Don Y
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...]

Ed Prochak

2023-03-10 18:10:16 UTC

Post by pozz
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.

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.

Post by Don Y
[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.

Post by Don Y
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.

Post by Don Y
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

Don Y

2023-03-10 19:10:19 UTC

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.

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!)]

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.

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

What better than a human brain?

Post by Ed Prochak
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.

Post by Ed Prochak
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]

Don Y

2023-03-10 19:49:05 UTC

Post by Don Y
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! :>

Ed Prochak

2023-03-10 22:02:48 UTC

We think a lot alike because we've both have done this a long time.

To your 1st sentence: AMEN. We don't really disagree here.
To the rest: I've seen it too. Developers that write C code
thinking they are programming in C++ is an extreme example.

Yes.
When I have done a lot of regex work I kept a quick reference card handy.

Personally, Yes, I admit to my own limitations.

Post by Don Y
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".

True, but that is a different issue that the selection of the tool in the first place.

Post by Don Y
[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!)]

You're preaching to the choir here Don.

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.

Yes a lot of projects don't follow due diligence. Hence my phrase
earlier about "good management and teams" was used deliberately.

Post by Don Y
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.

Yes. That's true. Computer engineering has been in constant flux for
70+years. Those that fail to learn history are condemned to repeat it.

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

What better than a human brain?

I was focusing on documenting the design. I've tried to leave projects
with enough clear design so that I can be replaced.

But you can use a pencil and paper (or drawing program) to make
such a diagram and "see" the same missing states/incorrect transitions.

Well, whiteboard is easier to "edit and then save via camera (&/or printer)

Post by Don Y
The tool just automates binding the design to a particular implementaion.

Ideally it should do both, act as a design recording medium and
output the implementation.

Post by Ed Prochak
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.

Haven't used Harel charts. That's part of UML and no place that
I worked at has needed a tool set that complex. KISS
Taking a quick look, [again!] I can see why it may not be a good choice.

Post by Don Y
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?

If it is the design, then it better be clear enough to just read through
and be understandable and complete.
If it is the implementation, then I never assume I am familiar with
the code (even it I wrote it).

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

On some projects more than others. But I've managed to work on a couple
projects where putting in the time up front in design paid off big in the
integration and release. I'm especially proud of those projects.

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

At one of the last places I worked we developed a saying that
we violently agree. 8^)

You make great contributions here Don. Keep it up.
Ed

Don Y

2023-03-11 13:01:40 UTC

Post by Ed Prochak
We think a lot alike because we've both have done this a long time.

Long lost brother? <raises eyebrows> Tell me, do you, too, have
that extra thumb on your left hand?? :>

Yes.
When I have done a lot of regex work I kept a quick reference card handy.

Personally, Yes, I admit to my own limitations.

There are two issues potentially at play, here.

One is "vanity/pride/overestimation of your abilities".
The other is simply not *knowing* that you don't really know what
you need to know (or, that you know "enough" that the "rest" is
insignificant)

[Recall, we also have to address newcomers to the codebase
who may be seeing these techniques for the first time and
convince themselves that they *think* they know what it does]

Post by Don Y
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".

True, but that is a different issue that the selection of the tool in the first place.

I'm just commenting on "little details" that are too easy to "forget to
remember" -- like the nonbreaking hyphen, below. In my defense, I
*know* that the nonbreaking hyphen exists, why/where it should
be used AND HOW *EASILY* I CAN REFRESH MY MEMORY (by opening the
"shortcuts" manual). So, the fact that I keep forgetting the
shortcut doesn't bother me.

But, some of the FSM tools are overly cryptic in how they try
to encode different "machine aspects" into the definition of
the machine. How likely would a "stale" developer be to
remember what all of those are and how they are used/invoked?
Would he be humble/practical enough to admit his need for a
refresher? Would he have the *time* to do so (perceived or
otherwise)?

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.

Yes a lot of projects don't follow due diligence. Hence my phrase
earlier about "good management and teams" was used deliberately.

This is the crux of our difference. Ed, you (appear to be) optimistic
about what you can expect from other developers and managers. I'm
highly (HIGHLY!) jaded/cynical. I expect people to be lazy (why crack
open a reference?) as well as over-estimate their abilities.

I've personally seen products released with KNOWN bugs, rationalizing
that they aren't "that important" (isn't the customer/end user the one
who is supposed to make that decision?). Or, that they'll be fixed in an
upcoming release -- that never comes (because there are other issues
that preempt it in the queue).

Even the simplest/easiest of tasks often get overlooked or ignored.

I have been trying to get a copy of my medical record under HIPPA.
This is a CIVIL RIGHT (!) I filled out the APPROVED form. HAND
DELIVERED to the office (so no need to rely on the mail for prompt
delivery). "It can take up to 30 days" (because a third party has to
fulfill the request)

Sit back and *patiently* wait. Don't pester them cuz they've already
told you "up to 30 days". And, maybe a few more in case it got mailed
on the 30th day!

Day 35, time to call and see what's going on. "Press 3 for Records
and Referrals" 10 rings. Voicemail. OK, its possible the person
is away from their desk. Leave message, name, reason for calling,
callback number.

Next day, still no callback. Try again. Same result. Leave ANOTHER
message.

Lather, rinse, repeat for a total of 5 days!

OK, they've obviously got a problem with their "Records and Referrals"
person! Escalate to office manager. Don't accept their offer to "send
me to her voicemail" as we've done that for 5 days, already, with the
records flunky.

Office manager will track down the records person (why isn't she
at work? at 9:30AM? Office opens at 8!) and get back to me.

Don't pester later that day -- give them time, you're not the only
thing that they need to deal with.

Or, the next.

Two days later, call again and office manager avoids the call relying
on someone else to give me a message: A third party "records" firm
is processing my request (Duh, we knew that when I dropped off the
request ~6 weeks earlier!). "When can I expect it from THEM?" Dunno.
"Who can I call for more information?" (cuz you folks have been really
tedious to deal with). Dunno.

Eventually, get office manager on the phone. She's got their phone
number and a "request ID" used to identify the request initiated on
my behalf.

Call third party. Automated "Your request is being processed. Call
back in 7 days." (we're well beyond that 30 day initial limit).

Out of curiosity, call back and talk to a human. Who repeats the
same 7 day message. "Why is it taking so long? I requested these
40+ days ago!"

"We just got the request YESTERDAY."

Ah, so now I know that the "office" never filed my request.
They just lost it (or it was still sitting in the Records person's
inbox).

Long story. But, the point is, all the Records person had to do was
pass the request on to the third party, initially. Insert in FAX machine
(or document scanner) and press "SEND". Yet, this was beyond their
abilities!

And, thereafter (had they done their job originally), all they
would have had to do to address my followups was to give me the phone
number and identifier for me to contact the third party!

Instead, they try to hide the fact that they didn't do their
job (office manager didn't say, "Gee, Don, we're really sorry
but your request got lost, somehow. We only just recently
submitted it to the third party (AFTER YOU PESTERED US). We'll
try to EXPEDITE it for you (so YOU don't have to deal with
*OUR* problem)"

[What would have happened had I been in need of a REFERRAL and the
"Records and Referrals" person been just as negligent? Would I
have been letting the clock run out on a potentially serious
medical condition?]

Back to the topic at hand...

Ask developers why their code is buggy and they'll tell you
it's because their *boss* doesn't give them time to do proper
testing, or doesn't have good design practices in place, etc.
AS IF *they* would do much better in the absence of those
nasty, ignorant managers and corporate culture.

Yet, look at FOSS products -- no boss, no deadlines, put
whatever design practices *you* want in place (after all,
it's !your! name that will be on the "product"; you won't
be some anonymous employee/developer) and you still see
the same /ad hoc/ practices at play.

Or, *you* WITNESSED a particular bug while testing your code.
Yet, you weren't able to (easily) reproduce it. So, you
DISMISS it (as a fluke) -- despite KNOWING that it happened
and you haven't done anything DELIBERATE to eliminate it.
Really? What's your defense? You'll address it when
some user encounters it? Or, you'll hope some other user
finds and fixes it?

<frown> No, I don't expect developers to "do the right thing"
any more than I expect managers to put in place the right practices.
There's always a rationalization...

Jaded.

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

What better than a human brain?

I was focusing on documenting the design. I've tried to leave projects
with enough clear design so that I can be replaced.

My arguments have been towards "tools that do this code generation"
(pozz/roland's upthread comments). To do so, they have to have more
information encoded in the representation.

A classic state diagram is conceptually simple. You don't have special
symbols to reference timed transitions, history, nested machines, etc.
Yet, even a small number of states can quickly have too many transitions
to easily represent on a sheet of paper.

This is a small (hardware) FSM. Poor quality because it was *hand*
drawn (straight edge, lead holder and lettering guide) on a *D*-size
sheet of paper, reduced to B size and then scanned at 1200dpi (in an
attempt to preserve as much detail as possible)!

<https://mega.nz/file/A3x03aAA#YNsJhdikiucjU6aKGWKL2eTu4D0i95sqjcLuzIhz7ys>

8 state variables (Moore type so they also represent the outputs). About
35 states. And, it is highly regular (as evidenced by the symmetry in
the presentation. Imagine an embedded system (software) that has all
sorts of "exceptions" to take into consideration (transtion vectors
crisscrossing willy-nilly)

All this machine does is act as mediator between an internal FIFO
(controlled by another FSM) and a "swappable hardware interface".
It allows that interface to present dots (foreground/background),
lines (essentially "line feeds") and pages to a marking engine.
It prioritizes multiple concurrent requests and acknowledges each
(interlocking REQ-ACK handshake). The "work" it does is sorting out
how to accumulate dots to deliver to the FIFO as packed bytes,
pad out lines that have not specified enough dots to fill the
width of the line, etc. I.e., it is *trivial*. Yet, a visual mess.

Post by Don Y
The tool just automates binding the design to a particular implementaion.

Ideally it should do both, act as a design recording medium and
output the implementation.

But, again, if what you're trying to codify (in the drawing) has
too many subtleties, how likely will you be to draw it correctly?
How often will you "test your knowledge" just by seeing if it
(the code) *appears* to do what you want?

[Have a look at all of the subtlety in Harel state charts. They
try to encode *everything* in the drawing -- which is what you'd
need to do if you were going to generate code FROM that drawing.
I contend that someone using them day in, day out, *could* likely
be very effective with them. But, someone just using them for
part of a project would perpetually be uncertain of the actions
they're taking wrt them. Like trying to create an arbitrary
regex after months of not using them]

Documents should *enhance* your understanding of a product
(or its behavior). They shouldn't become challenges in and of
themselves (because they try to be equivalences for the actual code!)

Each "node" in my current design operates in several "major states".
It can be:
- powered down (by the system)
- powering up (at the behest of the system, running POST, acquiring OS image)
- running diagnostics (taken out of service due to a fault)
- powered up but "cold" (ready to receive application code, known to be
in a reliable hardware state to deliver its potential functionality)
- powered up and actively providing services
- powered up but only serving compute resources (field is powered off)
- powering down (shedding load to other nodes at the behest of the system)
- faulted (failure detected so trying to recover)
etc.

It's really just a handful of different *major* states. Yet, the state
diagram is a mess, just indicating how a node can move from one of
these states to another (ignoring all of the "details" involved). And,
it ignores the many states *within* a major state (to manage complexity)

If you think about *applications*, in detail, you quickly discover that there
are lots of states that need to be visible -- IF YOU WANT TO MODEL THE ENTIRE
APPLICATION as a FSM).

Instead, use state diagrams to explain portions of the design in
more intuitive/visual ways -- without requiring them to be "complete
enough" to generate code (via some other tool). Let the developer look
elsewhere for more detail -- expressed in a medium that is better
suited to THAT task.

Post by Ed Prochak
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.

Haven't used Harel charts. That's part of UML and no place that
I worked at has needed a tool set that complex. KISS
Taking a quick look, [again!] I can see why it may not be a good choice.

But that shouldn't rule out using state diagrams *or* state
machines. Harel just seems to think "if a little is good, a lot
will be better!"

I've implemented (software) state machines in probably a few dozen
*different* ways -- each an "experiment" to see if some tweek of an
earlier approach can give me better "app coverage" (without jeopardizing
the project's design). My conclusion: there is no *best* way. So,
adopting *an* approach (dictated by a tool) seems like a straight-jacket.

The important thing is to have a visible structure to the design
that is reasonably easy to grasp -- without wading through pages
of case/switch statements with interspersed code fragments.

If it is the design, then it better be clear enough to just read through
and be understandable and complete.

Does it really need to be complete for you to grok intent?
Do I really care how the code detects a power failure to
understand how it *reacts* to one? Use good abstractions
and the next guy won't *have* to understand ALL of it.

Post by Ed Prochak
If it is the implementation, then I never assume I am familiar with
the code (even it I wrote it).

Wise man! :> Also, a testament to writing what needs to
be written, instead of trying to be clever!

I had to modify some of my baking Rxs do to egg shortages.
Being reasonably good with arithmetic, I can scale recipes
in my head. So, just jot down the actual quantities that
I used (after scaling).

Now, going back to clean up the little scraps of paper that
I used (is this a universal truth? I always see folks with
Rxs on oddball slips of paper -- the back of cash register
receipts, envelopes, etc. I think the only folks who use
those nice printed index cards are folks who don't bake! :<),
I find some quantities that obviously aren't in the correct
scaled proportions evident in the *other* quantities.

As it's unlikely that I "figured wrong", there must have been
a reason for my instituting that change... yet I've neglected
to commit it to paper so I'm now at risk of having to make a
similar change, in the future, and not realizing it until after
the fact! :<

Don Y

2023-03-11 13:17:13 UTC

Post by Don Y
If you think about *applications*, in detail, you quickly discover that there
are lots of states that need to be visible -- IF YOU WANT TO MODEL THE ENTIRE
APPLICATION as a FSM).
Instead, use state diagrams to explain portions of the design in
more intuitive/visual ways -- without requiring them to be "complete
enough" to generate code (via some other tool). Let the developer look
elsewhere for more detail -- expressed in a medium that is better
suited to THAT task.

Old-school analogy: you'd no longer write a (detailed) flowchart
to document a piece of code (before or after writing it). But, would
likely sketch the "major flow" -- even if only on the back of a
napkin -- to act as general guidance.

StateMachineCOM

2023-03-10 15:54:15 UTC

This question is precisely what I've been exploring, working on, and writing about for decades.

Unfortunately, like most terms in our discipline of embedded programming, the term FSM means different things to different people. That's why you will get many different answers because some people mean "input-driven" state machines, others mean "event-driven" state machines, and yet others mean everything in between. Of course, all of this means different implementations, from nested-switch, through state tables, OO State design patterns, various state machine "compilers", etc.

I tried to cut through this confusion in my video playlist "State Machines" on YouTube:

https://www.youtube.com/playlist?list=PLPW8O6W-1chxym7TgIPV9k5E8YJtSBToI

I've also collected a lot of resources about state machines, including my books and papers about the subject. To find out more, just google "Miro Samek".
--MMS

jmariano

2023-03-10 17:51:29 UTC

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

Rick C

2023-03-10 19:27:54 UTC

Post by jmariano
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

Don Y

2023-03-10 19:46:57 UTC

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)

Post by jmariano
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.

Post by jmariano
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]]

Ed Prochak

2023-03-10 21:11:30 UTC

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

Gerhard Hoffmann

2023-03-13 20:20:25 UTC

Post by jmariano
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 learned state machines using the PLD compiler "CUPL" on
a VAX11/750. That had a nice syntax for Mealy and Moore
state machines and once I had understood that, I could also
do it in PALASM or VHDL.

Another useful tool is yacc from Unix or bison on Linux.
It reads a grammar and builds a state machine from it.
The state machine is later a blob of C. It reads a series of
symbols from its input much like your serial device and hopps
through the state machine if the string of symbols is legal
given the grammar. If a legal grammar rule is recognized,
you can trigger the execution of some C code.

Grammar:

expression = number: { $$ = $1; )
| expression = sym_variable: { $$ = $1; )
| expression = Number '+' number : { $$ = $1 + $3; }
| expression = epression '*' expression: { $$ = $1 * $3; }
| expression = epression '/' expression: { $$ = $1 / $3; }
| expression = '(' expression and so on

assignment = sym_variable ":=" expression: { $$ = $3; )

My syntax is wrong, but you get the principle. The stuff
in curly braces is the executed C code when a rule is
discovered, the $$ thingies are replaced by the relevant variables. Yacc
tries to find the most general rules possible.
That makes sure that y = a + b + c * sin(333); is recognized.

Usually you will insert a lexical scanner in the input, like
lex, so that the state machine does not grow beyond a reasonable
size. That would filter out things like "begin", "end",
"integer", ":=" and so on. lex() would return integer constants
like SY_BEGIN, VARIABLE_NAME, '(' and so on.

Yacc stands for "Yet Another Compiler Compiler", but it's
original job was to create Weinberger arrays, a LSI structure
not unlike a PAL.

Cheers,
Gerhard

Don Y

2023-03-13 22:41:32 UTC

Post by Gerhard Hoffmann
I learned state machines using the PLD compiler "CUPL" on
a VAX11/750. That had a nice syntax for Mealy and Moore
state machines and once I had understood that, I could also
do it in PALASM or VHDL.

CUPL, PALASM, PLDshell, ABEL, etc.

Post by Gerhard Hoffmann
Another useful tool is yacc from Unix or bison on Linux.
It reads a grammar and builds a state machine from it.
The state machine is later a blob of C. It reads a series of
symbols from its input much like your serial device and hopps
through the state machine if the string of symbols is legal
given the grammar. If a legal grammar rule is recognized,
you can trigger the execution of some C code.

Yes, but tedious for things like event driven code (where the symbols
in the alphabet are events).

Post by Gerhard Hoffmann
expression = number:                       { $$ = $1;    )
| expression = sym_variable:               { $$ = $1;    )
| expression = Number '+' number :         { $$ = $1 + $3; }
| expression = epression '*' expression:   { $$ = $1 * $3; }
| expression = epression '/' expression:   { $$ = $1 / $3; }
| expression = '(' expression and so on
assignment = sym_variable ":=" expression: { $$ = $3;    )
My syntax is wrong, but you get the principle. The stuff
in curly braces is the executed C code when a rule is
discovered, the $$ thingies are replaced by the relevant variables. Yacc tries
to find the most general rules possible.
That makes sure that y = a + b + c * sin(333); is recognized.
Usually you will insert a lexical scanner in the input, like
lex, so that the state machine does not grow beyond a reasonable
size. That would filter out things like "begin", "end",
"integer", ":=" and so on. lex() would return integer constants
like SY_BEGIN, VARIABLE_NAME, '(' and so on.

lex(1) most often used to aggregate things like <digit>s into <number>
or <character>s into <token>/<reserved_word> without unduly burdening
the grammar with individual rules for each token. No real "actions"
done inside those tokens.

lex/yacc are more applicable to parsing strings of characters
as you'd encounter in a (programming) language.

AFAICT, none of these tools knows how to optimize states by
noting equivalences (?) [George would know for sure]
OTOH, when dealing with hardware machines, it's a common step
to reduce via implication tables, etc.

Post by Gerhard Hoffmann
Yacc stands for "Yet Another Compiler Compiler", but it's
original job was to create Weinberger arrays, a LSI structure
not unlike a PAL.
Cheers,
Gerhard

George Neuner

2023-03-14 03:07:02 UTC

On Mon, 13 Mar 2023 15:41:32 -0700, Don Y

Post by Don Y
lex/yacc are more applicable to parsing strings of characters
as you'd encounter in a (programming) language.
AFAICT, none of these tools knows how to optimize states by
noting equivalences (?) [George would know for sure]
OTOH, when dealing with hardware machines, it's a common step
to reduce via implication tables, etc.

yacc and bison will remove unreachable PDA states. Unreachable states
in the parser typically are not deliberate but rather result from
ambiguities in the grammar. lex, being LALR(1), does not tolerate
much ambiguity - however bison can generate more powerful LR(1) and
GLR(1) parsers, and these are far more likely to have unreachable
states accidentally generated.

Similarly, lex will remove unreachable DFA states. Again, these
typically are not deliberate, but rather result from lex combining the
various input regex into a single DFA having multiple entry points and
multiple accepting states.

Then there is flex.

flex has some DFA optimizations available. First, flex can compress
the data tables which encode its DFA states. Second, flex can
discover "equivalence" classes: groups of characters which result in
the same action. And finally, flex can [sometimes] discover
"meta-equivalence" classes: commonly expected sequences of characters
and/or other equivalence classes.

All of these can result in a smaller and/or more efficient recognizer
than is possible with lex.

yacc and lex are ancient and haven't been maintained for decades. They
have limitations that will never be addressed, and bugs that will
never be fixed. If you really need backward compatibility with them,
it is available using bison and flex ... and if you don't need bacward
compatibility, bison and flex are much more powerful and modern tools
for use with new projects.
[There are other modern alternatives to yacc and lex also, but
discussion of them is beyond the scope of this missive.]

George

Don Y

2023-03-14 05:59:25 UTC

Post by George Neuner
On Mon, 13 Mar 2023 15:41:32 -0700, Don Y

But, the FSM parallel would be an "orphan" state that would (*likely*)
be readily apparent in a state diagram. "You can't get there from here".

In hardware designs, it is not uncommon to have multiple equivalent
states that aren't easily recognized as such (because you tend to
ignore "don't cares" -- which are ripe for collapsing equivalents).

Post by George Neuner
Then there is flex.
flex has some DFA optimizations available. First, flex can compress
the data tables which encode its DFA states. Second, flex can
discover "equivalence" classes: groups of characters which result in
the same action. And finally, flex can [sometimes] discover
"meta-equivalence" classes: commonly expected sequences of characters
and/or other equivalence classes.

But, those are mapping equivalent *inputs* together, not equivalent
*states*. I.e., treating "BEGIN" and "begin" as equivalent.

Would it recognize a common sequence of state transitions
that occurs in two different places in the grammar? E.g.,
specifying the syntax for a numeric quantity in two different
places only to realize that it's actually the same part of
the grammar expressed as two different instances?

<number> ::= <digit><digits>

<value> ::= <digit><digits>

<expr> ::= <number> <op> <number> | <value> <op> <value>

(silly example; but the inputs in each case are the same)

Post by George Neuner
All of these can result in a smaller and/or more efficient recognizer
than is possible with lex.
yacc and lex are ancient and haven't been maintained for decades. They
have limitations that will never be addressed, and bugs that will
never be fixed. If you really need backward compatibility with them,
it is available using bison and flex ... and if you don't need bacward
compatibility, bison and flex are much more powerful and modern tools
for use with new projects.
[There are other modern alternatives to yacc and lex also, but
discussion of them is beyond the scope of this missive.]

Now, to the question at hand (or, a version thereof).

It's relatively common to design an algorithm or a hardware machine
as a "state transition diagram" and then reduce to an implementation.
(The question, posed here, is how much this can be automated and
the benefits that might acrue).

But, IME, DFA for grammars are most usually expressed in (e)bnf
and *later* rendered into graphical form (e.g., railroad dwgs).
The graphical form being a consequence of the specification,
not the *driver* of the specification. And, the graphical
form often *omitting* detail (i.e., how each rule in the grammar
is acted upon).

Said another way, do you see folks designing grammars graphically
and relying on tools to convert these "expressions" to more
concrete forms for parser generators? (this being the analog of
how graphical tools are being suggested for application to FSM)

George Neuner

2023-03-15 01:29:17 UTC

On Mon, 13 Mar 2023 22:59:25 -0700, Don Y

Post by George Neuner
On Mon, 13 Mar 2023 15:41:32 -0700, Don Y

But, the FSM parallel would be an "orphan" state that would (*likely*)
be readily apparent in a state diagram. "You can't get there from here".
In hardware designs, it is not uncommon to have multiple equivalent
states that aren't easily recognized as such (because you tend to
ignore "don't cares" -- which are ripe for collapsing equivalents).

When you merge two FSM you often get redundant "don't care" nodes, but
you also can get nodes which either are impossible to enter [dead
code], or impossible to leave [halt], because there are no legal
transitions that will permit it. Joining FSM involves identifying and
pruning both types of nodes.

But, those are mapping equivalent *inputs* together, not equivalent
*states*. I.e., treating "BEGIN" and "begin" as equivalent.

No. Consider the case of just recognizing a decimal digit: compare
the graph using the alternation: (0|1|2|3|4|5|6|7|8|9), vs the graph
using the class [:digit:].

Using the OR alternation, including start you have 11 nodes. Start has
10 transitions exiting, and each digit node has a single transition
entering.

Using the digit class, you have 2 nodes, with 10 transitions that all
get you from start to the digit class node.

Obviously this is simplistic, because the members of the character
class form a subgraph which itself has to be recognized. The
important point here is that the subgraph as a whole can represent a
/single/ node in a much more complex graph - its constituent
characters need not be repeated in the complex graph. More on this
below.

A complex DFA that combines many different regex may present other
opportunities to recognize given (possibly arbitrary) sets of
characters - opportunites that may not be apparent from looking at the
constituent regex.

Post by Don Y
Would it recognize a common sequence of state transitions
that occurs in two different places in the grammar? E.g.,
specifying the syntax for a numeric quantity in two different
places only to realize that it's actually the same part of
the grammar expressed as two different instances?

When given the option to find equivalence classes, flex can identify
sets of characters that are used repeatedly. Those characters are
gathered into an "equivalence" that then can be a node in the DFA
instead of redundantly repeating individual characters.

Remember DFA are deterministic - a node can't take different actions
depending on which of multiple transitions entered (or left) it ... so
if you want the same character to be recognized in a different context
(leading to a different action), you must repeat it in a different
node.

This is where being able to identify, essentially arbitrary, sets of
character and coalesce them into a recognizer "class" is useful. If a
given set of N(>1) characters is used M times in the graph, then by
coalescing them you remove M(N-1) nodes from your graph. The number
of /transitions/ in the graph remains the same, but recall that it is
the /nodes/ that consume space in the lexer tables.

Post by Don Y
<number> ::= <digit><digits>
<value> ::= <digit><digits>
<expr> ::= <number> <op> <number> | <value> <op> <value>
(silly example; but the inputs in each case are the same)

You're mixing abstraction levels here: <digit>, <digits>, <number>,
and <value> are lexical tokens, whereas <expr> is syntax.

However ...

Knowing that yacc and bison CAN handle characters as tokens, and
assuming you have defined <digit> and <digits> elsewhere in your
grammar, neither yacc nor bison can find this kind of equivalence. In
yacc it will result in a reduce/reduce error. In bison what happens
depends on the kind of parser you asked for (LALR,SLR,LR,GLR), but in
any case the result won't be pretty.

Assuming instead that you meant for <number> and <value> to be
recognized by the lexer rather than the parser ... flex (not lex)
could discover that <number> and <value> are equivalent, but since
they would lead to different actions: returning a different token -
both would included in the DFA. However, whichever one happened to be
tried first would be the only one that ever was recognized, and your
parser would only ever get one of the expected tokens.

Post by George Neuner
yacc and lex are ancient and haven't been maintained for decades. They
have limitations that will never be addressed, and bugs that will
never be fixed. If you really need backward compatibility with them,
it is available using bison and flex ... and if you don't need bacward
compatibility, bison and flex are much more powerful and modern tools
for use with new projects.
[There are other modern alternatives to yacc and lex also, but
discussion of them is beyond the scope of this missive.]

Algorithms for turning graphs into table driven FSM, or equivalently a
switch / case statement, are well known.

Assuming an appropriate graphical IDE, a designer certainly could
specify a state graph and code for actions, and have a program
generated from it. Given the right input from the designer, a great
deal of checking could be done against the graph to verify that it
covers enumerated inputs and transitions, that specified inputs lead
to specified actions, that action code exists, etc.

But what is NOT possible is to verify that all /possible/ inputs and
state transitions have been enumerated. Nor is it possible to verify
that required actions have been specified, or necessarily that the
actions are being taken in proper context ... those are things for
which the tool simply MUST trust the graph designer.

George

Don Y

2023-03-15 02:40:07 UTC

Post by George Neuner
On Mon, 13 Mar 2023 22:59:25 -0700, Don Y