[boost] Re: Re: review of proposed fsm library

From: Andreas Huber (ahd6974-spamgroupstrap_at_[hidden])
Date: 2005-03-20 10:53:51

Dave Gomboc wrote:
>>> class state_machine: public state, private state_control { ... };
>>>
>>> is a possibility.  However, leaving the control manager separate
>>> from the state data (structure) might be better yet.   Why does this
>>> separation of concerns seem obscure?
>>
>> I don't see why an FSM should behave like a state. An FSM is not a
>> state, it has a state.
>
> Does your state code stand alone from the state machine code?  e.g.
> Can I re-use "state" without buying "state_machine"?  I guess that is
> what I'm really after.

I'm not sure whether the following answers your question: State code can
stand alone if you want it to, by making all your simple_state and state
subtypes templates, accepting at least the Context a template parameter.
See http://tinyurl.com/6xdh3 (Submachines & Parameterized states) for an
example.

>>> Perhaps the control manager
>>> can iterate over the state data structure?  operator++ advances to
>>> the next state; operator() performs the reaction, etc.  Okay, I've
>>> entered pure brainstorming territory  :-), but really, things might
>>> be improved by not commingling data and control.
>>
>> Any use-cases?
>
> Just brainstorming.

Brainstorming can be fun but I hope you understand that I will not add
or change anything for which there aren't any real-world use-cases.

>>> I think problems with examples are alleviated partially when people
>>> can take the source files comprising the example, compile them, and
>>> see them run -- a success was achieved immediately.  For instance,
>>> Boost.Serialization does this with at least some of its examples
>>> (demo_xml.hpp and demo_xml.cpp, if I recall correctly).
>>
>> How is this relevant?
>
> I'm recommending that you adjust your documentation so that one can
> readily compile complete examples by downloading source and header
> code
> files via links embedded within the documentation page.  You could

That's already on the yet unpublished to-do list.

> also
> have a templated version of some code in separate files (given that
> you
> don't like the idea of templatizing regularly).

Ok, I can do that for the keyboard example, where templatizing makes
perfect sense.

>> I guess I don't really understand what you want to say here. Making a
>> component generic is always more work than leaving it the way you
>> need it for your current problem at hand. E.g. for a submachine,
>> you'd need to make the external transition targets template
>> parameters.
>
> What I'm asking for is an example of this to be included in the
> documentation, so that people who want to build a component library,
> plug those components together, etc. have a pre-made example
> conforming to best practice (as given by you, the expert) to consult.

It's already there, see the link above.

> This is why I
> recommended an example involving a half-adder component, used twice to
> create a full-adder.

I'll consider adding such an example.

>>> This comment does not address myriad uses that I would have for an
>>> fsm library that met my needs.
>>
>> Please briefly describe one such use, non-parser related if possible.
>
> I've come to realize that really what I was thinking about was using
> the hierarchical state mechanism, separate from the standard state
> machine execution procedure.  The goal is to construct a hierarchical
> state representation of a search space as a program gathers
> information.

That should be possible, you can use whatever CT algorithms you like to
assemble your FSM. The BitMachine example does something in this
direction, the number of states is dependent on the number of bits you
want it to represent.

>>> Perhaps it is because people would like the freedom to employ fsm in
>>> contexts that you did not target your solution for.
>>>
>>> Maybe, an example of such use would be interesting.
>
> One thing that fits within the rubric of FSM (as opposed to more
> general state categorization and manipulation) is simply to build an
> fsm at
> runtime.  This was explicitly not a design goal of yours, though.

Yep, you'd lose validation at compile time.

> I also have a desire for NFA -> DFA and DFA -> minimized DFA
> procedures; I still don't know if it's possible to do this or not
> with the library.

Well, I can certainly say that the library was never designed to enable
such uses. However, provided you can do the minimization at compile time
I don't see many obstacles, I probably need to add few typedefs here and
there and you should be able to extract all the information you need.

> With these items, I'm obviously willing to take the compilation time
> hit
> of everything being known to a single translation unit, if that is
> necessary (and you've made what looked to me like a good argument
> that it would be).

Ok.

>>> Why? Must I really offer all the functionality in the first version
>>> of the library?
>
> I think I suggested otherwise earlier.

Ok, I must have missed that.

>> I've just reread you original post and fail to see anything that
>> resembles a request to support full deep history. Instead you find it
>> suspicious that I have taken the liberty to not support something
>> that is - in my experience - needed only very rarely and diffcult to
>> implement too. It is of course your right to find that suspicious but
>> for me that is not encouraging in any way. If you file such a request
>> now I hope you understand that I will not make an attempt to
>> implement full deep history until you have convinced me that it is
>>   a) absolutely necessary in some real-world cases (i.e. the
>>      workaround is not sufficient)
>>   b) needed by a sufficiently large group of people
>>
>> My time is limited and I tend to address the issue that is the most
>> pressing first. I seriously doubt that full deep history support will
>> make it to the top of my to-do list in the near future.
>
> [and]
>
>>> Excuse me, I really don't understand what the problem is. Fork bars
>>> are not supported for the very same reasons that full deep history
>>> is not supported. They are - in my experience - needed only rarely
>>> and they are difficult to implement. I ask again: Why should I
>>> invest my time in such a feature now? Or, why should I have
>>> invested that time before submission?
>>>
>>> Most libraries have some limitations, even the ones at boost.
>
> [and]
>
>>>> The interface change for this is rather easy: Simply specify
>>>> multiple rather than just one target state. I don't see the
>>>> problem. BTW, this is connected to deep history not working for
>>>> orthogonal sub-states.
>>>
>>> I suspected so.  I believe it was caused by starting with the fsm
>>> having abilities that applied to one state at a time, then later
>>> adding orthogonality support but without a full conversion to
>>> supporting state-supersets in all places of the code.  However, this
>>> is sheer speculation on my part and may well be wrong. :-)
>>
>> I can't answer this because I don't understand what a state-superset
>> is.
>
> The superset of the set S = {"0", "1", "2"} is
>
> S* = {
>       { },
>       { "0" },
>       { "1" },
>       { "2" },
>       { "0", "1" },
>       { "0", "2" },
>       { "1", "2" },
>       { "0", "1", "2" }
>     }
>
> A basic FSM machine M will map S x T -> S (S = state, T =
> transition); but when orthogonal states are supported, instead one
> must map S* x T -> S* (where S* is the superset of S).  Where I wrote
> "state-superset", I was referring to S*.

