Do you use FSMs or HSMs?

[pozz]

I often encounter many problems when I have to implement a "behaviour"
in a microcontrollor. For example, I have some analog/digital inputs and
some user commands. Based on that, the logic should set some outputs
(digital or analog).

Most of the time you (the developer) must understand what is the good
behaviour of the machine, because noone is able to describe it in a good
way. I usually heard the sentence: when the user presses the ON button,
you switch on the engine.
After some short implementation, you understand that the engine should
be on only if the interlock input is closed.
And so on...

I think the best method to describe a machine behaviour is a
state-machine, mainly a hierarchically state-machine (HSM). Do you agree?

My post here is to understand if you really use HSMs to describe the
beahviour of the system you are coding and how do you implement them in
C or C++ (or whatever).

[Don Y]

*Always*. They act as a sort of "application specific language" to codify
behavior in a high level form.

I always implement them with an interpreter that takes a "current state"
and some number of "input variables", along with a set of tables defining
the transitions from each potential "current state" to other "next states"
(along with "action routines" to be executed when the transition is
made.

The manner in which the tables are encode varies based on what I expect
the needs of the machine being modeled to be.

For example, to accept a decimal value from a "digit source" (which could be
a keypad or a character stream received from a UART) I might code a little
machine:

STATE IDLE
; prompt and default value are displayed, here, and the FIRST digit is expected
CASE "CLEAR" GOTO IDLE EXECUTING no_op()
CASE '0' GOTO ENTRY EXECUTING first_digit()
CASE '1' GOTO ENTRY EXECUTING first_digit()
...
CASE '9' GOTO ENTRY EXECUTING first_digit()
CASE "ENTER" GOTO CHECK EXECUTING completed()
ORELSE GOTO same EXECUTING complain()

STATE ENTRY
; first digit has been entered, prompt and default value have been removed
CASE "CLEAR" GOTO IDLE EXECUTING restore_default()
CASE '0' GoTO DIGITS EXECUTING accept_digit()
CASE '1' GOTO DIGITS EXECUTING accept_digit()
...


no_op()
return

first_digit()
accumulator() = digit;
remove_prompt();
printf("%s: %d", shortened_prompt, accumulator)
return

accept_digit()
accumlator = 10 * accumulator + digit;
printf("%s: %d", shortened_prompt, accumulator)
return

complain()
beep()
return

restore_default()
accumulator = default_value;
printf("%s: %d", long_prompt, accumulator);
return

...

Obviously, another encoding might support a syntax like:
STATE ENTRY
; first digit has been entered, prompt and default value have been removed
CASE "CLEAR" GOTO IDLE EXECUTING no_op()
CASE '0' THRU '9' GOTO ENTRY EXECUTING first_digit()
...
CASE "ENTER" GOTO CHECK EXECUTING completed()
ORELSE GOTO same EXECUTING complain()

How you acquire "inputs" is also variable. You can force each input to appear
in a particular "variable" that the FSM interpreter polls (different variables
for different FSM's -- one interpreteer can handle multiple FSM's).

I prefer having a LIST of "input variables" that the FSM interpreter examines
sequentially. Individual "tasks" can then maintain their own "variables"
without having to coordinate a SHARED variable among many competing tasks.

E.g., the "keypad" task can have a "key_detected" variable that is LISTED
in those variables consumed by the above FSM. The example suggests this
variable would be a char -- though there is no requirement that it be so.

The task responsible for polling and debouncing keystrokes from the keypad
can watch the "key_detected" variable and, any time it is found to be
"empty" (NUL, by convention), can place the next enqueued keystroke into
that variable. It can then continue scanning/debouncing the keypad
while queuing subsequent keystrokes until the "key_detected" variable
is "not busy".

The FSM interpreter can then, by convention, CLEAR any variable that it
has acted upon to remove the stimulus from subsequent FSM iterations
AND "signal" the producer task that the consumer (the FSM!) has processed
the previous "event/datum" and is ready for another FROM THAT DATA SOURCE.

[This opens up lots of hacks -- like allowing a stimulus to be propagated
to the next state -- by NOT clearing it!]

Note that you can also deviate from conventional FSM implementations by
supporting "special" next state codes (e.g., "same" refers to the *current*
state -- don't transition to another state, just stay here!)

The number of variations in syntax and mechanisms is far too many to enumerate
here -- as are the encodings for the "state tables" illustrated above.

But, the point is, you can cleanly codify the behavior of an algorithm
without resorting to lots of spaghetti code and conditionals.

[Dave Nadler]

On Monday, February 6, 2017 at 4:43:26 AM UTC-5, pozz wrote:
> My post here is to understand if you really use HSMs to describe the
> beahviour of the system you are coding and how do you implement them in
> C or C++ (or whatever).

I often use FSMs but not formal HSMs.
Make sure you read Miro Samek's "Practical Statecharts in C/C++"
Never found a framework that fit nicely with my projects
though I read about lots of them, so seems like I keep redoing this.
Probably I should look at Miro Samek's latest open source offerings...

Let us know what you end up using this round,
Best Regards, Dave

[QL]

Let me start with the full disclosure: I'm the author of the book
"Practical UML Statecharts in C/C++, 2nd Edition" and I run a company
called Quantum Leaps that makes open-source state machine software
frameworks and a free state machine modeling tool. The company website
is:

http://www.state-machine.com


So, yes, I also strongly believe that hierarchical state machines (a.k.a.
UML statecharts) combined with event-driven programming are the best way
to go when it comes to developing real-time embedded software.

From my two decades of experience, however, I see that the biggest
obstacle in adopting state machines is the required paradigm shift from
sequential programming based on blocking (like blocking on a semaphore or
a time delay in a traditional RTOS or a "superloop") and the event-driven
programming based on run-to-completion event processing without blocking
(like in a state machine).

Anyway, if you are seriously interested in (hierarchical) state machines
for embedded real-time systems I would recommend to start with the key
concepts:

http://www.state-machine.com/doc/concepts.html


You might also wish to try the free state machine modeling tool called QM,
which allows you to draw hierarchical state machine diagrams and
automatically generate production-quality C or C++ code from them:

http://www.state-machine.com/qm


Miro Samek
www.state-machine.com

---------------------------------------
Posted through http://www.EmbeddedRelated.com

[John Speth]

> I think the best method to describe a machine behaviour is a
> state-machine, mainly a hierarchically state-machine (HSM). Do you agree?

FSM models are my #1 considered method for documenting required
behavior. But it's not always the best way. Some requirements sets
just don't lend themselves well to FSM diagrams. I find that sometimes
I'll sketch a FSM and then find out it's just too simple or too linear.
ON the flip side, I've had project for which I'd have an extremely
simple FSM documented and later it's starts to get elaborate and useful
as new requirements emerge.

JJS

[Tom Gardner]

On 06/02/17 17:17, John Speth wrote:
>> I think the best method to describe a machine behaviour is a
>> state-machine, mainly a hierarchically state-machine (HSM). Do you agree?
>
> FSM models are my #1 considered method for documenting required behavior. But
> it's not always the best way. Some requirements sets just don't lend themselves
> well to FSM diagrams.

Precisely.

A good engineer knows which tools to use/avoid
for each job.

> I find that sometimes I'll sketch a FSM and then find out
> it's just too simple or too linear. ON the flip side, I've had project for which
> I'd have an extremely simple FSM documented and later it's starts to get
> elaborate and useful as new requirements emerge.

Precisely.

A large part of engineering is being able to
demonstrate which part of an design implements
each part of the specification.

A good implementation of an FSM enables you
to easily see exactly what will happen when
any event occurs in any state. That can be very
difficult with if-then-else clauses.

[Don Y]

On 2/6/2017 11:03 AM, Tom Gardner wrote:
>> I find that sometimes I'll sketch a FSM and then find out
>> it's just too simple or too linear. ON the flip side, I've had project for which
>> I'd have an extremely simple FSM documented and later it's starts to get
>> elaborate and useful as new requirements emerge.
>
> Precisely.
>
> A large part of engineering is being able to
> demonstrate which part of an design implements
> each part of the specification.
>
> A good implementation of an FSM enables you
> to easily see exactly what will happen when
> any event occurs in any state. That can be very
> difficult with if-then-else clauses.

Exactly. IME, they are excellent for representing UI actions
along with other formal "protocols". They allow you to verify
by inspection that all possibilities are addressed and
addressed in the manner intended -- without having to
count nesting levels of conditionals, etc.
"Will this 'if' cover this condition in ALL states? Or,
does it only apply to some subset of the states, based on
where it is syntactically anchored?"

I'd *not* use one to implement a floating point package...

[Don Y]

On 2/6/2017 7:56 AM, QL wrote:
> So, yes, I also strongly believe that hierarchical state machines (a.k.a.
> UML statecharts) combined with event-driven programming are the best way
> to go when it comes to developing real-time embedded software.
>
> From my two decades of experience, however, I see that the biggest
> obstacle in adopting state machines is the required paradigm shift from
> sequential programming based on blocking (like blocking on a semaphore or
> a time delay in a traditional RTOS or a "superloop") and the event-driven
> programming based on run-to-completion event processing without blocking
> (like in a state machine).

The two aren't mutually exclusive. So, silly to limit yourself to
that mindset.

And, a "machine" doesn't have to be a cohesive, monolithic block of
code easily recognizable as "something special". It can, instead,
be coded "in-line" if the environment supports seemless redefinition
of program (task) entry points; the "current state" is then effectively
encoded in the "saved entry point" which is explicitly changed each time
you explicitly command it (yield()/reschedule())

In this way, you can undertake lengthy operations without resorting to
a preemptive MTOS/RTOS to ensure you aren't monopolizing the processor
as well as doing the same in a fully preemptive environment.

[Tom Gardner]

Yes, but...

They are very neat way of implementing parsing an ascii
string and turning it into a floating point number.
Each input character is an "event", and the states are
things like "skipping leading whitespace, parsing
before decimal point" etc. An "E" transitions from
"parsing before decimal point" or parsing after
decimal point" to "parsing exponent", and transitions
to "error" elsewhere.

E&OE, of course :)

[Don Y]

Different problem -- and one that could be "automated" with a
simple grammar/lex/yacc.

You'd find it hard to apply it to performing multiplications,
divisions, etc. in a way that was anywhere near as efficient
as the underlying instruction set!

[An FSM effectively gives you a new "language" layered atop
the native instruction set via any intermediate languages]

> Each input character is an "event", and the states are
> things like "skipping leading whitespace, parsing
> before decimal point" etc. An "E" transitions from
> "parsing before decimal point" or parsing after
> decimal point" to "parsing exponent", and transitions
> to "error" elsewhere.
>
> E&OE, of course :)

