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

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

Text on FSM

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

Contents

  Text on FSM jmariano <jmariano65@gmail.com> - 2023-03-09 14:17 -0800
    Re: Text on FSM Rick C <gnuarm.deletethisbit@gmail.com> - 2023-03-09 16:52 -0800
    Re: Text on FSM Don Y <blockedofcourse@foo.invalid> - 2023-03-09 19:11 -0700
      Re: Text on FSM Bill Davy <Bill@XchelSys.co.uk> - 2023-03-10 08:37 +0000
        Re: Text on FSM Don Y <blockedofcourse@foo.invalid> - 2023-03-10 03:50 -0700
    Re: Text on FSM pozz <pozzugno@gmail.com> - 2023-03-10 09:54 +0100
      Re: Text on FSM Don Y <blockedofcourse@foo.invalid> - 2023-03-10 04:17 -0700
      Re: Text on FSM Robert Roland <fake@ddress.no> - 2023-03-10 12:48 +0100
        Re: Text on FSM Rick C <gnuarm.deletethisbit@gmail.com> - 2023-03-10 07:20 -0800
          Re: Text on FSM pozz <pozzugno@gmail.com> - 2023-03-13 16:35 +0100
            Re: Text on FSM StateMachineCOM <statemachineguru@gmail.com> - 2023-03-13 08:55 -0700
              Re: Text on FSM pozz <pozzugno@gmail.com> - 2023-03-14 15:44 +0100
            Re: Text on FSM Don Y <blockedofcourse@foo.invalid> - 2023-03-13 09:29 -0700
              Re: Text on FSM pozz <pozzugno@gmail.com> - 2023-03-14 15:54 +0100
                Re: Text on FSM Don Y <blockedofcourse@foo.invalid> - 2023-03-14 08:39 -0700
                Re: Text on FSM Niklas Holsti <niklas.holsti@tidorum.invalid> - 2023-03-14 18:49 +0200
        Re: Text on FSM Don Y <blockedofcourse@foo.invalid> - 2023-03-10 09:39 -0700
          Re: Text on FSM Don Y <blockedofcourse@foo.invalid> - 2023-03-10 10:02 -0700
          Re: Text on FSM Ed Prochak <edprochak@gmail.com> - 2023-03-10 10:10 -0800
            Re: Text on FSM Don Y <blockedofcourse@foo.invalid> - 2023-03-10 12:10 -0700
              Re: Text on FSM Don Y <blockedofcourse@foo.invalid> - 2023-03-10 12:49 -0700
              Re: Text on FSM Ed Prochak <edprochak@gmail.com> - 2023-03-10 14:02 -0800
                Re: Text on FSM Don Y <blockedofcourse@foo.invalid> - 2023-03-11 06:01 -0700
                  Re: Text on FSM Don Y <blockedofcourse@foo.invalid> - 2023-03-11 06:17 -0700
    Re: Text on FSM StateMachineCOM <statemachineguru@gmail.com> - 2023-03-10 07:54 -0800
    Re: Text on FSM jmariano <jmariano65@gmail.com> - 2023-03-10 09:51 -0800
      Re: Text on FSM Rick C <gnuarm.deletethisbit@gmail.com> - 2023-03-10 11:27 -0800
      Re: Text on FSM Don Y <blockedofcourse@foo.invalid> - 2023-03-10 12:46 -0700
      Re: Text on FSM Ed Prochak <edprochak@gmail.com> - 2023-03-10 13:11 -0800
      Re: Text on FSM Gerhard Hoffmann <dk4xp@arcor.de> - 2023-03-13 21:20 +0100
        Re: Text on FSM Don Y <blockedofcourse@foo.invalid> - 2023-03-13 15:41 -0700
          Re: Text on FSM George Neuner <gneuner2@comcast.net> - 2023-03-13 23:07 -0400
            Re: Text on FSM Don Y <blockedofcourse@foo.invalid> - 2023-03-13 22:59 -0700
              Re: Text on FSM George Neuner <gneuner2@comcast.net> - 2023-03-14 21:29 -0400
                Re: Text on FSM Don Y <blockedofcourse@foo.invalid> - 2023-03-14 19:40 -0700
                  Re: Text on FSM George Neuner <gneuner2@comcast.net> - 2023-03-22 16:37 -0400
                    Re: Text on FSM Don Y <blockedofcourse@foo.invalid> - 2023-03-22 18:15 -0700
                      Re: Text on FSM George Neuner <gneuner2@comcast.net> - 2023-03-26 00:45 -0400
                        Re: Text on FSM Don Y <blockedofcourse@foo.invalid> - 2023-03-26 03:35 -0700
                          Re: Text on FSM George Neuner <gneuner2@comcast.net> - 2023-03-27 02:32 -0400
                            Re: Text on FSM Don Y <blockedofcourse@foo.invalid> - 2023-03-27 01:16 -0700
                              Re: Text on FSM George Neuner <gneuner2@comcast.net> - 2023-03-28 15:25 -0400
                                Re: Text on FSM Don Y <blockedofcourse@foo.invalid> - 2023-03-28 16:56 -0700
                        Re: Text on FSM Clifford Heath <no.spam@please.net> - 2023-03-27 16:18 +1100
                          Re: Text on FSM George Neuner <gneuner2@comcast.net> - 2023-03-28 11:17 -0400
                            Re: Text on FSM Clifford Heath <no.spam@please.net> - 2023-03-29 09:00 +1100
                              Re: Text on FSM George Neuner <gneuner2@comcast.net> - 2023-03-28 21:27 -0400
                                Re: Text on FSM Clifford Heath <no.spam@please.net> - 2023-03-30 08:33 +1100
                            Re: Text on FSM Richard Damon <Richard@Damon-Family.org> - 2023-03-28 21:31 -0400
    Re: Text on FSM George Neuner <gneuner2@comcast.net> - 2023-03-10 16:49 -0500

