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

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

Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)?

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

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Mike Perkins <spam@spam.com> - 2017-12-10 14:56 +0000
    Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Les Cargill <lcargill99@comcast.com> - 2017-12-16 11:58 -0600
      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Ed Prochak <edprochak@gmail.com> - 2017-12-19 08:19 -0800
        Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm@gmail.com> - 2017-12-19 11:51 -0500
          Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Ed Prochak <edprochak@gmail.com> - 2018-01-02 14:58 -0800
          Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Les Cargill <lcargill99@comcast.com> - 2018-01-03 06:07 -0600
            Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-03 12:59 -0500
              Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Les Cargill <lcargill99@comcast.com> - 2018-01-03 17:59 -0600
                Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-04 03:33 -0500
                  Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-04 14:31 -0500
                    Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Rob Gaddi <rgaddi@highlandtechnology.invalid> - 2018-01-04 11:56 -0800
                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Les Cargill <lcargill99@comcast.com> - 2018-01-04 21:46 -0600
                    Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-04 16:46 -0800
                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Les Cargill <lcargill99@comcast.com> - 2018-01-04 21:47 -0600
                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-06 18:55 -0500
                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-07 00:54 +0000
                        Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-07 13:41 -0800
                          Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-07 23:32 +0000
                            Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-10 10:33 -0500
                              Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-10 16:29 +0000
                          Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? upsidedown@downunder.com - 2018-01-08 08:11 +0200
                            Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-07 23:05 -0800
                              Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? upsidedown@downunder.com - 2018-01-08 10:06 +0200
                                Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? David Brown <david.brown@hesbynett.no> - 2018-01-08 10:27 +0100
                                  Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-08 09:56 -0800
                                    Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-08 18:39 +0000
                                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-08 12:20 -0800
                                        Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-08 22:11 +0000
                                    Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? David Brown <david.brown@hesbynett.no> - 2018-01-08 22:26 +0100
                                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-08 22:23 +0000
                                        Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-08 14:44 -0800
                                          Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-08 23:06 +0000
                              Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-08 10:02 +0000
                            Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Les Cargill <lcargill99@comcast.com> - 2018-01-08 17:34 -0600
                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-06 22:29 -0500
                        Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-07 00:46 -0800
                    Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Les Cargill <lcargill99@comcast.com> - 2018-01-04 21:44 -0600
                    Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-05 09:12 +0000
                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Phil Hobbs <pcdhSpamMeSenseless@electrooptical.net> - 2018-01-05 21:40 -0500
                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Les Cargill <lcargill99@comcast.com> - 2018-01-05 21:29 -0600
                        Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-06 09:10 +0000
                          Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Les Cargill <lcargill99@comcast.com> - 2018-01-06 16:35 -0600
                            Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-07 01:04 +0000
                        Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-06 09:17 +0000
                          Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Les Cargill <lcargill99@comcast.com> - 2018-01-06 16:37 -0600
                            Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-07 01:11 +0000
                              Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-06 17:31 -0800
                                Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-07 01:52 +0000
                                  Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-07 00:39 -0800
                                    Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-07 09:55 +0000
                                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-07 10:43 -0800
                                        Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-07 19:35 +0000
                          Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-06 19:06 -0500
                            Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-06 16:58 -0800
                              Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-06 22:37 -0500
                                Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-07 00:58 -0800
                                  Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-07 09:32 -0500
                                    Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-07 10:53 -0800
                                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-10 11:40 -0500
                            Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-07 01:14 +0000
                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-06 18:57 -0500
                        Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-07 01:17 +0000
                          Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-06 22:40 -0500
                            Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-07 09:59 +0000

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

#27512

On 06/01/18 03:29, Les Cargill wrote:
> Tom Gardner wrote:
>> On 04/01/18 19:31, rickman wrote:
>>> rickman wrote on 1/4/2018 3:33 AM:
>>>> Les Cargill wrote on 1/3/2018 6:59 PM:
>>>>> rickman wrote:
>>>>>> Les Cargill wrote on 1/3/2018 7:07 AM:
>>>>>>> rickman wrote:
>>>>>>>> Ed Prochak wrote on 12/19/2017 11:19 AM:
>>>>>>>>> On Saturday, December 16, 2017 at 12:56:31 PM UTC-5, Les Cargill wrote:
>>>>>>>>>> Mike Perkins wrote:
>>>>>>>>>>> On 09/12/2017 16:05, pozz wrote:
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> I use it where I have a number of 'tasks' which then interact with each
>>>>>>>>>>> other.
>>>>>>>>>>>
>>>>>>>>>>> If your system is a pure state machine then there is no need for an
>>>>>>>>>>> RTOS.
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> Indeed. Indeed.
>>>>>>>>>
>>>>>>>>> If it is just one state machine. Then yes, indeed.
>>>>>>>>> ed
>>>>>>>>
>>>>>>>> It can always be one state machine.  The only issue is how complex the
>>>>>>>> combined state machine is.
>>>>>>>>
>>>>>>>
>>>>>>> It's always a case of "how long should a man's legs be?" Lincoln
>>>>>>> is alleged to have said "long enough to touch the ground."
>>>>>>>
>>>>>>>> Actually the issue is not how many state machines you have.  It is the
>>>>>>>> timing requirements of the various state machines.  If your timing is lax,
>>>>>>>> sequential operation of multiple machines is easy.  But this often becomes
>>>>>>>> a huge discussion with everyone talking past each other.
>>>>>>>>
>>>>>>>
>>>>>>> They should use state machines to keep track then :)
>>>>>>>
>>>>>>> If your system can be decomposed as roughly events cross
>>>>>>> state, you have a snowball's chance of "understanding" it.
>>>>>>
>>>>>> Sorry, I don't know what this means "roughly events cross state".
>>>>>>
>>>>>>
>>>>>
>>>>> You are in state A. Event 42 occurs. Lookup.... ah, here -
>>>>> if we get event 42 whilst in state A, we move to state B
>>>>> and send message m.
>>>>
>>>> So what makes that so hard to understand?
>>>
>>> To be more explicit, I think every FSM I've ever coded was along the lines of a
>>> case statement on the state with IF conditions on all the interesting inputs.  I
>>> find this structure to be self documenting if the signal names are chosen well.
>>>
>>> Why is this structure hard to understand?
>>
>> I've seen a commercial case where that type of structure was
>> mutated by people under pressure to:
>>   - have a single state machine for all different customers
>>   - make the minimum change
>>   - do it fast
>>   - where the original designers had left
>>   - a custom domain specific language, ugh
>>
>> The result was an unholy unmaintainable mess, with
>> if-then-elses nested up to 10 (ten!) deep.
>>
>
> Eh, doing it totally, totally wrong. With all due respect - you really
> need a configuration system managed well within the code itself, and
> customer specializations are but different settings.