In a similar vein, using it to parse "messages" in some
arbitrary syntax. There, it makes it relatively easy to
add new "message options" without having to rewrite a
bunch of spaghetti code. *Or*, buffer an entire message
before it can be parsed.

I've often used it to decode barcode labels at higher
levels. I.e., use procedural mechanisms to process the
"raw video" into "characters"; then a FSM to decide which
sequences of characters are representative of valid messages.

In my implementations, an "action routine" (transition routine)
can perform a test on the data and then simulate a GO/NOGO
event that is the *only* "event" processed in the succeeding
state. It can then redirect the machine to the correct
next state based on some (possibly complex) computation
performed on "embedded" data (e.g., verifying a checksum
is not something that you would encode into the normal
state transitions; instead, compute it in the CHECK state
and then act on that GO/NOGO event in the DISPATCH state
that immediately follows)

At the same time, input from keypads, mains power detectors,
UART character streams, etc. can continue, being buffered
until the machine opts to examine them, again (based on
the significant events defined for THIS particular state).

Allowing inputs to simultaneously arrive from multiple
sources WITHOUT enforcing an ordering on them external
to the FSM lets you cascade machines, have machines
talking to each other while operating concurrently,
implement co-routine machines, etc.

It's just like designing synchronous hardware.

[Tom Gardner]

