headers
Martin Vuille | 19 Aug 02:21

[review] FSM Second Call for Reviews

The formal review for Andrey Semashev's Finite State Machines (FSM) 
library has been running for a week now and continues until the 20th.

There have been some lively discussions about the library, but no
one has yet entered an explicit yes or no vote. If there are no votes
either way, the FSM library submission will be rejected by default.

If you wish to review, but don't have time before the review period
ends on the 20th, please let me know as it may be possible to extend
the review period.

And, finally, a reminder to include an explicit "for" or "against"
vote in your review.

-----------

The documentation (overview and reference) is available online:
http://boost-extension.redshoelace.com/docs/boost/fsm/doc/state_machine.html
http://boost-extension.redshoelace.com/docs/boost/fsm/doc/reference.html

The current submission is available from the sandbox vault at 
http://tinyurl.com/yjozfn (or 
http://www.boostpro.com/vault/index.php?action=downloadfile&filename=FSM.zip
&directory=&PHPSESSID=48493076c1ea60ae316f7b60f15b9ed1,
if you prefer.)

There has already been some discussion of the library
since the rewiew was first announced:
http://www.nabble.com/FSM-Review-Announcement-to18820219.html
http://www.nabble.com/FSM-Review-Reminder-to18890305.html
(Continue reading)

Permalink | Reply |
headers
Jeff Flinn | 29 Aug 05:01
Favicon

Re: [review] FSM Second Call for Reviews

My review appears here with an attached cpp file implementing four 
approaches (not compiled): a manual nested switch/if function, the TMP 
book's mpl state table, boost.statechart, this FSM library.

> What is your evaluation of the implementation?
> Did you try to use the library? With what compiler? Did you have any
> problems?

Didn't download the library code, just read through docs and tried to 
implement a simple state machine comparing other approaches.

> What is your evaluation of the potential usefulness of the library?

I think there are many applications for a lightweight, expressive FSM 
library in areas not typically using FSM's such as mouse event processing, 
filtering/transforming iterators,...

> What is your evaluation of the design?
> What is your evaluation of the documentation?

My view of the design is limited to what is described in the documentation. 
I was a little dismayed that some of the basic features that I needed are 
considered Advanced features such as sharing state and accessing the current 
state from outside the state machine. These are very easily accomplished in 
the TMP and StateChart libraries. The section on accessing state is not 
sufficient for me to determine which state the fsm is in between calls to 
process(). The data sharing approach between sibling states using a virtual 
base class is perplexing... there's no discussion of just what is the 
structure of the state machine. There is a lot of repititious boilerplate 
required relative to other libraries. There is a mixing of the transition
(Continue reading)

Permalink | Reply |
headers
Andrey Semashev | 30 Aug 09:32
Gravatar

Re: [review] FSM Second Call for Reviews

Jeff Flinn wrote:

>> What is your evaluation of the design?
>> What is your evaluation of the documentation?
> 
> My view of the design is limited to what is described in the
> documentation. I was a little dismayed that some of the basic features
> that I needed are considered Advanced features such as sharing state and
> accessing the current state from outside the state machine. These are
> very easily accomplished in the TMP and StateChart libraries.

It's just a name for the section. Everything that didn't fit into
Tutorial went into that section.

> The
> section on accessing state is not sufficient for me to determine which
> state the fsm is in between calls to process().

Huh? There is a section that tells precisely how to do this. The
is_in_state and get_current_state_type methods fill your requirement.

> The data sharing
> approach between sibling states using a virtual base class is
> perplexing... there's no discussion of just what is the structure of the
> state machine.

Actually, this feature is one of those I love in the library.

The description of the structure is given in the "Common data and
methods among states" section. I admit, however, there's no graphical
(Continue reading)

Permalink | Reply |
headers
Jeff Flinn | 1 Sep 15:25
Favicon

Re: [review] FSM Second Call for Reviews

