Refactoring state machines (Was a bunch of other stuff...)

"Bob Badour" wrote:
> David Barrett-Lennard wrote:
>> Bob Badour wrote:

<snip>

>>>When one uses OO, one naturally tends to have interacting state
>>>machines and to have more of these than when does not use OO. When
>>>one's application is naturally a very large state machine, one can
>>>decompose it into smaller state machines as an abstraction technique
>>>to break it up into human-manageable chunks.
>>
>> Yes, this is both a good characterisation of OO, and of the types of
>> problems it is good at solving.
>>
>>
>>>However, if one were truly abstracting a large state machine like
>>>that, one would tend to want to prove that the aggregate of the
>>>smaller state machines omits no states and introduces no new and
>>>unwanted state transitions etc. Nobody, as far as I know, practices
>>>OO in this way.
>>
>> I try to.
>
> You are the first I have encountered, and I suspect you are from a
> very select few. Does any theory of state machines exist that
> facilitates this task?

This is a good question, and one I've been interested in for a long time. In my experience, OO does not begin with a single state machine modelling an overall application, but rather identifies individual state machines (i.e. objects) and their interactions. Now I have wondered if a more robust approach might be to start with a state machine design of the entire application. Then refactor it into smaller, interacting state machines. I don't know how manageable such an approach would be for a large application, but I'd be curious to try it.

The question I have is how does one refactor a large state machines into smaller ones?

I don't have a lot of experience attempting this. The few times I've tried it, I've found it to be less than intuitive. I guess one could begin by identifying clusters of states that are connected via transitions. Factor these clusters out into their own state machines. Using hierarchical state machines, one could take the substates of a superstate and factor them out as a small state machine in and of themselves.

An interesting exercise might be to take David Harel's state machine model of a Citizens quartz watch and factor it into a set of smaller state machines.

http://www.quantum-leaps.com/resources/Harel87.pdf

One key point, though: A state machine can only be in one state at a time (orthagonal states notwithstanding). If we split a single state machine into two state machines, this implies that only one of these state machines will be active at a time. In splitting our state machine in two, we severed one or more of the transitions that connected the two groups of states. Instead of theses transitions, one of the smaller state machines reach a final state, sending an event to the other state machine, which then enters its initial state and begins its life. The resulting behavior should be exactly the same.

I probably didn't express this very clearly, and I'm mainly thinking out loud here. I'd be interested in hearing what others with more experience would have to say. Received on Sat Jul 01 2006 - 05:15:31 CEST