SCXML Code Generation Framework, JavaScript Edition (SCXML/cgf/js): An SCXML-to-JavaScript Compiler Optimized for User Interface Development on the World Wide Web

Jacob Beard

March 31, 2010

Contents

1 Project Summary
2 Project Part 1: Developing an SCXML-to-JavaScript Compiler Optimized for User Interface Development on the World Wide Web
 2.1 Background and Related Work
  2.1.1 Flattening Statecharts
  2.1.2 Nested Switch Statement
  2.1.3 State Table
  2.1.4 State Design Pattern
  2.1.5 “Optimal” Pattern
 2.2 Goals
 2.3 Solution Strategy
 2.4 Analysis of Results
 2.5 Current Project Status
3 Project Part 2: Automated Synthesis of Graphical Simulation Environments
 3.1 Goals
  3.1.1 Graphical Depiction of Static Structure
  3.1.2 Animation of Graphical Depictions to Support Visualization of Dynamic Behaviour
 3.2 Background and Related Work
 3.3 Solution Strategy
4 Schedule of Activities
5 Availability

1 Project Summary

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.

At the same time, the “Open Web” is becoming increasingly popular as a platform for application development. Applications may be built using a suite of technologies implemented in modern web browsers. In particular, the JavaScript language is used to implement interactivity and dynamic behaviour in UI objects. It is thus possible to create browser-based applications that are richly interactive. These applications are typically called Rich Internet Applications (RIAs).

SCXML is a human-readable XML application for describing Statecharts [2]. An SCXML-to-JavaScript compiler, then, would allow developers of RIAs to use Statecharts to describe and implement the behaviour of their UIs, which would thus make it easier to develop RIAs with complex behaviour requirements.

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.

2 Project Part 1: Developing an SCXML-to-JavaScript Compiler Optimized for User Interface Development on the World Wide Web

2.1 Background and Related Work

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.[13] The semantics of Statecharts were first formalized in [8], and Statecharts has been included as part of the Unified Modeling Language specification [14].

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.

2.1.1 Flattening Statecharts

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. [16]

However, [16] 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.

2.1.2 Nested Switch Statement

The Nested Switch Statement implementation strategy is described in [13] and [12]. 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 [13].

2.1.3 State Table

The State Table implementation strategy is described in [5] and [12]. 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 |S|× |E | size matrix, where S  is the set of states, and E  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.[7]

2.1.4 State Design Pattern

The State Design Pattern implementation strategy is described in [10], [9], and [12]. 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.[11]

2.1.5 “Optimal” Pattern

The “Optimal” Pattern implementation strategy is described in [12]. 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.

2.2 Goals

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.

Target code size must also be kept to a minimum, as all code must be downloaded over a network, most often the Internet, and thus verbose code increases the amount of time required before a UI may be used. This is particularly relevant, as JavaScript code may not be encoded in a binary representation, thus increasing the size of the code payload.

Reducing memory usage is also an important consideration, particularly when one considers the proliferation of JavaScript-enabled web browsers on mobile devices (for example, the mobile Safari browser on the iPhone). However, this project will focus primarily on desktop web browsers, and thus will prefer reduction of target code size and execution time to memory usage.

Finally, readability of target code is not considered to be important for the purposes of this project.

Thus, the goal of Project Part 1 may be refined. Project Part 1 will attempt to implement an SCXML-to-JavaScript compiler, such that the targeted statechart implementation strategy will minimize execution time, particularly with respect to dispatching events, and minimize target code size. Furthermore, the code targeted by the SCXML-to-JavaScript compiler should support all of the features of SCXML, including those in the Core Module, the External Communications Module, the Data Module, and the Anchor Module.

2.3 Solution Strategy

Because JavaScript is a multi-paradigm language, it may implement all of the above Statechart implementation strategies directly, which is to say, the high-level language features required by each strategy map well onto JavaScript’s high-level language features. In order to determine which implementation strategy produces optimal results, I will implement an SCXML-to-JavaScript compiler for several Statechart implementation strategies. I will then analyze the resulting compiled statecharts with respect to the before-mentioned optimizations. Additionally, it will be important to test the generated code with different JavaScript interpreters, as each interpreter may include unique optimization strategies for executing JavaScript. The goal will be to look for clear outliers with respect to execution speed and target code size.

Similar to the approach described in [15] and [16], 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.

I will then perform tests for execution speed and memory usage for each benchmark model, and in each of the following JavaScript interpreters (their associated web browser is included in parentheses).

  1. TraceMonkey (Mozilla Firefox 3.5)
  2. JScript (Internet Explorer 7)
  3. JScript (Internet Explorer 8)
  4. V8 (Google Chrome 4.0)
  5. SquirrelFish (Safari 3.0)
  6. SquirrelFish Extreme (Safari 4.0)
  7. Carakan (Opera 10.5)
  8. Mozilla Rhino 1_7R2 (runs on the Java Virtual Machine, and not in a web browser)

