"Alexander Nasonov" <alnsn@yandex.ru> writes:

Jonathan Turkanis wrote:

...

It looks very interesting. Since there is no documentation, it would be helpful if you would give a brief description of what the library does and how it might be used.

See for example fsm.cpp here: http://aspn.activestate.com/ASPN/Mail/Message/boost/2185183

or http://aspn.activestate.com/ASPN/Mail/Message/2483684

Unfortunately, there is no documentation yet. I hope MPL interface can help understanding it. Basically, you turn *definition* defined below into MPL Associative Sequence with simple typedef overloads::set<definition>. It will behave similar to mpl::set<int(int,int), float(int,float)>. Note that without typeof deref can't be defined (workaround exists).

struct definition { int operator()(id<1> , int a, int b) const { return a + b; } float operator()(id<2> , int a, float b) const { return a + b; } };

Alexander, If you want to convince people that your idea is useful it would be a good idea to make it easier for them to understand why. While I understand everything you've written above, I still don't know why I'd want this, and I'm not prepared to reverse-engineer an example FSM implementation to find out. -- Dave Abrahams Boost Consulting www.boost-consulting.com

Alexander Nasonov wrote:

-- David Abrahams wrote:

...

Alexander,

If you want to convince people that your idea is useful it would be a good idea to make it easier for them to understand why. While I understand everything you've written above, I still don't know why I'd want this, and I'm not prepared to reverse-engineer an example FSM implementation to find out.

I don't know what do you mean exactly but I'm not yet going to convince people to use it because I'm in the middle of switching it from old interface to MPL set style.

What I would like to know is why you want to represent overload sets as compile-time collections: what sort of computations can you do with them in practice? I'm not expressing any scepticism that it's useful, I just want more information. Jonathan