Page 1 of 3  [1] 2 3  Next page →

#31632 — Text on FSM

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

[toc] | [next] | [standalone]

#31633

On Thursday, March 9, 2023 at 5:17:18 PM UTC-5, jmariano wrote:
> 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

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

#31634

On 3/9/2023 3:17 PM, jmariano wrote:
> 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).

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

#31635

On 10/03/2023 02:11, Don Y wrote:
> On 3/9/2023 3:17 PM, jmariano wrote:
>> 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).
> 

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

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

#31637

On 3/10/2023 1:37 AM, Bill Davy wrote:
> 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".

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

#31636

Il 09/03/2023 23:17, jmariano ha scritto:
> 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.
> Thanks
> jmariano

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.

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

#31638

On 3/10/2023 1:54 AM, pozz wrote:
> 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.
> 
> 

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

#31639

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

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

#31640

On Friday, March 10, 2023 at 6:48:13 AM UTC-5, 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. 

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

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

#31655

Il 10/03/2023 16:20, Rick C ha scritto:
> On Friday, March 10, 2023 at 6:48:13 AM UTC-5, 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.
> 
> 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.

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

#31656

> 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:
- https://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...

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

-  https://youtu.be/fLXxNe4YeJ4

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.

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

#31662

Il 13/03/2023 16:55, StateMachineCOM ha scritto:
>> 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:
> - https://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.


>> 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:
> 
> -  https://youtu.be/fLXxNe4YeJ4

I read your book ;-)


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

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

#31657

On 3/13/2023 8:35 AM, pozz wrote:
> 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!]

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

#31663

Il 13/03/2023 17:29, Don Y ha scritto:
> On 3/13/2023 8:35 AM, pozz wrote:
>> 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.


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

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


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

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


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

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

#31664

On 3/14/2023 7:54 AM, pozz wrote:
> Il 13/03/2023 17:29, Don Y ha scritto:
>> On 3/13/2023 8:35 AM, pozz wrote:
>>> 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!)

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

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

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

#31665

On 2023-03-14 16:54, pozz wrote:
> Il 13/03/2023 17:29, Don Y ha scritto:
>> On 3/13/2023 8:35 AM, pozz wrote:
>>> 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.


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.

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

#31642

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

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

#31643

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

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

#31645

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

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

#31646

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]

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

Page 1 of 3  [1] 2 3  Next page →

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

csiph-web