http://www.perlmonks.org?node_id=413021

samtregar has asked for the wisdom of the Perl Monks concerning the following question:

Ahoy, hoy monks. I've got a problem to solve which seems like a perfect fit for a finite state machine. I've got an object which can be in exactly one state at a time. The set of possible states is complex - each one has a number of possible next states and rules for when those states are valid. When the object goes from one state to the next there may be actions to perform. To make matters worse, the set of possible states is very likely to change in the future as more is learned about the problem.

I figured I could get some help from CPAN, but so far my search has come up empty. DFA::Simple and DFA::Command both seem to be built specifically for parsing text coming from a filehandle. The events that would cause changes in my machine come from actions in a web application. I could bend over backwards to make them work for my problem but it'd be a tremendous hack. I could build something from scratch but it's hard to believe I'm the first to have this problem.

So I put these questions to you, kind monks:

  1. Am I right thinking that my problem calls for a FSA?
  2. Is there a module on CPAN which can help me?

-sam

Replies are listed 'Best First'.
Re: Are state machines just for parsing?
by fglock (Vicar) on Dec 07, 2004 at 22:16 UTC

    How about POE:NFA?

    POE::NFA combines a runtime context with an event driven nondeterministic finite state machine. Its main difference from POE::Session is that it can embody many different states, and each state has a separate group of event handlers. Events are delivered to the appropriate handlers in the current state only, and moving to a new state is an inexpensive way to change what happens when an event arrives.

      POE seems like overkill here, but I'll take a closer look if nothing else will do. Thanks!

      -sam

Re: Are state machines just for parsing?
by osunderdog (Deacon) on Dec 07, 2004 at 23:19 UTC

    I have been thinking about this problem also. I have written a package that is a rule engine. The engine is fed a context (Set::Scalar) and each rule examines the set to see if the rule should fire or not. An activiated rule (one that has fired) can modify the context as well as do other things.

    This could be used as a NFA if the context started out containing the initial state of the state machine and each activated rule updated the context with the new state.

    Here is quick example of some of the output showing the context as it changes as events are received. This machine moves parts from one type of container (TRAY) to another type of container (BIB):

    I'm trying to get the time to get it all packaged up and posted to CPAN.

    This discussion may be related: Event loop with rules

    Update. Forgot to close readmore.


    "Look, Shiny Things!" is not a better business strategy than compatibility and reuse.


    OSUnderdog
Re: Are state machines just for parsing?
by diotalevi (Canon) on Dec 07, 2004 at 22:15 UTC

    They are also used for application state and workflow processes. I don't normally formally create an FSA but I could draw out a diagram if pressed to do so.

    As for your problem, couldn't you just serialize your DFA::Simple object's state to storage between web requests? I imagine it would take a bit of custom work because you won't be able to just Storable::freeze() the object - it contains code references. That's easy to work around - just store the name of the function it is supposed to call and when rebuilding your object, reassociate the hard reference. You might also just give DFA::Simple the ability to call functions by name and avoid having code references at all.

      As for your problem, couldn't you just serialize your DFA::Simple object's state to storage between web requests?

      That's not the problem. The problem is that DFA::Simple wants to parse text on a filehandle to trigger events. I don't have a text file full of events, I have a user on the other end of an HTTP connection!

      -sam

        I didn't see anything in the referenced code to indicate that it parsed anything. All it does to decide the next state is run a bunch of your test functions to see which one returns true. What your test functions do is up to them.
Re: Are state machines just for parsing?
by simonm (Vicar) on Dec 07, 2004 at 23:00 UTC
    Yup, this seems like a classic state machine application.

    Take a look at Workflow to see if it's a match with your needs.