I didn't have due respect; I had due disrespect.

It was all contained in a configuration system, that
bloated wrong-headed pile of ordure IBM Rational
Clearcase.

I once, and only once, looked at the version trees.
For a couple of years it was respectable and sane:
a trunk with a few branches. Then it exploded over
the screen and looked like a plant with a serious
enzyme disorder: there were even backwards branching
loops. I have no idea how they achieved that nor why
(other that get it out the door tomorrow).


> On one product, the "model number' was nothing more than a name
> that pointed to a hard table of defaults for the configuration,
> and further config changes were possible. If the support
> people requested it, we'd grow a model number when they got too painful.
>
> That being said - OO and configuration go together like chalk and cheese
> :)
>
>> Completely insane, of course.
>>
>
> Well, yeah. You can make anything disgusting
> if you work hard enough :)

And they did work hard enough; enhancements were
positively sclerotic.



>> My preference is for a dispatch table based on event+state,
>> since that forces you to consider all possibilities.
>
> Yup yup. And you can generate a test vector for it with combinators.
> Then testing essentially becomes compressing the output - tedious, but
> ... rewarding.
>
> If the tested FSM is properly tested, then all remaining
> defects are 1) either tweak/tone of unrealistic expectations or
> 2) hardware bugs.
>
>> The
>> dispatch table can be either a 2D array of function pointers,
>> or inherent in an OOP inheritance hierarchy where the
>> hierarchy is a direct mirror of the state hierarchy.
>
>
> There's something to be said for the 2d approach. It's
> more canonical ( and more normal ) for one.

Agreed, but it can be convenient to express the design
in other terms. For example:
  - the top level catches events that have not been dealt
    with elsewhere; I prefer this to be a "should not
    happen" which is logged
  - next level down is divided into a small number of
    superstates, maybe "initialising", "working normally",
    "gross fault recovery"
  - bottom level is the normal states, e.g. "door open",
    "door closed", "fire alarm", etc
Events are "delivered" to the bottom level and, if not
handled, percolate up to the next level. Levels naturally
correspond to an OOP class hierarchy.

That's nothing new, see Harel's StateCharts. Having said
that, I'm not overly fond of some aspects of StateCharts.

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

#27518

Tom Gardner wrote:
> On 06/01/18 03:29, Les Cargill wrote:
>> Tom Gardner wrote:
>>> On 04/01/18 19:31, rickman wrote:
>>>> rickman wrote on 1/4/2018 3:33 AM:
>>>>> Les Cargill wrote on 1/3/2018 6:59 PM:
>>>>>> rickman wrote:
>>>>>>> Les Cargill wrote on 1/3/2018 7:07 AM:
>>>>>>>> rickman wrote:
>>>>>>>>> Ed Prochak wrote on 12/19/2017 11:19 AM:
>>>>>>>>>> On Saturday, December 16, 2017 at 12:56:31 PM UTC-5, Les 
>>>>>>>>>> Cargill wrote:
>>>>>>>>>>> Mike Perkins wrote:
>>>>>>>>>>>> On 09/12/2017 16:05, pozz wrote:
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> I use it where I have a number of 'tasks' which then 
>>>>>>>>>>>> interact with each
>>>>>>>>>>>> other.
>>>>>>>>>>>>
>>>>>>>>>>>> If your system is a pure state machine then there is no need 
>>>>>>>>>>>> for an
>>>>>>>>>>>> RTOS.
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> Indeed. Indeed.
>>>>>>>>>>
>>>>>>>>>> If it is just one state machine. Then yes, indeed.
>>>>>>>>>> ed
>>>>>>>>>
>>>>>>>>> It can always be one state machine.  The only issue is how 
>>>>>>>>> complex the
>>>>>>>>> combined state machine is.
>>>>>>>>>
>>>>>>>>
>>>>>>>> It's always a case of "how long should a man's legs be?" Lincoln
>>>>>>>> is alleged to have said "long enough to touch the ground."
>>>>>>>>
>>>>>>>>> Actually the issue is not how many state machines you have.  It 
>>>>>>>>> is the
>>>>>>>>> timing requirements of the various state machines.  If your 
>>>>>>>>> timing is lax,
>>>>>>>>> sequential operation of multiple machines is easy.  But this 
>>>>>>>>> often becomes
>>>>>>>>> a huge discussion with everyone talking past each other.
>>>>>>>>>
>>>>>>>>
>>>>>>>> They should use state machines to keep track then :)
>>>>>>>>
>>>>>>>> If your system can be decomposed as roughly events cross
>>>>>>>> state, you have a snowball's chance of "understanding" it.
>>>>>>>
>>>>>>> Sorry, I don't know what this means "roughly events cross state".
>>>>>>>
>>>>>>>
>>>>>>
>>>>>> You are in state A. Event 42 occurs. Lookup.... ah, here -
>>>>>> if we get event 42 whilst in state A, we move to state B
>>>>>> and send message m.
>>>>>
>>>>> So what makes that so hard to understand?
>>>>
>>>> To be more explicit, I think every FSM I've ever coded was along the 
>>>> lines of a
>>>> case statement on the state with IF conditions on all the 
>>>> interesting inputs.  I
>>>> find this structure to be self documenting if the signal names are 
>>>> chosen well.
>>>>
>>>> Why is this structure hard to understand?
>>>
>>> I've seen a commercial case where that type of structure was
>>> mutated by people under pressure to:
>>>   - have a single state machine for all different customers
>>>   - make the minimum change
>>>   - do it fast
>>>   - where the original designers had left
>>>   - a custom domain specific language, ugh
>>>
>>> The result was an unholy unmaintainable mess, with
>>> if-then-elses nested up to 10 (ten!) deep.
>>>
>>
>> Eh, doing it totally, totally wrong. With all due respect - you really
>> need a configuration system managed well within the code itself, and
>> customer specializations are but different settings.
> 
> I didn't have due respect; I had due disrespect.
> 
> It was all contained in a configuration system, that
> bloated wrong-headed pile of ordure IBM Rational
> Clearcase.
> 