Yes, and I didn't spot that "loonie idea" was being
considered.

> Allowing inputs to simultaneously arrive from multiple
> sources WITHOUT enforcing an ordering on them external
> to the FSM lets you cascade machines, have machines
> talking to each other while operating concurrently,
> implement co-routine machines, etc.

Having architected and implemented soft-realtime
telecom billing systems, I can only agree :)

> It's just like designing synchronous hardware.

Oh, indeed.

I like playing a game with people that think
there is a difference between hardware and
software: get them to try to provide a test to
distinguish one from the other. They always fail.

It is best played in a pub, with a few pints,
after work.

[Don Y]

On 2/6/2017 3:12 PM, Tom Gardner wrote:
>> It's just like designing synchronous hardware.
>
> Oh, indeed.
>
> I like playing a game with people that think
> there is a difference between hardware and
> software: get them to try to provide a test to
> distinguish one from the other. They always fail.
>
> It is best played in a pub, with a few pints,
> after work.

My preference is for designing hardware. And, synchronous
circuits are hands-down easier to design/debug. So,
FSM's are almost /de rigueur/.

To me, it's only natural to use the same design techniques
when it comes to software. It also makes debugging easier
("things only change on -- FSM -- clock edges" :> ).

Some folks opt for *huge* tables that enumerate all inputs
for all current_states and declared next_states. Rarely is
this necessary (it's often a gross inefficiency -- in space).

The big advantage to software FSM implementations is that
you can implement all sorts of mechanisms that would be
costly or impractical to implement in hardware, at the
same level of abstraction. (e.g., specifying a "next_state"
of PREVIOUS_STATE!)

For newbies, the concept is usually a little unsettling.
They're looking for "the code" and, instead, their seeing
an abstract description of a machine with smatterings
of code around the edges.

("How can you CALL a FSM???" "Why not?!" :> )

But, I've yet to find someone who didn't ultimately embrace
the technology; its just too damn intuitive not to!

[Clifford Heath]

Lex is a language for describing a regular expression,
which it implements by turning it *into* an FSA.

You don't need yacc to parse FP numbers. Such parsers
are for handling languages that require unbounded state,
not finite state.

I'm also enthusiastic in using FSAs where appropriate,
but a lot of problems I face require unbounded state.
In either case, I tend not to do them long-hand - there
are good domain-specific languages to generate the code.

Clifford Heath.

[jim.bra...@ieee.org]

]> Anyway, if you are seriously interested in (hierarchical) state machines

]> for embedded real-time systems I would recommend to start with the key
]> concepts:

Not entirely enlightened on hierarchical state machines.
Gather that the lower level state "inherits" from the higher level state.
E.g., unless over-ridden, the lower level state defaults to the actions of the higher level state?

Side issue: in communications many states use a timer to have a time-out action, and the methodology/diagrams accommodate this?

[Don Y]

In my implementations, you can "call" (bad choice of terms but it is something
to which a programmer can easily relate!) a "state table" as if it had been
inserted into the current state table, "in line" (though it doesn't incur the
expected space penalty).

[likewise, common data entry FSMs "shared" in a larger UI FSM]

So, you take these common things and wrap them in a "pseudo state (table)"
and then reference (CALL) it from every state in which it should apply
(which might not be ALL states!)

E.g., I will embed power fail handling in such a pseudo table and add
it to every state that CAN support power fail handling (some might not
be designed to tolerate that exception). Likewise, power *recovery*
in the same pseudo table (each maintaining a separate FSM orthogonal
to the FSM in question and interacting with it in the applicable
"transition routines")

[Paul Rubin]

pozz <pozz...@gmail.com> writes:
> My post here is to understand if you really use HSMs to describe the
> beahviour of the system you are coding and how do you implement them
> in C or C++ (or whatever).

I looked up HSM in Wikipedia and see it's UML-speak for nested state
machines. I don't see exactly how it applies to the calculator example
but I've preferred to use multiple communicating processes with the
appearance blocking operations, rather than explicit state machines. Of
course you can simulate that with an event dispatcher and coroutines, or
alternatively do it with an RTOS and tasks. I suppose there is overhead
compared to a FSM or HSM approach, but on the big processors I use, it
hasn't been an issue.

[Don Y]

IME its not the space/time efficiency but, rather, the conciseness of
expression.

Designing/debugging an algorithm ("machine") with a state diagram is
*so* much easier to sort out what is happening -- and what ISN'T,
that should!

There are tools that can take diagramatic representations and
convert them to code. But, they make assumptions about the
implementation that constrain your solution space. Using the
design concept without committing to a particular implementation
style is where the biggest wins lie.

