[boost] Re: review of proposed fsm library

From: Andreas Huber (ahd6974-spamgroupstrap_at_[hidden])
Date: 2005-03-11 19:57:25

Dave Gomboc wrote:
>> I didn't justify it because it feels natural to me that a
>> state machine has
>> only one event queue, and one place where history is stored (both
> are
>> containers inside state_machine). Admittedly, because the
>> outermost state
>> knows at compile time that it is the outermost state, the
>> state_machine class
>> template could be "abstracted away". You'd then only have
>> simple_state and
>> state. However, this seems at best obscure to me.
>
> 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.

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

>> While I might agree with your reasoning in theory, I don't
>> think that it would
>> work in practice. Even now I sometimes get complaints that
>> the examples are
>> too complex (too many templates) and changing all examples to
>> work with
>> templated states would make them even more so. Plus, often
>> there is no need to
>> use a state in more than one place, so why bother with
>> templated states then?
>
> 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?

> It is not presumptuous for a coder to assume that their machine will
> never be needed in another context?  If templating improves
> reusability considerably, while not costing much, then it should be
> done.  However, if there are other obstacles to component reuse,
> rather than say it's not worth it to template these, instead say
> these other obstacles must be cleared.

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.

> One cannot build a library of fsm components that may be connected
> together to build more complex fsms without this,

Without what? (I must be having a bad brain day)...

[snip]
>> An FSM however must
>> return after
>> processing each event. Parsers can exploit this fact and
>> store state with
>> recursive calls, which is of course much faster (some stuff
>> can even be
>> inlined) than any super-clever double-dispatch scheme.
>> There is often a hard limit for stack space which - I think -
>> is the reason
>> why FSMs do make sense in parsers nevertheless. However, all
>> the FSM-employing
>> parsers I know are of the dynamic variant (e.g. regex) and
>> these FSMs are not
>> directly designed by humans but computed by an algorithm.
>
> For reading a identifier character-by-character, sure, one would not
> want to use an fsm to process each character individually.  However,
> one can design the fsm to proceed to read an entire identifier at
> once.  In situations where a parser might require extensive
> backtracking (and Spirit-1 doesn't actually backtrack after accepted
> symbols, which is something I could employ an fsm to work around!)
> the use of an non-deterministic FA may be well-justified.
> Also, if one is merely testing for the presence of a regular
> expression match, I agree that just signalling once when the match
> is complete is sufficient, however, often one wants substrings
> within a match that correspond to certain portions of the match, in
> which case actions at transition points may be a fine solution to
> the problem, both reasonably efficient and easily understood by the
> developer.
>
> Furthermore, the possibilities for error comprehension and recovery
> in a parsing process may be improved by the use of an fsm framework.

I'm a parser dummy, I can't really comment this.

> It is certainly true that I have use for dynamically-arranged fsms
> -- and not only for parsing.  It was a disappointment for me that I
> would not be able to do some tasks with this library.
>
>> Last but not least I
>> think it would be tedious for a human to implement a parser
>> on the state-
>> level, which is probably the reason why I dared to make the
>> admittedly dumb
>> remark in the first place.
>> I think Darryl puts this rather nicely:
>> <quote>
>> Fast flat fsms to process simple events and having little
>> additional context
>> are best implemented using other methods. However such
>> implementations are not
>> difficult, and there are plenty of domain specific tools
>> already (eg various
>> language recognisers).
>> </quote>
>
> 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.

>> [snip]
>> Unless you use a perfect hashing algorithm (which is
>> infeasible because you
>> need to know all the ids beforehand), this would essentially
>> wreck the ability
>> to use this library in real-time systems. Hashed containers
>> are a bad idea for
>> real-time as there is no upper limit for a search operation.
>
> However, one would know the maximum dispatch time guarantee by the
> end of the compilation process, and it likely would be less
> time-consuming (where sufficient memory exists) than the linear
> search currently employed.

Agreed.

>>> While perhaps each state (compilation module) must know of its
>>> successor states, no central table of "current state x action x
> next
>>> state" encompassing the entire machine need be explicitly
> created.
>>
>> Which is exactly what this library is doing. There is a
>> lookup "table" within
>> each state and if that fails lookup considers the states
>> outer state. However,
>> this inevitably means that you cannot have constant time
>> lookup. The larger
>> your FSM becomes the longer lookup takes. BTW, as I've
>> written in another post
>> I don't see why reaction search is so important for people,
>> because in typical
>> FSMs I'd expect transition execution to be much more of a
>> performance hog.
>
> 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.

>>> I have an uneasy feeling about how differently asynchronous and
>>> synchronous machines are operated, but did not consider this
> issue
>>> in detail.
>>
>> Why? They are rather different things aren't they?
>
> 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.

>>> Allowing the tracking of history is intruiging; the prohibition
>>> against deep history of states with orthogonal regions is
>>> suspicious.
>>
>> Why?
>
> Why not?

I think it is very common for a library to not support functionality 
that is useful only very rarely, especially if it is hard to implement. 
Why is that suspicious?

>>> The explanation given is that it would be more
>>> complicated (but still possible) to implement.
>>
>> It would be much more complicated to be precise.
>>
>>> In my experience,
>>> that sort of reasoning just doesn't fly at Boost.
>>
>> Why? Must I really offer all the functionality in the first
>> version of the
>> library?

????

> Very few people use deep history and orthogonal states in
>
>> conjunction. For those that do I describe a work-around. I
>> have not received a
>> single request to implement full deep history.
>
> Well, you've received at least one, but your response was 'why?'.
> ;-)

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.

>>> The discussion of fork and join bars, combined with the event
>>> dispatch to orthogonal regions discussion immediately below
> that,
>>> suggests that the implementation is not truly designed to handle
>>> concurrent states.
>>
>> Why?
>
> Otherwise, these items would be addressed, that's why.  But see
> below.

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.

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

>>> There is no explicit discussion of non-deterministic fsms.  Of
>>> course, every such fsm can be re-expressed deterministically.
>>
>> I don't see why I should discuss that.
>
> 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.

>>> However, I would like to ask if (excepting possible
>>> compiler limitations) is there anything about the library that
>>> precludes extending it such that NDFAs could be specified in
> code,
>>> and converted into the minimized DFA during compilation?
>>
>> Yes, the scalability requirements. As I explain above (and
>> you seem to have
>> found that yourself) there is no way to have a global view at an
> FSM
>> implemented with this library.
>
> I am not suggesting that you provide this functionality  yourself.
> What I am asking is that if another needs this functionality can
> they add code to your library to do it without too much trouble, or
> are there implementation considerations that make it impossible?  It
> should be clear that if one intends to perform a NFA->DFA or DFA
> minimization that it is recognized that they are forfeiting
> scalability by requiring whole-machine view.

I could surely extend the interface so that CT algorithms can operate on 
an FSM definition. I wouldn't be much work either.

Regards,

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