Miro Samek, Ph.D.Miro Samek, Ph.D.quantum programmingCopyright © 2003 by Miro Samek. All Rights Reserved.Hierarchical State Machines Hierarchical State Machines ——a Fundamentally Important a Fundamentally Important Way of DesignWay of DesignAssociation Association of C & C++ Users,of C & C++ Users,March 11, 2003March 11, 20032quantum programmingCopyright © 2003 by Miro Samek. All Rights Reserved.About the SpeakerAbout the SpeakerMiro Samek is the author of Practical Statecharts in C/C++: Quantum Programming for Embedded Systems (CMP Books, 2002) and a contributing editor to C/C++ Users Journal. He is the lead software architect at IntegriNautics Corporation (Menlo Park, CA) and a consultant to industry. He previously worked at GE Medical Systems, where he has developed safety-critical, real-time software for diagnostic imaging X-ray machines. Miro earned his Ph.D. in nuclear physics at GSI (Darmstadt, Germany) where he conducted heavy-ion experiments. Miro welcomes contact and can be reached [email protected] programmingCopyright © 2003 by Miro Samek. All Rights Reserved.ObjectivesObjectives•Introduce Hierarchical State Machines (HSMs)•Describe a particularly small and highly maintainable implementation of HSMs in C•Show how a good HSM implementation can lead to a paradigm shift in programming reactive systems•Demonstrate that HSMs are a fundamentally important way of design — not the use of a particular CASE tool.•90 minutes maximum.•Discussion.4quantum programmingCopyright © 2003 by Miro Samek. All Rights Reserved.The Challenge of EventThe Challenge of Event--Driven SystemsDriven Systems•Almost all computers today are event-driven systems •The main programming challenge is to quickly pick and execute the right code in reaction to an event•The reaction depends both on the nature of the event and on the current context, that is, the sequence of past events in which the system was involved•Traditional “bottom up” approaches represent the context ambiguously by a multitude of variables and flags, which results in code riddled with a disproportionate number of convoluted conditional branches (if-else or switch-case statements in C/C++)5quantum programmingCopyright © 2003 by Miro Samek. All Rights Reserved.The Significance of “State”The Significance of “State”•State machines make the response to an event explicitly dependent on both the nature of the event and the context of the system (state) •State captures the relevant aspects of the system’s history very efficiently'A''a'EXAMPLE: a character code generated by a keyboard depends if the Shift has been depressed, but not on how many and which specific characters have been typed previously. A keyboard can be said to be in the “shifted” state or in the “default” state. •A state can abstract away all possible (but irrelevant) event sequences and capture only the relevant ones6quantum programmingCopyright © 2003 by Miro Samek. All Rights Reserved.State Machines State Machines ——Coding PerspectiveCoding Perspective•When properly represented in software, a state machine radically reduces the number of different paths though the code and simplifies the conditions tested at each branching point•In all but the most basic coding technique (e.g., the switchstatement) even the explicit testing of the “state variable” disappears as a conditional statement and is replaced by a table lookup or a function-pointer dereferencing•This aspect is similar to the effect of polymorphism in OOP, which eliminates branching based on object's class7quantum programmingCopyright © 2003 by Miro Samek. All Rights Reserved.Visual RepresentationVisual Representation——State DiagramsState Diagrams•State machines have a compelling and intuitive graphical representation in form of state diagrams•State diagrams are directed graphs in which nodes denote states and connectors denote transitions•The UML provides a standard notation and precise, rich semantics for state machinesANY_KEY/ send_upper_case_code();shiftedANY_KEY/send_lower_case_code();defaultSHIFT_DOWN SHIFT_UPtransitioninitialtransitioninternaltransitionstateaction(s)8quantum programmingCopyright © 2003 by Miro Samek. All Rights Reserved.The Limitations of Traditional The Limitations of Traditional FSMsFSMs•The traditional FSMs tend to become unmanageable, even for moderately involved reactive systems (the “state-explosion” phenomenon)•In practice, many states are similar, but classical FSMs have no means of capturing such commonalities and require repeating the same behavior in many states•What’s missing in FSMs is a mechanism of factoring out the common behavior in order to reuse it across many states9quantum programmingCopyright © 2003 by Miro Samek. All Rights Reserved.Introducing StatechartsIntroducing Statecharts•Statecharts (invented by David Harel in the 1980’s, [Harel 87]) provide exactly what’s been missing in classical FSMs: a way of capturing the common behavior in order to reuse it across many states•The most important innovation of statecharts is the introduction of hierarchically nested states•The UML 1.4 state machines [OMG 01] are an object-based variant of Harel statecharts [Harel 87]. They incorporate several concepts similar to those defined in ROOMcharts, a variant of statechart defined in the ROOM modeling language [Selic+ 94].10quantum programmingCopyright © 2003 by Miro Samek. All Rights Reserved.The Semantics of State NestingThe Semantics of State Nesting•If a system is in the nested state s11 (called substate), it also (implicitly) is in the surrounding state s1 (called superstate)s1s11superstatesubstate•Any event is first handled in the context of substate s11, but all unhandled events are automatically passed over to the next level of nesting (s1superstate)•The substates need only define the differences from the superstates, and otherwise can easily share (reuse) behavior defined in higher levels of nesting11quantum programmingCopyright © 2003 by Miro Samek. All Rights Reserved.Programming By DifferenceProgramming By Difference•State nesting lets you define a new state rapidly in terms of anold one, by reusing the behavior from the parent state•State nesting allows new states to be specified by differencerather than created from scratch each time•State nesting lets you get new behavior almost for free, reusing most of what is common from the