Using Java langauge constructs to define static graphs and trees
Graphs, networks and trees are commonly used to model application domains. In some cases these structures are highly dynamic and can not be defined at design time. Yet there are also cases when they are rather static and do not change during the application life cycle. An example of such static structure is a finite state automaton – defined as a part of design, it remains unchanged at the run-time.
However, programming languages do not provide facilities that would make creation of graphs (trees) an easy task. Most common approach is to use XML with a custom schema and encode a graph (a tree) with XML tags. Unfortunately, development tools does not provide the same degree of support for editing an XML file as they do for many wide spread programming languages – detecting typos as you type, reference navigation with one mouse click, etc. Additionally, using an XML requires a utility to process the XML and build a model corresponding to the definition. Another approach to define a graph – instantiating objects and establishing references among them “by hands”. The code created with this approach is burdened with poor readability and maintainability. An ideal solution would be using a domain specific language for these purposes, however cost of creating such a language is tremendous at present time.
This article suggests an approach on adapting the Java programming language for defining static graphs, trees.
The idea
If we look at Java classes, interfaces and references among them at the high level of abstraction, their appear to be a linked graph where classes/interfaces can be thought as nodes and references – as links between them. These thoughts, being turned inside out, lead to the following rationales: a graph can be represented as a set of interfaces where an interface represents a node and a reference to another interface represents a link. Such references, for instance, could be return types of methods defined in the interface.
Rationales
The following table lists rationales on graph representation.
| FSA primitive | Represented as |
| State chart | A Java class that includes definition of all its states |
| State | An interface extending State interface |
| Set of On Enter actions | One or more methods returning void and annotated with @OnEnter |
| On Enter Action | A parameter type extending Action of a method mentioned above |
| Set of On Leave actions | One or more methods returning void and annotated with @OnLeave |
| On Leave Action | A parameter type extending Action of a method mentioned above |
| Transition | A method returning interface corresponding to the “To” state |
| Condition | A parameter type extending Condition of a method mentioned above |
| Action | A parameter type extending Action of a method mentioned above |
 |
| Figure 1 |
Microwave automaton
Lets consider a simple microwave with one push-button and a knob timer. This microwave starts heating when the user pushes the button and the door is closed and the timer is set. Pushing button again stops heating, opening the door suspends heating until the door is closed again. A state chart for this microwave is shown on Figure 1. The following code snippet shows how this state chart can be represented with the rationales given above.
public class MicrowaveStateMachine {
/**
* In Door Open State MW waits until the door is closed
*/
interface DoorOpenState extends State {
@OnEnter void enter (DoDing a); // on entering Door Open State issue a Ding action
WaitingState idle (OnDoorClose e, IfTimerIsSet a); // on Door Close Event transit to Waiting State
HeatingState resume (OnDoorClose e, IfTimerIsNotSet a); // on Door Close Event transit to Waiting State
DoorOpenState ignore (OnPushButton e, DoBeep a); // on Push Button Event issue a Beep and remain in DoorOpenState
@OnLeave void leave (DoDong a); // on entering Door Close State issue a Dong
}
/**
* In Waiting State MW waits until a button is pushed
* If timer is set, it starts heating, otherwise it beeps
*/
interface WaitingState extends State {
HeatingState start (OnPushButton e, IfTimerIsSet c); // on Push Button Event if timer is set transit to heating
WaitingState beep (OnPushButton e, IfTimerIsNotSet c, DoBeep a); // otherwise issue a Beep and remain in waiting
DoorOpenState open (OnDoorOpen e); // on Door Open Event transit to Door Open State
}
/**
* In Heating state it actually heats.
* On entering this state MW starts the heater and the cook timer;
* On leaving this state MW stops the heater and suspends the cook timer
*/
interface HeatingState extends State {
@OnEnter void enter (DoStartHeater a, DoStartCookTimer t); // on entering HeatingState State issue Start Heater Action
WaitingState timer (OnCookTimerExpired e); // on Timer Expired Event transit to Waiting State
WaitingState stop (OnPushButton e); // on Push Button Event transit to WaitingState State
DoorOpenState open (OnDoorOpen e); // on Door Open Event transit to Door Open State
@OnLeave void leave (DoStopHeater a, DoSuspendCookTimer b); // on leave issue DoStopHeater
}
}
Constructing run-time artifacts
Obviously, this is only definition and it requires, as well as an XML definition, some code to turn it into a run-time artifact. Java Reflection API provides all necessary means for examining the definition but producing a valuable output is an application specific task. In other words, the task is split on two concerns – (1) examining the definition and (2) generating the output. The source code sample attached to this article provides a utility class that implements first concern (Walker) and an application class (MicrowaveSample) that generates microwave automaton assembler code for a PICmicro MCU (see sample output below). Walker class exposes one method processAutomaton accepting a state chart definition class and communicates with MicrowaveSample via WalkerCallback interface implemented by MicrowaveSample.
;-----------------------------------------------------
DoorOpenState
call DoDing
DoorOpenState_begin
call sleepAndWaitEvents
DoorOpenState_0
btfss OnDoorClose ; resume
bra DoorOpenState_1
btfss IfTimerIsNotSet
bra DoorOpenState_1
call DoorOpenState_leave
bra HeatingState
DoorOpenState_1
btfss OnDoorClose ; idle
bra DoorOpenState_2
btfss IfTimerIsSet
bra DoorOpenState_2
call DoorOpenState_leave
bra WaitingState
DoorOpenState_2
btfss OnPushButton ; ignore
bra DoorOpenState_3
call DoBeep
call DoorOpenState_leave
bra DoorOpenState
DoorOpenState_3
DoorOpenState_end
bra DoorOpenState_begin
DoorOpenState_leave
call DoDong
return
HeatingState
call DoStartHeater
call DoStartCookTimer
HeatingState_begin
call sleepAndWaitEvents
HeatingState_0
btfss OnPushButton ; stop
bra HeatingState_1
call HeatingState_leave
bra WaitingState
HeatingState_1
btfss OnDoorOpen ; open
bra HeatingState_2
call HeatingState_leave
bra DoorOpenState
HeatingState_2
btfss OnCookTimerExpired ; timer
bra HeatingState_3
call HeatingState_leave
bra WaitingState
HeatingState_3
HeatingState_end
bra HeatingState_begin
HeatingState_leave
call DoStopHeater
call DoSuspendCookTimer
return
WaitingState
WaitingState_begin
call sleepAndWaitEvents
WaitingState_0
btfss OnPushButton ; start
bra WaitingState_1
btfss IfTimerIsSet
bra WaitingState_1
bra HeatingState
WaitingState_1
btfss OnDoorOpen ; open
bra WaitingState_2
bra DoorOpenState
WaitingState_2
btfss OnPushButton ; beep
bra WaitingState_3
btfss IfTimerIsNotSet
bra WaitingState_3
call DoBeep
bra WaitingState
WaitingState_3
WaitingState_end
bra WaitingState_begin
 |