We've all been there.

I worked one place where the software chief published a
config spec daily ( or even more often ).

This being said, CM people
have a natural affinity for ClearCase.

> I once, and only once, looked at the version trees.
> For a couple of years it was respectable and sane:
> a trunk with a few branches. Then it exploded over
> the screen and looked like a plant with a serious
> enzyme disorder: there were even backwards branching
> loops. I have no idea how they achieved that nor why
> (other that get it out the door tomorrow).
> 
> 
>> On one product, the "model number' was nothing more than a name
>> that pointed to a hard table of defaults for the configuration,
>> and further config changes were possible. If the support
>> people requested it, we'd grow a model number when they got too painful.
>>
>> That being said - OO and configuration go together like chalk and cheese
>> :)
>>
>>> Completely insane, of course.
>>>
>>
>> Well, yeah. You can make anything disgusting
>> if you work hard enough :)
> 
> And they did work hard enough; enhancements were
> positively sclerotic.
> 
> 
> 
>>> My preference is for a dispatch table based on event+state,
>>> since that forces you to consider all possibilities.
>>
>> Yup yup. And you can generate a test vector for it with combinators.
>> Then testing essentially becomes compressing the output - tedious, but
>> ... rewarding.
>>
>> If the tested FSM is properly tested, then all remaining
>> defects are 1) either tweak/tone of unrealistic expectations or
>> 2) hardware bugs.
>>
>>> The
>>> dispatch table can be either a 2D array of function pointers,
>>> or inherent in an OOP inheritance hierarchy where the
>>> hierarchy is a direct mirror of the state hierarchy.
>>
>>
>> There's something to be said for the 2d approach. It's
>> more canonical ( and more normal ) for one.
> 
> Agreed, but it can be convenient to express the design
> in other terms. For example:
>   - the top level catches events that have not been dealt
>     with elsewhere; I prefer this to be a "should not
>     happen" which is logged
>   - next level down is divided into a small number of
>     superstates, maybe "initialising", "working normally",
>     "gross fault recovery"
>   - bottom level is the normal states, e.g. "door open",
>     "door closed", "fire alarm", etc
> Events are "delivered" to the bottom level and, if not
> handled, percolate up to the next level. Levels naturally
> correspond to an OOP class hierarchy.
> 

To an extent, that's true. It seemed to make the systems
engineers happier than the software guys.

> That's nothing new, see Harel's StateCharts. Having said
> that, I'm not overly fond of some aspects of StateCharts.

Right. But they're adaptable.

-- 
Les Cargill

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

#27527

