Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > State design pattern proliferation issue

Reply
Thread Tools

State design pattern proliferation issue

 
 
cstratelos@gmail.com
Guest
Posts: n/a
 
      05-22-2006
Hello,

I am currently working on a finite state machine framework and the use
of the command and state design patterns (as well as some other ones
obviously) has come up naturally.

So, the state design pattern seems to be the most logical solution to a
state dependent system. The problem is that most of the examples,
tutorials, discussions and books (the GOF book and the Head First
Design Patterns) I have read on this pattern only use a very small
number of states. What happens when your system can be modeled with
hundreds of states for example?

One such occasion is when there is a number of variables (or degrees of
freedom, or whatever you want to call them) the system has to get from
the user. If I create a state for each variable then it becomes obvious
that the number of states grows very rapidly.

For example if the system has variables A, B and C then you could have
the following states:

Var_A_Is_Filled
Var_B_Is_Filled
Var_C_Is_Filled

Vars_AB_Are_Filled
Vars_AC_Are_Filled
Vars_BC_Are_Filled

Vars_ABC_Are_Filled

and all the transitions between them.

Any thoughts?

PS: How do you go about extending the pattern in order to allow for the
system to be in multiple states at the same time?

 
Reply With Quote
 
 
 
 
bugbear
Guest
Posts: n/a
 
      05-22-2006
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> Hello,
>
> I am currently working on a finite state machine framework and the use
> of the command and state design patterns (as well as some other ones
> obviously) has come up naturally.
>
> So, the state design pattern seems to be the most logical solution to a
> state dependent system. The problem is that most of the examples,
> tutorials, discussions and books (the GOF book and the Head First
> Design Patterns) I have read on this pattern only use a very small
> number of states. What happens when your system can be modeled with
> hundreds of states for example?


IMHO the pattern becomes a poor choice.

Either that, or you use multiple independent
state machines.

BugBear
 
Reply With Quote
 
 
 
 
Ed Kirwan
Guest
Posts: n/a
 
      05-22-2006
(E-Mail Removed) wrote:
> Hello,
>
> I am currently working on a finite state machine framework and the use
> of the command and state design patterns (as well as some other ones
> obviously) has come up naturally.
>


>
> For example if the system has variables A, B and C then you could have
> the following states:
>
> Var_A_Is_Filled
> Var_B_Is_Filled
> Var_C_Is_Filled
>
> Vars_AB_Are_Filled
> Vars_AC_Are_Filled
> Vars_BC_Are_Filled
>
> Vars_ABC_Are_Filled
>
> and all the transitions between them.
>
> Any thoughts?


The, "State," of the, "State pattern," shouldn't reflect the bit-by-bit
representation of your system. The states should encapsulate useful
chunks of your system's behaviour, where all those chunks have a similar
interface. You can then, of course, form a hierarchy of states to get
down to the nitty-gritty.

What is your system? Is it an application/J2EE monster/servlet?

If, for example, your system is a servlet, and your customers are to
select a product to buy on one page, then credit card information on the
next, then a shipping address, then a, "Congratulations," screen, then
here straight away are four, high-level states.

The first state will be ProductSelectionState: this state will show all
your goods and a means of selecting one (or more) - this certainly won't
be a number of different states, each one representing the possibility
to select an individual item.

The second state will be CreditCardProcessingState, which will allow the
client to type in all information in all its fields, and will let him
know when any fields are unfilled or incorrect - it will not be a
separate state for each field.

Etc.

If memory serves, GoF give the example of a Socket: and that's fine for
defining a socket's behaviour; but if you're trying to design a system,
then you'll certainly end up with, "Bigger," states, and most likely
hierarchies of states.

>
> PS: How do you go about extending the pattern in order to allow for the
> system to be in multiple states at the same time?
>


Hmm, I suppose the closest thing I can think of here is that hierarchy
again. Given the example above, a higher state could be DataEntryState,
who's two children are CreditCardProcessingState and
PersonalInformationState. This way your system is in the DataEntryState
at one level and also in the PersonalInformationState at another,
without contradiction.