Re: Are state machines just for parsing?
by sleepingsquirrel (Chaplain) on Dec 07, 2004 at 22:55 UTC
    Why doesn't the simple-minded method work?
    #!/usr/bin/perl -w # State transition table # # Current Inputs Next Action $next{'initial'}{'left' } = ['red', sub { print "Red \n"} ]; $next{'initial'}{'right'} = ['blue', sub { print "Blue\n"} ]; $next{'red'} {'left' } = ['blue', sub { print "Blue\n"} ]; $next{'red'} {'right'} = ['end', sub { print "End \n"} ]; $next{'blue'} {'left' } = ['blue', sub { print "Blue\n"} ]; $next{'blue'} {'right'} = ['red', sub { print "Red \n"} ]; $next{'end'} {'left' } = ['end', sub { print "End \n"} ]; $next{'end'} {'right'} = ['end', sub { print "End \n"} ]; @arbitrary_inputs = qw/left left right left left right right left/; $state = 'initial'; for (@arbitrary_inputs) { $action = $next{$state}{$_}->[1]; $action->(); $state = $next{$state}{$_}->[0]; }


    -- All code is 100% tested and functional unless otherwise noted.
      Well, first off because my problem doesn't have states with just one possible next state, it has a set. Sure I could enhance your example until it could handle a fully generalized state machine. Then I could find a good name and put our solution on CPAN. But if there's already a solution out there I can use, wouldn't it be better to use that?

      -sam

        But if there's already a solution out there I can use, wouldn't it be better to use that?
        See also: Abstraction Inversion.
      It occured to me that it might be beneficial to show the state transition diagram for the above state machine.
      +--------------------------------------------------+ | | | _______ | | left / \ right | | +------------|initial|-----------------+ | | | \_______/ | | | | | | | | +--------+ | | | ___V___ | | | | |left / \ right | _V__V_V_ +-----| red |--------------+ | left / \ right \_______/ | +------| blue |------+ ^ | \________/ | | | | | | | | __V____ | | left / \ right | | +-----| end |------+ | | | \_______/ | | | | ^ ^ | | | | | | | | | +-------+ +---------+ | | | +-------------------------------------------------+


      -- All code is 100% tested and functional unless otherwise noted.
Re: Are state machines just for parsing?
by metaperl (Curate) on Dec 07, 2004 at 23:13 UTC
Re: Are state machines just for parsing?
by talexb (Chancellor) on Dec 08, 2004 at 15:24 UTC

    To answer your title, if not your article, no, state machines aren't used just to parse stuff.

    About ten years ago I rewrote the communications layer for a pharmacy management system that was used in about 900 stores in Ontario. Because the system could be used with either a dial modem or a 3201 (poll select) device, I needed to have a state machine that was configurable at run-time, based on the current configuration. Thus, if the 3201 service went down (it did occasionally), a store owner could be talked through changing the configuration, restarting the communications layer and getting back on-line to filing on-line health claims. There were also stores in Northern Ontario that didn't have 3201 service and were permanently on dial modem connections.

    The differences were that the modem had more states: it had to dial a number, check that it got CONNECT back, send the transaction, get a response, try again if the timeout was exceeded (and possibly do this for multiple transactions), then break the connection. The 3201 device was always connected, so it just had to send the transaction and get a response.

    I used a state machine to take care of all this -- an array of function pointers (this was a C program). Depending on what mode it was in, and what the exit state of the previouis step was, the machine could determine where to go next (and what to do). It worked just fine.

    And the same executable also ran as either a TSR or as a separate task under PC-MOS -- that was a fun piece of code to write.

    Alex / talexb / Toronto

    "Groklaw is the open-source mentality applied to legal research" ~ Linus Torvalds

Re: Are state machines just for parsing?
by dragonchild (Archbishop) on Dec 08, 2004 at 13:20 UTC
    What kind of interface / API would you be interested in seeing? How would you want to use said module?

    The reason I ask is that I've built state machines for several projects and they were different enough that I don't think I could've used a generic solution / framework. For example, I've used state machines to

    • perform actions in a basic scripting language
    • handle events that have been defined to fire when X occurs
    • be the engine for a web application (both before I found CGI::Application and with it)

    It's kinda like trying to build a module for the Schwartzian Transform or the Guttman-Rosler Transform (GRT). It's good to know the pattern, but making a generic version just complicates the matter. Or, put another way, we'd almost have to write another mini-language to have a state machine. And, we already have that with regexes.

    Being right, does not endow the right to be rude; politeness costs nothing.
    Being unknowing, is not the same as being stupid.
    Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
    Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.

      What kind of interface / API would you be interested in seeing?

      I see two phases. First, I need an API to lay out the network. For my purposes each state has to have:

      • A unique name
      • A description
      • A list of possible next states
      • Code which runs when the state is reached
      • Code to determine if this state should be the next one

      I don't know what this API should look like. Maybe each state is a Perl module implementing a few methods. Maybe it's just a big data structure made of hashes and arrays. Whatever it is it has to be easy to change later when the businessmen change their minds.

      Next I need to give the machine a starting state and an event. The machine should either tell me what the next state is or produce an error if the event doesn't trigger a valid next state. Something like:

      $next_state = $machine->run($state, $event);

      -sam

