State machines in Perl

I just did a quick CPAN search and turned up a number of interesting packages:

• FSA::Rules is the package I initially started building a wrapper for. It's actually pretty nice, and has a couple of constructs that my last post probably is missing.
• Parse::FSM builds a parser based on an FSM constructed laboriously by function call.
• State::ML provides a utility for converting XML-encoded state machines into other things or even code. I like the code generation aspect!
• Win32::CtrlGUI::State is a slick little state-machine controller for Win32 GUIs.
• Basset::Machine builds a state machine class in much the same way Term::Shell builds a command line shell.

All pretty cool aspects of the state-machine paradigm. If you really wanted to start getting into the semantic programming approach writ large, you'd think of ways to produce code generators for any of these starting from a Decl state machine description, and ways to organize that kind of code generator family into a semantic domain.

State machine redux redux

My random link strategy is working - it brought me to my state machine post of last year, whereupon I realized I'd kind of forgotten about state machines entirely. And yet a clear state machine presentation is such an improvement over code!

Incidentally, the Wikipedia page for finite-state machines is pretty nice.

Here's my tentative DSL for state machines, then:

• The overall tag is "statemachine" and has a name. This name will resolve as a function outside the state machine.
• The state machine tag is an iffy executor; that is, if it's the last tag in a program, it will be in control.
• Within the state machine node, the children are named. Children named "prepare", "output", or "input" that occur before "start" are special.
• The "prepare" child is code executed on each input to prepare it. The local variable $input contains the prepared input (the return from the "prepare" code) and $raw contains the raw input should it be required (this is @_ in the "prepare" code).
• The "output" child is code executed on each out-of-band output in the state machine (see below). The default output is the same as anywhere in Decl; it's to pass output to the parent, where eventually it just gets printed to stdout if you don't redirect it.
• The "input" child is code executed to obtain the next input token, if the state machine is in control. If there is no input, then the state machine can't be in control; it must be called from other code for each input token.
• The "start" child is the first state - every child after "start" is another state, so you can still call a state "prepare" or "input" if you need to.
• Within a state, we still have special parse rules, but in general, execution goes down the list of the state's children.
• A string followed by "->" consumes an input token if it matches, and changes the state.
• A line introduced by "->" just changes the state.
• Either of those may have code attached; if so, this code executes before the state transition. But with or without code, both of those act like a "do".
• A line that doesn't consist of string and -> or just -> is parsed as normal Decl code and does whatever it's supposed to.
• The code morpher will be updated to understand "->" at the start of a line as a state transition if you're inside a state machine. (That's probably a trickle-up thing as well, actually.)

It should be possible to compile a state machine to Perl or C or something; run it in interpreted mode for testing, then spin out C for performance later. Something like that. I'm only vaguely starting to apprehend this aspect of Decl - that eventually it should be entirely master of its own fate and understand how to generate high-performance code from its own programs when necessary.

I still think this would be a pretty powerful feature; I nearly always run aground when coding things based on state machines because it's just so hard to keep track of the darn things, but this lets me pseudocode my way right through it.

Here's a possible rendering of a recognizer for "nice", each letter being an input token:

statemachine nice
start
  n -> n_found
  -> error
n_found
  i -> i_found
  -> error
i_found
  c -> c_found
  -> error
c_found
  e -> success
  -> error
success (accept)
  >> Yay!

   -> start

 error (fail)
  >> bad!

   -> start

That seems to do what I want; it doesn't show any code, but it does show the basic pseudocode I want to use.

Automata as macros

Interesting article on using Scheme macros to encode automata.

It goes through the steps from writing a crude interpreter for an automaton to writing a nice macro to produce higher-performance code. That's cool.

State machines

An interesting little article about state machines and useful patterns that build on them.

State machines redux (link dump)

I started digging around looking for some good examples of state machines to test with, and found a bunch of stuff. (And I could swear that I'd already written this post, but ... apparently not.)

State machines are used for simple sentence parsing. Turns out they're not powerful enough to do the job in all cases (which I knew, but coming at a topic from another angle always allows me to be surprised again and again). However, they've been used pretty successfully for extraction of noun phrases and names from newsfeeds, which is kind of interesting.

Here's a kind of fun approach (though Java-based) to FSMs, using the example of a kind of treasure-hunt game. A state machine lends itself well to Zork-like games.

Here's a tutorial from a robotics approach, although not one I find all that convincing. State machines are, however, very commonly used for robotics controllers, for the obvious reasons. There is lots of material about compiling state machines onto microcontrollers. So my original reason for looking about state machines, WWW::Mechanize, makes a lot of sense. A state machine is a natural way of describing the actions of an agent.

Here's a Ruby/Rails state machine plugin, with good examples.

There's a guy in St. Petersburg who has coined the term "Automata-based programming".

An interesting application of a state machine in building a tree from a serialized protocol.

Charming Python has a chapter on state machines, particularly focused on text processing (e.g. generating HTML from Wiki, which is a good example).

And that's pretty much my link dump. Not a lot of coherence.

Update 11/17/11: I did a little more thinking on this topic.

State machines

Yeah, so I'm going to add explicit state machines support to the language. It looks like this:

state-machine

  start {

    # Figure stuff out.

    => a1

    => b1

  }

  a1 {

    # Other stuff.

    => return

    ...

You can parameterize a state machine:

state-machine (input)

  ...

Put like this, a state machine is itself an action (e.g. a "do" that runs on ->go()). You can also simply declare a state machine and instantiate it on input elsewhere, in which case the instance will be a ....

[we interrupt this post to point out that FSA::Rules really does.]

... function that you can call repeatedly. And thanks to FSA::Rules, all the hard work is done; I can just wrap it. The only question remaining being whether state machines belong in the core or not. Actually, I think not. Which means I have to figure out how to chain semantic domains (but I had to figure that out eventually anyway).