There are many challenges that software developers face during the development of complex User Interfaces (UI). Desired behaviour may be autonomous or reactive, and possibly real-time. Each UI component may be required to exhibit a radically different behaviour from that of any other component, and the behaviour of components may be inter-related. These complex behavioural relationships between components are often difficult to express, and are even more difficult to encode and maintain.
A solution may be found in Model-Driven Engineering. In particular, Statecharts, a formalism for describing complex, state-based behaviour, is well-suited for describing certain kinds of UI behaviour.
Furthermore, in order to allow developers to better comprehend the dynamic behaviour described by their statechart, it would be useful to provide a tool that may generate graphical depictions of statecharts from SCXML input documents, which may then be animated in response to live user interface events.
Statecharts is a visual language for describing state-based behaviour. It is similar to Finite State Automata, but includes additional syntax to encode hierarchy and concurrency. The semantics of Statecharts were first formalized in , and Statecharts has been included as part of the Unified Modeling Language specification .
Statecharts were developed in order to be intuitive for developers, but capturing the semantics of Statecharts in a target language is a nontrivial task. A Statecharts implementation strategy must choose how to encode the various features of the Statecharts formalism, including: Events, Event Parameters, States, Transitions, Event Dispatch, State Hierarchy, Actions and Guards. Additionally, target code may be optimized for execution speed, memory usage, code size, or readability.
Many strategies have been derived in order to implement Statecharts in a target language. The following is an overview of common strategies described in existing literature, and their relative advantages and disadvantages.
One concern that cuts across all Statecharts implementation strategies is whether or not a flattening transformation will be applied to the statechart model before code is generated. Flattening is a central transformation for Statecharts, the goal of which is to remove hierarchy from the model, and retain concurrency. The advantages of flattening Statecharts is that a simpler runtime and less mutable data structures are required, which can lead to faster execution and reduced memory consumption. The disadvantage is that the naïve flattening algorithm can lead to a “state explosion”, as the number of states in the transformed state machine will increase exponentially with the number of states in the input state machine. 
However,  claims to have created an algorithm with a polynomial upper bound on the target state space, which may make flattening appropriate to use for larger models.
The Nested Switch Statement implementation strategy is described in  and . In this strategy, States and Events are encoded as enumerations (or, if native enumerations are not available in the target language, something similar, for example integer constants). On event dispatch, the current state is passed to a switch statement, and the event is then sent to another switch statement nested in the case statement corresponding to the current state. The resulting transition is then included inline in the case statement corresponding to the input Event. The current state is encoded in a scalar variable local to the statechart.
The advantages of this strategy are that state hierarchy is easily encoded, only a small amount of memory is required to maintain the current state, and it is easy to read and understand the target code. The disadvantage of this strategy is that it tends to lead to to verbose target code, and dispatch is slow relative to other strategies.
This strategy has been used in the Rhapsody tool .
The State Table implementation strategy is described in  and . In this strategy the statechart’s set of states and events are mapped to unique integer labels, starting from 0. These integer labels corresponds to indexes in a “State Table”, a size matrix, where is the set of states, and the set of events. Each cell in the matrix may contain an action and state. On event dispatch, then, the statechart indexes into the State Table using the indexes of the current state and input event, in order to obtain the next state and transition action.
The advantage to this strategy is that it has a fast, constant dispatch time. The disadvantage is that the State Table tends to be large and sparse, which leads to slow initialization times, and wastes memory. Additionally, an extra data structure is required to encode the hierarchy.
This strategy has been used in the SCC Statechart compiler.
The State Design Pattern implementation strategy is described in , , and . In this strategy, each state is mapped to a unique class. Events are mapped to methods on each state class. A global state machine context aggregates a single state instance which captures the current state. Hierarchy is encoded via class inheritance.
The advantages of this approach is that it leverages high-level, object-oriented language features, which may make forward-engineering (implementing a statechart by hand) easier. Also, it is very easy to read and understand the target code. Its impact on performance, however, is unclear, and may be extremely dependent on the target language.
This strategy is used in the SMC Statechart compiler.
The “Optimal” Pattern implementation strategy is described in . This implementation strategy is heavily optimized for C++ semantics. As in the State Design Pattern strategy, in this strategy there is a state machine context object. States are then mapped to member functions on the state machine context object. The current state is then encoded as a pointer to a member function. On event dispatch, events are delegated to the current state member function. Events are enumerated, and switched in each member function. Transition code is then included inline in each case statement.
The advantage to this approach is that it has a very fast dispatch: the author disassembles the resultant machine code to show that dispatch is achieved using only two machine instructions. It is also very readable, and well-suited to forward engineering. The disadvantage of this approach is that it is unclear how one would represent state hierarchy without first flattening the input statechart.
I am not aware of any existing Statechart compilers that use this strategy.
This project will attempt to determine which of the above code generation strategies is optimally suited for implementing rich UI behaviour on the World Wide Web.
This problem statement may be further refined, as the restrictions imposed by the web browser environment will inform for which factors one should optimize. Specifically, I feel that dispatch execution time and target code size are the factors that are most likely to impact UI usability on the World Wide Web. The reasoning behind this is intuitive. Fast execution, including a fast event dispatch, is required in order to handle high-fidelity UI events. For example, when dragging the mouse, mouse movement events are fired very rapidly. If a Statecharts implementation is unable to handle events in real time, as they occur, then events may begin to queue, which may result in visible UI “lag”. This would, in turn, negatively impact usability.
Finally, readability of target code is not considered to be important for the purposes of this project.
Similar to the approach described in  and , I will assemble a set of benchmark models which vary in size and complexity. For each of these models, I will examine the size of the compiled code using each of the above strategies.
Additionally, Opera, Safari, Chrome, and Firefox (via the Firebug extension) all include profilers that will report fine-grained details with respect to where time is being spent in each test.
Because of the large set of tests that must be performed, some tools for automation may be used.
I would consider a positive result to be the discovery of a Statecharts implementation strategy that is a clear outlier with respect to target code size and execution speed for a nonempty set of web browsers. Note that it is not necessary for a Statecharts implementation strategy to perform well across all web browsers, as code optimized for a particular web browser may be downloaded specifically for that browser at runtime.
Work on Project Part 1 began in March, 2010 as a course project at McGill University for the course COMP-621, Optimizing Compilers.
Thus far, the project has focused only on generating code that supports event dispatch and state transitions. Most of the SCXML Core Module is supported, with the following exceptions: the only executable content supported is < log >, and < donedata > is not supported. A limited form of < send > from the External Communications module is supported, such that only “event” and “delay” attributes are recognized.
The project supports generation of three Statecharts implementation strategies: Nested Switch Statement, State Table, and State Design Pattern. It performs some transition flattening transformations for the State Table and Nested Switch Statement implementations.
By the end of April, preliminary data acquisition and analysis will have been performed using as benchmarks several Statecharts which I have used previously in Web UI development .
The code that has up to this point been implemented would be released under an Apache License, and would be donated to the Apache Software Foundation.
Project Part 1, then, would attempt to implement the remainder of the SCXML specification, including the Executable Content of the Core Module, the Data Module, the External Communications Module, and the Script module. Once full coverage has been implemented, it should be possible to solicit the community for larger, more complex benchmark models. It would then be possible to perform more extensive testing, followed by performance tuning of the generated code.
The performance of the compiler itself may also require performance tuning, as it has not been tested on very large models.
The goal of Project Part 2 is to provide tools to facilitate the generation of graphical depictions of SCXML documents, which may additionally be animated in reaction to UI events.
Project Part 2 is primarily motivated by two needs.
As in conventional programming languages, the behaviour a statechart may encode can be very complex. This complexity will be reflected in the statechart’s structure, in terms of the number of the states and transitions, their depth, and the transition topology. For a developer to initially comprehend the statechart’s structure, and its resultant dynamic behaviour, an intuitive depiction is needed. The depiction offered by standard SCXML is textual. While this depiction may capture the statechart’s state hierarchy very well, it is poorly suited for depiction of graph-like structures with complex topologies.
On the other hand, graphical depictions of statecharts as hierarchical, directed graphs, as presented in  and , are more comprehensible when depicting statecharts with complex topologies. In order to aid comprehensibility, then, it would thus be useful to generate graphical depiction from SCXML input documents.
The goal of the Statecharts formalism is to describe dynamic reactive behaviour of objects in object-oriented systems. It would therefore be useful to support the visualization of the dynamic reactive behaviour of statechart instances through the animation of the graphical depiction of their static structure, such that changes in state, in reaction to events, may be visualized in real time by highlighting corresponding states in the graphical depiction. This would allow developers to more easily “trace” the “live” behaviour of their statechart models, thus facilitating simulation and graphical debugging.
The following Statechart development environments support animation of graphical depictions of statecharts in response to events:
The strategy I propose to fulfill the requirements of Project Part 2 is as follows.
Project Part 2 would then involve two parts: the generation of an SVG document from an SCXML document, and the instrumentation of code generated by the compiler from Part 1.
There would be two possible solutions to facilitate the generation of an SVG depiction of a statechart. The first would be to target an existing graph visualization system. Graphiz is a possibility in this context, as it is free and open source, and is able to generate SVG depictions of hierarchical, directed graphs from a neutral input language. Unfortunately, there would be several downsides to using Graphviz. First, it does not have very good support for using compound shapes as a transition source or destination. Such scenarios lead to unexpected layout, particularly with respect to the position of labels on transitions. Second, it may not be possible to have much control over the output SVG document generated by Graphviz. This is problematic, because, in order to animate the SVG document, it would be necessary to locate graphical representations of statechart model entities in the generated SVG code. Graphviz may not be able to provide this level of control over the SVG output document.
More research would be required in order to determine the optimal approach.
|Begin Project Part 1||May 24th|
|External Communications Module||May 24th - June 2nd|
|Data Module||June 2nd - June 11th|
|Assemble Benchmarks||June 11th - June 20th|
|Data acquisition, analysis||June 20th - June 29th|
|Performance tuning, additional data acquisition and analysis||June 21st - July 13th|
|Project Part 1 Complete||July 13th|
|Begin Project Part 2||July 14th|
|Automatic generation of graphical depiction of statechart static structure||July 14th - August 2nd|
|Project Part 2 Complete||August 9th|
|Bug-fixing, documentation||August 10th - August 16th|
I am available to work full-time on this project between the dates of May 24th and August 16th. My only additional obligation is to begin work on my Master’s thesis.
 Jacob Beard. Modelling the reactive behaviour of SVG-based scoped user interfaces with hierarchically-linked statecharts. http://www.svgopen.org/2009/papers/36-Modelling_the_Reactive_Behaviour_of_SVGbased_Scoped_User_Interfaces_with_Hierarchicallylinked_Statecharts/.
 Thomas Huining Feng. DCharts, a formalism for modeling and simulation based design of reactive software systems. Master’s thesis, School of Computer Science, McGill University, Montréal, Canada, February 2004.