| Figure 2 |
Extending state charts
Now, lets image that we have this microwave automaton in full production, and R&D department came up with a innovative and conceptual design of a microwave with two buttons 
and sales department insisted on adding a ‘polite reminder’ feature. State chart for the new microwave automaton is given on Figure 2 where blue color indicates new state and transitions and red cross denotes transition no longer needed. A big part of the state chart remains the same as in previous version one and, thus, can be reused in a new state chart. With the approach that this article suggests, a state chart can be extended by means of Java inheritance, e.g. new state chart extends the previous. With very little efforts the new automaton is defined as given below.
/**
* State machine of a microwave oven with two buttons and polite reminder feature:
* when cooked and door was not open - beep every N seconds during M minutes
*/
public class ModernMicrowaveStateMachine extends MicrowaveStateMachine {
/**
* This machine introduces several new events and actions
*/
interface OnPushStopButton extends Event {}
interface OnPoliteBeepTimer extends Event {}
interface OnPoliteOffTimer extends Event {}
interface DoStartPoliteBeepTimer extends Action {}
interface DoStopPoliteBeepTimer extends Action {}
interface DoStartPoliteOffTimer extends Action {}
interface DoStopPoliteOffTimer extends Action {}
interface DoAddOneMinuteCookTimer extends Action {}
/**
* Alter the inherited Heating State
*/
interface HeatingState extends MicrowaveStateMachine.HeatingState {
HeatingState add (OnPushButton e, DoAddOneMinuteCookTimer a); // add one minute to the timer when push button is pressed
@Disable
WaitingState timer (OnCookTimerExpired e); // disable this transition inherited from the old MW
CookedState cooked (OnCookTimerExpired e); // introduce new transition on Timer Expired Event transit to CookedState State
WaitingState stop (OnPushStopButton e); // on Push Stop Button Event transit to WaitingState State
@Disable
WaitingState stop (OnPushButton e); // disable this transition inherited from the old MW
}
/**
* Add new state to provide polite beep reminder
*/
interface CookedState extends State {
@OnEnter void onEnter (DoStartPoliteBeepTimer a, DoStartPoliteOffTimer b ); // on enter start timers Polite Beep and Polite Off
DoorOpenState stop (OnDoorOpen e); // on Door Open Event transit to Door Open State
HeatingState start1 (OnPushButton e, IfTimerIsNotSet i, DoAddOneMinuteCookTimer t); // on Push Button Event transit to WaitingState State
HeatingState start (OnPushButton e, IfTimerIsSet i); // on Push Button Event transit to WaitingState State
WaitingState stop (OnPushStopButton e); // on Push Stop Button Event transit to WaitingState State
WaitingState idle (OnPoliteOffTimer e); // stop beeping after M minutes
CookedState beep (OnPoliteBeepTimer e); // beep every N seconds
@OnLeave void onleave (DoStopPoliteBeepTimer a, DoStopPoliteOffTimer b ); // on leave stop timers
}
}
There is one new annotation added: @Disabled. It is used to indicate a deletion of unused links that were inherited from the original chart. Output for this automaton is following
;-----------------------------------------------------
CookedState
call DoStartPoliteBeepTimer
call DoStartPoliteOffTimer
CookedState_begin
call sleepAndWaitEvents
CookedState_0
btfss OnPushButton ; start
bra CookedState_1
btfss IfTimerIsSet
bra CookedState_1
call CookedState_leave
bra HeatingState
CookedState_1
btfss OnPushStopButton ; stop
bra CookedState_2
call CookedState_leave
bra WaitingState
CookedState_2
btfss OnDoorOpen ; stop
bra CookedState_3
call CookedState_leave
bra DoorOpenState
CookedState_3
btfss OnPoliteOffTimer ; idle
bra CookedState_4
call CookedState_leave
bra WaitingState
CookedState_4
btfss OnPoliteBeepTimer ; beep
bra CookedState_5
call CookedState_leave
bra CookedState
CookedState_5
btfss OnPushButton ; start1
bra CookedState_6
btfss IfTimerIsNotSet
bra CookedState_6
call DoAddOneMinuteCookTimer
call CookedState_leave
bra HeatingState
CookedState_6
CookedState_end
bra CookedState_begin
CookedState_leave
call DoStopPoliteBeepTimer
call DoStopPoliteOffTimer
return
HeatingState
call DoStartHeater
call DoStartCookTimer
HeatingState_begin
call sleepAndWaitEvents
HeatingState_0
btfss OnPushButton ; add
bra HeatingState_1
call DoAddOneMinuteCookTimer
call HeatingState_leave
bra HeatingState
HeatingState_1
btfss OnPushStopButton ; stop
bra HeatingState_2
call HeatingState_leave
bra WaitingState
HeatingState_2
btfss OnCookTimerExpired ; cooked
bra HeatingState_3
call HeatingState_leave
bra CookedState
HeatingState_3
HeatingState_end
bra HeatingState_begin
HeatingState_leave
call DoStopHeater
call DoSuspendCookTimer
return
DoorOpenState
call DoDing
DoorOpenState_begin
call sleepAndWaitEvents
DoorOpenState_0
btfss OnDoorClose ; resume
bra DoorOpenState_1
btfss IfTimerIsNotSet
bra DoorOpenState_1
call DoorOpenState_leave
bra HeatingState
DoorOpenState_1
btfss OnDoorClose ; idle
bra DoorOpenState_2
btfss IfTimerIsSet
bra DoorOpenState_2
call DoorOpenState_leave
bra WaitingState
DoorOpenState_2
btfss OnPushButton ; ignore
bra DoorOpenState_3
call DoBeep
call DoorOpenState_leave
bra DoorOpenState
DoorOpenState_3
DoorOpenState_end
bra DoorOpenState_begin
DoorOpenState_leave
call DoDong
return
WaitingState
WaitingState_begin
call sleepAndWaitEvents
WaitingState_0
btfss OnPushButton ; start
bra WaitingState_1
btfss IfTimerIsSet
bra WaitingState_1
bra HeatingState
WaitingState_1
btfss OnDoorOpen ; open
bra WaitingState_2
bra DoorOpenState
WaitingState_2
btfss OnPushButton ; beep
bra WaitingState_3
btfss IfTimerIsNotSet
bra WaitingState_3
call DoBeep
bra WaitingState
WaitingState_3
WaitingState_end
bra WaitingState_begin
Representing other graph and tree-alike structures
Although, this article is focused on finite state automatons, similar approach can be applied for defining other kind of graphs and trees. The author has a proof of concept for using nested classes as a representation of a web-application URI structure and mapping HTTP requests issued by very complex but strictly structured HTML forms.