Alexander Sakharov
 
     
 

Finite State Machine Specification and Generation in Java

F
i
n
i
t
e

S
t
a
t
e

M
a
c
h
i
n
e
s

*

Q
u
i
c
k

T
u
t
o
r
i
a
l

Download source code         OOPSLA 2000 Slides (pdf)
SIGPLAN Notices Paper on Hybrid State Machine Notation

Finite state machines (FSM) have become a standard model for representing object behavior. UML adopted this model. Experts from the software industry advocate use of state machines. Many real-time systems can be classified as FSMs. Numerous specification notations are based on the concept of FSMs. UML and SDL incorporate FSM notations. A FSM is defined by the following: a finite set of states, a finite set of event categories and transitions mapping some state-event pairs to other states. Actions are normally associated with transitions. Since the level of FSM specifications is pretty low, Harel introduced hierarchical statecharts in order to reduce the size of the specifications. State machines can be constructed from regular expressions. Regular expressions are a more capacious notation, but in general, they are not a good fit for specification of software units categorized as FSMs because regular expressions lack hooks for attaching actions.

In Java terms, state machines are event listeners. Listener methods of flat FSMs are implemented as switch statements or look-up tables, or employ the state pattern. Listener methods of hierarchical FSMs are state configuration traversals. State machines have to be combined with event adapters for asynchronous event processing.

The following three code fragments outline implementations based on switch statements, look-up tables, and the state pattern, respectively:


   switch(stateIndex) {
      case k:
         action(event); stateIndex = m;
      break;
   ...
   }

            ----------

   Object[] param = new Object[1];
   param[0] = event;
   try {
      methods[stateIndex].invoke(this, param);
   } catch (Exception e) { ... }

            ----------

   state[stateIndex].method(event);

Consider the following sample implementation of state configuration traversal:


   iter = stateConfigurationIterator();
   compLabel1: while ( (point = (StateConfiguration)iter.postorder())!=null ) {
      if ( concurs(point) ) {
         switch(point.getComponent()) {
            case k:
               preTransition(point);
               ((Type)component[k]).method(event);
               if ( component[k].transited() ) {
                  stateIndex =component[k].getStateIndex();
                  postTransition(point, stateIndex);
               }
            break;
            ...
   } } }
   adjustStateConfiguration();

The adapters may queue events


   public synchronized void method(EventObject event) {
      eventQueue.addElement(event);
      eventIndexQueue.addElement(new Integer(k));
   }
and then dispatch them:

   synchronized (this) {
      int n = dequeue();
      eventIndex = ((Integer)(eventIndexQueue.elementAt(n))).intValue();
      eventIndexQueue.removeElementAt(n);
      eventValue = (EventObject)(eventQueue.elementAt(n));
      eventQueue.removeElementAt(n);
   }
   switch( eventIndex ) { ... }

FSM specifications can be expressed directly in Java. Code generation is supported within Java as well. I implemented code generation facilities within a class that serves an abstract base for specification classes. Execution of a compiled specification class performs code generation that result in a class derived from the specification class.

I introduced hybrid FSM specifications. FSM transitions are expanded by adding regular expressions of events and by adding unions of source states. Use of transitions with regular expressions whose tokens are events may significantly reduce the complexity of FSMs by hiding plenty of states. These transitions with regular expressions of events are turned into internal FSMs that are automatically merged with a host FSM. These hybrid specifications are expressed in Java, and FSM code is generated from them.

Construction of hierarchical FSMs out of FSM components is automated as well. I introduced a notation for specification of assembly of FSM components. These specifications define containment; synchronization points; data exchange between pairs of FSM components; event sources; an event-processing mode. I utilize the same code generation technique: execution of a compiled specification class creates a class derived from the specification class. These classes generated from the assembly specifications implement control flow among components and support data exchange between them. In case of asynchronous event delivery, the classes generated from the assembly specifications also serve as event adapters. FSM containers play the role of composite states in hierarchical statecharts. Note that UML's concurrency facilities can be supported within this framework.

See my paper 'A Hybrid State Machine Notation for Component Specification' in the April 2000 issue of SIGPLAN Notices for a detailed description of the hybrid notation. Click here to view an earlier variant of this paper in PDF. See my article 'State Machine Specification Directly in Java and C++' in OOPSLA 2000 Companion for description of the assembly specifications. Source code of the FSM specification and generation package is written in Java and is available for download. Note that the variant of this package available for download does not incorporate support for synchronization points and for hybrid transitions with regular expressions of events.
 

Copyright 2000 Alexander Sakharov

Need to relax? Try brain teasers. I would recommend those marked 'cool'.