On 06/01/18 22:35, Les Cargill wrote:
> Tom Gardner wrote:
>> On 06/01/18 03:29, Les Cargill wrote:
>>> Tom Gardner wrote:
>>>> On 04/01/18 19:31, rickman wrote:
>>>>> rickman wrote on 1/4/2018 3:33 AM:
>>>>>> Les Cargill wrote on 1/3/2018 6:59 PM:
>>>>>>> rickman wrote:
>>>>>>>> Les Cargill wrote on 1/3/2018 7:07 AM:
>>>>>>>>> rickman wrote:
>>>>>>>>>> Ed Prochak wrote on 12/19/2017 11:19 AM:
>>>>>>>>>>> On Saturday, December 16, 2017 at 12:56:31 PM UTC-5, Les Cargill wrote:
>>>>>>>>>>>> Mike Perkins wrote:
>>>>>>>>>>>>> On 09/12/2017 16:05, pozz wrote:
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> I use it where I have a number of 'tasks' which then interact with
>>>>>>>>>>>>> each
>>>>>>>>>>>>> other.
>>>>>>>>>>>>>
>>>>>>>>>>>>> If your system is a pure state machine then there is no need for an
>>>>>>>>>>>>> RTOS.
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> Indeed. Indeed.
>>>>>>>>>>>
>>>>>>>>>>> If it is just one state machine. Then yes, indeed.
>>>>>>>>>>> ed
>>>>>>>>>>
>>>>>>>>>> It can always be one state machine.  The only issue is how complex the
>>>>>>>>>> combined state machine is.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> It's always a case of "how long should a man's legs be?" Lincoln
>>>>>>>>> is alleged to have said "long enough to touch the ground."
>>>>>>>>>
>>>>>>>>>> Actually the issue is not how many state machines you have.  It is the
>>>>>>>>>> timing requirements of the various state machines.  If your timing is
>>>>>>>>>> lax,
>>>>>>>>>> sequential operation of multiple machines is easy.  But this often
>>>>>>>>>> becomes
>>>>>>>>>> a huge discussion with everyone talking past each other.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> They should use state machines to keep track then :)
>>>>>>>>>
>>>>>>>>> If your system can be decomposed as roughly events cross
>>>>>>>>> state, you have a snowball's chance of "understanding" it.
>>>>>>>>
>>>>>>>> Sorry, I don't know what this means "roughly events cross state".
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>> You are in state A. Event 42 occurs. Lookup.... ah, here -
>>>>>>> if we get event 42 whilst in state A, we move to state B
>>>>>>> and send message m.
>>>>>>
>>>>>> So what makes that so hard to understand?
>>>>>
>>>>> To be more explicit, I think every FSM I've ever coded was along the lines
>>>>> of a
>>>>> case statement on the state with IF conditions on all the interesting
>>>>> inputs.  I
>>>>> find this structure to be self documenting if the signal names are chosen
>>>>> well.
>>>>>
>>>>> Why is this structure hard to understand?
>>>>
>>>> I've seen a commercial case where that type of structure was
>>>> mutated by people under pressure to:
>>>>   - have a single state machine for all different customers
>>>>   - make the minimum change
>>>>   - do it fast
>>>>   - where the original designers had left
>>>>   - a custom domain specific language, ugh
>>>>
>>>> The result was an unholy unmaintainable mess, with
>>>> if-then-elses nested up to 10 (ten!) deep.
>>>>
>>>
>>> Eh, doing it totally, totally wrong. With all due respect - you really
>>> need a configuration system managed well within the code itself, and
>>> customer specializations are but different settings.
>>
>> I didn't have due respect; I had due disrespect.
>>
>> It was all contained in a configuration system, that
>> bloated wrong-headed pile of ordure IBM Rational
>> Clearcase.
>>
>
> We've all been there.
>
> I worked one place where the software chief published a
> config spec daily ( or even more often ).
>
> This being said, CM people
> have a natural affinity for ClearCase.

I was able to clear the Augean stable and base the next
generation on plain old simple source code repositories.
/Much/ easier and faster and simpler to operate.

Naturally it is still /possible/ to create cancerous
trees; the only thing preventing that is good taste :(


>> I once, and only once, looked at the version trees.
>> For a couple of years it was respectable and sane:
>> a trunk with a few branches. Then it exploded over
>> the screen and looked like a plant with a serious
>> enzyme disorder: there were even backwards branching
>> loops. I have no idea how they achieved that nor why
>> (other that get it out the door tomorrow).
>>
>>
>>> On one product, the "model number' was nothing more than a name
>>> that pointed to a hard table of defaults for the configuration,
>>> and further config changes were possible. If the support
>>> people requested it, we'd grow a model number when they got too painful.
>>>
>>> That being said - OO and configuration go together like chalk and cheese
>>> :)
>>>
>>>> Completely insane, of course.
>>>>
>>>
>>> Well, yeah. You can make anything disgusting
>>> if you work hard enough :)
>>
>> And they did work hard enough; enhancements were
>> positively sclerotic.
>>
>>
>>
>>>> My preference is for a dispatch table based on event+state,
>>>> since that forces you to consider all possibilities.
>>>
>>> Yup yup. And you can generate a test vector for it with combinators.
>>> Then testing essentially becomes compressing the output - tedious, but
>>> ... rewarding.
>>>
>>> If the tested FSM is properly tested, then all remaining
>>> defects are 1) either tweak/tone of unrealistic expectations or
>>> 2) hardware bugs.
>>>
>>>> The
>>>> dispatch table can be either a 2D array of function pointers,
>>>> or inherent in an OOP inheritance hierarchy where the
>>>> hierarchy is a direct mirror of the state hierarchy.
>>>
>>>
>>> There's something to be said for the 2d approach. It's
>>> more canonical ( and more normal ) for one.
>>
>> Agreed, but it can be convenient to express the design
>> in other terms. For example:
>>   - the top level catches events that have not been dealt
>>     with elsewhere; I prefer this to be a "should not
>>     happen" which is logged
>>   - next level down is divided into a small number of
>>     superstates, maybe "initialising", "working normally",
>>     "gross fault recovery"
>>   - bottom level is the normal states, e.g. "door open",
>>     "door closed", "fire alarm", etc
>> Events are "delivered" to the bottom level and, if not
>> handled, percolate up to the next level. Levels naturally
>> correspond to an OOP class hierarchy.
>>
>
> To an extent, that's true. It seemed to make the systems
> engineers happier than the software guys.

I wonder why? I've found the design pattern outlined above
to be simple to comprehend and modify.

It does, however, tend to need some boilerplate (hence
ignorable) "trampoline" methods to get an incoming event
to the appropriate method (event handler) in the appropriate
class (state). Some might object to that, but often they
can be places to insert logging functions.


>> That's nothing new, see Harel's StateCharts. Having said
>> that, I'm not overly fond of some aspects of StateCharts.
>
> Right. But they're adaptable.

I merely used them as inspiration. Where there was
a choice between compliance with Statechart semantics
and fast simple code design patterns, I chose the latter.

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

#27513

On 06/01/18 03:29, Les Cargill wrote:
> Tom Gardner wrote:
>> My preference is for a dispatch table based on event+state,
>> since that forces you to consider all possibilities.
>
> Yup yup. And you can generate a test vector for it with combinators.
> Then testing essentially becomes compressing the output - tedious, but
> ... rewarding.
>
> If the tested FSM is properly tested, then all remaining
> defects are 1) either tweak/tone of unrealistic expectations or
> 2) hardware bugs.

Unfortunately you can't test FSMs "properly", for my
definition of "properly" :) That's based on the
unfashionable and inconvenient concept that "you
can't test quality into a product".

