Saturday, March 13, 2010

Java and Finite State Machines

OK. I have this thing about Event Driven Architectures and Finite State Automata. Sounds big and bold but its really very simple once you get past the lingo and hoopla!

I like Finite State Machines because its how we, as people, step through logic and its how we enact and implement workflow. They are easy to illustrate and explain, even to the novice or PhD (Pointy Haired Dude!).

FSMs track the condition of "thingies" through various conditions and logic cases. Associated with each FSM are a Start state, transitions, and states. Simple enough, right?

When you instance an FSM, it becomes an Object. This means that you have started to track a "Thingie" in your FSM and it is in the Start state.

Generally, there are two types of Finite State Automata - Moore or Mealy model. In practice, a Moore Model of a state machine uses only Entry Actions, such that its output depends on the state. A Mealy model of a state machine uses only Input Actions, such that the output depends on the state and also on inputs.

Sounds complex but its not. It all breaks down to states, transitions, and actions.
For simplicity sake, a Finite State machine can be described in a couple of database tables:

OLD_STATE varchar(32),
NEW_STATE varchar(32),
Transition_Name varchar(32),
Actions_Index integer,

CREATE TABLE Transitions {
Transition_Name varchar(32),
Transition_Method integer,

Actions_Index integer,
Action_cmd varchar(255),

When a State is Achieved as in becomes a new state, any transition that progresses the State Machine needs to be enacted and scheduled. For example, if you have a start state and its one transition out of start requires an action, that action needs to be enacted.

When a state machine receives triggers, these are parsed and assigned to transitions which move a tracked object from State to state. If an object is in a state where a transition cannot be applied, it is dropped. For example, if you have an object in an Up state and the poll determination send a transition to Obj_up but that transition is not present in the Up state, the transition is dropped.

When an Object transitions from an Old State to a new State, and actions for that transition need to be executed. (This is the workflow). Once the New State is achieved, we restart the process.

The benefits behind a state machine is that it lets you model objects in an asynchronous way, as fast or as slow as need be. Methods are only executed upon reaching an achieved state. So, you don't have to execute ALL methods upon instantiation of and object... Only as you progress through the state machine.

From a purely "Persistent" point of view, an Object instance is a row in a DB table. This row depicts the current state and a date-time stamp. Everything else around the FSM logic is used to determine the next state and perform actions based upon transitioning from one state to another.

Now that we have the basics down, lets look at some code examples:

First of all, there was this fellow name Rocco Caputo that developed a set of Perl modules called POE or Perl Object Environment. As per Rocco : "POE originally was developed as the core of a persistent object server and runtime environment. It has evolved into a general purpose multitasking and networking framework, encompassing and providing a consistent interface to other event loops such as Event and the Tk and Gtk toolkits."

POE cansists of a kernel that can be thought of as a small, operating system running in a user process. Each kernel supports one or more Sessions and each Session has its own space called a Heap. Each Session, in turn, has a series of events and event handlers which run when called.

Events can be yielded (They go to the bottom of the events for processing) or they can be called (They go to the top of the stack for processing). Event Handlers are perl subroutines that are executed upon running of the event in stack processing the session.

Additionally, Sessions can be named and events can be sent from one session to another.

Sessions are initiated in a couple of ways. States or Objects.

This is the States way:

inline_states => {
one => \&some_handler,
two => \&some_handler,
six => \&some_handler,
ten => \&some_handler,
_start => sub {
$_[KERNEL]->yield($_) for qw(one two six ten);

Heres a session initiation with Objcts and Inline States :

object_states => [
$object_1 => { event_1a => "method_1a" },
$object_2 => { event_2a => "method_2a" },
inline_states => {
event_3 => \&piece_of_code,

Notice that the events in inline states call sub routine Code references. Each event handler must be organized as a subroutine.

Each subroutine is setup like:

sub Yada_yada {
my ($kernel, $heap, $parameter) = @_[KERNEL, HEAP, ARG0];
# Do stuff in the sub...
# ....

While it may seem a bit unorthodox, Perl actually inits subs with an Arguments array @_ and POE uses this natively.

So, in POE, we init sessions which have states and actions (callbacks). And we have a Heap space to store our state data.

In a simplistic way of looking at it, transitions and ther application to state are accomplished in the events and callbacks. If the object is in the proper OLD_STATE to transition to a NEW_STATE, the transition occurs (writing the new state name to the Heap and executing the Actions.)

Now, here's something VERY INTERESTING about POE and Perl:

$_[KERNEL]->state sets or removes a Handler for an EVENT_NAME within the current Session. For example, the following line would remove the handler for the EVENT_NAME in the current session.

$_[KERNEL]->state( 'on_client_input' );

Subsequent calls that have a Sub routine Code reference get replaced as in:

$_[KERNEL]->state( 'on_client_input', \&new_subroutine );

Given Perl eval, one could read in new subroutines, check them in eval, AND put them into action within POE without having to stop, reread, and restart. Can you say

Now, when you look at Java and State Machines, I am in a bit of a conundrum. Objects must run their methods right away. So trying to model a "Thingie" becomes an exercise where my "Thingie" object becomes a container of states objects and transition objects. All of a sudden, the app is not scalable.

And in keeping pace with POE, each "Thingie" object must b a separate thread as each Session is its own "thread of execution..."

In looking over the Finite State Machine Framework on SourceForge :

I notice that this is a good FSM framework. However, State machines must be compiled and rerun under the JVM. No dynamic non-determinstic methods.

I could spoof Java into doing a persistent State machine by only handling transitions in objects. Everything else must be done via a pewrsistence storage such that only transitions are instanced and transition actions are executed upon transition execution. This adds a bit of overhead in the IO model as well as the states have to be hibernated or stored in data structure of some kind.

Changing transitions on the fly is an exercize in calling classes out of a database store. If a new class is applied, it gets exectued by name via the DB record. But, in order to change things, the process must stop and restart to reread all of the classes and class hierarchy.

Each transition must either have the same number of methjod arguments or iut must be uniquely named. Method overloading because of the variability of calling a transition with ever changing methods underneath means that method overloading would become rather prolific.

My Conclusion:

FSMs are hard to do in an OO type Object Model without instancing a whole lot of objects. But it could be accomplished if you make the object model look kinda like a FSM. Still no where near as dynamic as Perl and POE though. And because of the cooperative nature of the POE kernel, it is significantly tighter than attempting to spawn out hundreds of threads.

No comments:

Post a Comment