The web browser environment provides reasonably good tools for profiling JavaScript code. Specifically, the built-in Date object makes benchmarking JavaScript relatively easy. The following code snippet demonstrates how this may be achieved:

d1 = new Date()  
//run JavaScript code here  
d2 = new Date()  
time = d2 - d1; //returns elapsed time in milliseconds

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.

2.4 Analysis of Results

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.

2.5 Current Project Status

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 [4].

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.

3 Project Part 2: Automated Synthesis of Graphical Simulation Environments

3.1 Goals

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.

3.1.1 Graphical Depiction of Static Structure

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 [8] and [14], 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.

3.1.2 Animation of Graphical Depictions to Support Visualization of Dynamic Behaviour

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.

3.2 Background and Related Work

The following Statechart development environments support animation of graphical depictions of statecharts in response to events:

3.3 Solution Strategy

The strategy I propose to fulfill the requirements of Project Part 2 is as follows.

In general, in terms of graphical representations, I believe it makes sense to target Scalable Vector Graphics (SVG). SVG is an XML application for describing vector graphics [1]. It is for several reasons optimal in the context of this project. First, SVG is natively supported in most web browsers. This native integration would make it easy to “hook up” a live Web UI to an animated graphical depiction, thus facilitating tracing and debugging. Second, SVG documents can be scripted in a manner similar to HTML documents, using JavaScript and Document Object Model (DOM) API’s. Thus, targeting SVG would allow Project Part 2 to build upon the work done in Project Part 1, in that all that would be required to support the animation of generated SVG artifacts would be to instrument the code generated by the SCXML-to-JavaScript compiler, so as to make the generated JavaScript code aware of the SVG artifact. The generated code may then animate the SVG artifact using DOM.

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.

The second possibility is to generate SVG directly without using an existing graph visualization system. The advantage to this approach is that it would be possible to maintain fine control over the output, so that nodes could be labelled and identified in the resulting SVG document. It has the disadvantage that it would be necessary to perform layout on the resulting document, which may be very complex, particularly with respect to laying out transitions. This could be mitigated by the fact that graph layout is, to a certain extent, already a well-understood problem, and there exist layout algorithms that could be ported to JavaScript and applied to this project [3][6].

More research would be required in order to determine the optimal approach.

4 Schedule of Activities

Milestone Goal Date Range



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
Instrumentation of JavaScript backends to support animation of graphical depiction August 3rd - August 9th
Project Part 2 Complete August 9th
Bug-fixing, documentation August 10th - August 16th

5 Availability

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.

References

[1]   Scalable vector graphics (SVG). http://www.w3.org/Graphics/SVG/.

[2]   State chart xml (SCXML): State machine notation for control abstraction. http://www.w3.org/TR/scxml/.

[3]   G. Di Battista, P. Eades, R. Tamassia, and I. G Tollis. Graph drawing: algorithms for the visualization of graphs. Prentice Hall PTR Upper Saddle River, NJ, USA, 1998.

[4]   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/.

[5]   B. P Douglass. Doing hard time: Developing Real-Time systems with UML, objects, frameworks and patterns. Embedded Systems Programming, page 199, 2000.

[6]   Denis Dube. Graph layout for domain-specific modeling. Master’s thesis, School of Computer Science, McGill University, Montréal, Canada, February 2006.

[7]   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.

[8]   David Harel and Amnon Naamad. The STATEMATE semantics of statecharts. ACM Trans. Softw. Eng. Methodol., 5(4):293–333, 1996.

[9]   I. A Niaz. Automatic code generation from UML class and statechart diagrams. 2005.

[10]   I. A Niaz and J. Tanaka. An Object-Oriented approach to generate java code from UML statecharts. International Journal of Computer & Information Science, 6(2), 2005.

[11]   Charles W. Rapp. Smc: The state machine compiler. http://smc.sourceforge.net/.

[12]   Miro Samek. Practical statecharts in C/C++. Focal Press, 2002.

[13]   Emil Sekerinski and Rafik Zurob. iState: a statechart translator. In UML 2001 The Unified Modeling Language. Modeling Languages, Concepts, and Tools, pages 376–390. 2001.

[14]   O. M. G. Uml. 2.0 superstructure specification. OMG ed, 2003.

[15]   Andrzej Wasowski. On efficient program synthesis from statecharts. SIGPLAN Not., 38(7):163–170, 2003.

[16]   Andrzej Wasowski. Flattening statecharts without explosions. SIGPLAN Not., 39(7):257–266, 2004.