For the systems I've designed, there's a lot to
be gained by keeping a compressed log of "state
trajectory" around until not needed. That plus
accurate timestamping of events to/from external
systems has enabled me to quickly and unambiguously
deflect blame away from my stuff and onto other
companies. The lawyers were never even called :)

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

#27519

Tom Gardner wrote:
> On 06/01/18 03:29, Les Cargill wrote:
>> Tom Gardner wrote:
>>> My preference is for a dispatch table based on event+state,
>>> since that forces you to consider all possibilities.
>>
>> Yup yup. And you can generate a test vector for it with combinators.
>> Then testing essentially becomes compressing the output - tedious, but
>> ... rewarding.
>>
>> If the tested FSM is properly tested, then all remaining
>> defects are 1) either tweak/tone of unrealistic expectations or
>> 2) hardware bugs.
> 
> Unfortunately you can't test FSMs "properly", for my
> definition of "properly" :) That's based on the
> unfashionable and inconvenient concept that "you
> can't test quality into a product".
> 

Wait; you *can* do proofs on FSMs. "Quality" is
sufficiently nebulous and subjective to be a
not-a-thing.

> For the systems I've designed, there's a lot to
> be gained by keeping a compressed log of "state
> trajectory" around until not needed.


Yep yep....

> That plus
> accurate timestamping of events to/from external
> systems has enabled me to quickly and unambiguously
> deflect blame away from my stuff and onto other
> companies. The lawyers were never even called :)
> 

Exactly. Precisely even that.

-- 
Les Cargill

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

#27528

On 06/01/18 22:37, Les Cargill wrote:
> Tom Gardner wrote:
>> On 06/01/18 03:29, Les Cargill wrote:
>>> Tom Gardner wrote:
>>>> My preference is for a dispatch table based on event+state,
>>>> since that forces you to consider all possibilities.
>>>
>>> Yup yup. And you can generate a test vector for it with combinators.
>>> Then testing essentially becomes compressing the output - tedious, but
>>> ... rewarding.
>>>
>>> If the tested FSM is properly tested, then all remaining
>>> defects are 1) either tweak/tone of unrealistic expectations or
>>> 2) hardware bugs.
>>
>> Unfortunately you can't test FSMs "properly", for my
>> definition of "properly" :) That's based on the
>> unfashionable and inconvenient concept that "you
>> can't test quality into a product".
>>
>
> Wait; you *can* do proofs on FSMs.

In theory yes, in practice combinatorial explosion
is a problem. I well remember (c 1990) a neighbouring
group being very pleased they had been able to prove
some FSMs lock free.

We showed them the FSMs from the networking protocol
for the LANs we were developing; they gulped and went
silent :) I strongly suspect the same would have been
true for the telecom protocols I used 20 years later.


> "Quality" is
> sufficiently nebulous and subjective to be a
> not-a-thing.
>
>> For the systems I've designed, there's a lot to
>> be gained by keeping a compressed log of "state
>> trajectory" around until not needed.
>
>
> Yep yep....
>
>> That plus
>> accurate timestamping of events to/from external
>> systems has enabled me to quickly and unambiguously
>> deflect blame away from my stuff and onto other
>> companies. The lawyers were never even called :)
>>
>
> Exactly. Precisely even that.

It is really pleasant to be able to smile sweetly
at rabid XP/Agile/YAGNI dogmatists, and say "see, we
/did/ need that" :)

(For the avoidance of doubt, XP/Agile can be very
valuable techniques when tastefully deployed
alongside other techniques)

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

#27531

Tom Gardner <spamjunk@blueyonder.co.uk> writes:
> In theory yes, in practice combinatorial explosion is a problem. I
> well remember (c 1990) a neighbouring group being very pleased they
> had been able to prove some FSMs lock free.