Andrey Semashev wrote:
> Jeff Flinn wrote:
> 
>>> What is your evaluation of the design?
>>> What is your evaluation of the documentation?
>> My view of the design is limited to what is described in the
>> documentation. I was a little dismayed that some of the basic features
>> that I needed are considered Advanced features such as sharing state and
>> accessing the current state from outside the state machine. These are
>> very easily accomplished in the TMP and StateChart libraries.
> 
> It's just a name for the section. Everything that didn't fit into
> Tutorial went into that section.
> 
>> The
>> section on accessing state is not sufficient for me to determine which
>> state the fsm is in between calls to process().
> 
> Huh? There is a section that tells precisely how to do this. The
> is_in_state and get_current_state_type methods fill your requirement.

Ok, not sure why I had trouble reading through that earlier, other than 
I had a hard time finding this section whenever I went to look for it. 
Perhaps if you moved the Table of contents to the top of the docs, as it 
is it gets lost in the clutter.

So so I would use is_in_state<extracted_triplet>(); in the 
extractor::extracted method?

>> The data sharing
(Continue reading)

Permalink | Reply |
headers
Andrey Semashev | 1 Sep 18:16
Gravatar

Re: [review] FSM Second Call for Reviews

Jeff Flinn wrote:
> Andrey Semashev wrote:
>> Jeff Flinn wrote:
> So so I would use is_in_state<extracted_triplet>(); in the
> extractor::extracted method?

Yes.

>>> The data sharing
>>> approach between sibling states using a virtual base class is
>>> perplexing... there's no discussion of just what is the structure of the
>>> state machine.
>>
>> Actually, this feature is one of those I love in the library.
>>
>> The description of the structure is given in the "Common data and
>> methods among states" section. I admit, however, there's no graphical
>> representation of the design, but if I drew precisely what the structure
>> is, I think, it would confuse you even more.
> 
> Perhaps a Design/Rationale section would better convey that this section
> describes the overall architecture of the system.

Agreed.

>>>> Do you think the library should be accepted as a Boost library?
>>> No. I'd prefer that the performance and missing functionality be added
>>> to improve the existing StateChart library, and/or a true transition
>>> table approach be provided ala the TMP book's transition table.
>>
(Continue reading)

Permalink | Reply |
headers
Thomas Klimpel | 29 Aug 12:19

Re: [review] FSM Second Call for Reviews

> What is your evaluation of the design?

When I look at finite state machine in Wikipedia, Fig. 1 shows me an "Example  of a Finite State Machine". The
blue words "state", "transition", "transition condition", "entry action" in this picture probably
represent some of the important notions in this domain. How does the FSM library relate to these concepts?

The "state" concept is modeled as a class that has to publicly derive from fsm::state<Classname, 
StateList>. More on this later.

The "transition" concept is modeled as the class fsm::transition<InitialState, Event, FinalState>.
User defined transition actions can derive from this class and overide the "transit" method.

The "transition condition" is replaced with the "event" concept. I guess this is OK, since the Wikipedia
article also mentions event driven finite state machines. The "event" concept is modeled as an arbitrary
class. There doesn't seem to be an EventList (analogous to the StateList) that lists all allowed events,
so it's probably possible to send an arbitrary object to the state machine, which will then react somehow
to that (unexpected?) event. In case a reaction to the "any_event" class is defined, the single value
constructor (without the explicit keyword) of this class will probably convert this event to the "any_event".

I haven't investigated how the different types of "actions" are modeled by the library, or whether they are
modeled at all.

The most important design decision seems to be let the state machine have a member of a class that derives
from all states in StateList. The switching between the states now changes which of these "base classes"
is "in charge" of handling events.

I see two reasons for this design choice. The first is performance, which is one of the main goals of the
library, the second is that the library models a "state machine" instead of a "finite state machine". This
is OK, but I would consequently prefer the name "state_machine" instead of "fsm" for the library.
(Continue reading)

Permalink | Reply |
headers
Andrey Semashev | 30 Aug 09:12
Gravatar

Re: [review] FSM Second Call for Reviews

Thomas Klimpel wrote:
>> What is your evaluation of the design?
> 
> When I look at finite state machine in Wikipedia, Fig. 1 shows me an "Example  of a Finite State Machine". The
blue words "state", "transition", "transition condition", "entry action" in this picture probably
represent some of the important notions in this domain. How does the FSM library relate to these concepts?
> 
> I haven't investigated how the different types of "actions" are modeled by the library, or whether they
are modeled at all.