[And, there are "mechanical" ways that you can reduce the complexity
of state machines once you've settled on one that works]

However, just approaching the problem in a way that lends itself
to this sort of visualization makes a huge difference vs. trying to
trace paths through code (in potentially different process containers
or on different physical processors).

It also lends itself to having others (Manglement) review the
(planned) behavior without requiring them to understand the
latest implementation language, modeling language, etc.:
"What if a power fail event is signalled while I'm OVER HERE?
How is it handled if the user stalls his interaction at this
point -- which doesn't RECOGNIZE the event until after he has
done X, Y or Z?"

[Les Cargill]

pozz wrote:
> I often encounter many problems when I have to implement a "behaviour"
> in a microcontrollor. For example, I have some analog/digital inputs and
> some user commands. Based on that, the logic should set some outputs
> (digital or analog).
>
> Most of the time you (the developer) must understand what is the good
> behaviour of the machine, because noone is able to describe it in a good
> way. I usually heard the sentence: when the user presses the ON button,
> you switch on the engine.
> After some short implementation, you understand that the engine should
> be on only if the interlock input is closed.
> And so on...
>
> I think the best method to describe a machine behaviour is a
> state-machine, mainly a hierarchically state-machine (HSM). Do you agree?
>

It all depends. This being said, I do like state machines, mainly
because they lend well to comprehensive unit/regression test suites
and have some advantage in coverage measurement.

Hierarchical may or may not help that much.

> My post here is to understand if you really use HSMs to describe the
> beahviour of the system you are coding and how do you implement them in
> C or C++ (or whatever).
>

I have implemented them in multiple languages and programing paradigms.

--
Les Cargill

[Les Cargill]

A state of the higher level state can be another state machine.

> E.g., unless over-ridden, the lower level state defaults to the actions of the higher level state?
>

Probably, but events may resolve to the higher level state machine.
I am biased by the way ObjecTime/Rational did this.

> Side issue: in communications many states use a timer to have a time-out action, and the methodology/diagrams accommodate this?
>

To my knowledge they all do.

--
Les Cargill

[Les Cargill]

Just to be pedantic :), it's deterministic vs. non deterministic FA.
Deterministic FA are equivalent to regular expressions. NFA
are not, and very often, NFA are what we use for program control flow.

> I'm also enthusiastic in using FSAs where appropriate,
> but a lot of problems I face require unbounded state.

This is where NFA shine - they're less formal than DFA.

> In either case, I tend not to do them long-hand - there
> are good domain-specific languages to generate the code.
>
> Clifford Heath.

--
Les Cargill

[Les Cargill]

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

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

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

--
Les Cargill

[Paul Rubin]

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

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

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

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

[George Neuner]

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

>Clifford Heath wrote:
>
>> Lex is a language for describing a regular expression,
>> which it implements by turning it *into* an FSA.
>>
>> You don't need yacc to parse FP numbers. Such parsers
>> are for handling languages that require unbounded state,
>> not finite state.
>
>Just to be pedantic :), it's deterministic vs. non deterministic FA.
>Deterministic FA are equivalent to regular expressions. NFA
>are not, and very often, NFA are what we use for program control flow.

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

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

>> I'm also enthusiastic in using FSAs where appropriate,
>> but a lot of problems I face require unbounded state.
>
>This is where NFA shine - they're less formal than DFA.

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

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


George

[Clifford Heath]

I didn't mention determinism. Why did you?
I said "FSA", meaning Finite State Automaton.

>> I'm also enthusiastic in using FSAs where appropriate,
>> but a lot of problems I face require unbounded state.
>
> This is where NFA shine - they're less formal than DFA.

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

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

[Paul Rubin]

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

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

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

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

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

[pozz]

Il 06/02/2017 15:56, QL ha scritto:
> Let me start with the full disclosure: I'm the author of the book
> "Practical UML Statecharts in C/C++, 2nd Edition" and I run a company
> called Quantum Leaps that makes open-source state machine software
> frameworks and a free state machine modeling tool. The company website
> is:
>
> http://www.state-machine.com

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

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

> So, yes, I also strongly believe that hierarchical state machines (a.k.a.
> UML statecharts) combined with event-driven programming are the best way
> to go when it comes to developing real-time embedded software.
>
> From my two decades of experience, however, I see that the biggest
> obstacle in adopting state machines is the required paradigm shift from
> sequential programming based on blocking (like blocking on a semaphore or
> a time delay in a traditional RTOS or a "superloop") and the event-driven
> programming based on run-to-completion event processing without blocking
> (like in a state machine).

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

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

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

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

[Clifford Heath]

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

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

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

[Paul Rubin]

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

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

[Clifford Heath]

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

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

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

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

> and I explained.

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

Clifford Heath.

[Phil Hobbs]

Discharge a big cap into it. If it still works, it's software. ;)

Cheers

Phil Hobbs

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

160 North State Road #203
Briarcliff Manor NY 10510

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

[Tom Gardner]

Thus ruling out FPGAs :)

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

[Phil Hobbs]

On 02/08/2017 06:52 PM, Tom Gardner wrote:
<sniiiiip>

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

Curses, foiled again. ;)

[Les Cargill]