It's still not trivial but things have improved a lot since the 1990s
(https://techpolicy.acm.org/?p=572):

  A drawback of the Model Checking approach, known as the state-explosion
  problem, seemed to limit its applicability to small designs of mainly
  academic interest. Randal Bryant, Edmund Clarke, Allen Emerson and
  Kenneth McMillan invented Symbolic Model Checking, which greatly
  extended the size and complexity of systems that could be verified. It
  also led to the widespread adoption of Model Checking by the computer
  hardware industry. For this invention, Bryant, Clarke, Emerson, and
  McMillan received the 1998 Paris Kanellakis Award for Theory and
  Practice from ACM. In 1999, they also received the Allen Newell Award
  for Research Excellence from Carnegie Mellon University. Sifakis,
  together with Thomas A. Henzinger and Sergio Yovine, extended the Model
  Checking approach to address verification of real time systems. In 2001,
  Sifakis received the Centre National de la Recherche Scientifique Silver
  Medal.

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

#27533

On 07/01/18 01:31, Paul Rubin wrote:
> Tom Gardner <spamjunk@blueyonder.co.uk> writes:
>> In theory yes, in practice combinatorial explosion is a problem. I
>> well remember (c 1990) a neighbouring group being very pleased they
>> had been able to prove some FSMs lock free.
>
> It's still not trivial but things have improved a lot since the 1990s
> (https://techpolicy.acm.org/?p=572):
>
>   A drawback of the Model Checking approach, known as the state-explosion
>   problem, seemed to limit its applicability to small designs of mainly
>   academic interest. Randal Bryant, Edmund Clarke, Allen Emerson and
>   Kenneth McMillan invented Symbolic Model Checking, which greatly
>   extended the size and complexity of systems that could be verified. It
>   also led to the widespread adoption of Model Checking by the computer
>   hardware industry. For this invention, Bryant, Clarke, Emerson, and
>   McMillan received the 1998 Paris Kanellakis Award for Theory and
>   Practice from ACM. In 1999, they also received the Allen Newell Award
>   for Research Excellence from Carnegie Mellon University. Sifakis,
>   together with Thomas A. Henzinger and Sergio Yovine, extended the Model
>   Checking approach to address verification of real time systems. In 2001,
>   Sifakis received the Centre National de la Recherche Scientifique Silver
>   Medal.

Well I certainly hope that's the case, but he
formal methods crowd has a tendency to underestimate
the complexity of practical FSM!

Hence I'd like to see some independent assessment
on some _existing_ real-world protocols/FSMs. Failing
that, how do their techniques perform when developing
_new_ protocols/FSMs? If they are generally a help,
then that would be great!

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

#27537

Tom Gardner <spamjunk@blueyonder.co.uk> writes:
> Hence I'd like to see some independent assessment on some _existing_
> real-world protocols/FSMs.

I don't know where to find any of those.  Got any suggestions?

> Failing that, how do their techniques perform when developing _new_
> protocols/FSMs? If they are generally a help, then that would be
> great!

I'd be interested to know what you think of ImProve.  The link I gave
earlier:

  https://github.com/tomahawkins/improve/wiki/ImProve

I'd look at the "verification primer" section to get an idea of what it
does.  Don't worry about understanding the syntax etc, which takes some
getting used to.

The basic approach is to control the state space explosion using a SAT
solver.  Those have gotten very powerful in recent years.  They might
get even more powerful with reinforcement learning techniques soon.

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

#27540

On 07/01/18 08:39, Paul Rubin wrote:
> Tom Gardner <spamjunk@blueyonder.co.uk> writes:
>> Hence I'd like to see some independent assessment on some _existing_
>> real-world protocols/FSMs.
>
> I don't know where to find any of those.  Got any suggestions?

The early 90s one was the FDDI token ring LAN. The
various FSMs had to deal with lost token, duplicated token,
broken links, split and reconnected rings, traffic priority
_etc_.

IMNSHO there's a reason why nice simple ethernet is
common today and token rings aren't :)

The naughties ones were telecoms protocols such as
ETSI Parlay. Those specific protocols were not much
more than an attempt to provide a common interface
that would simplify connecting one telco's equipment
to another. The problem was they manufacturers all
implemented slightly different versions of the
underlying protocols, so the Parlay specs tended
to be a lowest common _multiple_ (but where each
manufacturer only implemented a subset!)

Quite frankly, you would have to be brave to look
spend time looking at such horrors!



>> Failing that, how do their techniques perform when developing _new_
>> protocols/FSMs? If they are generally a help, then that would be
>> great!
>
> I'd be interested to know what you think of ImProve.  The link I gave
> earlier:
>
>   https://github.com/tomahawkins/improve/wiki/ImProve
>
> I'd look at the "verification primer" section to get an idea of what it
> does.  Don't worry about understanding the syntax etc, which takes some
> getting used to.
>
> The basic approach is to control the state space explosion using a SAT
> solver.  Those have gotten very powerful in recent years.  They might
> get even more powerful with reinforcement learning techniques soon.

I'll have a quick look at that; thanks. I wonder
how much I will understand? :)

Ideally there would be some simple pedagogical
examples, _plus_ some statements of success with
"real world" protocols.

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

#27546

Tom Gardner <spamjunk@blueyonder.co.uk> writes:
>> I don't know where to find any of those.  Got any suggestions?
> The early 90s one was the FDDI token ring LAN.

Well, I meant I hoped for a url that I could look at, with a not too
verbose description of the FSMs.

> The various FSMs had to deal with lost token, duplicated token, broken
> links, split and reconnected rings, traffic priority _etc_.

Without knowing the requirements I can't tell why this has to be
implemented with FSMs.

> I'll have a quick look at that; thanks. I wonder how much I will
> understand? :)

Basically that you write the requirements in what I hope is a
comprehensible way, and also write the code in a fairly traditional way
(except for the weird syntax).  The prover then verifies that the code
implements the requirements.

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

#27548

On 07/01/18 18:43, Paul Rubin wrote:
> Tom Gardner <spamjunk@blueyonder.co.uk> writes:
>>> I don't know where to find any of those.  Got any suggestions?
>> The early 90s one was the FDDI token ring LAN.
>
> Well, I meant I hoped for a url that I could look at, with a not too
> verbose description of the FSMs.

I haven't looked at it in 25 years; I have no idea whether
there are any live FDDI rings!


>> The various FSMs had to deal with lost token, duplicated token, broken
>> links, split and reconnected rings, traffic priority _etc_.
>
> Without knowing the requirements I can't tell why this has to be
> implemented with FSMs.

It was defined/specified that way in the FDDI standards.

I can't think of a better way to define/specify and
implement such functionality.


>> I'll have a quick look at that; thanks. I wonder how much I will
>> understand? :)
>
> Basically that you write the requirements in what I hope is a
> comprehensible way, and also write the code in a fairly traditional way
> (except for the weird syntax).  The prover then verifies that the code
> implements the requirements.

I had a quick skim of the "verification primer" and,
quite reasonably, it is a small simple pedagogical example.
It is of similar size to the examples I saw in the early
90s, and isn't representative of the FSMs I've had to deal
with.

The kind of thing I'd like to see is
  - presuming a token ring is partitioned and then reconnected
  - define the maximum time that two tokens can be circulating
      - before detection, and
      - before one is deleted and normal operation is resumed

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

#27524