They are. The article defines the following actions:
- Entry action. Is modeled with on_enter_state handlers.
- Exit action. Is modeled with on_leave_state handlers.
- Input action. Is modeled with on_process handlers.
- Transition action. Is modeled with transit handlers.

> The most important design decision seems to be let the state machine have a member of a class that derives
from all states in StateList. The switching between the states now changes which of these "base classes"
is "in charge" of handling events.
> 
> I see two reasons for this design choice. The first is performance, which is one of the main goals of the
library, the second is that the library models a "state machine" instead of a "finite state machine".

Why? The machine is definitely finite, since it consists of finite
number of states and defines finite number of transitions between them.

> The modeling of the "transition" concept could and should probably be improved. The transition table
where I can specify for given "intial states" and "events" the resulting "final states" and "actions"
(modeled as functions that take a const reference to the corresponding event) to perform appears
superior to me.
(Continue reading)

Permalink | Reply |
headers
Thomas Klimpel | 30 Aug 12:29

Re: [review] FSM Second Call for Reviews

Andrey Semashev wrote:
> > The most important design decision seems to be let the state machine 
> > have a member of a class that derives from all states in StateList.
> > The switching between the states now changes which of these
> > "base classes" is "in charge" of handling events.
> >
> > I see two reasons for this design choice. The first is performance,
> > which is one of the main goals of the library, the second is that the
> > library models a "state machine" instead of a "finite state machine".
>
> Why? The machine is definitely finite, since it consists of finite
> number of states and defines finite number of transitions between them.

Other designs model 'states' as enums, while the fsm library models 'states' as classes. A 'state' modeled
by an enum would be a "stateless state", while a 'state' modeled by a class can have "internal state". I'm
quite sure that the "finite" in "finite state machine" refers to the number of "stateless states",
because the Wikipedia article says: "A finite state machine is an abstract model of a machine with a
primitive internal memory.". In other words, the resulting "machine" (created by
"fsm::state_machine<...> machine") viewed as a black box is not guaranteed to only have a finite number
of "stateless states", so it may exhibit behavior that is not possible for a finite state machine (like
parsing a grammar that is too complex for a finite state machine)

I don't say that this is a bad thing. I just say that I guess this is one of the reasons why fsm models 'states' as
classes and not just as enums.

> > The modeling of the "transition" concept could and should probably be improved.
> > The transition table where I can specify for given "intial states" and "events"
> > the resulting "final states" and "actions" (modeled as functions that take a const
> > reference to the corresponding event) to perform appears superior to me.
>
(Continue reading)

Permalink | Reply |
headers
Andrey Semashev | 30 Aug 19:27
Gravatar

Re: [review] FSM Second Call for Reviews

Thomas Klimpel wrote:
> Andrey Semashev wrote:
>>> The most important design decision seems to be let the state machine 
>>> have a member of a class that derives from all states in StateList.
>>> The switching between the states now changes which of these
>>> "base classes" is "in charge" of handling events.
>>>
>>> I see two reasons for this design choice. The first is performance,
>>> which is one of the main goals of the library, the second is that the
>>> library models a "state machine" instead of a "finite state machine".
>> Why? The machine is definitely finite, since it consists of finite
>> number of states and defines finite number of transitions between them.
> 
> Other designs model 'states' as enums, while the fsm library models 'states' as classes. A 'state'
modeled by an enum would be a "stateless state", while a 'state' modeled by a class can have "internal
state". I'm quite sure that the "finite" in "finite state machine" refers to the number of "stateless
states", because the Wikipedia article says: "A finite state machine is an abstract model of a machine
with a primitive internal memory.". In other words, the resulting "machine" (created by
"fsm::state_machine<...> machine") viewed as a black box is not guaranteed to only have a finite number
of "stateless states", so it may exhibit behavior that is not possible for a finite state machine (like
parsing a grammar that is too complex for a finite state machine)

Ok then. I didn't think of the internal data of the states as an
additional sub-state.

>>> The modeling of the "transition" concept could and should probably be improved.
>>> The transition table where I can specify for given "intial states" and "events"
>>> the resulting "final states" and "actions" (modeled as functions that take a const
>>> reference to the corresponding event) to perform appears superior to me.
>> You already can do that, as I've shown in my replies to David. The only
(Continue reading)

