Background

SCXML is being developed (at the time of this writing, it is a Last Call Working Draft waiting for Implementation Reports and solving its remaining issues to become a Candidate Recommendation) by the W3C's Voice Browser Working Group, which is responsible for the dialog management languages [CCXML] and [VoiceXML].

While there have been previous implementations or use of Harel State Charts, none has become a generic and standard tool for both design and programming. That is, most uses of the State Charts have been limited to design specification (most importantly in UML 2 [UML2]) and lacking direct machine interpretability. Some applications or documents, like the RPC spec [RPC-SC], had to define their own State Chart formalisms that were not reused, demonstrating the appeal of such representations and the need for a standard.

In a departure from its older VoiceXML and CCXML cousins, SCXML has no default voice-specific features such as grammars, speech, and form definition. However, it is extensible and those features (and more) can be added when relevant. On the other hand, the core control elements and State Chart semantics are more powerful and adaptable than in its predecessors.

Features

Let us now focus on what SCXML brings to the table beside the State Charts formalism, whose features were illustrated in the previous section (here is the source code for figure 5).

For one thing, SCXML is on the way to become a W3C recommendation. It already has a dozen implementations, including several that are free, open-source and highly conformant (see table below). It is one of the preferred languages in the very recently approved recommendation for Multimodal Architectures and Interfaces [MMI-arch].

SCXML is also compatible with UML 2 State Charts so that existing UML diagrams can be easily converted to SCXML, and UML 2 editing tools should be able to handle SCXML with minimal effort. Besides, dedicated SCXML editors and debuggers will become available and, as I am developing one of them, I can safely predict that there will be at least one good, free, Web-based editor for SCXML.

When they are available, SCXML interacts nicely with DOM events, which enable loosely-coupled interaction with all sorts of HTML and XML-based applications in a way that authors are already very familiar with.

With all that, core SCXML is lightweight. It can be embedded in Web pages even on somewhat low-powered devices like tablets and set-top boxes. That is a big improvement over the monolithic VoiceXML and CCXML that simply had to run on a server (also using expensive, proprietary software on that server).

Those features should encourage widespread adoption of SCXML, particularly in Web applications.

scalability

Keeping a complex application state for hundreds (of thousands) of clients is expensive, as is running the application logic. On the other hand, keeping and managing a complex application state for one client is well within the capabilities of even the cheapest smartphone. So let them do it! Not only does it reduce infrastructure costs, it may enable more complex designs than would have been possible with server-side control.

latency

Under some circumstances, network latency could degrade the responsiveness of server-controlled Web applications to unacceptable levels. Not so if the client handles user interaction. Even when communication is necessary, a powerful controller can remain responsive while blocking only the parts of the user interface that strictly require a server response, or simply marking them as unsynchronized without blocking. Using local storage, the application could function offline and synchronize whenever network becomes available.

security and privacy

Some users care about their privacy (and those who do not, surely would not complain if you respect theirs anyway). In particular, streaming every detail of user interaction to a server may range from undesirable to unacceptable. There could also be security risks involved if that information were intercepted. By handling the details of user interaction on the client, an application need not transfer all that information. Other information, such as preferences and documents, can be saved locally as well (which means that even more of the application logic moves to the client, reinforcing the other benefits of a decentralized architecture).

openness

Distributing more application code to the client means that the user has more control over how it runs and what it does. They could build plug-ins and modifications to adapt the application to their needs, increasing the value of the application with no additional effort from the original developer.

Of course, some developers (and a greater number of their managers) consider openness a drawback rather than an opportunity. Hence the proposal for protected media playback in HTML that is hotly debated at the moment. It is easy to imagine that its proponents would push for a similar API to run encrypted versions of fundamentally open content such as SCXML and JavaScript to (try in vain to, if history is any guide) prevent that content from being reverse-engineered and modified, while still sending it to client devices.

Web Workers

Web Workers are JavaScript threads, with their own execution context, that run in the background and communicate with their parent Web page through DOM events. That sounds ideal for a SCXML interpreter which is supposed to be a black box with only events going in or out, and this option was given some thought.