Tom Gardner wrote on 1/6/2018 4:17 AM:
> On 06/01/18 03:29, Les Cargill wrote:
>> Tom Gardner wrote:
>>> My preference is for a dispatch table based on event+state,
>>> since that forces you to consider all possibilities.
>>
>> Yup yup. And you can generate a test vector for it with combinators.
>> Then testing essentially becomes compressing the output - tedious, but
>> ... rewarding.
>>
>> If the tested FSM is properly tested, then all remaining
>> defects are 1) either tweak/tone of unrealistic expectations or
>> 2) hardware bugs.
>
> Unfortunately you can't test FSMs "properly", for my
> definition of "properly" :) That's based on the
> unfashionable and inconvenient concept that "you
> can't test quality into a product".

FSM is one of the things where this isn't true.  You can set up a unit test 
that exhaustively tests all possible combinations of inputs and states to 
verify the machine matches the specification.


> For the systems I've designed, there's a lot to
> be gained by keeping a compressed log of "state
> trajectory" around until not needed. That plus
> accurate timestamping of events to/from external
> systems has enabled me to quickly and unambiguously
> deflect blame away from my stuff and onto other
> companies. The lawyers were never even called :)


-- 

Rick C

Viewed the eclipse at Wintercrest Farms,
on the centerline of totality since 1998

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

#27526

rickman <gnuarm.deletethisbit@gmail.com> writes:
> FSM is one of the things where this isn't true.  You can set up a unit
> test that exhaustively tests all possible combinations of inputs and
> states to verify the machine matches the specification.

You can't exhaustively test all the combinations because there's an
infinite set of possible input event sequences.  Your spec might
require, say, that no possible sequence of events can move the FSM from
state A to state B without passing through state C in between.  At the
higher level, that could mean that you can't fire the missiles without
releasing the safety.

Maybe you can prove that invariant with model checking, but it's a
complicated topic, not something that can be trivialized as a "unit
test".

This might be of interest:

https://github.com/tomahawkins/improve/wiki/ImProve

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

#27535

Paul Rubin wrote on 1/6/2018 7:58 PM:
> rickman <gnuarm.deletethisbit@gmail.com> writes:
>> FSM is one of the things where this isn't true.  You can set up a unit
>> test that exhaustively tests all possible combinations of inputs and
>> states to verify the machine matches the specification.
>
> You can't exhaustively test all the combinations because there's an
> infinite set of possible input event sequences.  Your spec might
> require, say, that no possible sequence of events can move the FSM from
> state A to state B without passing through state C in between.  At the
> higher level, that could mean that you can't fire the missiles without
> releasing the safety.

Of course that can be proven.  Why do you think it can't?  If a set of 
inputs returns you to a state you have already tested, you don't need to 
continue testing any further.  The definition of a FSM says its universe 
consists of inputs and states.  Test every state for every input and verify 
it goes to the appropriate state.

In your example you only need to test state A for every possible input to 
verify it doesn't go to state B.  Or if there are other states, you simply 
need to verify there are two sets of states, those that let you get to state 
B and those that let you get to state C.  Show that state A is in the latter 
and you are done.  You don't need to consider infinitely long sequences 
because it is a FINITE state machine.

-- 

Rick C

Viewed the eclipse at Wintercrest Farms,
on the centerline of totality since 1998

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

#27539

rickman <gnuarm.deletethisbit@gmail.com> writes:
> In your example you only need to test state A for every possible input
> to verify it doesn't go to state B.

An input is a sequence of events e1,e2,e3,...e_n.  For example, think of
pressing buttons and flipping switches in the cockpit of the space
shuttle.  Each flip is an event that can represent any of the 100s of
switches being flipped.  Maybe a drunk astronaut flips switch 5, then
switch 27, then switch 9, etc.

Question: is there some sequence of flips, maybe 1000 flips long, that
blows up the space shuttle by accident?  Your spec might require that no
such sequence exists, but how do you make sure?  You can't exhaustively
search every sequence of 1000 flips to test that.  And even if you
somehow check all the 1000-flip sequences, you still have to worry about
the possibility of a 2000-flip sequence, etc.

There are ways to deal with this problem (the link I gave is a useful
approach) but it's not so simple, and lots of work is done on it.

> You don't need to consider infinitely long sequences because it is a
> FINITE state machine.

Not infinitely long, but of arbitrarily large finite length.  You don't
have to worry about infinitely long sequences, but there are infinitely
many of finite size, and you do have to worry about those.

It's like saying there is no infinite integer (1,2,3... are all finite).
But since they can be arbitrarily large, the collection of them is not
finite.

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

#27545

Paul Rubin wrote on 1/7/2018 3:58 AM:
> rickman <gnuarm.deletethisbit@gmail.com> writes:
>> In your example you only need to test state A for every possible input
>> to verify it doesn't go to state B.
>
> An input is a sequence of events e1,e2,e3,...e_n.  For example, think of
> pressing buttons and flipping switches in the cockpit of the space
> shuttle.  Each flip is an event that can represent any of the 100s of
> switches being flipped.  Maybe a drunk astronaut flips switch 5, then
> switch 27, then switch 9, etc.
>
> Question: is there some sequence of flips, maybe 1000 flips long, that
> blows up the space shuttle by accident?  Your spec might require that no
> such sequence exists, but how do you make sure?  You can't exhaustively
> search every sequence of 1000 flips to test that.  And even if you
> somehow check all the 1000-flip sequences, you still have to worry about
> the possibility of a 2000-flip sequence, etc.
>
> There are ways to deal with this problem (the link I gave is a useful
> approach) but it's not so simple, and lots of work is done on it.
>
>> You don't need to consider infinitely long sequences because it is a
>> FINITE state machine.
>
> Not infinitely long, but of arbitrarily large finite length.  You don't
> have to worry about infinitely long sequences, but there are infinitely
> many of finite size, and you do have to worry about those.

There is *no* infinity is finite state machines.  Not input sequence lengths 
or input sequence combinations.  I can count all possible combinations of 
inputs and states which is why it is a *finite* state machine.