Permalink | Reply |
headers
Thomas Klimpel | 31 Aug 15:28

Re: [review] FSM Second Call for Reviews

Andrey Semashev wrote:
> Not exactly. You don't have to override the transit handler unless you
> want to define some non-trivial transition logic. If you stick to the
> same degree of functionality that TMP provides (IOW, no runtime
> conditions for the transition to take place), then you can use the
> fsm::transition class as a direct replacement for the row template in
> the TMP approach.
> 
> If you have to decide when and which state to transit to in runtime,
> then yes, you have to define your custom transition rule.

But how can I specify the "transition action", if not by overriding the "transit" method? And even if I
override the "transit" method, how should I handle the fact that the event will still be delivered to the
target state?
Attachment (winmail.dat): application/ms-tnef, 3089 bytes
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Andrey Semashev | 31 Aug 18:55
Gravatar

Re: [review] FSM Second Call for Reviews

On Sun, 2008-08-31 at 15:28 +0200, Thomas Klimpel wrote:
> Andrey Semashev wrote:
> > Not exactly. You don't have to override the transit handler unless you
> > want to define some non-trivial transition logic. If you stick to the
> > same degree of functionality that TMP provides (IOW, no runtime
> > conditions for the transition to take place), then you can use the
> > fsm::transition class as a direct replacement for the row template in
> > the TMP approach.
> > 
> > If you have to decide when and which state to transit to in runtime,
> > then yes, you have to define your custom transition rule.
> 
> But how can I specify the "transition action", if not by overriding the "transit" method?

As I said, if you need some non-trivial (i.e. something more complex
than a mere call to switch_to), you have to implement the transit
handler. Otherwise, you don't have to do that and you get precisely what
the TMP solution provides. 

> And even if I override the "transit" method, how should I handle the fact that the event will still be
delivered to the target state?

Process the event. Every event passed to the state machine must be
processed in some way - either in one of the on_process handlers, or in
the unexpected events handler. You cannot cancel the event delivery
because the machine has to return something from the FSM's process
method.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
(Continue reading)

Permalink | Reply |
headers
Thomas Klimpel | 1 Sep 21:00

Re: [review] FSM Second Call for Reviews

Andrey Semashev wrote:
> > But how can I specify the "transition action", if not by overriding the "transit" method?
>
> As I said, if you need some non-trivial (i.e. something more complex
> than a mere call to switch_to), you have to implement the transit
> handler. Otherwise, you don't have to do that and you get precisely what
> the TMP solution provides. 

Your answers confirm my initial statement: "The modeling of the "transition" concept could and should
probably be improved."

Also, your statement "you get precisely what the TMP solution provides" is misleading. It's easiest for me
to explain this with an example from graph theory. A graph can be described by an "adjacency list", but it
can also be described by an "incidence list". The state-based approach of the FSM library corresponds to
the description of a graph by the "adjacency list". The transition-based approach of the TMP solution
corresponds to the "incidence list". The description by an "adjacency list" will often be more efficient
than the description by an "incidence list", but the "incidence list" makes it easy to associate
additional information to the edges of the graph. You basically claim that you also support the
"incidence list" approach, but you don't provide support for associating additional information to the
edges of the graph, because you consider this "too complex".
Attachment (winmail.dat): application/ms-tnef, 3501 bytes
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Andrey Semashev | 2 Sep 19:15
Gravatar

Re: [review] FSM Second Call for Reviews

Thomas Klimpel wrote:
> Andrey Semashev wrote:
>>> But how can I specify the "transition action", if not by
>>> overriding the "transit" method?
>> As I said, if you need some non-trivial (i.e. something more
>> complex than a mere call to switch_to), you have to implement the
>> transit handler. Otherwise, you don't have to do that and you get
>> precisely what the TMP solution provides.
> 
> Your answers confirm my initial statement: "The modeling of the
> "transition" concept could and should probably be improved."

I'm just trying to understand how, exactly, it should be improved. Your
previous posts were referring to the necessity to override transit
handlers in order to define transition actions. I confirmed that but
added that it is not worse than other solutions mentioned. So, I don't
see how and why this particular feature should be improved.

