Your comments on the SCXML Algorithm

Torbjorn,

Thankyou for your detailed comments on the new draft of SCXML.  This email addresses only your comments on the algorithm.  We will respond to your other comments as we have a chance to consider them individually in our meetings.

 

We considered a "looser" semantics for SCXML, but decided to make the semantics as deterministic as possible for reasons of interoperability.  In the commercial marketplace, for example, VoiceXML has been popular largely because it frees customers from their vendors - if you have a VoiceXML app, you can run it on anyone's platform.  For this reason, there is a strong demand for interoperability, and that in turn requires that the application behave the same way on the different platforms.  The industry has in fact had a lot of problems due to small indeterminacies in the VoiceXML specification that complicate this portability, and the VoiceBrowser Group intends to tighten future drafts of the VoiceXML specification.  For this reason, we have decided to make the semantics of SCXML as tight and deterministic as possible from the beginning. 

 

As for the efficiency of the algorithm, there are a number of places where an intelligent implementation can improve over the pseudo code we provide.  The Select Transitions and Remove Conflicting Transitions Phases are one such place.  In configurations not involving parallel states, all an implementation needs to do is to start at the atomic active state and work up the ancestor tree, selecting the first transition (in document order) whose 'event' and 'cond' attributes are satisfied.  This is highly efficient and matches the behavior specified in our more elaborate algorithm.  

 

In cases with parallel states, the Remove Conflicting Transitions Phase should be efficient in cases with moderate numbers of states.  That should include most cases involving natural language dialog applications.  The asymptotic complexity of the Phase is probably quite bad, in the sense that it is inherently slow in configurations with very large numbers of parallel states, but, as you point out, it would be possible to optimize by precomputing conflict sets and their resolutions.  (Storing the results of this calculation would require a lot of space, but any implementation that requires high efficiency in both time and space and a very large number of parallel states will have problems no matter what semantics we assign.)  Thus we currently believe that performance will not be a problem, though we are prepared to revisit this issue if practical problems arise in the field.  

 

A formal specification of the semantics of parallelism that gives applications a choice is an interesting idea, but quite a challenge, and we will postpone it to a future version.  UML does not do this, by the way:  the definition of our Remove Confliction Transitions Phase is largely taken from the UML specification.  Consistency with UML is a secondary design goal for SCXML, and was an additional reason for adopting the semantics that we did.