Perhaps the part you are missing is that it is irrelevant how a state was 
reached.  Once in a state it is the same having been reached from states A 
through L as from states M through Z and the input which caused the 
transition to the current state is also irrelevant.  The only things that 
matters are the state you are in and the input at that point.

I've already explained how you could analyze your example of states A and B 
being separated by state C always.  Making up arbitrarily complex scenarios 
is not useful.


> It's like saying there is no infinite integer (1,2,3... are all finite).
> But since they can be arbitrarily large, the collection of them is not
> finite.

Hmmm... clearly you don't understand the nature of the infinite.  Integers 
*are* infinite.

-- 

Rick C

Viewed the eclipse at Wintercrest Farms,
on the centerline of totality since 1998

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

#27547

rickman <gnuarm.deletethisbit@gmail.com> writes:
> There is *no* infinity is finite state machines.  Not input sequence
> lengths or input sequence combinations.

There are infinitely many sequences of inputs.  Of course since it's an
FSM, you end up getting repeated states.  For example, consider the
event sequence [A,B].  Then consider [A,A,B].  Then [A,A,A,B].  Then
[A,A,A,A,B], etc.  There are infinitely many such sequences.  Obviously
after a while they will start repeating states, and you can analyze that
example since every transition except the last one is on event A.

The problem happens when there's multiple transitions from each state,
so you have to consider all the combinations [A,C], [B,C], [A,A,C],
[A,B,C], [B,A,C], [B,B,C], etc.  The number of such combinations is
exponential in the number of states.  And the state space itself can be
exponentially large.  E.g. if a straightforward code implementation of
something involves a 3-bit retry counter, you need 8 states to handle
all the possible counts, maybe ok.  But if it's a 64-bit packet size
counter, the number of states required is ridiculous.

> I can count all possible combinations of inputs and states which is
> why it is a *finite* state machine.

We're talking about what you can do in practice on a real computer, not
whether something is mathematically finite.  Can you count to 1000?
Sure.  To a million?  Maybe.  To a googol (1e100)?  I don't think so,
even though a googol is finite.

> Hmmm... clearly you don't understand the nature of the infinite.
> Integers *are* infinite.

I am always willing to learn.  I'd be interested in seeing an example of
an infinite integer.

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

#27568

Paul Rubin wrote on 1/7/2018 1:53 PM:
> rickman <gnuarm.deletethisbit@gmail.com> writes:
>> There is *no* infinity is finite state machines.  Not input sequence
>> lengths or input sequence combinations.
>
> There are infinitely many sequences of inputs.

Which is irrelevant.  There are also infinitely long times, again irrelevant.


> Of course since it's an
> FSM, you end up getting repeated states.  For example, consider the
> event sequence [A,B].  Then consider [A,A,B].  Then [A,A,A,B].  Then
> [A,A,A,A,B], etc.  There are infinitely many such sequences.  Obviously
> after a while they will start repeating states, and you can analyze that
> example since every transition except the last one is on event A.

I don't follow your logic.  I don't care about the extent of the input 
sequence.  The machine only responds to the combination of the current input 
and current state.  The previous inputs at any given time are not relevant 
just as subsequent inputs are not relevant at this time.  All appropriate 
analysis can be done by considering a finite sequence that exercises the 
finite limits of the machine.

Any infinite sequence will result in repetition of tests that have already 
been performed.


> The problem happens when there's multiple transitions from each state,
> so you have to consider all the combinations [A,C], [B,C], [A,A,C],
> [A,B,C], [B,A,C], [B,B,C], etc.  The number of such combinations is
> exponential in the number of states.  And the state space itself can be
> exponentially large.  E.g. if a straightforward code implementation of
> something involves a 3-bit retry counter, you need 8 states to handle
> all the possible counts, maybe ok.  But if it's a 64-bit packet size
> counter, the number of states required is ridiculous.

I again refer you to the earlier statements regarding the relevance of 
current input and current state.


>> I can count all possible combinations of inputs and states which is
>> why it is a *finite* state machine.
>
> We're talking about what you can do in practice on a real computer, not
> whether something is mathematically finite.  Can you count to 1000?
> Sure.  To a million?  Maybe.  To a googol (1e100)?  I don't think so,
> even though a googol is finite.

Irrelevant.


>> Hmmm... clearly you don't understand the nature of the infinite.
>> Integers *are* infinite.
>
> I am always willing to learn.  I'd be interested in seeing an example of
> an infinite integer.

"An infinite integer"?  The range of integers are infinite.

-- 

Rick C

Viewed the eclipse at Wintercrest Farms,
on the centerline of totality since 1998

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

#27529

On 07/01/18 00:06, rickman wrote:
> Tom Gardner wrote on 1/6/2018 4:17 AM:
>> On 06/01/18 03:29, Les Cargill wrote:
>>> Tom Gardner wrote:
>>>> My preference is for a dispatch table based on event+state, since that
>>>> forces you to consider all possibilities.
>>>
>>> Yup yup. And you can generate a test vector for it with combinators. Then
>>> testing essentially becomes compressing the output - tedious, but ...
>>> rewarding.
>>>
>>> If the tested FSM is properly tested, then all remaining defects are 1)
>>> either tweak/tone of unrealistic expectations or 2) hardware bugs.
>>
>> Unfortunately you can't test FSMs "properly", for my definition of
>> "properly" :) That's based on the unfashionable and inconvenient concept
>> that "you can't test quality into a product".
>
> FSM is one of the things where this isn't true.  You can set up a unit test
> that exhaustively tests all possible combinations of inputs and states to
> verify the machine matches the specification.

Not for many of the FSMs I've had to deal with. I've
watched some people making that claim look at such FSMs,
gulp, and become very quiet.

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

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

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

csiph-web