[I'm sending this again because the first version never showed up] Alexander Nasonov wrote:

Jonathan, /* I'm replying to you privately because I don't have access to my private * mailbox from work and apparently I don't want to publish my business * address on internet. As soon as I get home I'll post it to boost list. */

Thanks, Alexander. I'm starting to understand now. Sorry I'm so slow.

Jonathan Turkanis wrote:

...

What I would like to know is why you want to represent overload sets as compile-time collections: what sort of computations can you do with them in practice? I'm not expressing any scepticism that it's useful, I just want more information.

Ok. Using state machine as an example:

struct Fsm { Running operator()( id<1>, Passive, EvActivate ) const; Stopped operator()( id<2>, Running, EvStartStop ) const; Running operator()( id<3>, Stopped, EvStartStop ) const; Stopped operator()( id<4>, Active, EvReset ) const; // ... };

I assume you're using id<..>'s to distinguish signatures even if they agree at every other position. My initial guess is that operator()'s with the same id<..> would correspond to functions having the same name. But then I see that each operator() seems to have a unique id<..>, which make me wonder where the overloading is.

Every call operator has such pattern:

NewState operator()(id<N>, State, Event) const;

and represents a transition from a state State to a state NewState caused by event Event. Transition logic is defined in the call operator body. If you were using MPL containers you would need to implement the logic in separate functions and pass them along the lines of metainformation about FSM:

Most interesing part here is FSM generator. Using the power of MPL and type_traits, it gets states out of transitions, allocates storage for them and generates transition table. Additionally, it could take into account inheritance relashionship between states to allow superstates/substates or it could treat void return type as no transition (action only) or it could discard transitions under certain circumstances or it could turn thrown exception into event and process it or ... A lot of interesting things are possible, thanks to MPL and other boost libraries :) My library is supposed to do same things. The difference is that step 1 and 2 are now not separated and you don't have to scroll up and down to make sure both parts are in sync.

Okay, I think I understand this example. I'm not so sure I see how, or if, this relates to overload resolution. In addition to the associative sequence operators, I would expect to have a metafunction that takes an argument list and determines which overload is called. Best Regards, Jonathan

Alexander Nasonov wrote:

Jonathan Turkanis wrote:

...

I assume you're using id<..>'s to distinguish signatures even if they agree at every other position. My initial guess is that operator()'s with the same id<..> would correspond to functions having the same name. But then I see that each operator() seems to have a unique id<..>, which make me wonder where the overloading is.

All ids are unique. This is how I can deduce a signature of every function without ambiguity. Of course, these ids change original overloads relation between functions but you can "bring it back" at call time:

Fsm fsm; fsm(enable_all(), Passive(), EvActivate()); ^^^^^^^^^^^^ enable_all is not yet in tarball but it's very simple. You just make sure every id<N> has a constructor that accept enable_all.

Why is it called an overload set, then? Because all the functions are overloads of operator()?

...

I'm not so sure I see how, or if, this relates to overload resolution. In addition to the associative sequence operators, I would expect to have a metafunction that takes an argument list and determines which overload is called.

Hmm, I'm not sure I can implemenent such metafunction because of complexity of C++ rules. I have to look at details.

I'm not really asking for you to provide this metafunction; I'm mostly trying to figure out what your implementation of overload sets has to do with the overload sets described in the standard. Jonathan

"Alexander Nasonov" <alnsn@yandex.ru> writes:

struct Fsm { Running operator()( id<1>, Passive, EvActivate ) const; Stopped operator()( id<2>, Running, EvStartStop ) const; Running operator()( id<3>, Stopped, EvStartStop ) const; Stopped operator()( id<4>, Active, EvReset ) const; // ... };

It's not directly relevant to your overloads component, but I'm very curious as to why you want to use _types_ to represent states. It seems counter-productive because of course types are static, and states are, well, stateful. Don't you end up wasting time and code translating between states and types? -- Dave Abrahams Boost Consulting www.boost-consulting.com

I wrote:

That's possible. If your automata is essentially value-based (for example, FSM for searching subsrings in a string) then it's better to use something else. But, in a modern world, type identity plays an important role too. For example, if someone is developing FSM silimar to mine where each event has additional params (eg, EvActive may have priority), what would he/she prefer, to invent his/her own protocol to transmit event code and event specific params or to use existing technology like CORBA and to send objects?

Oopps, I mixed states and events up. I answer again. David Abrahams wrote:

"Alexander Nasonov" <alnsn@yandex.ru> writes:

...

struct Fsm { Running operator()( id<1>, Passive, EvActivate ) const; Stopped operator()( id<2>, Running, EvStartStop ) const; Running operator()( id<3>, Stopped, EvStartStop ) const; Stopped operator()( id<4>, Active, EvReset ) const; // ... };

It's not directly relevant to your overloads component, but I'm very curious as to why you want to use _types_ to represent states. It seems counter-productive because of course types are static, and states are, well, stateful. Don't you end up wasting time and code translating between states and types?

That's not exactly true. States are _types_ only at compile-time. At runtime, they are objects passed to correspondent call operator. Objects may be stateful. struct Running { /* stateful */ }; struct Stopped { /* stateful */ }; Fsm fsm; Passive initial; Running r = fsm(enable_all(), initial, EvActivate()); Stopped s = fsm(enable_all(), r, EvStartStop()); r = fsm(enable_all(), s, EvStartStop()); s = fsm(enable_all(), r, EvReset()); -- Alexander

David Abrahams wrote:

"Alexander Nasonov" <alnsn@yandex.ru> writes:

...

struct Running { /* stateful */ }; struct Stopped { /* stateful */ };

Even more confusing; now you need a dynamic allocation Why I need it?

to represent and change the current state of the machine. I suppose you could use variant, That's one possible representation

but I never understood why people want to put state _inside_ of states -- it doesn't match up with the domain abstraction of state machines. The state's identity should be enough.

There are two kinds of state: state of machine and class state. They're from different domains. Suppose Running state has m_speed member. Is it worth adding this member to the state identity? PS: We are ahead of time, boost::fsm review is scheduled on Feb 21 :) -- Alexander

David Abrahams wrote:

What is "class state?" Can you describe its domain? What are the principle abstractions in that domain? Ok, you catched me. In most cases, these members are shared across states. So, they have to be members of Fsm. Class states might hold a "baton" to pass on to a next state but I don't see any important use case.

If I try to map what you're describing onto the state machine designs that we did for "C++ Template Metaprogramming" (and that I posted here), I could achieve something similar by simply putting storage for auxilliary data (like speed) in a data member of the derived FSM class.

The man who invented examples is the greatest inventor of all time! After looking at mpl example I understand what do you mean. My code can be rewriten to support your style. You could typedef Running as state<0>, Stopped as state<1> and so on. The framework could find out that all state<N> are stateless (what a mess! :) and left out storage generation for them. I wonder when and why you need these numbers? Not for passing to switch statement, I hope? I suppose, you use them to check for a particular state of set of states like whether FSM is in final state(s) or not. If you do so, I do so as well.

While I have to admit that your particular example seems to naturally call for associating that auxilliary data directly with the state class, that model doesn't generalize well AFAICT. There could be auxilliary data that's needed -- persistently -- for more than one state.

Agree.

David Abrahams <dave@boost-consulting.com> writes:

oops, it didn't make it onto the CD. I've posted it here in the past, but it's attached again.

Oops again! Here it is: -- Dave Abrahams Boost Consulting www.boost-consulting.com

"Alexander Nasonov" <alnsn@yandex.ru> writes:

David Abrahams wrote:

...

I'll ask again: what is the point of using types for states?

You can't easily emulate is-a relationship with numbers. With classes you just derive one class from another.

Okay, but what's the value of modeling an is-a relationship between states? In a FSM, states are distinct. One state is-not-a nother state.

My example demonstrates this technique.

AFAICT it seems to be a way of grouping states, or perhaps of emulating substates, so you can avoid writing the transitions that a group of states has in common (?)

...

I don't know if I do so, yet ;-)

I mean I _can_ do so but switching to mpl concept doesn't go smoothly. Currently, I'm trying to understand why size of mpl::set<id<1>, id<2> > is 2 while distance between begin and end is one?

I'm lost, sorry. -- Dave Abrahams Boost Consulting www.boost-consulting.com

"Alexander Nasonov" <alnsn@yandex.ru> writes:

David Abrahams wrote:

...

Okay, but what's the value of modeling an is-a relationship between states? In a FSM, states are distinct. One state is-not-a nother state.

Dog is-a Animal at modelling state.

Sorry, I don't understand the meaning of "at modelling state." Oh, you mean "at modelling stage?"

At runtime

Dog dog;

is not-a

Animal animal;

Likewise, Running state is-a Active state at modelling stage.

So it's just a way of classifying states with common properties?

...

AFAICT it seems to be a way of grouping states, or perhaps of emulating substates, so you can avoid writing the transitions that a group of states has in common (?)

Yep.

That's a clever approach to dealing with substates. I'm not sure it works for every case, but then, the details of how substates are supposed to work have always eluded me. I still don't see how you can keep associated data stored in the Active base sub-object alive across all the other active states, at least not without copying it. -- Dave Abrahams Boost Consulting www.boost-consulting.com

"Alexander Nasonov" <alnsn@yandex.ru> writes:

David Abrahams wrote:

...

So it's just a way of classifying states with common properties? Yes.

...

That's a clever approach to dealing with substates. I'm not sure it works for every case, but then, the details of how substates are supposed to work have always eluded me.

I'm not quite sure my approach works well with substates.

...

I still don't see how you can keep associated data stored in the Active base sub-object alive across all the other active states, at least not without copying it.

Transition is copying. It is implied by transition pattern:

NewState operator()(id, State, Event) const; ^^^^^^^^ new state is returned by value

That's a bit unattractive performance-wise. -- Dave Abrahams Boost Consulting www.boost-consulting.com

David Abrahams wrote:

...

That's not exactly true. States are _types_ only at compile-time. At runtime, they are objects passed to correspondent call operator. Objects may be stateful.

struct Running { /* stateful */ }; struct Stopped { /* stateful */ };

Even more confusing; now you need a dynamic allocation to represent and change the current state of the machine. I suppose you could use variant, but I never understood why people want to put state _inside_ of states --

You very often encounter the situation that you need a variable that is only used in a part of a state machine (i.e. only one state or a few states need access to it). IMO, it is good design to confine the lifetime of such a variable so that it will not even exist when the machine does not happen to reside in the states that need access to the variable. Even for a very tiny state machine like the StopWatch in my tutorial it made sense to limit the lifetime of one variable. See http://tinyurl.com/5q9hk (State-local storage) for details.

it doesn't match up with the domain abstraction of state machines.

How do you come to that conclusion?

The state's identity should be enough.

It is sometimes enough for small simple machines but not almost never for large complex ones. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.

David Abrahams wrote:

"Andreas Huber" <ahd6974-spamgroupstrap@yahoo.com> writes:

...

You very often encounter the situation that you need a variable that is only used in a part of a state machine (i.e. only one state or a few states need access to it). IMO, it is good design to confine the lifetime of such a variable so that it will not even exist when the machine does not happen to reside in the states that need access to the variable. Even for a very tiny state machine like the StopWatch in my tutorial it made sense to limit the lifetime of one variable. See http://tinyurl.com/5q9hk (State-local storage) for details.

But as I pointed out and -- you seem to agree -- that variable must often persist through several states to which it applies.

Yes, often.

In that case, if you want the lifetime to change based on those states, you can't store the variable in the state object.

Not in an innermost state, no. But you can simply store the variable in an outer state that contains all the states that need to access the variable. More often than not the outer state already exists for other reasons (e.g. reactions that all inner states have in common). E.g. in the StopWatch example, the Active state not only exists so that it can store the elapsedTime_ member but also because there is a self-transition that can be triggered when the machine is in either the Stopped or Running states.

boost::optional in the state machine itself is the proper generalization of the idea.

It makes things global that should rather be left local. Below, as a counter-measure, you devise a system that does away with one aspect of the globality (the lifetime). But, other negative aspects of the globality remain, i.e. you still have to change the FSM class when you want to introduce a new variable or change an existing one.

...

...

it doesn't match up with the domain abstraction of state machines.

How do you come to that conclusion?

I have never seen a formal description of the FSM abstraction that described states as carrying additional data inside them. Have you?

No I haven't. To me this just follows naturally and at least a few boost::fsm users seem to agree. I think it is awkward to store variables in the state machine object, where they can be accessed from states that are not supposed to access them. Of course this can be managed by the framework as you suggest below, but the FSM class still becomes a change hotspot. To me, such hotspots are an indication that there is something wrong with the design. Moreover, parameterized states (aka submachines, which are reusable FSM building blocks) are hard to implement without state-local storage.

...

...

The state's identity should be enough.

It is sometimes enough for small simple machines but not almost never for large complex ones.

I believe that auxilliary data is sometimes needed, but I don't believe it's ever needed *in the state*. A framework that managed auxilliary state data might accept a a structure like this:

mpl::vector< // speed applies to the "running" state aux_data<&player::speed, running>

// title applies to the "stopped" and "paused" states , aux_data<&player::title, stopped, paused>

...

where speed and title are boost::optional objects that are automatically cleared by the state machine framework upon leaving the states listed with them.

As outlined above, I think it is more natural and much more obvious to just store variables in outer states. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.

David Abrahams <dave <at> boost-consulting.com> writes:

"Andreas Huber" <ahd6974-spamgroupstrap <at> yahoo.com> writes:

...

David Abrahams wrote:

...

"Andreas Huber" <ahd6974-spamgroupstrap <at> yahoo.com> writes:

...

You very often encounter the situation that you need a variable that is only used in a part of a state machine (i.e. only one state or a few states need access to it). IMO, it is good design to confine the lifetime of such a variable so that it will not even exist when the machine does not happen to reside in the states that need access to the variable. Even for a very tiny state machine like the StopWatch in my tutorial it made sense to limit the lifetime of one variable. See http://tinyurl.com/5q9hk (State-local storage) for details.

But as I pointed out and -- you seem to agree -- that variable must often persist through several states to which it applies.

Yes, often.

...

In that case, if you want the lifetime to change based on those states, you can't store the variable in the state object.

Not in an innermost state, no. But you can simply store the variable in an outer state that contains all the states that need to access the variable.

Can't we call that thing "the state's associated data object?"

You mean the variable?

Calling it "the state" gives me the willies.

Huh? I don't see where I have called the variable a state, so my assumption above must be wrong. I guess you lost me...

...

More often than not the outer state already exists for other reasons (e.g. reactions that all inner states have in common). E.g. in the StopWatch example, the Active state not only exists so that it can store the elapsedTime_ member but also because there is a self-transition that can be triggered when the machine is in either the Stopped or Running states.

Sorry, details please? Where is this example?

http://tinyurl.com/5q9hk (State-local storage)

...

...

...

...

it doesn't match up with the domain abstraction of state machines.

How do you come to that conclusion?

I have never seen a formal description of the FSM abstraction that described states as carrying additional data inside them. Have you?

No I haven't. To me this just follows naturally and at least a few boost::fsm users seem to agree. I think it is awkward to store variables in the state machine object, where they can be accessed from states that are not supposed to access them. Of course this can be managed by the framework as you suggest below, but the FSM class still becomes a change hotspot. To me, such hotspots are an indication that there is something wrong with the design. Moreover, parameterized states (aka submachines, which are reusable FSM building blocks) are hard to implement without state-local storage.

Do you agree with Mr. Nasonov that outer states should be implemented as base classes of inner states?

Not as a general rule, no. However, sometimes it can be a valuable way of implementing FSMs but this of course limits the value of variables in states, see below.

Because I don't see how the data lifetime issues work out if you do that. Transitioning from INNER1 to INNER2 still causes all the data members of OUTER to be destroyed, because the INNER1/2 instances have distinct OUTER sub-objects.

I guess you could copy the relevant portion of the old state object by the means of giving each inner state a templated constructor (untested): struct Active {}; struct Running : Active { template< class Outer > Running( const Outer & outer ) : Active( outer ) {} }; The Ctor is templated so that this continues to work even if Active stops being an outermost state. But now I must admit that it's getting unwieldy ;-). Anyway, your observation is correct: Without the workaround above, there is no difference in lifetime no matter whether you store your variable in an innermost state or any of its direct or indirect outer states. It gets destructed with each transition. However, such variables would still be useful for in-state reactions. BTW, this lifetime issue is the primary reason why in boost::fsm an inner state does not derive from its direct outer state. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.

David Abrahams wrote: [snip]

...

...

...

Not in an innermost state, no. But you can simply store the variable in an outer state that contains all the states that need to access the variable.

Can't we call that thing "the state's associated data object?"

You mean the variable?

No, I mean the thing you're calling "the state."

That's pretty much agreed-upon terminology. The word "state" in the FSM field refers to two different things: 1. From <http://en.wikipedia.org/wiki/State_%28computer_science%29>: <quote>In information processing, a state is the complete set of properties (for example, its energy level, etc. see state (physics)) transmitted by an object to an observer via one or more channels. Any change in the nature or quantity of such properties in a state is detected by an observer and thus a transmission of information occurs.</quote> By this definition one would say that an FSM *has* a particular state. I assume that's the definition you use. 2. In state charts people call the boxes or circles (see e.g. <http://en.wikipedia.org/wiki/State_diagram#Mealy_machine>) also states. By this definition one would say that an FSM *is* *in* a particular state.

It's really the collection of data that is live when the machine is in a particular state.

Exactly.

The machine's state does _not_ correspond to the identity of that object.

Right.

Maybe it corresponds to that object's type.

... plus the auxilary data objects that are used/accessible when the machine is in that state.

...

...

Calling it "the state" gives me the willies.

Huh? I don't see where I have called the variable a state, so my assumption above must be wrong. I guess you lost me...

Let me know if you're still confused.

I hope not.

...

...

...

More often than not the outer state already exists for other reasons (e.g. reactions that all inner states have in common). E.g. in the StopWatch example, the Active state not only exists so that it can store the elapsedTime_ member but also because there is a self-transition that can be triggered when the machine is in either the Stopped or Running states.

Sorry, details please? Where is this example?

http://tinyurl.com/5q9hk (State-local storage)

So, it's a shorthand for writing the same transition to stop out of all of its substates.

Yes, or more verbosely, the self-transition on Active expresses that no matter in what inner state (Running or Stopped) the machine currently is, EvReset will always trigger an exit out of the currently active inner state and the Active state. After that the Active state is entered and then the Stopped state is entered (because it is the initial state inside Active).

...

...

Because I don't see how the data lifetime issues work out if you do that. Transitioning from INNER1 to INNER2 still causes all the data members of OUTER to be destroyed, because the INNER1/2 instances have distinct OUTER sub-objects.

I guess you could copy the relevant portion of the old state object by the means of giving each inner state a templated constructor (untested):

Copying data doesn't extend its lifetime; it makes a copy. It may be important not to destroy the original. Furthermore, the original may not be copyable.

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