> Also, your statement "you get precisely what the TMP solution
> provides" is misleading. It's easiest for me to explain this with an
> example from graph theory. A graph can be described by an "adjacency
> list", but it can also be described by an "incidence list". The
> state-based approach of the FSM library corresponds to the
> description of a graph by the "adjacency list". The transition-based
> approach of the TMP solution corresponds to the "incidence list". The
> description by an "adjacency list" will often be more efficient than
> the description by an "incidence list", but the "incidence list"
> makes it easy to associate additional information to the edges of the
> graph. You basically claim that you also support the "incidence list"
> approach, but you don't provide support for associating additional
(Continue reading)

Permalink | Reply |
headers
David Abrahams | 2 Sep 21:50
Favicon
Gravatar

Re: [review] FSM Second Call for Reviews


on Tue Sep 02 2008, Andrey Semashev <andrey.semashev-AT-gmail.com> wrote:

> transitions model actions

FWIW, It has always been my understanding that state transitions and the
actions associated with them were separate concepts.  The first class
status of transitions seems to me to be essential for being able to
understand the flow of the state machine.

--

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Andrey Semashev | 3 Sep 05:18
Gravatar

Re: [review] FSM Second Call for Reviews

David Abrahams wrote:
> on Tue Sep 02 2008, Andrey Semashev <andrey.semashev-AT-gmail.com> wrote:
> 
>> transitions model actions
> 
> FWIW, It has always been my understanding that state transitions and the
> actions associated with them were separate concepts.  The first class
> status of transitions seems to me to be essential for being able to
> understand the flow of the state machine.

I'm confused. What are transitions are used then, if not for describing
when, where and how to transit?
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Thomas Klimpel | 3 Sep 00:49

Re: [review] FSM Second Call for Reviews

Andrey Semashev wrote:
> > Your answers confirm my initial statement: "The modeling of the
> > "transition" concept could and should probably be improved."
>
> I'm just trying to understand how, exactly, it should be improved. Your
> previous posts were referring to the necessity to override transit
> handlers in order to define transition actions. I confirmed that but
> added that it is not worse than other solutions mentioned. So, I don't
> see how and why this particular feature should be improved.

OK, maybe the purpose of this particular feature was different from what I thought. So I will change my
statement to:

The library should provide true support for the "transition" concept.

I tried to explain why I think this is important. If you ask me, "how" this should be done, all I can say is that
the TMP approach seems to look nice from the user perspective (disregarding compile times).

> > Also, your statement "you get precisely what the TMP solution
> > provides" is misleading. It's easiest for me to explain this with an
> > example from graph theory. A graph can be described by an "adjacency
> > list", but it can also be described by an "incidence list". The
> > state-based approach of the FSM library corresponds to the
> > description of a graph by the "adjacency list". The transition-based
> > approach of the TMP solution corresponds to the "incidence list". The
> > description by an "adjacency list" will often be more efficient than
> > the description by an "incidence list", but the "incidence list"
> > makes it easy to associate additional information to the edges of the
> > graph. You basically claim that you also support the "incidence list"
> > approach, but you don't provide support for associating additional
(Continue reading)

Permalink | Reply |
headers
Andrey Semashev | 3 Sep 23:43
Gravatar

Re: [review] FSM Second Call for Reviews

Thomas Klimpel wrote:

> I don't think that transitions should have internal state. But I
> think that the user should have the possibility to model them
> explicitly. And this includes associating an action to them.

You can. However, not everyone liked the exact syntax the library
provides in order to do that.

> This paragraph was more about Dave's statement "To start with,
> "states handle events" is not part of the abstraction of what an FSM
> is." and your reaction to it. Because I'm more familiar with graphs
> than with finite state machines, it's easier for me to think in terms
> of graphs.
> 
> One of my thoughts is: "Why not? The "adjacency list" is a valid
> description of a graph, just as the "incidence list" is." But on the
> other hand, you insist to deliver each event to a state, so you
> somehow take the "states handle events" to the extreme. I understand
> that you prefer the "states handle events", because the "adjacency
> list" is the more efficient representation of the two.