Re: Are state machines just for parsing?
by injunjoel (Priest) on Dec 07, 2004 at 22:37 UTC
    Greetings all,
    Perhaps Im way off base here but is this not a situation for CGI::Application or mod_perl? Sounds like run modes to me.

    -InjunJoel
    "I do not feel obliged to believe that the same God who endowed us with sense, reason and intellect has intended us to forego their use." -Galileo
      Yeah, you're pretty much off base. CGI::Application is a great tool but it's not a general state machine system. And mod_perl? That's a Perl interface to the Apache API which has, um, nothing to do with the problem at hand.

      Of course, that said, my application already uses both!

      -sam

Re: Are state machines just for parsing?
by lachoy (Parson) on Dec 08, 2004 at 21:32 UTC

    This is actually what the Workflow module does. (I think someone else mentioned it too.) You can create:

    • Actions to move from one state to another (or not change state at all)
    • Conditions to see whether the current environment can execute an action (which changes state).
    • Validators to check data coming into the system

    All of these are simple Perl classes, and because there's a 'context' moving data into and out of the workflow it doesn't care where it's run, and neither do your classes.

    I gave a presentation on it a couple months ago to the Pittsburgh Perlmongers that might be helpful, and it comes with working examples, decent docs, some tests, etc.

    Chris
    M-x auto-bs-mode

      That's a cool presentation. And the module looks great... except, why do I have to program Perl inside an XML file? This makes my skin crawl:

      <workflow> <type>myworkflow</type> <state name="INITIAL"> <action name="upload file" resulting_state="uploaded" /> </state> <state name="uploaded" autorun="yes"> <action name="verify file" resulting_state="annotate"> <!-- everyone other than 'CWINTERS' must verify --> <condition test="$context->{user} ne 'CWINTERS'" /> </action> ...

      I'd be much happier with:

      my $workflow = Workflow::Generator->new(type => "myworkflow"); $state = $workflow->add_state(name => "INITIAL"); $state->add_action(name => "upload file", resulting_state => "uploa +ded"); $state = $workflow->add_state(name => "uploaded", autorun => "yes") +; $state->add_action(name => "verify_file", resulting_state => "annot +ate"); $condition = $state->add_condition(test => \&check_file);

      It's more conscise and all the power of Perl is available for making repetitive structures from common data. If I ever decided to use Workflow I think Workflow::Generator would be my first project.

      -sam

        Well, the "perl in XML" part is entirely optional and is actually a recent addition. But I like the idea of creating it programmatically and it should be pretty easy, actually. I might swipe this for later -- with credit, of course...

        Chris
        M-x auto-bs-mode

Re: Are state machines just for parsing?
by Anonymous Monk on Dec 08, 2004 at 15:00 UTC
    All state machines are used to parse. Parsing doesn't have to be "parse text from a text file". For instance, a TCP/IP stack uses a state machine as well. It's "parsing" the network packets, and it's using the content of the headers, combined with the current state, to determine what its next state (if different from the current) will be.

    In a broader sense, state machines (which can or cannot have memory - FAs don't have memory, PDAs and TMs do), parsing (aka recognizing languages) and calculability are all the same.

    Classical literature about these subjects include the Dragon book and the Cinderella book.

        All state machines are used to parse.

      Don't think so. See my reply below.

      Alex / talexb / Toronto

      "Groklaw is the open-source mentality applied to legal research" ~ Linus Torvalds

        To mis-quote a former US President:

        It depends on how you parse "Parse".

        In some sense receiving an event is very much like looking at the next character in a file. You either expect it or you don't. It all depends on what your language is.

        Someone pointed out FOLDOC eariler so here's a reference to Parser.


        "Look, Shiny Things!" is not a better business strategy than compatibility and reuse.


        OSUnderdog
        And your example differs from the TCP/IP state machine example in which way? Your example is doing what every other state machine does: it uses the current state and the current input to determine what the next state will be (that is, it's performing a "calculation"). Your example only strengthens my point.
      I disagree. State machines are used in many fields, not just in software that evaluates data. As a tiny selection of applications, they are used to drive washing machines and dishwashers, as well as most battery-driven toys. In those cases, they certainly don't parse anything, but simply perform timed steps of a program to wash your dishes or clothes (I hope they are not being parsed!), or move a toy car while making some fitting noises. Similarly, in software, they are used in practically all programs in one form or another. Just think of any game you know, and it certainly is based on a state machine.
Re: Are state machines just for parsing?
by valdez (Monsignor) on Dec 13, 2004 at 21:26 UTC