George Neuner wrote:
> On Mon, 6 Feb 2017 23:36:01 -0600, Les Cargill
> <lcarg...@comcast.com> wrote:
>
>> Clifford Heath wrote:
>>
>>> Lex is a language for describing a regular expression,
>>> which it implements by turning it *into* an FSA.
>>>
>>> You don't need yacc to parse FP numbers. Such parsers
>>> are for handling languages that require unbounded state,
>>> not finite state.
>>
>> Just to be pedantic :), it's deterministic vs. non deterministic FA.
>> Deterministic FA are equivalent to regular expressions. NFA
>> are not, and very often, NFA are what we use for program control flow.
>
> Every NFA is equivalent to some DFA, and either can be mechanically
> translated into the other. However the DFA version, in general, will
> have many more states: in the (theoretical) worst case, equal to the
> size of the power set of states in the NFA.
>

I've had perfectly good NFA deployed that I would hate
to have to translate into a regexp :)

As a practical matter ( and as you note ) , there is a very
significant tactical difference.

> But such explosive growth is very rare. In practice, the majority of
> elements in the power set of NFA states will represent either unwanted
> or redundant operations.
>
>
>>> I'm also enthusiastic in using FSAs where appropriate,
>>> but a lot of problems I face require unbounded state.
>>
>> This is where NFA shine - they're less formal than DFA.
>
> Not "less formal" per se if you are concerned about correctness.
> However, in general, NFA are easier to specify and to understand.
>

That's the key. As you say - there may be a (small) price in
the ability to demonstrate correctness.

The principal advantage is the ability to generate
nearly exhaustive test suites for them. It at least becomes a matter of
exploiting combinators.

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

--
Les Cargill

[Les Cargill]

Paul Rubin wrote:
> Les Cargill <lcarg...@comcast.com> writes:
>> It's always dangerous to generalize, but anything I can easily
>> make non-blocking I will.
>
> Ok, you prefer to handle the event dispatch manually, with callbacks or
> a switch around the protocol state. I know some people find that
> intuitive but I've never gotten the hang of it.
>

There are a small legion of approaches. It depends on the problem
domain.

But yeah - you dispatch event messages to a machine of some sort.

>> Some FSM oriented systems use an "actor" model where actors can be
>> threads or even pseudothreads[1], communicating with sequential
>> message passing.
>
> Yes, that's what I'm used to doing under the covers. Each thread waits
> for some action while appearing to block, and moves forward when the
> action occurs. Erlang is designed for programming in this style and
> some very complex, highly reliable systems (phone switches) have been
> programmed in it.
>

Most/many of the protocols for circuit switched phone systems
have explicit FSM drawn in the standards.

It's possible to have "pseudothreads", where the event sink
dispatches based on event type to whoever is waiting on that event.
This does not require a separate, O/S thread each. You maintain the
advantages of run-to-completion and in cases, can be done on
something which is too small for an O/S.

--
Les Cargill

[Paul Rubin]

Les Cargill <lcarg...@comcast.com> writes:
> It's possible to have "pseudothreads", where the event sink
> dispatches based on event type to whoever is waiting on that event.

Yes, this is what the Erlang runtime does under the hood. From the user
program's perspective it looks like OS processes, but they are very
lightweight--you can have many 1000s of them on a small computer, or
millions on a big one.

[Les Cargill]

ObjecTime did the same, as did Rational Rose.

--
Les Cargill

[Steve Watt]

In article <Xw6mA.154283$6N1....@fx09.am4>,

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

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

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

[Tom Gardner]

On 17/02/17 00:30, Steve Watt wrote:
> In article <Xw6mA.154283$6N1....@fx09.am4>,
> Tom Gardner <spam...@blueyonder.co.uk> wrote:
>> On 06/02/17 21:19, Don Y wrote:
>>> It's just like designing synchronous hardware.
>>
>> Oh, indeed.
>>
>> I like playing a game with people that think
>> there is a difference between hardware and
>> software: get them to try to provide a test to
>> distinguish one from the other. They always fail.
>>
>> It is best played in a pub, with a few pints,
>> after work.
>
> "I want to make these 15 changes. Can I have the changed model working
> tomorow and deployable next week?"

Sometimes software can become ossified; typical
unit-testing practices (in XP/TDD/agile methods)
actively encourage that.

I've seen a company where the software turnaround
time was 6 *months*, due to software that had grown
like a cancerous tumour, and inept internal structure.

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

It largely depends on how many are required. One-off
is more likely to be do-able in hardware.

> Mind, the definition of "working" when it comes to software is quite
> notably different than it is for hardware. Nothing quite like
> a fresh tapeout because the verification team didn't get enough time.

Ditto much hardware.

Summary: insufficient differences to be a useful test.