Unless you've nudged into the realm of quantum computing, that is, in
which case one state should take care of everything, simultaneously (as
long as you don't try to observe it).

--
www.EdmundKirwan.com - Home of The Fractal Class Composition.

Download Fractality, free Java code analyzer:
http://www.EdmundKirwan.com/servlet/...c-page130.html
 
Reply With Quote
 
Thomas Weidenfeller
Guest
Posts: n/a
 
      05-22-2006
(E-Mail Removed) wrote:
> What happens when your system can be modeled with
> hundreds of states for example?


The state-pattern approach blows up, rapidly. It just does not scale.

At that point people go back to the trusted and tried way of
representing the current state of a state machine by using a simple
integer or enum.

> One such occasion is when there is a number of variables (or degrees of
> freedom, or whatever you want to call them) the system has to get from
> the user. If I create a state for each variable then it becomes obvious
> that the number of states grows very rapidly.


Now you are mixing up things. You don't have a "state for each
variable". In your own example you have a state for each possible
combination of the variables (which are themselves boolean). And this is
what your state-pattern approach blows out of the water. The possible
combinations, and thus the required number of classes explode.

> Any thoughts?


Do it the classic way.

> PS: How do you go about extending the pattern in order to allow for the
> system to be in multiple states at the same time?


What do you mean exactly? A system with multiple independent states?
Multiple independent state machines.

Or a system with multiple, but dependent states? Then this is logically
one big state machine. Depending on the coupling of the states it might
be possible to break down the big state machine in a couple of smaller
ones, and using superstates to decide which one is currently active.

/Thomas
--
The comp.lang.java.gui FAQ:
ftp://ftp.cs.uu.nl/pub/NEWS.ANSWERS/...g/java/gui/faq
http://www.uni-giessen.de/faq/archiv....java.gui.faq/
 
Reply With Quote
 
cstratelos@gmail.com
Guest
Posts: n/a
 
      05-22-2006
The fact that it does not scale is my problem exactly.

Obviously nobody wants to reinvent the wheel. You wouldn't want to
model the actual hardware (memory) state in your application by
following a "one variable one state" approach.

But what I'm talking about is not _one_ application. I'm talking about
a framework that will allow the development of applications that will
have states and some kind of information discovery associated with each
one of them. One extra contraint is that, unlike a classic web app, the
flow is not predefined. You could actually fill multiple variables at a
time. When you design a web page you set the rules. You say: "here the
user enters their phone number". This is not the case here.

Anyway, I guess the pattern works for problems with a few states. Lots
of states make it intractable...

 
Reply With Quote
 
Chris Uppal
Guest
Posts: n/a
 
      05-22-2006
(E-Mail Removed) wrote:

> But what I'm talking about is not _one_ application. I'm talking about
> a framework that will allow the development of applications that will
> have states and some kind of information discovery associated with each
> one of them. One extra contraint is that, unlike a classic web app, the
> flow is not predefined. You could actually fill multiple variables at a
> time. When you design a web page you set the rules. You say: "here the
> user enters their phone number". This is not the case here.


I've never been wildly impressed by the State pattern when used -- as its name
would seem to encourage -- to implement state machines. Typically, if an app
has a small, fixed number of "states" then there is little or nothing to be
gained by pulling the "stateness" of it out into a separate abstraction.
Objects are already the ideal tool for managing and expressing changing state,
so why do we need /another/ object ?

OTOH, if the set of states is not small, or is calculated dynamically, or is
otherwise not easy to hardwire, then a table-driven approach seems more
feasible than the State pattern.

In this case, you might benefit from a complete re-think of your underlying
abstraction (which is not to say junk hundreds of thousands of lines of code,
but change the way you think about how things work together).

I don't know your application, but one possible replacement abstraction would
be a system of "gates" and "conditions" -- each gate would own a list of
conditions, and the user would only be allowed to pass through a gate when s/he
had satisfied all the relevant conditions (e.g. supplying a certain value in a
form). You could make that linear (or tree-shaped) so that the user advanced
down a pre-determined sequence of gates. Alternatively you could remove that
sequence and just consider the user to have "passed through" all the gates with
conditions that have all been satisfied, and were thus s/he is allowed to
perform any of the actions controlled by those gates. Or maybe a hybrid system
when some sets of gates form a sequence, whereas others work indeterminately.
Or perhaps passing though some gates would deactivate others (e.g. pressing
the final OK means you can't go back and add to the sopping cart).

I have no idea whether any of the previous paragraph makes any real sense for
the class of applications you are considering. Even if it does, I really mean
it only as an illustration of how reformulating the way you think about a
problem can remove apparently insurmountable problems.

(And also as a small illustration of how design /precedes/ Patterns. You
don't design by selecting from a palette of Patterns; you design by choosing
apt and implement abstractions. You /then/, if you want, look for
well-known Patterns in that design, since that may make it easier for you to
communicate aspects of the /implementation/ of your abstraction.)

-- chris



 
Reply With Quote
 
Patricia Shanahan
Guest
Posts: n/a
 
      05-22-2006
(E-Mail Removed) wrote:
> Hello,
>
> I am currently working on a finite state machine framework and the use
> of the command and state design patterns (as well as some other ones
> obviously) has come up naturally.
>
> So, the state design pattern seems to be the most logical solution to a
> state dependent system. The problem is that most of the examples,
> tutorials, discussions and books (the GOF book and the Head First
> Design Patterns) I have read on this pattern only use a very small
> number of states. What happens when your system can be modeled with
> hundreds of states for example?
>
> One such occasion is when there is a number of variables (or degrees of
> freedom, or whatever you want to call them) the system has to get from
> the user. If I create a state for each variable then it becomes obvious
> that the number of states grows very rapidly.
>
> For example if the system has variables A, B and C then you could have
> the following states:
>
> Var_A_Is_Filled
> Var_B_Is_Filled
> Var_C_Is_Filled
>
> Vars_AB_Are_Filled
> Vars_AC_Are_Filled
> Vars_BC_Are_Filled
>
> Vars_ABC_Are_Filled
>
> and all the transitions between them.
>
> Any thoughts?
>
> PS: How do you go about extending the pattern in order to allow for the
> system to be in multiple states at the same time?
>


I think you should consider refactoring the state machine representation
before mapping it into classes and objects.

A large state machine, especially when the system has components with
their own states, is usually more tractable decomposed into a hierarchy
of interacting state machines.

If you do that decomposition, the state machine hierarchy will naturally
map into an object hierarchy in which a system state object has several
objects representing states of subsystems.

http://faculty.juniata.edu/rhodes/smui/statechart.htm has a quick
introduction, with diagrams, that may help.

See search terms such as "statechart", and "hierarchy" or
"decomposition" in combination with "state machine".

Patricia
 
Reply With Quote
 
Martin Gregorie
Guest
Posts: n/a
 
      05-22-2006
Chris Uppal wrote:
> OTOH, if the set of states is not small, or is calculated dynamically, or is
> otherwise not easy to hardwire, then a table-driven approach seems more
> feasible than the State pattern.
>

Yes, this works well. I've used it to define and implement sliding
window protocols for handling sequentially numbered messages. This
approach is easy to implement and, as a bonus, once you get your mind
around it, defining the state machine is easy too.

I've also implemented FSM design tools for this approach. This is very
easy if you can predefine the number of variables used to select cells
in the FSM table and lends itself to the development of an interactive
FSM editor: I did that using a 4GL but it should be fairly straight
forward in Java. The benefit of doing this is that the evolving design
is easy to modify interactively, it can be printed for inspection and
its also possible to automate FSM validation (e.g. completeness checks).

Generating an automatic test harness from the database is quite easy
too. FSM code generation shouldn't be too difficult, either, though I
never went there. Both would, of course, probably need handcrafted
interfacing code and FSM action modules, but the ability to generate
test cases and the main FSM logic is still very useful.


--
martin@ | Martin Gregorie
gregorie. | Essex, UK
org |
 
Reply With Quote
 
Wibble
Guest
Posts: n/a
 
      05-23-2006
Patricia Shanahan wrote:
> (E-Mail Removed) wrote:
>> Hello,
>>
>> I am currently working on a finite state machine framework and the use
>> of the command and state design patterns (as well as some other ones
>> obviously) has come up naturally.
>>
>> So, the state design pattern seems to be the most logical solution to a
>> state dependent system. The problem is that most of the examples,
>> tutorials, discussions and books (the GOF book and the Head First
>> Design Patterns) I have read on this pattern only use a very small
>> number of states. What happens when your system can be modeled with
>> hundreds of states for example?
>>
>> One such occasion is when there is a number of variables (or degrees of
>> freedom, or whatever you want to call them) the system has to get from
>> the user. If I create a state for each variable then it becomes obvious
>> that the number of states grows very rapidly.
>>
>> For example if the system has variables A, B and C then you could have
>> the following states:
>>
>> Var_A_Is_Filled
>> Var_B_Is_Filled
>> Var_C_Is_Filled
>>
>> Vars_AB_Are_Filled
>> Vars_AC_Are_Filled
>> Vars_BC_Are_Filled
>>
>> Vars_ABC_Are_Filled
>>
>> and all the transitions between them.
>>
>> Any thoughts?
>>
>> PS: How do you go about extending the pattern in order to allow for the
>> system to be in multiple states at the same time?
>>

>
> I think you should consider refactoring the state machine representation
> before mapping it into classes and objects.
>
> A large state machine, especially when the system has components with
> their own states, is usually more tractable decomposed into a hierarchy
> of interacting state machines.
>
> If you do that decomposition, the state machine hierarchy will naturally
> map into an object hierarchy in which a system state object has several
> objects representing states of subsystems.
>
> http://faculty.juniata.edu/rhodes/smui/statechart.htm has a quick
> introduction, with diagrams, that may help.
>
> See search terms such as "statechart", and "hierarchy" or
> "decomposition" in combination with "state machine".
>
> Patricia


If you're looking for opportunism, consider a rule base system
like

http://labs.jboss.com/portal/index.h...ect=jbossrules

State machines become pretty hard to debug, or conceptualize once you
have more than a handful of states. You generally have to write some
kind of language to model it, and java is probably a better language,
with more support.

 
Reply With Quote
 
Thomas Weidenfeller
Guest
Posts: n/a
 
      05-23-2006
(E-Mail Removed) wrote:
> The fact that it does not scale is my problem exactly.


And it will not scale. It is inherent to the pattern that each state is
represented by an own class. Many states therefore means many classes.
Many classes means it becomes rapidly unmanageable. Game over.

Logical conclusion: Drop the concept of each state being a separate class.

> But what I'm talking about is not _one_ application.


And what are you talking about. Because you are not making clear what
you really want.

> I'm talking about
> a framework that will allow the development of applications that will
> have states and some kind of information discovery associated with each
> one of them.


So? There is nothing special about that. People build state machines
since ages. With toolkits, with description languages, with code
generators, by hand or with a mixture of methods. With and without
existing frameworks. And definitely not only for one application.

> One extra contraint is that, unlike a classic web app, the
> flow is not predefined.


What flow? I wish you wouldn't invent your own terminology. Do you mean
a sequence of events? That one is never predefined. It is up to the
state machine implementation to determine if a particular sequence of
events is valid or illegal.


--
The comp.lang.java.gui FAQ:
ftp://ftp.cs.uu.nl/pub/NEWS.ANSWERS/...g/java/gui/faq
http://www.uni-giessen.de/faq/archiv....java.gui.faq/
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
C++ and design Pattern (Composite design Pattern ) Pallav singh C++ 1 01-22-2012 10:48 PM
C++ and design Pattern (Composite design Pattern ) Pallav singh C++ 0 01-22-2012 10:26 PM
C++ and design Pattern (Composite design Pattern ) Pallav singh C++ 0 01-22-2012 10:25 PM
May I have a example of design pattern of "composite", I still feel fuzzy after reading book of Addison-Wesley's"design pattern " jones9413@yahoo.com C++ 1 08-31-2007 04:09 AM
Network proliferation =?Utf-8?B?QnJlYWQtdGVhc2Vy?= MCSE 27 05-05-2006 02:45 AM



Advertisments