ceph/src/boost/libs/statechart/doc/rationale.html

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
   2
   3 <html>
   4 <head>
   5   <meta http-equiv="Content-Language" content="en-us">
   6   <meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
   7   <meta name="GENERATOR" content="Microsoft FrontPage 6.0">
   8   <meta name="ProgId" content="FrontPage.Editor.Document">
   9   <link rel="stylesheet" type="text/css" href="../../../boost.css">
  10
  11   <title>The Boost Statechart Library - Rationale</title>
  12 </head>
  13
  14 <body link="#0000FF" vlink="#800080">
  15   <table border="0" cellpadding="7" cellspacing="0" width="100%" summary=
  16   "header">
  17     <tr>
  18       <td valign="top" width="300">
  19         <h3><a href="../../../index.htm"><img alt="C++ Boost" src=
  20         "../../../boost.png" border="0" width="277" height="86"></a></h3>
  21       </td>
  22
  23       <td valign="top">
  24         <h1 align="center">The Boost Statechart Library</h1>
  25
  26         <h2 align="center">Rationale</h2>
  27       </td>
  28     </tr>
  29   </table>
  30   <hr>
  31
  32   <dl class="index">
  33     <dt><a href="#Introduction">Introduction</a></dt>
  34
  35     <dt><a href="#WhyYetAnotherStateMachineFramework">Why yet another state
  36     machine framework</a></dt>
  37
  38     <dt><a href="#StateLocalStorage">State-local storage</a></dt>
  39
  40     <dt><a href="#DynamicConfigurability">Dynamic configurability</a></dt>
  41
  42     <dt><a href="#ErrorHandling">Error handling</a></dt>
  43
  44     <dt><a href="#AsynchronousStateMachines">Asynchronous state
  45     machines</a></dt>
  46
  47     <dt><a href="#MemberFunctionsVsFunctionObjects">User actions: Member
  48     functions vs. function objects</a></dt>
  49
  50     <dt><a href="#Limitations">Limitations</a></dt>
  51   </dl>
  52
  53   <h2><a name="Introduction" id="Introduction">Introduction</a></h2>
  54
  55   <p>Most of the design decisions made during the development of this library
  56   are the result of the following requirements.</p>
  57
  58   <p>Boost.Statechart should ...</p>
  59
  60   <ol>
  61     <li>be fully type-safe. Whenever possible, type mismatches should be
  62     flagged with an error at compile-time</li>
  63
  64     <li>not require the use of a code generator. A lot of the existing FSM
  65     solutions force the developer to design the state machine either
  66     graphically or in a specialized language. All or part of the code is then
  67     generated</li>
  68
  69     <li>allow for easy transformation of a UML statechart (defined in
  70       <a href="http://www.omg.org/cgi-bin/doc?formal/03-03-01">http://www.omg.org/cgi-bin/doc?formal/03-03-01</a>)
  71       into a working state machine. Vice versa, an existing C++
  72       implementation of a state machine should be fairly trivial to transform
  73       into a UML statechart. Specifically, the following state machine
  74       features should be supported:
  75
  76       <ul>
  77         <li>Hierarchical (composite, nested) states</li>
  78
  79         <li>Orthogonal (concurrent) states</li>
  80
  81         <li>Entry-, exit- and transition-actions</li>
  82
  83         <li>Guards</li>
  84
  85         <li>Shallow/deep history</li>
  86       </ul>
  87     </li>
  88
  89     <li>produce a customizable reaction when a C++ exception is propagated
  90     from user code</li>
  91
  92     <li>support synchronous and asynchronous state machines and leave it to
  93     the user which thread an asynchronous state machine will run in. Users
  94     should also be able to use the threading library of their choice</li>
  95
  96     <li>support the development of arbitrarily large and complex state
  97     machines. Multiple developers should be able to work on the same state
  98     machine simultaneously</li>
  99
 100     <li>allow the user to customize all resource management so that the
 101     library could be used for applications with hard real-time
 102     requirements</li>
 103
 104     <li>enforce as much as possible at compile time. Specifically, invalid
 105     state machines should not compile</li>
 106
 107     <li>offer reasonable performance for a wide range of applications</li>
 108   </ol>
 109
 110   <h2><a name="WhyYetAnotherStateMachineFramework" id=
 111   "WhyYetAnotherStateMachineFramework">Why yet another state machine
 112   framework?</a></h2>
 113
 114   <p>Before I started to develop this library I had a look at the following
 115   frameworks:</p>
 116
 117   <ul>
 118     <li>The framework accompanying the book "Practical Statecharts in C/C++"
 119     by Miro Samek, CMP Books, ISBN: 1-57820-110-1<br>
 120     <a href=
 121     "http://www.quantum-leaps.com">http://www.quantum-leaps.com<br></a> Fails
 122     to satisfy at least the requirements 1, 3, 4, 6, 8.</li>
 123
 124     <li>The framework accompanying "Rhapsody in C++" by ILogix (a code
 125     generator solution)<br>
 126     <a href=
 127     "http://www.ilogix.com/sublevel.aspx?id=53">http://www.ilogix.com/sublevel.aspx?id=53<br>
 128     </a> This might look like comparing apples with oranges. However, there
 129     is no inherent reason why a code generator couldn't produce code that can
 130     easily be understood and modified by humans. Fails to satisfy at least
 131     the requirements 2, 4, 5, 6, 8 (there is quite a bit of error checking
 132     before code generation, though).</li>
 133
 134     <li>The framework accompanying the article "State Machine Design in
 135     C++"<br>
 136     <a href=
 137     "http://www.ddj.com/184401236?pgno=1">http://www.ddj.com/184401236?pgno=1<br>
 138     </a> Fails to satisfy at least the requirements 1, 3, 4, 5 (there is no
 139     direct threading support), 6, 8.</li>
 140   </ul>
 141
 142   <p>I believe Boost.Statechart satisfies all requirements.</p>
 143
 144   <h2><a name="StateLocalStorage" id="StateLocalStorage">State-local
 145   storage</a></h2>
 146
 147   <p>This not yet widely known state machine feature is enabled by the fact
 148   that every state is represented by a class. Upon state-entry, an object of
 149   the class is constructed and the object is later destructed when the state
 150   machine exits the state. Any data that is useful only as long as the
 151   machine resides in the state can (and should) thus be a member of the
 152   state. This feature paired with the ability to spread a state machine over
 153   several translation units makes possible virtually unlimited
 154   scalability.&nbsp;</p>
 155
 156   <p>In most existing FSM frameworks the whole state machine runs in one
 157   environment (context). That is, all resource handles and variables local to
 158   the state machine are stored in one place (normally as members of the class
 159   that also derives from some state machine base class). For large state
 160   machines this often leads to the class having a huge number of data members
 161   most of which are needed only briefly in a tiny part of the machine. The
 162   state machine class therefore often becomes a change hotspot what leads to
 163   frequent recompilations of the whole state machine.</p>
 164
 165   <p>The FAQ item "<a href="faq.html#StateLocalStorage">What's so cool about
 166   state-local storage?</a>" further explains this by comparing the tutorial
 167   StopWatch to a behaviorally equivalent version that does not use
 168   state-local storage.</p>
 169
 170   <h2><a name="DynamicConfigurability" id="DynamicConfigurability">Dynamic
 171   configurability</a></h2>
 172
 173   <h3>Two types of state machine frameworks</h3>
 174
 175   <ul>
 176     <li>A state machine framework supports dynamic configurability if the
 177     whole layout of a state machine can be defined at runtime ("layout"
 178     refers to states and transitions, actions are still specified with normal
 179     C++ code). That is, data only available at runtime can be used to build
 180     arbitrarily large machines. See "A Multiple Substring Search Algorithm"
 181     by Moishe Halibard and Moshe Rubin in June 2002 issue of CUJ for a good
 182     example (unfortunately not available online).</li>
 183
 184     <li>On the other side are state machine frameworks which require the
 185     layout to be specified at compile time</li>
 186   </ul>
 187
 188   <p>State machines that are built at runtime almost always get away with a
 189   simple state model (no hierarchical states, no orthogonal states, no entry
 190   and exit actions, no history) because the layout is very often <b>computed
 191   by an algorithm</b>. On the other hand, machine layouts that are fixed at
 192   compile time are almost always designed by humans, who frequently need/want
 193   a sophisticated state model in order to keep the complexity at acceptable
 194   levels. Dynamically configurable FSM frameworks are therefore often
 195   optimized for simple flat machines while incarnations of the static variant
 196   tend to offer more features for abstraction.</p>
 197
 198   <p>However, fully-featured dynamic FSM libraries do exist. So, the question
 199   is:</p>
 200
 201   <h3>Why not use a dynamically configurable FSM library for all state
 202   machines?</h3>
 203
 204   <p>One might argue that a dynamically configurable FSM framework is all one
 205   ever needs because <b>any</b> state machine can be implemented with it.
 206   However, due to its nature such a framework has a number of disadvantages
 207   when used to implement static machines:</p>
 208
 209   <ul>
 210     <li>No compile-time optimizations and validations can be made. For
 211     example, Boost.Statechart determines the <a href=
 212     "definitions.html#InnermostCommonContext">innermost common context</a> of
 213     the transition-source and destination state at compile time. Moreover,
 214     compile time checks ensure that the state machine is valid (e.g. that
 215     there are no transitions between orthogonal states).</li>
 216
 217     <li>Double dispatch must inevitably be implemented with some kind of a
 218     table. As argued under <a href="performance.html#DoubleDispatch">Double
 219     dispatch</a>, this scales badly.</li>
 220
 221     <li>To warrant fast table lookup, states and events must be represented
 222     with an integer. To keep the table as small as possible, the numbering
 223     should be continuous, e.g. if there are ten states, it's best to use the
 224     ids 0-9. To ensure continuity of ids, all states are best defined in the
 225     same header file. The same applies to events. Again, this does not
 226     scale.</li>
 227
 228     <li>Because events carrying parameters are not represented by a type,
 229     some sort of a generic event with a property map must be used and
 230     type-safety is enforced at runtime rather than at compile time.</li>
 231   </ul>
 232
 233   <p>It is for these reasons, that Boost.Statechart was built from ground up
 234   to <b>not</b> support dynamic configurability. However, this does not mean
 235   that it's impossible to dynamically shape a machine implemented with this
 236   library. For example, guards can be used to make different transitions
 237   depending on input only available at runtime. However, such layout changes
 238   will always be limited to what can be foreseen before compilation. A
 239   somewhat related library, the boost::spirit parser framework, allows for
 240   roughly the same runtime configurability.</p>
 241
 242   <h2><a name="ErrorHandling" id="ErrorHandling">Error handling</a></h2>
 243
 244   <p>There is not a single word about error handling in the UML state machine
 245   semantics specifications. Moreover, most existing FSM solutions also seem
 246   to ignore the issue.&nbsp;</p>
 247
 248   <h3>Why an FSM library should support error handling</h3>
 249
 250   <p>Consider the following state configuration:</p>
 251
 252   <p><img alt="A" src="A.gif" border="0" width="230" height="170"></p>
 253
 254   <p>Both states define entry actions (x() and y()). Whenever state A becomes
 255   active, a call to x() will immediately be followed by a call to y(). y()
 256   could depend on the side-effects of x(). Therefore, executing y() does not
 257   make sense if x() fails. This is not an esoteric corner case but happens in
 258   every-day state machines all the time. For example, x() could acquire
 259   memory the contents of which is later modified by y(). There is a different
 260   but in terms of error handling equally critical situation in the Tutorial
 261   under <a href=
 262   "tutorial.html#GettingStateInformationOutOfTheMachine">Getting state
 263   information out of the machine</a> when <code>Running::~Running()</code>
 264   accesses its outer state <code>Active</code>. Had the entry action of
 265   <code>Active</code> failed and had <code>Running</code> been entered anyway
 266   then <code>Running</code>'s exit action would have invoked undefined
 267   behavior. The error handling situation with outer and inner states
 268   resembles the one with base and derived classes: If a base class
 269   constructor fails (by throwing an exception) the construction is aborted,
 270   the derived class constructor is not called and the object never comes to
 271   life.<br>
 272   In most traditional FSM frameworks such an error situation is relatively
 273   easy to tackle <b>as long as the error can be propagated to the state
 274   machine client</b>. In this case a failed action simply propagates a C++
 275   exception into the framework. The framework usually does not catch the
 276   exception so that the state machine client can handle it. Note that, after
 277   doing so, the client can no longer use the state machine object because it
 278   is either in an unknown state or the framework has already reset the state
 279   because of the exception (e.g. with a scope guard). That is, by their
 280   nature, state machines typically only offer basic exception safety.<br>
 281   However, error handling with traditional FSM frameworks becomes
 282   surprisingly cumbersome as soon as a lot of actions can fail and the state
 283   machine <b>itself</b> needs to gracefully handle these errors. Usually, a
 284   failing action (e.g. x()) then posts an appropriate error event and sets a
 285   global error variable to true. Every following action (e.g. y()) first has
 286   to check the error variable before doing anything. After all actions have
 287   completed (by doing nothing!), the previously posted error event has to be
 288   processed what leads to the execution of the remedy action. Please note
 289   that it is not sufficient to simply queue the error event as other events
 290   could still be pending. Instead, the error event has absolute priority and
 291   has to be dealt with immediately. There are slightly less cumbersome
 292   approaches to FSM error handling but these usually necessitate a change of
 293   the statechart layout and thus obscure the normal behavior. No matter what
 294   approach is used, programmers are normally forced to write a lot of code
 295   that deals with errors and most of that code is <b>not</b> devoted to error
 296   handling but to error propagation.</p>
 297
 298   <h3>Error handling support in Boost.Statechart</h3>
 299
 300   <p>C++ exceptions may be propagated from any action to signal a failure.
 301   Depending on how the state machine is configured, such an exception is
 302   either immediately propagated to the state machine client or caught and
 303   converted into a special event that is dispatched immediately. For more
 304   information see the <a href="tutorial.html#ExceptionHandling">Exception
 305   handling</a> chapter in the Tutorial.</p>
 306
 307   <h3>Two stage exit</h3>
 308
 309   <p>An exit action can be implemented by adding a destructor to a state. Due
 310   to the nature of destructors, there are two disadvantages to this
 311   approach:</p>
 312
 313   <ul>
 314     <li>Since C++ destructors should virtually never throw, one cannot simply
 315     propagate an exception from an exit action as one does when any of the
 316     other actions fails</li>
 317
 318     <li>When a <code>state_machine&lt;&gt;</code> object is destructed then
 319     all currently active states are inevitably also destructed. That is,
 320     state machine termination is tied to the destruction of the state machine
 321     object</li>
 322   </ul>
 323
 324   <p>In my experience, neither of the above points is usually problem in
 325   practice since ...</p>
 326
 327   <ul>
 328     <li>exit actions cannot often fail. If they can, such a failure is
 329     usually either
 330
 331       <ul>
 332         <li>not of interest to the outside world, i.e. the failure can simply
 333         be ignored</li>
 334
 335         <li>so severe, that the application needs to be terminated anyway. In
 336         such a situation stack unwind is almost never desirable and the
 337         failure is better signaled through other mechanisms (e.g.
 338         abort())</li>
 339       </ul>
 340     </li>
 341
 342     <li>to clean up properly, often exit actions <b>must</b> be executed when
 343     a state machine object is destructed, even if it is destructed as a
 344     result of a stack unwind</li>
 345   </ul>
 346
 347   <p>However, several people have put forward theoretical arguments and
 348   real-world scenarios, which show that the exit action to destructor mapping
 349   <b>can</b> be a problem and that workarounds are overly cumbersome. That's
 350   why <a href="tutorial.html#TwoStageExit">two stage exit</a> is now
 351   supported.</p>
 352
 353   <h2><a name="AsynchronousStateMachines" id=
 354   "AsynchronousStateMachines">Asynchronous state machines</a></h2>
 355
 356   <h3>Requirements</h3>
 357
 358   <p>For asynchronous state machines different applications have rather
 359   varied requirements:</p>
 360
 361   <ol>
 362     <li>In some applications each state machine needs to run in its own
 363     thread, other applications are single-threaded and run all machines in
 364     the same thread</li>
 365
 366     <li>For some applications a FIFO scheduler is perfect, others need
 367     priority- or EDF-schedulers</li>
 368
 369     <li>For some applications the boost::thread library is just fine, others
 370     might want to use another threading library, yet other applications run
 371     on OS-less platforms where ISRs are the only mode of (apparently)
 372     concurrent execution</li>
 373   </ol>
 374
 375   <h3>Out of the box behavior</h3>
 376
 377   <p>By default, <code>asynchronous_state_machine&lt;&gt;</code> subtype
 378   objects are serviced by a <code>fifo_scheduler&lt;&gt;</code> object.
 379   <code>fifo_scheduler&lt;&gt;</code> does not lock or wait in
 380   single-threaded applications and uses boost::thread primitives to do so in
 381   multi-threaded programs. Moreover, a <code>fifo_scheduler&lt;&gt;</code>
 382   object can service an arbitrary number of
 383   <code>asynchronous_state_machine&lt;&gt;</code> subtype objects. Under the
 384   hood, <code>fifo_scheduler&lt;&gt;</code> is just a thin wrapper around an
 385   object of its <code>FifoWorker</code> template parameter (which manages the
 386   queue and ensures thread safety) and a
 387   <code>processor_container&lt;&gt;</code> (which manages the lifetime of the
 388   state machines).</p>
 389
 390   <p>The UML standard mandates that an event not triggering a reaction in a
 391   state machine should be silently discarded. Since a
 392   <code>fifo_scheduler&lt;&gt;</code> object is itself also a state machine,
 393   events destined to no longer existing
 394   <code>asynchronous_state_machine&lt;&gt;</code> subtype objects are also
 395   silently discarded. This is enabled by the fact that
 396   <code>asynchronous_state_machine&lt;&gt;</code> subtype objects cannot be
 397   constructed or destructed directly. Instead, this must be done through
 398   <code>fifo_scheduler&lt;&gt;::create_processor&lt;&gt;()</code> and
 399   <code>fifo_scheduler&lt;&gt;::destroy_processor()</code>
 400   (<code>processor</code> refers to the fact that
 401   <code>fifo_scheduler&lt;&gt;</code> can only host
 402   <code>event_processor&lt;&gt;</code> subtype objects;
 403   <code>asynchronous_state_machine&lt;&gt;</code> is just one way to
 404   implement such a processor). Moreover,
 405   <code>create_processor&lt;&gt;()</code> only returns a
 406   <code>processor_handle</code> object. This must henceforth be used to
 407   initiate, queue events for, terminate and destroy the state machine through
 408   the scheduler.</p>
 409
 410   <h3>Customization</h3>
 411
 412   <p>If a user needs to customize the scheduler behavior she can do so by
 413   instantiating <code>fifo_scheduler&lt;&gt;</code> with her own class
 414   modeling the <code>FifoWorker</code> concept. I considered a much more
 415   generic design where locking and waiting is implemented in a policy but I
 416   have so far failed to come up with a clean and simple interface for it.
 417   Especially the waiting is a bit difficult to model as some platforms have
 418   condition variables, others have events and yet others don't have any
 419   notion of waiting whatsoever (they instead loop until a new event arrives,
 420   presumably via an ISR). Given the relatively few lines of code required to
 421   implement a custom <code>FifoWorker</code> type and the fact that almost
 422   all applications will implement at most one such class, it does not seem to
 423   be worthwhile anyway. Applications requiring a less or more sophisticated
 424   event processor lifetime management can customize the behavior at a more
 425   coarse level, by using a custom <code>Scheduler</code> type. This is
 426   currently also true for applications requiring non-FIFO queuing schemes.
 427   However, Boost.Statechart will probably provide a
 428   <code>priority_scheduler</code> in the future so that custom schedulers
 429   need to be implemented only in rare cases.</p>
 430
 431   <h2><a name="MemberFunctionsVsFunctionObjects" id=
 432   "MemberFunctionsVsFunctionObjects">User actions: Member functions vs.
 433   function objects</a></h2>
 434
 435   <p>All user-supplied functions (<code>react</code> member functions,
 436   entry-, exit- and transition-actions) must be class members. The reasons
 437   for this are as follows:</p>
 438
 439   <ul>
 440     <li>The concept of state-local storage mandates that state-entry and
 441     state-exit actions are implemented as members</li>
 442
 443     <li><code>react</code> member functions and transition actions often
 444     access state-local data. So, it is most natural to implement these
 445     functions as members of the class the data of which the functions will
 446     operate on anyway</li>
 447   </ul>
 448
 449   <h2><a name="Limitations" id="Limitations">Limitations</a></h2>
 450
 451   <h4>Junction points</h4>
 452
 453   <p>UML junction points are not supported because arbitrarily complex guard
 454   expressions can easily be implemented with
 455   <code>custom_reaction&lt;&gt;</code>s.</p>
 456
 457   <h4>Dynamic choice points</h4>
 458
 459   <p>Currently there is no direct support for this UML element because its
 460   behavior can often be implemented with
 461   <code>custom_reaction&lt;&gt;</code>s. In rare cases this is not possible,
 462   namely when a choice point happens to be the initial state. Then, the
 463   behavior can easily be implemented as follows:</p>
 464   <pre>
 465 struct make_choice : sc::event&lt; make_choice &gt; {};
 466
 467 // universal choice point base class template
 468 template&lt; class MostDerived, class Context &gt;
 469 struct choice_point : sc::state&lt; MostDerived, Context &gt;
 470 {
 471   typedef sc::state&lt; MostDerived, Context &gt; base_type;
 472   typedef typename base_type::my_context my_context;
 473   typedef choice_point my_base;
 474
 475   choice_point( my_context ctx ) : base_type( ctx )
 476   {
 477     this-&gt;post_event( boost::intrusive_ptr&lt; make_choice &gt;(
 478       new make_choice() ) );
 479   }
 480 };
 481
 482 // ...
 483
 484 struct MyChoicePoint;
 485 struct Machine : sc::state_machine&lt; Machine, MyChoicePoint &gt; {};
 486
 487 struct Dest1 : sc::simple_state&lt; Dest1, Machine &gt; {};
 488 struct Dest2 : sc::simple_state&lt; Dest2, Machine &gt; {};
 489 struct Dest3 : sc::simple_state&lt; Dest3, Machine &gt; {};
 490
 491 struct MyChoicePoint : choice_point&lt; MyChoicePoint, Machine &gt;
 492 {
 493   MyChoicePoint( my_context ctx ) : my_base( ctx ) {}
 494
 495   sc::result react( const make_choice &amp; )
 496   {
 497     if ( /* ... */ )
 498     {
 499       return transit&lt; Dest1 &gt;();
 500     }
 501     else if ( /* ... */ )
 502     {
 503       return transit&lt; Dest2 &gt;();
 504     }
 505     else
 506     {
 507       return transit&lt; Dest3 &gt;();
 508     }
 509   }
 510 };
 511 </pre>
 512
 513   <p><code>choice_point&lt;&gt;</code> is not currently part of
 514   Boost.Statechart, mainly because I fear that beginners could use it in
 515   places where they would be better off with
 516   <code>custom_reaction&lt;&gt;</code>. If the demand is high enough I will
 517   add it to the library.</p>
 518
 519   <h4>Deep history of orthogonal regions</h4>
 520
 521   <p>Deep history of states with orthogonal regions is currently not
 522   supported:</p>
 523
 524   <p><img alt="DeepHistoryLimitation1" src="DeepHistoryLimitation1.gif"
 525   border="0" width="331" height="346"></p>
 526
 527   <p>Attempts to implement this statechart will lead to a compile-time error
 528   because B has orthogonal regions and its direct or indirect outer state
 529   contains a deep history pseudo state. In other words, a state containing a
 530   deep history pseudo state must not have any direct or indirect inner states
 531   which themselves have orthogonal regions. This limitation stems from the
 532   fact that full deep history support would be more complicated to implement
 533   and would consume more resources than the currently implemented limited
 534   deep history support. Moreover, full deep history behavior can easily be
 535   implemented with shallow history:</p>
 536
 537   <p><img alt="DeepHistoryLimitation2" src="DeepHistoryLimitation2.gif"
 538   border="0" width="332" height="347"></p>
 539
 540   <p>Of course, this only works if C, D, E or any of their direct or indirect
 541   inner states do not have orthogonal regions. If not so then this pattern
 542   has to be applied recursively.</p>
 543
 544   <h4>Synchronization (join and fork) bars</h4>
 545
 546   <p><img alt="JoinAndFork" src="JoinAndFork.gif" border="0" width="541"
 547   height="301"></p>
 548
 549   <p>Synchronization bars are not supported, that is, a transition always
 550   originates at exactly one state and always ends at exactly one state. Join
 551   bars are sometimes useful but their behavior can easily be emulated with
 552   guards. The support of fork bars would make the implementation <b>much</b>
 553   more complex and they are only needed rarely.</p>
 554
 555   <h4>Event dispatch to orthogonal regions</h4>
 556
 557   <p>The Boost.Statechart event dispatch algorithm is different to the one
 558   specified in <a href=
 559   "http://www.wisdom.weizmann.ac.il/~dharel/SCANNED.PAPERS/Statecharts.pdf">David
 560   Harel's original paper</a> and in the <a href=
 561   "http://www.omg.org/cgi-bin/doc?formal/03-03-01">UML standard</a>. Both
 562   mandate that each event is dispatched to all orthogonal regions of a state
 563   machine. Example:</p>
 564
 565   <p><img alt="EventDispatch" src="EventDispatch.gif" border="0" width="436"
 566   height="211"></p>
 567
 568   <p>Here the Harel/UML dispatch algorithm specifies that the machine must
 569   transition from (B,D) to (C,E) when an EvX event is processed. Because of
 570   the subtleties that Harel describes in chapter 7 of <a href=
 571   "http://www.wisdom.weizmann.ac.il/~dharel/SCANNED.PAPERS/Statecharts.pdf">his
 572   paper</a>, an implementation of this algorithm is not only quite complex
 573   but also much slower than the simplified version employed by
 574   Boost.Statechart, which stops searching for <a href=
 575   "definitions.html#Reaction">reactions</a> as soon as it has found one
 576   suitable for the current event. That is, had the example been implemented
 577   with this library, the machine would have transitioned
 578   non-deterministically from (B,D) to either (C,D) or (B,E). This version was
 579   chosen because, in my experience, in real-world machines different
 580   orthogonal regions often do not specify transitions for the same events.
 581   For the rare cases when they do, the UML behavior can easily be emulated as
 582   follows:</p>
 583
 584   <p><img alt="SimpleEventDispatch" src="SimpleEventDispatch.gif" border="0"
 585   width="466" height="226"></p>
 586
 587   <h4>Transitions across orthogonal regions</h4>
 588
 589   <p><img alt="TransAcrossOrthRegions" src="TransAcrossOrthRegions.gif"
 590   border="0" width="226" height="271"></p>
 591
 592   <p>Transitions across orthogonal regions are currently flagged with an
 593   error at compile time (the UML specifications explicitly allow them while
 594   Harel does not mention them at all). I decided to not support them because
 595   I have erroneously tried to implement such a transition several times but
 596   have never come across a situation where it would make any sense. If you
 597   need to make such transitions, please do let me know!</p>
 598   <hr>
 599
 600   <p><a href="http://validator.w3.org/check?uri=referer"><img border="0" src=
 601   "../../../doc/images/valid-html401.png" alt="Valid HTML 4.01 Transitional"
 602   height="31" width="88"></a></p>
 603
 604   <p>Revised
 605   <!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %B, %Y" startspan -->03 December, 2006<!--webbot bot="Timestamp" endspan i-checksum="38512" --></p>
 606
 607   <p><i>Copyright &copy; 2003-<!--webbot bot="Timestamp" s-type="EDITED" s-format="%Y" startspan -->2006<!--webbot bot="Timestamp" endspan i-checksum="770" -->
 608   <a href="contact.html">Andreas Huber D&ouml;nni</a></i></p>
 609
 610   <p><i>Distributed under the Boost Software License, Version 1.0. (See
 611   accompanying file <a href="../../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or
 612   copy at <a href=
 613   "http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)</i></p>
 614 </body>
 615 </html>