However, Web Workers in practice lack features that normal client-side code can rely on, most importantly the DOM. By using and abusing the DOM, JSSC can do very powerful XML manipulation “for free”, and enjoys native performance. Also, at the moment there is no good browser interface for debugging Web Workers, which is a serious issue when you are looking at writing a few thousand lines of code.

So JSSC was written as a regular JavaScript program, running in the Web page's own context. Well, almost (keep reading).

Encapsulation

SCXML documents can contain executable ECMAScript code that is supposed to run in an encapsulated data model. But Web browsers do not let you just create a new JavaScript context (yet) to evaluate code.

Spawning a Web Worker just for the embedded ECMAScript was not an option either, because it would have made it a black box for the interpreter just as for the rest of the Web page. And the interpreter needs to access the data model very often (and preferably without the overhead of inter-thread communication).

The closest thing to a fresh JavaScript context that unprivileged code can have is a dedicated window object, instead of the page's main window object. So JSSC creates a hidden iframe (which counts as a “window” just like a tab does) for each SCXML session, and uses some rather unsightly tricks to make ECMAScript code from the SCXML document run transparently in that iframe's window, and to hide the browser's environment from that code as much as possible (source code). Those tricks include:

• shadowing predefined browser properties and internal JSSC properties by dynamically adding an object to the scope chain [ScopeChain] of the execution of SCXML-embedded ECMASCript
• calling eval() from a function defined in the iframe itself, rather than the main window
• writing <script> elements in the iframe to execute the same elements from the SCXML document
• wrapping setTimeout calls so their callbacks are executed in the modified scope (the setInterval wrapper is not yet implemented)
• defining getter and setter methods allowing access to SCXML system properties that are supposed to be read-only, such as _event

It is not possible to create a perfect sandbox (not without implementing a full ECMAScript interpreter, anyway) in the existing browser environment. The iframe-based data model implementation is relatively modular, so it can be replaced in case that changes in the future. Until then, there are several unavoidable ways for SCXML-embedded ECMASCript to gain access to its parent window, the browser, and its own interpreter. Obviously, that violates the encapsulation principle of SCXML, but at least JSSC makes it hard to do so accidentally.

Working with JavaScript structures

The reference algorithm from the SCXML recommendation uses blocking queues to implement the interpreter's event queues. Such structures are unavailable and unnatural in Web browsers. The JavaScript way is asynchronous calls and callbacks. Thus, JSSC's translation of the SCXML event loop is exited as soon as the SC reaches a stable configuration and has no more events to process. The loop can then be recalled by the interpreter's fireEvent() method when it accepts an external event.

Then there are structures which could be implemented in ECMAScript, but at a price. ECMAScript natively has only one data structure: the hash table. Everything is a hash table, except some C-like arrays that were added recently and cannot contain references. ECMAScript Arrays are just hash tables with numerical keys, with the performance you would expect for insertion/deletion.

