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

From: Dave Gomboc (dave_at_[hidden])
Date: 2005-03-15 05:25:39

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

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

> > 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 also 
have a templated version of some code in separate files (given that you 
don't like the idea of templatizing regularly).

> 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.  This is why I
recommended an example involving a half-adder component, used twice to
create a full-adder.

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

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

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

> > No, not really.  Certainly, I would expect to be able to plug
> > together an asynchronous and synchronous submachines into a larger,
> > single fsm (which would need to be modelled asynchronously).
> 
> You can do that with the current version.

Good stuff.

> > Why? Must I really offer all the functionality in the first version
> > of the library?

I think I suggested otherwise earlier.

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

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*.  I thought that this
explained why fork bars are not supported, why join bars are not
supported, and why the "orthogonal multiple-state-change from single
transition" is not supported.  But, as before, I readily concede that this
intuition (or hunch) could well be wrong.

>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 your
view, sure, it's completely understandable that you have to implement what
is most pressing for "clients" of your code.

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

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.

Disclaimer: I hope I didn't blow it on any of the details in this message.  
It's getting a bit late!

Dave