Re: Your comments on the SCXML Algorithm

Jim,
>
> 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.
>
Thanks for your comments on my comments! Please find my responses below:
>
> 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.
>
I appreciate your concern. Indeterminism is usually a bad thing, and you 
should try to get rid of most of it. But I doubt that developers would 
be very surprised if the semantics of <parallel> involved some 
indeterminism. After all, parallelism/concurrency in for example Java 
has this indeterminacy, so people should be used to it, and perhaps even 
expect it.
>
> 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.
>
But you *could* do it the other way around, couldn't you? For SCXML 1.0 
you could simply *assume* that state machines are conflict-free (and 
also strongly suggest to vendors that they provide off-line tools for 
detecting conflicts). Then, if developers feel conflict-freeness becomes 
a straightjacket (which I doubt they will) you could include run-time 
conflict resolution in SCXML 2.0. From a backwards compatibility point 
of view this would make sense, since 1.0 documents would still run in 
the 2.0 version.

In support of my stand here, I cite from a paper that I read the other day:

"Dynamic conflict resolution is a well-known concept in history of 
statechart languages. Still we believe that this is an expensive concept 
to implement at runtime, and that it does not aid good modeling 
practices. It is doubtful whether it should be implemented in a code 
generator targeting embedded systems. The assumption that there are no 
conflicts requires a cleaner model and gives better opportunities for 
compile-time optimizations." ([1] p. 17)

Now, SCXML may not target embedded systems, but the point is still 
valid, I think. BTW, the draft *does* claim that SCXML targets not only 
natural language dialog applications - it is also being presented "As a 
general process control language in other contexts not involving speech 
processing". I think that in order to gain wide acceptance for SCXML, it 
should be in the interest of W3C to present an as general and widely 
usable SCXML as possible, and that implies not making it very 
hard/impossible to implement efficiently.

(An analogy: The Prolog programming language was possible to implement 
efficiently only since interpreters/compilers 'cheated' and didn't 
impose the so called "occurs check" - see 
<http://en.wikipedia.org/wiki/Occurs_check>)

> 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.
>
Perhaps the formal semantics presented in [1] would be a good start? I 
agree that consistency with UML is an important design goal. But as far 
as I know (but I may well be wrong here), UML *defines* the notion of 
conflict, but does not suggest that dynamic conflict *resolution* should 
take place. Conflicts should be avoided, but that could be left as a 
responsibility of the SCXML author, perhaps aided by a tool capable of 
detecting conflicts off-line, or by an interpreter that refuses to deal 
with documents in which conflicts appear.

References:
[1] Andrzej Wasowski and Peter Sestoft "On the Formal Semantics of 
VisualSTATE Statecharts", IT University Technical Report Series. 
TR-2002-19. ISSN 1600–6100, 
<http://www.dina.kvl.dk/~sestoft/papers/ITU-TR-2002-19.pdf>

Best regards,
Torbjörn

Received on Monday, 26 March 2007 12:34:13 UTC