It's not just for efficiency reasons, it's a consequence of my
understanding of the FSM concept. I believe, the transitions should not
be responsible for actually processing events, but instead should
describe the state changes. While sometimes this is quite enough (e.g.
in case of validators of different kinds), it is often needed to do
other useful stuff on a certain event - IOW, to react on the event
receipt. It is my belief that this is not what transitions are intended
to do. That is why the proposed library is designed so that events
(Continue reading)

Permalink | Reply |
headers
Thomas Klimpel | 4 Sep 23:08

Re: [review] FSM Second Call for Reviews

> It's not just for efficiency reasons, it's a consequence of my
> understanding of the FSM concept. I believe, the transitions should not
> be responsible for actually processing events, but instead should
> describe the state changes. While sometimes this is quite enough (e.g.
> in case of validators of different kinds), it is often needed to do
> other useful stuff on a certain event - IOW, to react on the event
> receipt. It is my belief that this is not what transitions are intended
> to do. That is why the proposed library is designed so that events
> eventually are processed in states (or put it another way, reactions on
> the events receipt are defined in states).

Because fsm will currently deliver events handled by transitions to the target state, it's more sort of a
"transfer control to" than a "transition". This is probably a useful feature, especially for events that
should always be handled by the same state, but it's not suited for a simple representation of a finite
state machine in source code.

> However, I admit that there are possibilities that there is no need in
> reactions on events and the whole purpose of the state machine is to
> trace the transitions path, and the library is not perfectly suited for
> such use (although, it is still quite possible).

I don't think that the difference is the use case, but the representation in source code. I guess one
possible representation of a finite state machine (one with a finite number of stateless states) is the
list of transitions with the corresponding actions. (Let's forget about C++ for a moment. Let's simply
imagine a text file with this list, and some tools to process this list in order to perform certain tasks,
like optimizing the finite state machine, or verifying some important properties of the finite state
machine.) Some people seem to think that this is a particularly clear representation of the
corresponding machine. I'm no expert in this domain, so I can't say whether this judgment is justified.
But my evaluation lead me to the conclusion that the "transition" feature of the fsm library is ill suited
for a direct translation of this representation into source code.
(Continue reading)

Permalink | Reply |
headers
David Abrahams | 5 Sep 01:31
Favicon
Gravatar

Re: [review] FSM Second Call for Reviews


on Thu Sep 04 2008, "Thomas Klimpel" <Thomas.Klimpel-AT-synopsys.com> wrote:

> I don't think that the difference is the use case, but the representation in
> source code. I guess one possible representation of a finite state machine (one
> with a finite number of stateless states) is the list of transitions with the
> corresponding actions. (Let's forget about C++ for a moment. Let's simply
> imagine a text file with this list, and some tools to process this list in order
> to perform certain tasks, like optimizing the finite state machine, or verifying
> some important properties of the finite state machine.) Some people seem to
> think that this is a particularly clear representation of the corresponding
> machine. I'm no expert in this domain, so I can't say whether this judgment is
> justified. But my evaluation lead me to the conclusion that the "transition"
> feature of the fsm library is ill suited for a direct translation of this
> representation into source code.

For what it's worth, when I write an STT, I always group the transitions
by source state, so the representation is ultimately not all that
different than the state-based representation used by the proposed
library.  I think the main difference is in the ability to read the
structure of the machine without too much interference from other code.

--

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
(Continue reading)

Permalink | Reply |
headers
Chris Knight | 30 Aug 00:05

Re: [review] FSM Second Call for Reviews

On Monday 18 August 2008 7:21:51 pm Martin Vuille wrote:

> The formal review for Andrey Semashev's Finite State Machines (FSM)
> library has been running for a week now and continues until the 20th.