Okay, I guess I got that.

> My speculation, which was not based on an in-depth examination of the
> code (though I did look at it briefly), was that your FSM code
> started out supporting S x T -> S, which is very natural, and that
> parts of it must
> yet be altered to fully support S* x T -> S*.

FWIW, the code indeed started out by supporting S x T -> S. Of course,
some parts of the code must be changed to fully support S* x T -> S*
(otherwise the feature would already be there).

If I were to implement support for fork bars (and subsequently also for
full deep history) I wouldn't need to change a single line of code in
the state representation. Apart from the obvious interface changes, I
would "only" need to implement the CT algorithm that calculates which
states need to be entered in what order as the result of a given
innermost common context and a list of orthogonal states that should be
entered. Currently this CT algorithm only accepts one state.

> I thought that this
> explained why fork bars are not supported,

See above.

 why join bars are not
> supported,

I don't think I will ever support join bars. This would require vast
interface changes and you can easily work around this lack with guards.

>> From a theoretical view, software that does not fully support the
>> mapping
> S* x T -> S* cannot correctly adhere to the UML specification -- which
> seems important given that the main purpose of your library appears
> to be
> to provide a diagram-to-code implementation of that specification.
> Accordingly, I consider this to be a "correctness of design" issue,
> not merely a "these features aren't needed that often" issue.  As for

See above. I don't think the current design is incorrect in this regard.

> your
> view, sure, it's completely understandable that you have to implement
> what
> is most pressing for "clients" of your code.

Exactly.

>>> Because people may want the ability to use epsilon-transitions,
>>> which NFAs support and make finite automata modelling considerably
>>> simpler in many cases.
>>
>> It seems such a discussion belongs into a state theory text and not a
>> tutorial for a FSM library.
>
> Why?
>
> Epsilon-transitions increase the ease with which one can specify a
> state machine.  Does the UML state machine standard not support them
> at all?

I'm not sure. From googling around it seems that epsilon transitions are
the same as triggerless transitions in UML?

> While it is true that their use would effectively make machine M
> require
> the use of S* x T -> S* instead of S x T -> S, is this not also true
> for
> join bars, or fork bars, or orthogonal states (at least, where there
> are actions that cause multiple simultaneous transitions)?
>
> The process of converting an NFA to a DFA is the process of
> transforming machine M: S* x T -> S* into a new machine M': S' x T'
> -> S' with
> identical behaviour, but without epsilon transitions.  It seems to me
> that this same process can convert a machine that relies on fork
> bars, join
> bars, and "orthogonal multiple-state-change from single transition"
> to one that relies on none of the above.  (Additionally, a DFA
> minimization pass
> may be run on it after conversion to try to combat state-space
> explosion.)
>
> Is it really a surprise that such fundamental algorithms could be of
> use?

I'm not sure whether such algorithms would be used more than rarely by
the targeted user group. I do agree that such algorithms are probably
extremely useful for FSMs that are generated by algorithms (regex) but I
have my doubts whether the same is true for machines that are directly
engineered by humans. As I have mentioned before, I think one
significant obstacle for any such transformations is state-local storage
(I might be wrong).

> New comment:
>
> Andreas outlines 9 requirements that his library satisfies.  Some
> users
> have the same requirements, or a subset of them, and they are no doubt
> extremely pleased with the library as proposed.
>
> Others have different requirements, some of which conflict with the 9
> selected:
>
> 10. Dynamic (run-time) FSM construction.
> 11. Reusable finite automata components.
> 12. Modelling of non-determinism; availability of epsilon-transitions.
> 13. Constant-time dispatch.
>
> For my own purposes, all four of these are more important than
> Andreas' #3 and #4 requirements.  For others, the situation will be
> different.  I
> believe the crux of the review manager's task is to weigh the
> requirements that have been satisfied, plus its potential to fulfill
> the others against the requirements that the various potential users
> of the library have.

I believe it is not feasible to implement a single library that
satisfies all 13 requirements. It is probably possible but I seriously
doubt that such a library would be of any use for more than a handful of
people. All of these additional requirements inevitably complicate the
interface and the implementation. I strongly believe that there are two
groups of FSM users (as defined in the rationale) with a very small
intersection. It would make little sense to provide one library that
satisfies both groups. It makes much more sense to implement two
distinct libraries.

Regards,

-- 
Andreas Huber
When replying by private email, please remove the words spam and trap
from the address shown in the header.