Developing a Statechart-to-ECMAScript Compiler Optimized for SVG User Interface Development for the World Wide Web

Jacob Beard

Modelling, Simulation and Design Lab
School of Computer Science
McGill University
Montréal
Québec
Canada

Hans Vangheluwe

Modelling, Simulation and Design Lab
Department of Mathematics and Computer Science
University of Antwerp
Antwerp
Belgium

Modelling, Simulation and Design Lab
School of Computer Science
McGill University
Montréal
Québec
Canada


Table of Contents


1. Introduction
2. Statechart Compilation Strategies
     2.1 Nested Switch Statement
     2.2 State Table
     2.3 State Design Pattern
     2.4 Flattening Statecharts
3. ECMAScript as a Target Language for Statecharts
     3.1 Internal Representation of Current Configuration
          3.1.1 Basic Configuration vs. Full Configuration
          3.1.2 ECMAScript Set Implementation
     3.2 Application Programming Interface
     3.3 Threading Model
     3.4 Flattening Transformation
4. Choosing an Optimal Compilation Strategy for UI Development on the World Wide Web
     4.1 Problem Statement
     4.2 Experimental Framework
     4.3 Data Acquisition
     4.4 Testing Platform
     4.5 Analysis of Results
5. Developing SVG User Interfaces with scxml-js
     5.1 Usage Contexts
     5.2 Just-in-Time Compilation in the Browser
     5.3 Ahead-of-Time Compilation from the Command Line
6. Conclusion
7. Future Work
8. Acknowledgements
Bibliography

1. Introduction

There are many challenges that software developers face during the development of complex User Interfaces (UIs). 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, reactive, timed, state-based behaviour, is highly suited to model UI behaviour.

At the same time, SVG, in combination with ECMAScript, is becoming increasingly popular as a platform for application development. The ECMAScript language is used to implement interactivity and dynamic behaviour in SVG visual objects. It is thus possible to create browser-based, SVG UIs which are rich in both their visual appearance and in their interactive behaviour.

A Statechart-to-ECMAScript compiler allows developers of SVG+ECMAScript-based Web applications to use Statecharts to describe the behaviour of their UIs, followed by simulation and application synthesis.

Statecharts was developed in order to be intuitive for modellers. Translating Statechart models correctly into ECMAScript is a nontrivial task, however. A Statecharts compilation strategy must choose how to encode the various features of the Statecharts semantics, including: Events, Event Parameters, States, Transitions, Event Dispatch, State Hierarchy, Orthogonality, History, Actions and Guards. Additionally, it is desirable to optimize target code for execution speed, memory usage and compiled code size, all of which are important in the development of rich UIs, often running in constrained environments such as a Web browser on a mobile device.

Because ECMAScript is a flexible, dynamic, multi-paradigm language, the space of possible Statechart compilation strategies is quite large. In general, it is desirable to map the high-level features of Statecharts onto the high-level language features of ECMAScript. Additionally, it is important to take into consideration the constraints imposed by the Web browser environment.

The SCXML JavaScript Code Generation Framework (scxml-js) began as a project to develop a Statechart-to-ECMAScript compiler, for McGill University course COMP-621, Program Analysis and Transformations, taught by Professor Laurie Hendren. It was then accepted as a Google Summer of Code project under the Apache Commons SCXML project of the Apache Software Foundation, and was developed full-time throughout the summer of 2010. It is currently available under the Apache 2.0 license.

This paper has three goals. The first goal is to discuss three strategies that may be employed for implementing Statecharts in ECMAScript, and the tradeoffs that each approach entails with respect to execution speed, memory usage, and compiled code size. Second, it will be shown how these techniques influenced the development of scxml-js. Finally, the paper will demonstrate how scxml-js may be used to accelerate the development of fast, robust, and richly interactive SVG UIs.

2. Statechart Compilation Strategies

Statecharts is a visual language for describing state-based behaviour. It is similar to Finite State Automata, but includes additional constructs to encode hierarchy and concurrency [Sekerinski2001]. The semantics of Statecharts have been described precisely [Harel1996][Harel2001], and Statecharts has been included as part of the Unified Modeling Language and SCXML specifications [UML2Superstructure][SCXML].

Statecharts are meant to be intuitive for developers, but capturing the semantics of Statecharts in a target language is hard. A Statecharts compilation 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 developed to compile Statecharts to a target language. The following is an overview of common strategies described in the literature, and their relative advantages and disadvantages.