> What is your evaluation of the design?
I completed my FSM review by attempting to convert an existing implementation 
of the FIX transport protocol 
(http://www.fixprotocol.org/specifications/fixt1.1spec) that currently uses an 
in-house event driven state machine and swap it for the FSM's framework. 
Unfortunately, I was unable to agreeably implement such a system and I will 
now enumerate over the issues I came upon. 

The major architectural problem I see is the factoring of the transition 
handlers (which is usually defined in the transition table) into the state 
classes. This peculiar arrangement necessarily results in an overall verbose 
code structure. 

By placing the on_process() function in the state event handlers, FSM users 
are forced to define an is_applicable<> specialization and supply a static 
transit() function that defines the pattern matching rules the state machine 
applies to incoming events.  Factoring the transition handler into the various 
states results in the dispersion of the very transition table that defines 
the identity of a finite state machine. This was more than likely done in an 
attempt to optimize away the linked list pattern match (dispatch) found in 
the more common approach. Abstractly thinking however, the run-time switch 
based upon the current state of the fsm is going to occurr whether it be 
found in the fsm driver; whether it be found in the linked-list dispatch of 
CTM's fsm example or whether it be split amongst the various states.
(Continue reading)

Permalink | Reply |
headers
Andrey Semashev | 30 Aug 08:55
Gravatar

Re: [review] FSM Second Call for Reviews

Chris Knight wrote:
> 
> I do note my agreement that transition handler concept should be allowed to 
> return values on invalid events rather than be forced to throw exceptions 
> since in many cases an invalid event for a particular state is an error only 
> when viewed at the level of the state machine's "protocol" and often times 
> occurs just as often as the situation in which there is a valid match. 
> 
> This is somewhat provided with the switch_to<> mechanism however this seems to 
> exist outside the realm of the well-defined state machine's transition rules. 

There's no connection between unexpected events handling and the
switch_to mechanism. Unexpected events are detected before the FSM has a
chance to call switch_to (effectively, such events are detected at
compile time).

> This approach forces error handling into what would best be 
> described as the lexer (state_machine::process()'s callee) and thus outside 
> the domain of the state machine.

I disagree. When an event is unexpected, there's no handler in the FSM
that would be able to handle it. This is the whole point behind the term
"unexpected".

Since, as you said yourself, such unexpected events may actually appear
quite often, the library must provide an option to customize the
behavior when receiving them. This is accomplished with the unexpected
events handler, which is basically a user-provided functor, that is
called on such event receipt.
(Continue reading)

Permalink | Reply |
headers
Chris Knight | 31 Aug 08:58

Re: [review] FSM Second Call for Reviews

On Saturday 30 August 2008 1:55:57 am Andrey Semashev wrote:
> Chris Knight wrote:
> > I do note my agreement that transition handler concept should be allowed
> > to return values on invalid events rather than be forced to throw
> > exceptions since in many cases an invalid event for a particular state is
> > an error only when viewed at the level of the state machine's "protocol"
> > and often times occurs just as often as the situation in which there is a
> > valid match.
> >
> > This is somewhat provided with the switch_to<> mechanism however this
> > seems to exist outside the realm of the well-defined state machine's
> > transition rules.
>
> There's no connection between unexpected events handling and the
> switch_to mechanism. Unexpected events are detected before the FSM has a
> chance to call switch_to (effectively, such events are detected at
> compile time).

Sorry, I should have chosen my words more carefully. What I meant by 
an "invalid event" in this case was really an "error event" - a well defined 
event that simply is posted from within another event handler to handle 
protocol level errors. My only point was that one could implement a 
post_event via the switch_to<> functionality. 

> > This approach forces error handling into what would best be
> > described as the lexer (state_machine::process()'s callee) and thus
> > outside the domain of the state machine.
>
> I disagree. When an event is unexpected, there's no handler in the FSM
> that would be able to handle it. This is the whole point behind the term
(Continue reading)

Permalink | Reply |
headers
Andrey Semashev | 31 Aug 11:44
Gravatar

Re: [review] FSM Second Call for Reviews

On Sun, 2008-08-31 at 01:58 -0500, Chris Knight wrote:
> > Do you mean that the FSM should never compile if it detects
> unexpected
> > events?
> 
> Yes. If I say state_machine.process(Logon) when, for instance, the machine is 
> in the Disconnected state I would expect that to be detected by default if 
> for no other reason than the cost of doing so should be trivial/zero since 
> the check is done at compile time. It could potentially matter with the 
> addition of a post_event functionality as that would necessarily add the 
> additional requirement of state machien variant checking in the machine's 
> event double dispatcher that would process and dispatch posted base_events. 

IMHO, this would add too much burden for the FSM designers, especially
in case of relatively big state machines with lots of events. They would
have to add handlers in every state (or a generic template handler in a
state base class) to explicitly process such events. Often users don't
need such strict explicity in event processing and can simply rely on
unexpected events handler (which could be used to post events for the
state machine through a third-party scheduler). Having a macro to enable
strict consistency check looks quite enough for me.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
andrea carbone | 31 Aug 11:15

Re: [review] FSM Second Call for Reviews


Hello, hope it is not too late for my review, but I am a specialist in
missing deadlines ;) 
This review will be somewhat 'fair' on the technical issues that I don't
feel to be able to discuss.
I just want to report my feelings as a programmer.
I mostly code robotics/machine vision tasks and use boost almost everywhere.

>> What is your evaluation of the design?

As a programmer I  find FSM really clean and straightforward for my
programming tasks.
I have evaluated StateChart but really found it too complex when
implementing and everytime 
switched to ad hoc solutions.

>>What is your evaluation of the implementation?
Cannot evaluate the implementation. But following the discussion, I found
that the author has
replied consistently showing high knowledge on implementation issues. 

>> What is your evaluation of the documentation?
Very good. The author took care to offer a simple introductory example that
let you 
familiarize with the interface very smoothly. The rest of the documentation
is then appropriate.

>> What is your evaluation of the potential usefulness of the library?
I believe it is really helpful. Almost in my day to day coding tasks.
Following the discussion it is my impression that very few users use
(Continue reading)

Permalink | Reply |
headers
Andrey Semashev | 31 Aug 11:27
Gravatar

Re: [review] FSM Second Call for Reviews

On Sun, 2008-08-31 at 02:15 -0700, andrea carbone wrote:

> There seems to be problems with gcc-4.2 (the one shipped with apple
> developer tools) for a missing header but cannot be more precise now.

I don't have access to this platform to test the library. Could you send
me a code example and the compiler output? Perhaps, I could fix the
problem.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Thomas Klimpel | 31 Aug 15:50

Re: [review] FSM Second Call for Reviews

andrea carbone wrote:
> > What is your evaluation of the potential usefulness of the library?
> ...
> I had problems in reading the code offered by others while I felt
> immediately confortable with FSM examples. 

The example folder of the fsm library contains the "Turnstile" example and the "BitMachine" example. Do
there exists other "FSM examples" that I'm missing? I feel comfortable with the "Turnstile" example, but
I'm having a hard time with the "BitMachine" example. (I'm not a computer science PhD student.) On the
other hand, I had less problems with the statechart implementation of the same example. However, I admit
that my problems are probably caused by the usage of boost/preprocessor and boost/mpl techniques again.
Nevertheless, I find it surprising that somebody claims "I felt immediately comfortable with this code".
Attachment (winmail.dat): application/ms-tnef, 2961 bytes
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Andrey Semashev | 31 Aug 19:23
Gravatar

Re: [review] FSM Second Call for Reviews

On Sun, 2008-08-31 at 15:50 +0200, Thomas Klimpel wrote:
> andrea carbone wrote:
> > > What is your evaluation of the potential usefulness of the library?
> > ...
> > I had problems in reading the code offered by others while I felt
> > immediately confortable with FSM examples. 
> 
> The example folder of the fsm library contains the "Turnstile" example and the "BitMachine" example. Do
there exists other "FSM examples" that I'm missing? I feel comfortable with the "Turnstile" example, but
I'm having a hard time with the "BitMachine" example. (I'm not a computer science PhD student.) On the
other hand, I had less problems with the statechart implementation of the same example. However, I admit
that my problems are probably caused by the usage of boost/preprocessor and boost/mpl techniques again.
Nevertheless, I find it surprising that somebody claims "I felt immediately comfortable with this code".

Aside from these two examples, there are tests, which are quite
descriptive, and a number of examples that I have posted during the
discussion.

As for the BitMachine example, this is the code I used for performance
testing, which results are presented in the docs. It is not the typical
way of using the library, however, it shows an example of how the
library can be used to automatically generate state machines.

PS: Please, don't take that as offense, but I don't think that not
knowing some libraries or features may be given as an argument against
another library that internally uses them.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
(Continue reading)

Permalink | Reply |

Gmane