As a result, if you wanted to implement, say, an actual linked list in ECMAScript, you would have to use plenty of small objects (which are hash tables) to represent the links, with a property referencing the next link. The code, memory and performance overhead of having lots of tiny hash tables instead of C-like structures and pointers do not justify it. It is a shame, because a linked list would have been wonderful to represent the event queues in SCXML interpreters. Instead, JSSC uses plain Arrays, which do come with queue-like methods, and trusts the JavaScript engine (they're getting smarter all the time) to optimize accordingly.

Yet another structure used in the reference algorithm is the ordered list. That one too would be inefficient to implement in any classic way in ECMAScript, but even more inefficient to not implement and just sort an Array every time it should be in order. That is particularly true because the order of the items in the list is not trivial to compute in the case for which SCXML uses ordered lists. That is, representing the state chart's configuration.

JSSC does keep a handy hash table with the unsorted configuration for the purpose of testing whether an ID is in the current configuration. But other tasks require the ordered configuration or can be optimized by representing the configuration in an ordered way. And when you want a mutable, ordered list, the underlying structure is typically some sort of tree or linked list. Yet, like the links in linked lists, tree nodes suffer from being represented as a hash table. Here, I wrote my own data structure.

configuration tree and selection

JSSC is designed to work directly on the parsed SCXML DOM. Some operations, however, can be optimized by compiling a configuration tree with shortcuts. They are defined in JSSC by the CompiledTree constructor (source code).

As long as there is no parallel state in a subtree, its active states form a chain that can be represented as a list of nodes instead of as a full-blown tree. JSSC's CompiledTrees therefore contain not states but lists of states. These lists contain a direct reference to both ends for fast access, as well as a property saying whether they end in an atomic state or a parallel one. The chains are immutable once constructed, so they do not suffer much from being implemented as Arrays.

Each CompiledTree node (that does not contain an atomic-ended chain) has a table associating the id of all descendant parallel states to the node containing the chain ending with that state. That way, when a new node has been constructed for any chain in the SCXML document, the algorithm can instantly attach it to its parent node by looking up the chain's parent's id in previously built trees (and vice-versa if the existing trees are not rooted to the <scxml> element). If two chains have been built that begin with the same state (e.g. because of conflicting transition targets) the algorithm will detect it when trying to attach the most recent chain and will resolve the conflict very quickly.

One perk of (fully-built) CompiledTrees is that they are unable to represent conflicting state configurations. As long as the building algorithm finishes (and it always will, unless you kill the browser or some targets did not even exist), the result is guaranteed to be a valid configuration even if the targets passed to it were in conflict.

As the above figure illustrates with only a small configuration, CompiledTrees have less nodes: Only one for every <parallel> and every atomic state, instead of one for every state. That makes a greater difference in larger trees than the example, obviously. Less nodes mean less calls when using recursive functions on the tree.

One of the most performance-critical steps is transition selection. That is, looking over all the active states for transitions that match an event and current conditions. Many events can arrive quickly without triggering a state change or even without matching any transition at all, and the interpreter must be able to determine that before it can discard the event and dequeue the next one.

The selection process looks at all active states, and examines the transitions in each state. Under certain (frequent) conditions, some of the states or transitions may be skipped. The JSSC algorithm consists of the CompiledTree.select() method defined thus:

CompiledTree.prototype.select=function(test)
{
	var enabled=[]
	var allChildrenEnabled=true
	var enabledTargetedTransition=false
	
	if(!this.root.atomic){
		var childSelection
		for(var i=0; i<this.children.length; i++){
			childSelection=this.children[i].select(test)
			if(!childSelection.enabled.length){
				allChildrenEnabled=false
				continue
			}
			enabled=enabled.concat(childSelection.enabled)
			enabledTargetedTransition |= childSelection.hasTargets
		}
	}
	else allChildrenEnabled=false
	
	if(!allChildrenEnabled){
		var t
		for(var p=this.root.path, i=p.length-1; i>=0; i--) if(t=test(p[i])){
			if(!t.targets)
				enabled.push(t)
			else{
				if(enabledTargetedTransition) break
				enabled.push(t)
				enabledTargetedTransition=true
			}
			break
		}
	}
	return {hasTargets:enabledTargetedTransition, enabled:enabled}
}

This uses the classic recursive pattern for depth-first traversal, with the first part (under the condition if(!this.root.atomic)) of the function applying itself to child subtrees and pooling the results. The second part selects results within the current subtree. Depth-first traversal is equivalent to selection order, where a state is looked at before is parent, and siblings are examined left-to-right. That is important because transitions must be preempted, and later executed, in that order.

Transition matching is done by the test argument, a function that returns the first positive match in a state (or nothing).

The first optimization simply comes with using the CompiledTree structure, by reducing the number of calls as mentioned earlier. Recent browsers on recent hardware, even without CompiledTrees, are at no risk of overflowing the call stack unless the state chart contains hundreds of thousands of states (worst case would be a chain of single child states, overflowing at a few dozen thousand states; with CompiledTrees that chain would be reduced to one node). But memory and complexity savings are interesting long before then.

The SCXML specification deals with conflicting transitions by picking the one deepest and leftmost in the tree among a set of conflicting transitions: the first in selection order. Also, only one transition (the first match) may be selected for each active atomic state. Note how, in the second half of the select() method, some or all of the code may be skipped. That is, if all subtrees have selected a transition, the current node does not even look at its own transitions (yellow mark). Otherwise, as soon as a transition is selected in the current node, the function returns (orange). And if that transition has targets, and a transition with targets has already been selected, then the new transition will conflict with the previous one and therefore it is not selected (green).

More optimization is possible, to skip all conflicting transitions instead of only the hierarchical type, but it would require knowing the transitions' LCCA (Least Common Compound Ancestor) in advance. Since JSSC allows transitions with dynamic targets, it computes the LCCA lazily and so cannot in general use the LCCA during transition selection (only transitions that are selected will have their LCCA computed).

dynamic transitions

Dynamic targets mean that transitions in JSSC can have a targetexpr attribute instead of target. The attribute is evaluated just before taking the selected transitions in a microstep, and only if the transition was selected, so it will not show up as arrows on the graphical visualization.

Indeed, this feature makes the State Chart… not a State Chart, since it is no longer a connected graph at all times. In the general case, such structures lose some of their mathematical appeal. But dynamic transitions are an optional feature and, when used properly, do not make the SCXML document unstable nor unpredictable. If you can prove that the evaluation has a fixed set of outcomes, you can reason on the State Chart as usual despite that dynamic transition. And they are powerful and generic.

They could be used to implement history pseudo-states. Another example: In november, a user on the VBWG mailing list had a largely unrelated feature proposal that could also be implemented rather easily with dynamic transitions:

Arguably, an external entity should not tell a SC what states to go to because a SC is supposed to be a black box. But that is beside the point. In this case, rather than add another specific mechanism for this specific case, a dynamic transition could use values passed to it by the parent session.

Yet another use, dynamic transitions can replace a long switch-like list of transitions such as:

<transition cond="next=='s1'" target="s1"/>
<transition cond="next=='s2'" target="s2"/>
<transition cond="next=='s3'" target="s3"/>
…

In that last case, using the dynamic transition <transition targetexpr="next"/> is not only concise, but saves time during selection.

Eventually, JSSC will be able to interpret a SCXML document that is being modified at runtime. To make that possible, JSSC computes very little in advance, but still tries to run fast, keeping costly results as long as they are reusable. That includes the compiled configuration tree, which is not recalculated every microstep if all the selected transitions were targetless. Also, when targets and LCCA are computed for a transition, they are stored and reused unless the transition had dynamic targets.

scripting

All ECMAScript code embedded in SCXML attribute values is parsed at runtime. That is a constraint of working in the browser; only native SCXML support could avoid it. Modern browsers come with really good JavaScript optimization, but those do not apply to code evaluated by eval(), which JSSC uses for code in attribute values. Therefore, JSSC users are advised to put any performance-sensitive code in <script> elements (which are optimized on the fly, but there is an overhead for that), or even better, outside the interpreter so they can be optimized at load time and cached. JSSC provides a way for SCXML-embedded ECMAScript to transparently access libraries and other objects in the containing HTML document without resorting to platform-specific syntax inside the SCXML document:

var myLibrary = {…}

var sc = new SCxml("src.scxml", null, {lib1: myLibrary})

DOM Events

Unfortunately, at this time JSSC is the only SCXML implementation that supports DOM events. DOM Event integration is part of the SCXML draft, but because there is no other implementation, it will most likely be removed from the candidate recommendation. Support for DOM events will therefore become a non-standard extension for some time, but that does not really change anything for JSSC.

JSSC's SCxml instances have a fireEvent() method to which external JavaScript can simply pass an existing DOM event, or a name and data if that is more convenient. Explicitly constructing a full SCxml.ExternalEvent is unnecessary in many cases.

On the output side, JSSC supports <send type="DOM" …/> nearly as the draft specified it, allowing SCXML to transparently send custom DOM Events to any element in the parent document. Both CSS selectors and XPaths are supported to specify the target, and I plan to add a mechanism to specify the target document according to my latest proposal on the VBWG mailing list.

HTTP requests

The SCXML specification focuses on a symmetrical, fire-and-forget communication scheme called Event I/O Processors where both ends deal in events and both ends can send and receive to and from anywhere. That is, of course, impossible on a client machine; on the other hand, there are many existing and future services that Web applications can use over HTTP, and most do not understand SCXML events (even if the encoding of SCXML events were adequately specified for transport, which it is not).

JSSC fills the void left by the inability to implement remote Event I/O Processors by creating two extensions. The simplest is an executable content element (an action), <fetch> (full documentation), that lets a SCXML document send HTTP requests and receive events with the responses. It works much like XMLHttpRequest, and in fact it is implemented on top of it, simply wrapping it so the functionality fits into SCXML.

That gives SCXML good, generic, remote communication ability, but that is not all. Synchronous fetching of remote (and even local) resources is considered a very bad practice on the Web, more so for UI and high-level control which must be responsive all the time. The presence of the synchronous <data src> in SCXML is therefore an atrocity (which shall not be committed in JSSC). And it can be averted thanks, again, to <fetch>.

server-sent events

XMLHttpRequests are commonly used to implement virtual persistent connections, using various third-party JavaScript libraries. But one method has given rise to an actual browser API and W3C candidate recommendation, and, considering that is is called “Server-sent Events”, I just had to provide a SCXML way to use it.

Technically, a server cannot initiate a connection with a client (to send it an event, for example). So what happens is that the client initiates the connection, and then both ends keep it alive. The browser transparently reconnects if it times out, and there is an optional facility in the message protocol to recover any event that should have been sent during the disconnection. The browser gives us all that for free, and the server requires relatively little work to fulfil its end, since it all happens over good old HTTP.

The EventSource interface was designed to receive DOM Events remotely, but it is trivial to adapt it for SCXML events. That leaves the design question: how do we use this the SCXML way? It cannot be an executable content extension, because it has a persistent effect. That goes against the spirit of all the existing executable content elements.

At first, the plan was to create a new element that would work very much like <invoke>, the element used to define activities for a state. It makes sense, since a persistent connection is a sort of activity that can be started (opened) and stopped (closed), and, while it is running (or rather open), it can send and/or receive events to/from its invoker. But invocations are a complicated part of SCXML, with hundreds of lines of code in many different parts of the code. Not something that should be duplicated lightly. So I designed an extension to <invoke> itself, allowing a slightly different behaviour (about nine lines of code out of three hundred, that's how slightly) to occur based on its type attribute (specification). Then, I designed the event-stream type (documentation) to fit into that. Then I implemented it just as specified, without touching anymore existing code, and it worked.

As part of the design process, I specified that invocations in my proposed extension could be asymmetrical (since the EventSource interface for server-sent events, as the name implies, only receives events). That led to Jim Barnett (editor of the SCXML recommendation) suggesting that might also become true of Event I/O Processors. So maybe JSSC will implement (half of) the HTTP I/O Processor after all. But let us get back to the present.

The event-stream type allows a client-side SCXML-based application to effortlessly open a connection to a remote server (it is not that easy on the server-side, unless you already have the right sort of server). As long as the connection is open, the server can push events to the client. The restrictions are the same as for the underlying EventSource object.

test methodology

A series of tests were performed on the latest version of JSSC (as of 2 june 2013), using two devices, five state chart sizes, three types of microsteps, and two processing schedules. All the test charts except the first were generated by a recursive algorithm. They contain 1 parallel state for every 6 states, and most of their states have the same four transitions: two for “test1” and two for “test2”, with the first transition in each set having a false condition. The other transition for “test2” has a dynamic target expression which picks a random target state anywhere in the chart.

Green bars represent the time to process the event “test0”, which is not matched by any transition: thus, it only stresses the selection loop. Blue bars represent the time to process the event “test1”, matched by targetless transitions: the configuration stays the same; and purple bars stand for the time to process “test2”, which triggers randomly targeted transitions, so the configuration tree is rebuilt and the full microstep process is tested.

Unfortunately, JavaScript engines and profilers are unable to measure time more accurately than in milliseconds. Thus only the largest state charts would lead to non-zero processing times for one event. In order to obtain measurable times, a thousand events were added. Accordingly, the maximum acceptable time ranges (blurry red horizontal bars, because audio lag is more acceptable for violins than drums, and rendering frequencies can vary) were multiplied by 1000 (assuming that the time to process one event is roughly 1/1000 of the time to process 1000 events, which seems reasonable but could be wrong).

First, the events were all added before starting the interpreter and processed in batch (represented by the darker bar in the graph). CPU and compiler preference for batch-processing is obvious here. Then another thousand events were queued with the interpreter running, which leads to some wildly variable overhead (thus the blurry lighter bars — more tests will have to be performed to obtain proper statistical variation data).

results