Nested Switch Statement

In the Nested Switch Statement compilation strategy, States and Events are encoded as enumerations (or, if native enumerations are not available in the target language, an appropriate encoding such as 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 [Sekerinski2001][Samek2002].

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 verbose target code, and dispatch is slow relative to other strategies.

This strategy has been used in the Rhapsody tool [Sekerinski2001].

State Table

In the State Table compilation strategy, the statechart's set of states and events are mapped to unique integer labels, starting from 0. These integer labels correspond to indexes in a "State Table", a |S| x |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 a state. On event dispatch, then, the statechart indexes into the State Table using the integer labels of the current state and input event, in order to obtain the next state and transition action [Douglass2000][Samek2002].

The advantage of this strategy is that it has a fast, constant dispatch time. The disadvantage is that the State Table data structure 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 state hierarchy.

This strategy has been used in the SCC Statecharts compiler [FengSVM].

State Design Pattern

In the State Design Pattern compilation 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 [Niaz2005][Samek2002].

The advantage 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 is generally dependent on the target language. There are also semantic issues related to the correct resolution of identical event labels at different levels of a hierarchy.

This strategy is used in the SMC state machine compiler [Rapp].

Flattening Statecharts

One concern that cuts across all Statecharts compilation 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. Its goal is to remove hierarchy from the model, while retaining 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 a naive 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 [Wasowski2004].

3. ECMAScript as a Target Language for Statecharts

Internal Representation of Current Configuration

Basic Configuration vs. Full Configuration

There are many possible ways to encode the current configuration of a statechart.

A "configuration", also known as a "full configuration", is defined to be "a maximal set of states that the system can be in simultaneously", whereas a "basic configuration" is defined to be "a maximal set of basic states that the system can be in simultaneously". A full configuration may be derived from a basic configuration [Harel1996].

In scxml-js, the configuration of a statechart is captured as a basic configuration, which is to say, a set of basic states. This approach has the advantage of requiring less "bookkeeping" for many kinds of transitions than if a full configuration were used. For example, if one were to encode the current configuration as a full configuration, then transitioning from a basic state A that has k composite state ancestors, to a basic state B that has l composite state ancestors, would require k+1 elements to be removed from the current configuration set, and l+1 elements to be added. On the other hand, encoding the current configuration as a set of basic states requires only removing A and adding B to the current configuration set.

One disadvantage of this approach is that it becomes more expensive to query whether the statechart instance is within a particular composite state, as the set of ancestors in each basic state in the current configuration must be retrieved, and checked to see if it contains the given state. This makes the implementation of an In() predicate, which queries a statechart to determine if it is in a given state, and is defined as part of the Core Module of the SCXML specification [SCXML], less efficient.

ECMAScript Set Implementation

It was necessary to decide how to implement a set data structure in ECMAScript. Unlike Java, for example, which provides a hashtable-based set implementation as part of its standard library (java.util.HashSet), ECMAScript does not provide such an implementation as part of its core language, or part of a standard library. However, ECMAScript does provide rich primitive data types that may be used to implement the required set operations. These primitive types are Object and Array.

An ECMAScript Object is a Map-like data structure, which stores key-value pairs. The keys must be strings (when given any other type, the string representation of that type will be used as the key), and values can be of any type, including other complex types such as Object and Array.

An ECMAScript Array, on the other hand, is a list-like data structure, which has a dynamic property, length, that tracks the number of elements the structure contains, and maps integer indexes to ECMAScript values.

scxml-js uses an Array to encode the current configuration, because in many implementations of ECMAScript, use of a regular for loop to iterate over elements of an Array is faster than using for..in to iterate over the properties of an Object [Hollis][Prototype]. One of the most frequently occurring operations in the scxml-js implementation of the SCXML canonical step algorithm[SCXML] is to dispatch an event upon a statechart, using the given event and each state in the current configuration to compute the candidate transitions that may be taken, which would cause the current configuration to be updated. It was therefore important to optimize the process of iterating through each state in the current configuration. Hence an Array was used instead of an Object.

The disadvantage of using an Array to encode the current configuration's set of states, as opposed to an Object, is that updating the configuration becomes more expensive for some types of transitions. In many cases, the resulting configuration for a given transition can be known at compile-time, and thus the operation to update the current configuration can be implemented as a simple assignment of an Array literal to the variable that stores the current configuration. However, in the cases where it is not possible to know at compile-time the resulting configuration for a given transition, at run-time the basic state being exited must be removed dynamically from the current configuration Array, and the state or states being entered must be added to the Array. This can be implemented using a single call to the built-in method Array.splice, which, for many implementations of ECMAScript, is an expensive operation compared to adding and deleting the equivalent properties of an Object.

Application Programming Interface

scxml-js generates an ECMAScript constructor function, with the name "StatechartNameStatechartExecutionContext", for each given input statechart. New statechart instances may be created by using the ECMAScript new operator with this constructor function. New statechart instances may then be initialized by calling the method initialize on the statechart object. The statechart object then performs initial default transitions, and begins scheduling time on the Web browser thread.

As in the Rhapsody semantics of statecharts, events may be sent to the statechart object using a synchronous or asynchronous API [Harel2001]. To send an event synchronously, one calls a method on the statechart object which has the same name as the event. To send a message asynchronously, one calls the method GEN on the statechart object, passing the event name as a string. Optionally, an object may be passed as an addition parameter to the event method, in which case it will be used as a statechart event parameter.

Threading Model

In scxml-js, all statechart constructor functions may be considered "active classes" [Harel2001], meaning that each object created by that constructor function has its own thread of execution. This is needed in order to allow each statechart instance to process events asynchronously, and operate concurrently with other instances.

As the Web browser environment does not expose native, operating system-level threads, active classes in scxml-js are instead realized by scheduling asynchronous callback functions on the Web browser thread. This is implemented using the Window.setTimeout method exposed by the Web browser. The Web browser then acts as a scheduler. When using scxml-js compiled statechart instances under Rhino, the same threading model is used; the Window.setTimeout method is then emulated using Java's Thread.sleep method.

Flattening Transformation

A flattening transformation is applied for the Table and Switch compilation strategies. This is not the same as the flattening transformation mentioned in Section 2.4, as it does not attempt to transform orthogonal regions to a set of basic states. Rather, it transforms statecharts by recursively copying the transitions on composite states to their basic state descendants. This makes it possible to avoid hierarchical lookup of activated transitions when dispatching events. This flattening transformation avoids the problem of exponential state explosion induced by a naive flattening transformation mentioned in Section 2.4, but requires the use of a set data structure to capture the current configuration, whereas a naive flattening transformation would be able to represent the current configuration as a single scalar variable.

Figure 1 provides a simple example of this transformation.

flattening_transformation.svg

Figure 1: Simple statechart before and after flattening transformation is applied.

4. Choosing an Optimal Compilation Strategy for UI Development on the World Wide Web

Problem Statement

The scxml-js project has attempted to determine which of the compilation strategies described in Chapter 2 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 determine the factors for which one should optimize. Specifically, we felt that that event dispatch execution time and target code size were the factors that were most likely to impact the usability of UIs on the Web. The reasoning behind this was intuitive. Fast execution, including fast event dispatch, is required in order to handle high-fidelity UI events. For example, when dragging the mouse, mouse movement events are fired at a high rate. If a Statecharts implementation is unable to handle high-fidelity 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.

Reducing memory usage is also an important consideration, particularly when one considers the proliferation of ECMAScript-enabled Web browsers on mobile devices (for example, the mobile Safari browser on the iPhone or iPad) which have more limited memory than desktop devices.

Finally, readability of target code was not considered to be important for scxml-js, as facilities were added to allow high-level tracing and graphical debugging of target code.

The ECMAScript 4 language overview describes ECMAScript as, "a simple, highly dynamic, object-based language that takes its major ideas from the languages Self and Scheme". Furthermore, ECMAScript supports a mixture of functional, imperative, and object-based programming styles [ECMAScript4]. For these reasons, ECMAScript is often described as "multi-paradigm" programming language.

Thanks to its multi-paradigm nature, ECMAScript may implement each of the Statechart compilation strategies described in Chapter 2 directly, which is to say, the high-level language features required by each strategy map well onto ECMAScript's high-level language features. In order to determine which compilation strategy would produce optimal results, a compiler backend was written for scxml-js for each Statechart compilation strategy. The resulting compiled ECMAScript code was then benchmarked with different ECMAScript implementations. The goal was then to look for compilation strategies that were clear outliers with respect to execution speed for one or more ECMAScript implementations.

We chose to focus on analyzing performance, as target code size was comparable between the different statechart backends, especially when gzip compression was applied. Likewise, memory usage was not analyzed as scxml-js has thus far primarily focused on optimizing target code for desktop Web browsers, rather than mobile devices, and thus memory usage has been less of a critical concern.

Experimental Framework

A "Kitchen Sink" example statechart was created for the purposes of benchmarking. The transitions in this statechart created a closed loop, so that thousands of events could be sent to the statechart during a single testing session.

testing_state_diagram.svg

Figure 2: Kitchen Sink Statechart for Benchmarking

Tests were then performed for each of the following ECMAScript implementations and Web browsers:

  • TraceMonkey (Mozilla Firefox 3.6.3)
  • JScript (Internet Explorer 8)
  • V8 (Google Chrome 5.0.342.9 beta)
  • SquirrelFish Extreme (Safari 4.03)
  • Data Acquisition

    ECMAScript's built-in Date object was used to acquire benchmarking data. This used the following simple invocation pattern:

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

    As Date returns time rounded to the nearest millisecond, it did not provide a sufficient granularity for testing a single run of the Kitchen Sink example, as a full run through the Kitchen Sink example would often take less than a full millisecond. It therefore became necessary to measure the elapsed time taken by multiple runs.

    Each testing session measured elapsed time taken by 1000 runs through the Kitchen Sink. This measurement was repeated 10 times for each browser/compilation strategy pair, and the minimum and maximum results of each test were discarded.

    Because a large number of tests were performed (120, for 4 browsers, 3 compilation strategies, and 10 trials), software was used to automate the acquisition of benchmark data. Specifically, the Selenium library was used to automate the process of opening and closing Web browsers, as well as initiating tests and harvesting test results. A custom build script was written to persist the data, and generate reports. Charts were generated using the dojox.charting library.

    Testing Platform

    All benchmarks were run on an HP TouchSmart tx2z laptop with the following specifications:

  • AMD Turion X2 Ultra Dual-Core Mobile ZM-85 2.30 GHz
  • 4.00 GB RAM
  • Windows 7 Home Premium x64
  • Analysis of Results

    As stated in Section 4.1, we considered a positive result to be the discovery of a Statechart compilation strategy that was a clear outlier with respect to execution speed for some nonempty set of ECMAScript implementations and Web browsers. The final results were consistent with this desired outcome.

    all_browsers_2.svg

    Figure 3: Performance results for all compilation strategies and all web browsers

    Figure 3 shows the results of running the Kitchen Sink benchmark on all browser/compilation strategy pairs. The vertical axis indicates total running time in milliseconds, and the horizontal axis indicates a browser/strategy pair, ordered by increasing average execution time.

    There are several interesting things to note in Figure 3. First, browsers are naturally clustered together, revealing that, overall, their performance is tiered relative to one-another for the Kitchen Sink benchmark. Overall, some browsers seem to execute the Kitchen Sink benchmark faster than others.

    Second, one may observe that for all browsers, the Table compilation strategy has the best average performance. One may also see that the State Pattern strategy performs second-best for Safari, Firefox, and Internet Explorer; on Chrome, the Switch strategy performs second-best.

    The Table compilation strategy therefore appears to be an outlier across all Web browsers with respect to average execution speed. Table 1 illustrates the percent speed increase of average running time between the Table compilation strategy and other strategies, for each browser. One may see that, overall, the Table compilation strategy provides between an 8% and 18% speed increase compared to its nearest neighbor.

    Figure 4, Figure 7, Figure 6, and Figure 5 provide graphical comparisons of relative speed increases for each browser, in terms of best-case, worst-case, and average running times. From this, one may see that the Table compilation strategy typically also provides the lowest best-case and worst-case execution times across all browsers, except for Firefox, where the best-case times of the Table and State strategies are approximately equal.

    Performance comparison to Table Strategy for all Web browsers
    StrategyTime Difference (ms) Approx. Percent Speed Increase of Table Strategy
    Google Chrome
    Switch216%
    State21168%
    Safari
    State17.518%
    Switch20.822%
    Firefox
    State24.28%
    Switch103.135%
    Internet Explorer
    State68.517%
    Switch116.429%

    Table 1

    chrome_2.svg

    Figure 4: Performance results for Google Chrome 5.0.342.9 beta

    safari_2.svg

    Figure 5: Performance results for Safari 4.03

    firefox_2.svg

    Figure 6: Performance results for Mozilla Firefox 3.6.3

    ie_2.svg

    Figure 7: Performance results for Internet Explorer 8

    5. Developing SVG User Interfaces with scxml-js

    Usage Contexts

    scxml-js is implemented primarily as a series of XSL transformations. An ECMAScript front-end is used to set up the XSLT pipeline and accept options from the user. Because of the portability of XSLT and ECMAScript, scxml-js may be run in both the Web browser environment (currently tested in Firefox 3.6, Chrome 5, Opera 10.6, Internet Explorer 8, and Safari 5), and on the Java Virtual Machine (tested with Java 6 OpenJDK and Mozilla Rhino 1.7).

    scxml-js accepts SCXML documents as input and produces ECMAScript code as output. The following is a simple example of how drag-and-drop behaviour may be implemented using SCXML. It will be shown how this example may be used with scxml-js to add interactivity to graphical SVG elements.

    drag_and_drop.svg

    Figure 8: Graphical depiction of drag-and-drop behaviour

    
    <scxml 
      xmlns="http://www.w3.org/2005/07/scxml"
      version="1.0"
      profile="ecmascript"
      id="scxmlRoot"
      initial="initial_default">
    
      <script>
        function computeTDelta(oldEvent,newEvent){
          //summary:computes the offset between two events; to be used later with this.translate
          var dx = newEvent.clientX - oldEvent.clientX;
          var dy = newEvent.clientY - oldEvent.clientY;
    
          return {'dx':dx,'dy':dy};
        }
    
        function translate(rawNode,tDelta){
          var tl = rawNode.transform.baseVal;
          var t = tl.numberOfItems ? tl.getItem(0) : rawNode.ownerSVGElement.createSVGTransform();
          var m = t.matrix;
          var newM = rawNode.ownerSVGElement.createSVGMatrix().translate(tDelta.dx,tDelta.dy).multiply(m);
          t.setMatrix(newM);
          tl.initialize(t);
          return newM;
        }
      </script>
    
      <datamodel>
        <data id="firstEvent"/>
        <data id="eventStamp"/>
        <data id="tDelta"/>
        <data id="rawNode"/>
      </datamodel>
    
      <state id="initial_default">
        <transition event="init" target="idle">
          <assign location="rawNode" expr="_event.data.rawNode"/>
        </transition>
      </state>
    
      <state id="idle">
        <transition event="mousedown" target="dragging">
          <assign location="firstEvent" expr="_event.data"/>
          <assign location="eventStamp" expr="_event.data"/>
        </transition>
      </state>
    
      <state id="dragging">
        <transition event="mouseup" target="idle"/>
    
        <transition event="mousemove" target="dragging">
          <assign location="tDelta" expr="computeTDelta(eventStamp,_event.data)"/>
          <script>
            translate(rawNode,tDelta);
          </script>
          <assign location="eventStamp" expr="_event.data"/>
        </transition>
      </state>
    
    </scxml>
    

    Example 1: SCXML description of drag-and-drop behaviour

    Just-in-Time Compilation in the Browser

    The following is an example of how scxml-js may be used in the browser environment to add drag-and-drop behaviour to a single rect element.

    <html xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg">
      <head>
        <style type="text/css">
          html, body {
            height:100%;
            margin: 0;
            padding: 0;
          }
        </style>
        <script src="../../lib/js/requirejs/require.js" type="text/javascript"></script>
        <script src="../../lib/js/requirejs/require/text.js" type="text/javascript"></script>
        <script src="../../lib/js/requirejs/require/xml.js" type="text/javascript"></script>
      </head>
      <body>
        <svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" width="100%" height="99%" >
    
          <rect width="100" height="100" stroke="black" fill="red" id="rectToTranslate" >
            <scxml 
              xmlns="http://www.w3.org/2005/07/scxml"
              version="1.0"
              profile="ecmascript"
              id="scxmlRoot"
              initial="initial_default">
    
              <script>
                function computeTDelta(oldEvent,newEvent){
                  //summary:computes the offset between two events; to be later used with this.translate
                  var dx = newEvent.clientX - oldEvent.clientX;
                  var dy = newEvent.clientY - oldEvent.clientY;
    
                  return {'dx':dx,'dy':dy};
                }
    
                function translate(rawNode,tDelta){
                  var tl = rawNode.transform.baseVal;
                  var t = tl.numberOfItems ? tl.getItem(0) : rawNode.ownerSVGElement.createSVGTransform();
                  var m = t.matrix;
                  var newM = rawNode.ownerSVGElement.createSVGMatrix().translate(tDelta.dx,tDelta.dy).multiply(m);
                  t.setMatrix(newM);
                  tl.initialize(t);
                  return newM;
                }
              </script>
    
              <datamodel>
                <data id="firstEvent"/>
                <data id="eventStamp"/>
                <data id="tDelta"/>
                <data id="rawNode"/>
              </datamodel>
    
              <state id="initial_default">
                <transition event="init" target="idle">
                  <assign location="rawNode" expr="_event.data.rawNode"/>
                </transition>
              </state>
    
              <state id="idle">
                <transition event="mousedown" target="dragging">
                  <assign location="firstEvent" expr="_event.data"/>
                  <assign location="eventStamp" expr="_event.data"/>
                </transition>
              </state>
    
              <state id="dragging">
                <transition event="mouseup" target="idle"/>
    
                <transition event="mousemove" target="dragging">
                  <assign location="tDelta" expr="computeTDelta(eventStamp,_event.data)"/>
                  <script>
                    translate(rawNode,tDelta);
                  </script>
                  <assign location="eventStamp" expr="_event.data"/>
                </transition>
              </state>
    
            </scxml>
          </rect>
        </svg>
        <div id="statusDiv" style="position:absolute;bottom:0px;right:0px;"/>
        <script>
          var resultText;
    
          require(
            {
              "baseUrl":"/"
            },
            ["src/javascript/scxml/cgf/SCXMLCompiler"],
    
            function(compiler){
    
              require( [window.DOMParser ?
                  "src/javascript/scxml/cgf/util/xsl/browser" :
                  "src/javascript/scxml/cgf/util/xsl/ie"],
                function(transform){
    
                  var statusDiv = document.getElementById("statusDiv");
    
                  statusDiv.textContent="Compiling SCXML elements...";
    
                  //pull SCXML nodes from DOM
                  var scxmlElements = document.getElementsByTagName("scxml");
                  for(var i = 0; i < scxmlElements.length; i++){
                    var scxml_input = scxmlElements[i];
                    var domNodeToHookUp = scxml_input.parentNode;
    
                    //prep scxml document to transform by pulling the scxml node into its own document
                    var scxmlns = "http://www.w3.org/2005/07/scxml";
                    var scxmlToTransform = document.implementation.createDocument (scxmlns , "scxml", null);
                    var newNode = scxmlToTransform.importNode(scxml_input.cloneNode(true),true);
                    scxmlToTransform.replaceChild(newNode,scxmlToTransform.documentElement);
    
                    var compiledStatechartConstructor, compiledStatechartInstance;
    
                    compiler.compile({
                      inFiles:[scxmlToTransform],
                      //debug:true,
                      backend:"state",
                      beautify:true,
                      verbose:false,
                      log:false,
                      ie:false
                    }, function(scArr){
                      var transformedJs = scArr[0];
    
                      //eval
                      eval(transformedJs);
                      compiledStatechartConstructor = StatechartExecutionContext;
                      compiledStatechartInstance = new compiledStatechartConstructor();
    
                      //initialize
                      compiledStatechartInstance.initialize();
    
                      //pass reference to rect
                      compiledStatechartInstance.init({rawNode:domNodeToHookUp});
    
                      //hook up DOM events
                      ["mousedown","mouseup","mousemove"].forEach(function(eventName){
                        domNodeToHookUp.addEventListener(eventName,function(e){
                          e.preventDefault();
                          compiledStatechartInstance[eventName](e)
                        },false);
                      });
                    },transform);
                  }
    
                  statusDiv.textContent+=" Done!";
                }
              )
            }
          );
        </script>
      </body>
    </html>
    
    

    Example 2: Leveraging SCXML drag-and-drop behaviour using in-browser, just-in-time compilation technique

    In this example, the content from the SCXML document in Example 1 is included inline as part of a compound XHTML document. The XHTML context is currently needed in order to use RequireJS, a JavaScript library used in the development of the scxml-js front-end. The SCXML root element is a child of the SVG rect element to which drag-and-drop behaviour will be added.

    The SVG script element occurring after the rect element then performs the following actions. First, it queries the DOM for SCXML elements, and retrieves from them their parent nodes. It then uses scxml-js to compile the SCXML content to an ECMAScript string, and evaluates the string to produce a Statechart constructor function. Next, it instantiates and initializes a statechart instance. Finally, it registers DOM mouse event listeners on the SVG rect node so that DOM events will be dispatched by the statechart instance.

    In this example, the scxml-js compiler is being used in a fashion similar to a just-in-time (JIT) compiler: SCXML code is included in the host document as an "XML Data Island", and the compiler is run in the context of the user's web browser. It is important to note that the content in the final script element could easily be put into an external script file and linked to, so that the compiler would only need to be downloaded once, and would then be cached. Also, rather than being included inline, SCXML content could be referenced externally, and downloaded using XMLHttpRequest.

    This approach has several advantages. First, from the point of view of the developer, this is the easiest way to begin using scxml-js. Second, this approach allows developers to leverage SCXML as a "view-source" technology, as the statechart behaviour would easily be visible to the user, simply by viewing the source code of the Web page. Finally, the SCXML source document may be smaller than its corresponding compiled ECMAScript representation, potentially reducing the amount of data to be downloaded before the behaviour described in the SCXML document may be used.

    Ahead-of-Time Compilation from the Command Line

    The drag-and-drop behaviour example would be implemented as follows using ahead-of-time compilation.

    First, the SCXML document in Example 1 would be compiled from the command-line using the following command:

    ./run.sh --backend table --beautify drag-and-drop.scxml > drag-and-drop.js
    

    This compiles drag-and-drop.scxml using the Table backend, and beautifies the resulting code. The code is sent to standard out, and redirected to the file drag-and-drop.js.

    The compiled drag-and-drop.js file could then be used as follows.

    
    <svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" width="100%" height="99%">
    
      <script type="application/ecmascript" xlink:href="drag-and-drop.js"/>
    
      <rect width="100" height="100" stroke="black" fill="red" id="rectToTranslate" />
    
      <script>
        var resultText;
    
        var rectToTranslate = document.getElementById("rectToTranslate");
    
        var compiledStatechartInstance = new StatechartExecutionContext(); 
    
        //initialize
        compiledStatechartInstance.initialize();
        
        //pass reference to rect
        compiledStatechartInstance.init({rawNode:rectToTranslate}); 
    
        //hook up DOM events
        ["mousedown","mouseup","mousemove"].forEach(function(eventName){
          rectToTranslate.addEventListener(eventName,function(e){
            e.preventDefault();
            compiledStatechartInstance[eventName](e)
          },
          false);
        });
    
      </script>
    </svg>
    

    Example 3: Leveraging SCXML drag-and-drop behaviour using ECMAScript files that have been compiled ahead of time

    drag-and-drop.js is first imported into the SVG document using the script tag. This defines the StatechartExecutionContext constructor function in the global scope. The second script tag then obtains a reference to the rect element using DOM, instantiates and initializes a Statechart instance, and registers DOM mouse event listeners on the rect so that DOM events will be dispatched by the statechart instance.

    Note that in this example, an HTML context was no longer needed, as compilation was done ahead-of-time, and thus the RequireJS dependency was no longer present. A pure SVG document was therefore used, rather than an XHTML compound document.

    In this approach, the compilation step is performed before the SCXML document is downloaded to the user's browser. This entails a potentially larger payload, but also a potentially shorter startup time, as the code does not need to be compiled and evaluated before it can be used.

    6. Conclusion

    The scxml-js project has sought to develop a Statechart-to-ECMAScript compiler optimized for use in User Interface development for the World Wide Web. Three compiler backends were developed to test three different Statechart compilation strategies. The performance of each strategy was then tested, and it was found that the Table implementation strategy provided faster execution than other strategies, across all browsers, by a significant margin. Further testing will focus on comparing implementation strategies to optimize memory usage or target code size, both of which are important for Web UI development.

    7. Future Work

    There are many opportunities for future work involving scxml-js.

    First, it will be important to create non-trivial, fully developed examples that illustrate the use of Statecharts in SVG-based user interfaces for the World Wide Web.

    Second, it will be necessary to perform a more exhaustive performance analysis, which, in addition to compilation strategy, takes into account the compiled statechart size, and the rate at which events occur. It will also be important to test memory usage (as the Table approach may not scale to large statecharts), and to perform testing specifically on mobile devices.

    Third, we would like to add support for code synthesis of complete UML 2.0 Statecharts, which is to say, models comprised of Class Diagrams, Statecharts, and descriptions of inter-instance interaction.

    Finally, we would like to develop techniques for the effective use of statecharts in the creation of Web UI's. This process may be described as the development and cataloging of Design Patterns for modelling Web UI behaviour. It is our hope that one or more high-level domain-specific languages may emerge from these patterns, which themselves target statechart semantics.

    8. Acknowledgements

    We would like to acknowledge Prof. Laurie Hendren and Rahul Akolkar, without whose support, the development of scxml-js would not have been possible.

    Bibliography

    [Hollis]
    Ben Hollis Investigating JavaScript Array Iteration Performance – Blog textbar BenHollis.net Investigating JavaScript Array Iteration Performance – Blog textbar BenHollis.net http://benhollis.net/blog/2009/12/13/investigating-javascript-array-iteration-performance/
    [Prototype]
    Prototype JavaScript framework: Array Prototype JavaScript framework: Array http://www.prototypejs.org/api/array
    [Harel2001]
    IN INTEGRATION OF SOFTWARE SPECIFICATION TECHNIQUES FOR APPLICATION IN ENGINEERING, NUMBER 3147 IN LECTURE NOTES IN COMPUTER SCIENCE David HarelHillel Kugler The Rhapsody Semantics of Statecharts (or, On the Executable Core of the UML) The Rhapsody Semantics of Statecharts (or, On the Executable Core of the UML) 325-354 3147 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.6949 2001
    [Harel1996]
    ACM Trans. Softw. Eng. Methodol. David HarelAmnon Naamad The STATEMATE semantics of statecharts The STATEMATE semantics of statecharts 293-333 5 4 10.1145/235321.235322 http://portal.acm.org/citation.cfm?id=235322 1996
    [SCXML]
    Jim BarnettRahul AkolkarRJ Auburn State Chart XML (SCXML): State Machine Notation for Control Abstraction State Chart XML (SCXML): State Machine Notation for Control Abstraction http://www.w3.org/TR/scxml/
    [UML2Superstructure]
    UML 2.0 Superstructure Specification UML 2.0 Superstructure Specification http://www.omg.org/cgi-bin/doc?formal/09-02-02
    [Sekerinski2001]
    Emil SekerinskiRafik Zurob iState: A Statechart Translator iState: A Statechart Translator 376-390 «UML» 2001 — The Unified Modeling Language. Modeling Languages, Concepts, and Tools http://dx.doi.org/10.1007/3-540-45441-1_28 10.1007/3-540-45441-1_28 2001
    [Samek2002]
    Miro Samek Practical statecharts in C/C++ Practical statecharts in C/C++ 416 1578201101, 9781578201105 Focal Press 2002
    [Douglass2000]
    Embedded Systems Programming B. P Douglass Doing Hard Time: Developing Real-Time Systems with UML, Objects, Frameworks and Patterns Doing Hard Time: Developing Real-Time Systems with UML, Objects, Frameworks and Patterns 199 2000
    [FengSVM]
    T. H Feng SVM and SCC Tutorial SVM and SCC Tutorial
    [Niaz2005]
    International Journal of Computer & Information Science I. A NiazJ. Tanaka An Object-Oriented Approach To Generate Java Code From UML Statecharts An Object-Oriented Approach To Generate Java Code From UML Statecharts 6 2 2005
    [Rapp]
    Charles W. Rapp SMC: The State Machine Compiler SMC: The State Machine Compiler http://smc.sourceforge.net/
    [Wasowski2004]
    SIGPLAN Not. Andrzej Wasowski Flattening statecharts without explosions Flattening statecharts without explosions 257-266 39 7 10.1145/998300.997200 http://portal.acm.org/citation.cfm?id=998300.997200 2004
    [ECMAScript4]
    Proposed ECMAScript 4th Edition – Language Overview Proposed ECMAScript 4th Edition – Language Overview 4 http://www.ecmascript.org/es4/spec/overview.pdf 23 October 2007

    XHTML rendition made possible by SchemaSoft's Document Interpreter™ technology.