State design pattern proliferation issue

Discussion in 'Java' started by cstratelos@gmail.com, May 22, 2006.

  1. Guest

    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?
     
    , May 22, 2006
    #1
    1. Advertising

  2. bugbear Guest

    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
     
    bugbear, May 22, 2006
    #2
    1. Advertising

  3. Ed Kirwan Guest

    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:
    www.EdmundKirwan.com/servlet/fractal/frac-page130.html
     
    Ed Kirwan, May 22, 2006
    #3
  4. 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/computer-lang/java/gui/faq
    http://www.uni-giessen.de/faq/archiv/computer-lang.java.gui.faq/
     
    Thomas Weidenfeller, May 22, 2006
    #4
  5. Guest

    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...
     
    , May 22, 2006
    #5
  6. Chris Uppal Guest

    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
     
    Chris Uppal, May 22, 2006
    #6
  7. 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
     
    Patricia Shanahan, May 22, 2006
    #7
  8. 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 |
     
    Martin Gregorie, May 23, 2006
    #8
  9. Wibble Guest

    Patricia Shanahan wrote:
    > 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.html?ctrl:id=page.default.info&project=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.
     
    Wibble, May 23, 2006
    #9
  10. 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/computer-lang/java/gui/faq
    http://www.uni-giessen.de/faq/archiv/computer-lang.java.gui.faq/
     
    Thomas Weidenfeller, May 23, 2006
    #10
  11. Ed Kirwan Guest

    Thomas Weidenfeller wrote:

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


    Going OT here; particularly, I'm not dealing with the state pattern
    here, just normal, OO class development.

    I like scaling problems. I find the whole scaling issue poorly
    documented, though I admit that I've only Googled, and I'm sure there
    are wonderful, (for me) undiscovered academic papers out there (if any
    one has a link, please drop it). I find particularly that there are many
    dimensions to scaling: scaling of performance, scaling of complexity,
    scaling of client base, etc.

    I think what you're referring to here, Thomas, is scaling of complexity
    (please correct me if I'm wrong). I don't think, however, that the
    sentence, "Many classes means it becomes rapidly unmanageable," is
    necessarily true. At least I hope it's not.

    What would you say to this proposal: The more functionality an OO system
    has, the more classes it has.

    I think that's generally true, but if so, then, by your thesis, it must
    necessarily arrive at an unmanageable state. This is depressing.

    I think a good rule-of-thumb for complexity scaling is this: if you can
    add behaviour X without necessarily impacting system metric Y, then your
    system scales with Y. (I'm assuming here both that adding behaviour
    means adding complexity, and that this complexity is the beast which OO
    was born to fight - fire at will at both assumptions.)

    If we take that metric Y to be, "Number of classes in the system," then
    I think most (if not all) systems fail to scale when adding behaviour.

    I think this is why hierarchical name spaces are so great, as they give
    levels in which scaling can be investigated.

    If I have an MVC system, I might define name spaces model, view, and
    controller, in which all other name spaces and classes are contained.
    These three name spaces can, sort-of, be said to be at level 0. A name
    space contained within model can then, for example, be said to be at
    level 1.

    So model.shop is a level 1 name space. model.shop.pay is a level 2 name
    space, etc.

    Viewed using such hierarchical name spaces, we could define metric Y to
    be, "The number of name spaces at level 0;" and according to this, the
    system would scale with added behaviour, as the added behaviour would
    undoubtedly go into some name space at a higher level.

    Indeed, even ignoring levels, and just viewing the entire hierarchy as a
    whole yields precious results. Defining metric Y to be, "Number of name
    spaces in the system," we may also find that, most of the time, as
    adding behaviour X only adds classes to existing name spaces, the system
    does indeed scale with Y.

    This is not frivolous. If class are logically encapsulated within name
    spaces, then name space names will tell a good deal about the
    encapsulated behaviour; and so a casual glance at a system's
    hierarchical name space will indeed offer useful information about which
    name spaces hold which behaviours; surely this is a material value in
    the war on complexity.

    So, to sum up a fairly pointless ramble, I'd like to think that we have
    the tools that cause the statement, "Many classes means it becomes
    rapidly unmanageable," to collapse.

    But I might be wrong ...


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

    Download Fractality, free Java code analyzer:
    www.EdmundKirwan.com/servlet/fractal/frac-page130.html
     
    Ed Kirwan, May 23, 2006
    #11
  12. Ed Kirwan wrote:
    > I like scaling problems. I find the whole scaling issue poorly
    > documented, though I admit that I've only Googled, and I'm sure there
    > are wonderful, (for me) undiscovered academic papers out there (if any
    > one has a link, please drop it). I find particularly that there are many
    > dimensions to scaling: scaling of performance, scaling of complexity,
    > scaling of client base, etc.
    >
    > I think what you're referring to here, Thomas, is scaling of complexity
    > (please correct me if I'm wrong). I don't think, however, that the
    > sentence, "Many classes means it becomes rapidly unmanageable," is
    > necessarily true. At least I hope it's not.
    >
    > What would you say to this proposal: The more functionality an OO system
    > has, the more classes it has.
    >
    > I think that's generally true, but if so, then, by your thesis, it must
    > necessarily arrive at an unmanageable state. This is depressing.

    [...]

    You ignored one particular property in your argumentation: Dependencies.

    In a well designed OO application you have sub-systems which operate
    relatively independent from other systems. Each sub-system is only
    concerned with a relatively small aspect of the whole system's
    operation. You might have thousands of classes in a large system, but
    since each sub-system is manageable, you whole system is still manageable.

    But, in the state pattern issue you end up with a boatload of classes
    which only as a whole make up the state machine. They are not
    independent. They are a big ball of mud. With each class (alias state)
    which you add, you get number-of-events new possible (not necessarily
    legal) state transitions, and you have to potentially revise
    number-of-events times number-of-existing-states old possible (not
    necessarily legal) state transitions.

    When you maintain such a state machine you are presented with a list of
    classes (in Java possibly as much files, if you use public classes).
    That list does not give you any clue about the nature of the particular
    state machine they form. You don't see the interaction, a core property
    of a state machine, from the classes. One can argue that the state
    pattern is not a good OO model of a state machine, since it neglects an
    important property of the thing which it models. A consequence one can't
    make up a (mental) 1:1 mapping of what one wants/needs to implement to
    how and where it needs to be implemented. This makes maintenance harder.
    And it gets harder with each additional state.

    > I think a good rule-of-thumb for complexity scaling is this: if you can
    > add behaviour X without necessarily impacting system metric Y, then your
    > system scales with Y.


    See above. Adding a state can potentially affect the whole state
    machine, which is composed of all the existing state classes (plus a
    context). Changing a state has the same effect.

    /Thomas
    --
    The comp.lang.java.gui FAQ:
    ftp://ftp.cs.uu.nl/pub/NEWS.ANSWERS/computer-lang/java/gui/faq
    http://www.uni-giessen.de/faq/archiv/computer-lang.java.gui.faq/
     
    Thomas Weidenfeller, May 23, 2006
    #12
  13. Chris Uppal Guest

    Ed Kirwan wrote:

    > I think what you're referring to here, Thomas, is scaling of complexity
    > (please correct me if I'm wrong). I don't think, however, that the
    > sentence, "Many classes means it becomes rapidly unmanageable," is
    > necessarily true. At least I hope it's not.


    Well, of course, as the amount of code (or equivalently up to linear factors --
    one hopes!) the functionality increases, then one is always going to hit a
    brick wall sooner or later. I assume that the number of classes will scale
    linearly with the amount of code. For any "difficulty metric", that metric
    will increase with the amount of code, and hence with the number of classes.
    We all know and use techniques which -- we trust and believe -- will keep the
    relationship sub-linear, but I doubt very much whether there can ever be a way
    of making the relationship /flat/ (and if there is, then why not a way to make
    the relationship negative -- so that the difficulty metric decreases as
    complexity increases ?).

    But still, I suspect that Thomas meant something much more specific about the
    classes used in a State pattern. That's what /I/ would have meant anyway.

    If you try to implement a non-trivial state machine as an application of the
    State Pattern, then you end up with large (by definition) numbers of very
    closely related (by design) classes. There may be little or no /formal/
    coupling between them, but in fact they form a rat's nest of highly
    interdependent cross references. And you hit a comprehension barrier almost
    immediately.

    For instance modelling state transition graph of a simple network application
    might give:
    Disconnected
    Connecting
    Connected
    Loggng In
    Logged In
    Loggin out
    Logged out
    Ready
    AwaitingResponse
    UnrecoverableError
    and that might be perfectly feasible to implement with the State Pattern. But
    if it /is/ perfectly feasible, then the State Pattern isn't buying you a lot
    compared with just embedding the knowledge of the current state (not "State")
    into the code itself (or even into the /structure/ of the code).

    But if the state mesh is complicated -- for instance even a simple lexical
    analyser -- then the number of states, and the relationships between the
    classes which implement them, become unmanageable. Part of it is just the
    difficulty of working with large state meshes by hand, but another part of it
    is dealing with the /representation/ of that state mesh as classes. Finding
    names for them is a challenge all by itself.

    As an example (not using the State Pattern but still with a hand-coded state
    machine expressed using "normal" OO techniques rather than table-driven). A
    year or two ago I made the mistake of coding a tokeniser for a language (with
    fairly simple syntax) by hand. I represented each state as a method, the
    current "state" was invoked for each input character, and as it executed it
    would change the state and/or consume the input. I'm fairly happy thinking in
    terms of state machines (more so than most programmers), and that seemed a
    natural way to express the solution. It was (and is) a disaster. I can hardly
    modify it myself, and I doubt it anyone else would even be able to understand
    it at all. There are (only) about 40 states. Some are quite simple
    <inInteger>, <inMantissa>, <inString>, and so on. They don't cause the
    problems, it's the 30 or so more intricate states such as
    <seenExponenetLetterAfterInteger>, <seenLeadingMinusInArray>,
    <seenTrailingMinusAfterBinaryOperaror>, and the relationships between them,
    that make the thing incomprehensible.

    The language I was using allows me to refer to methods directly (as first class
    values, assignable to a variable). That representation would be impossible in
    Java; the nearest equivalent would be an application of the State Pattern. And
    that also would be a disaster ;-)

    -- chris
     
    Chris Uppal, May 23, 2006
    #13
  14. bugbear Guest

    Chris Uppal wrote:
    > 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 ?


    It can be extremely useful to associate actions
    with particular state transitions.

    Commonly, it is useful to define
    actions either for ALL transitions
    from a state, or ALL transitions to a state.

    One might (for example) have a cache
    object, with states LIVE, NEARLINE, FARLINE, ARCHIVE.

    One could (choose to) compress the associated
    data on any status transition to ARCHIVE, regardless of source status,
    and decompress the associated data on transitions from ARCHIVE.

    It's a very natural way of expressing things.

    BugBear
     
    bugbear, May 23, 2006
    #14
  15. Ed Kirwan Guest

    Chris Uppal wrote:

    >
    > As an example (not using the State Pattern but still with a hand-coded state
    > machine expressed using "normal" OO techniques rather than table-driven). A
    > year or two ago I made the mistake of coding a tokeniser for a language (with
    > fairly simple syntax) by hand. I represented each state as a method, the
    > current "state" was invoked for each input character, and as it executed it
    > would change the state and/or consume the input. I'm fairly happy thinking in
    > terms of state machines (more so than most programmers), and that seemed a
    > natural way to express the solution. It was (and is) a disaster. I can hardly
    > modify it myself, and I doubt it anyone else would even be able to understand
    > it at all. There are (only) about 40 states. Some are quite simple
    > <inInteger>, <inMantissa>, <inString>, and so on. They don't cause the
    > problems, it's the 30 or so more intricate states such as
    > <seenExponenetLetterAfterInteger>, <seenLeadingMinusInArray>,
    > <seenTrailingMinusAfterBinaryOperaror>, and the relationships between them,
    > that make the thing incomprehensible.
    >
    > -- chris


    Interesting.

    If I remember correctly, one of the discussions in GoF concerns whether
    each state should, itself, specify the next state which the system
    should enter, or whether each there should be a central table, mapping
    each state to the next.

    Someone else in the thread, also, mentions tables as a sort-of
    alternative to the State pattern, though states and tables are hardly
    not mutually exclusive.

    Do you think, Chris, that the table approach helps at all? This way, you
    can at least see, in one place, the transitions from all states. Does
    this side-step the, "rat's nest of highly interdependent cross references?"

    Also, given your fine example above of the tokeniser, would this have
    been less complicated if you'd not used the State pattern and had, as
    you mention, just, "embedd(ed) the knowledge of the current state (not
    "State") into the code itself (or even into the /structure/ of the code)?"

    Don't get me wrong: I do think agree with you and the excellent Mister
    Weidenfeller, and think the well-intentioned State pattern a little ...
    naieve.

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

    Download Fractality, free Java code analyzer:
    www.EdmundKirwan.com/servlet/fractal/frac-page130.html
     
    Ed Kirwan, May 23, 2006
    #15
  16. P.Hill Guest

    Ed Kirwan wrote:
    > the well-intentioned State pattern a little naieve.


    It is great for what is intended for which is just what
    several on this thread dismissed. Just last week my
    group implement two state machines using the state pattern, some very
    nice double dispatch and good use of base State class all to implement a
    wire protocol. The 2nd sate machine was a server for testing the client.

    Curiously I believe GOF has just such a simple protocol as their example.

    Sure when the states get beyond something you might draw on 1 page,
    then you probably need a different pattern, but not using the State
    pattern for the 3-20 state case (maybe more if there is a lot of shared
    behavior) seems to me to be ignoring a very good pattern.

    -Paul
     
    P.Hill, May 24, 2006
    #16
  17. Chris Uppal Guest

    Ed Kirwan wrote:

    > If I remember correctly, one of the discussions in GoF concerns whether
    > each state should, itself, specify the next state which the system
    > should enter, or whether each there should be a central table, mapping
    > each state to the next.


    I've just been back to re-read the State entry in GoF, and your memory is
    correct. It's worth noting that GoF /doesn't/ present the State Pattern as an
    implementation technique for state machines, but as a technique for creating
    objects with behaviour which changes over time (that changes its class, as they
    put it)


    > Do you think, Chris, that the table approach helps at all? This way, you
    > can at least see, in one place, the transitions from all states. Does
    > this side-step the, "rat's nest of highly interdependent cross
    > references?"


    For implementing state machines or for implementing the State Pattern ? For
    the former almost certainly -- simply because it presents the data in a more
    comprehensible form (and may be significantly more amenable to manipulation via
    automated tools). For the latter, I'm not so sure. I've never tried it, but I
    suspect that if an application of State Pattern were complicated enough to
    benefit from factoring out the underlying state-mesh into a table, then it is
    probably too complicated, period.


    > Also, given your fine example above of the tokeniser, would this have
    > been less complicated if you'd not used the State pattern and had, as
    > you mention, just, "embedd(ed) the knowledge of the current state (not
    > "State") into the code itself (or even into the /structure/ of the code)?"


    In my case, definitely not. I have worked with hand-written scanners
    structured as "normal code", which in this case means elaborate nested looping
    constructions, and I know from experience that they are pure hell. Some people
    seem to be able to manage them, but I know that /I/ quickly get out of my
    depth. I choose the state-machine approach because I know that I can manage
    scanner-like code a /lot/ more easily if I think in terms of state transitions
    than if I think in terms of nested loops and breaks. YMMV.


    Just BTW, and to round out the story: I have since switched to a completely
    different approach. I now have a set of classes which explicitly model
    classical FSAs (both deterministic and non-deterministic state machines). So I
    have a web of State objects, modelling the abstract FSA, which drives the
    scanner. The states are all of the same, rather trivial, class -- so this
    isn't like the State Pattern. In point of fact I build my DFA dynamically from
    the target language spec, but that's only because I rarely do anything
    statically that I can get away with doing dynamically ;-) A programmer with
    different prejudices would probably "compile" the language spec into a static
    state-transition table (probably without explicit state objects) -- and, of
    course, there are tools available to help one do that[*].

    -- chris

    ([*] Such as YACC, ANTLR, and so on. I'm not using such a tool myself because
    none of the available ones handle ambiguous tokenisation in the way I want.)
     
    Chris Uppal, May 25, 2006
    #17
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    8
    Views:
    414
    Joshua Cranmer
    Jul 23, 2008
  2. Replies:
    8
    Views:
    272
    Joshua Cranmer
    Jul 23, 2008
  3. Pallav singh
    Replies:
    0
    Views:
    415
    Pallav singh
    Jan 22, 2012
  4. Pallav singh
    Replies:
    0
    Views:
    435
    Pallav singh
    Jan 22, 2012
  5. Pallav singh
    Replies:
    1
    Views:
    475
    Peter Remmers
    Jan 22, 2012
Loading...

Share This Page