Practical Statecharts in C/C++: Quantum Programming for Embedded Systems
Table of Contents
Practical Statecharts in C/C++−Quantum Programming for Embedded Systems......................................1
Preface..................................................................................................................................................................3
Mission.....................................................................................................................................................3
Why Quantum Programming?.................................................................................................................4
QP versus XP and Other Agile Methodologies.......................................................................................5
Audience..................................................................................................................................................6
Guide to Readers......................................................................................................................................7
Acknowledgments....................................................................................................................................8
Part I: Statecharts.............................................................................................................................................10
Chapter List............................................................................................................................................10
Chapter 1: Whirlwind Tour of Quantum Programming..............................................................................11
Overview................................................................................................................................................11
1.1 The Ultimate Hook — Anatomy of a GUI Application..................................................................11
1.2 A Better Way of Programming — A Calculator That Works.........................................................13
1.2.1 Shortcomings of the Traditional Event–Action Paradigm.....................................................13
1.2.2 Calculator Statechart..............................................................................................................14
1.2.3 Integration with Windows......................................................................................................17
1.2.4 State Handler Methods...........................................................................................................18
1.3 Object−Oriented Analogy................................................................................................................20
1.3.1 State Hierarchy and Class Taxonomy....................................................................................20
1.3.2 Entering/Exiting States and Instantiating/Finalizing Classes.................................................21
1.3.3 Programming−by−Difference................................................................................................21
1.3.4 Behavioral Inheritance as a Fundamental Meta−Pattern........................................................21
1.3.5 State Patterns..........................................................................................................................21
1.3.6 Refactoring State Models.......................................................................................................22
1.3.7 Beyond Object−Oriented Programming.................................................................................22
1.4 Quantum Analogy............................................................................................................................23
1.5 Summary..........................................................................................................................................23
Chapter 2: A Crash Course in Statecharts.....................................................................................................25
Overview................................................................................................................................................25
2.1 The Essence of Finite State Machines.............................................................................................25
2.1.1 States......................................................................................................................................26
2.1.2 Extended States......................................................................................................................26
2.1.3 Guards....................................................................................................................................27
2.1.4 Events.....................................................................................................................................27
2.1.5 Actions and Transitions..........................................................................................................28
2.1.6 Mealy and Moore Automata...................................................................................................28
2.1.7 Execution Model — Run−to−Completion Step.....................................................................28
2.1.8 State Transition Diagrams......................................................................................................29
2.2 The Essence of UML Statecharts.....................................................................................................30
2.2.1 Hierarchical States..................................................................................................................30
2.2.2 Behavioral Inheritance...........................................................................................................31
2.2.3 Orthogonal Regions................................................................................................................33
2.2.4 Entry and Exit Actions...........................................................................................................34
Practical Statecharts in C/C++: Quantum Programming for Embedded Systems
i
Table of Contents
Chapter 2: A Crash Course in Statecharts
2.2.5 Transition Execution Sequence..............................................................................................35
2.2.6 Internal Transitions.................................................................................................................36
2.2.7 Pseudostates............................................................................................................................36
2.2.8 Refined Event Handling.........................................................................................................37
2.2.9 Semantics versus Notation.....................................................................................................37
2.2.10 Statecharts versus Flowcharts..............................................................................................38
2.2.11 Statecharts and Automatic Code Synthesis..........................................................................38
2.3 Examples of State Models...............................................................................................................39
2.3.1 Quantum Calculator...............................................................................................................40
2.3.2 Hydrogen Atom......................................................................................................................42
2.4 Summary..........................................................................................................................................45
Chapter 3: Standard State Machine Implementations..................................................................................47
Overview................................................................................................................................................47
3.1 State Machine Interface...................................................................................................................47
3.2 Nested switch Statement..................................................................................................................48
3.3 State Table.......................................................................................................................................51
3.4 State Design Pattern.........................................................................................................................54
3.5 Optimal FSM Implementation.........................................................................................................57
3.6 State Machines and C++ Exception Handling.................................................................................60
3.7 Role of Pointer−to−Member Functions...........................................................................................60
3.8 Implementing Guards, Junctions, and Choice Points......................................................................62
3.9 Implementing Entry and Exit Actions.............................................................................................63
3.10 Dealing with State Hierarchy.........................................................................................................63
3.11 Summary........................................................................................................................................64
Chapter 4: Implementing Behavioral Inheritance.........................................................................................66
Overview................................................................................................................................................66
4.1 Structure...........................................................................................................................................67
4.1.1 Events.....................................................................................................................................69
4.1.2 States......................................................................................................................................71
4.1.3 Entry/Exit Actions and Initial Transitions..............................................................................72
4.1.4 State Transitions.....................................................................................................................73
4.1.5 The top State and the initial Pseudostate................................................................................74
4.2 An Annotated Example....................................................................................................................75
4.2.1 Enumerating Signals and Subclassing QHsm........................................................................76
4.2.2 Defining State Handler Methods............................................................................................77
4.2.3 Initialization and Dispatching Events.....................................................................................79
4.2.4 Test Run.................................................................................................................................80
4.3 Heuristics and Idioms......................................................................................................................81
4.3.1 Structuring State Machine Code.............................................................................................81
4.3.2 Choosing the Right Signal Granularity..................................................................................83
4.3.3 UML−Compliant HSMs.........................................................................................................83
4.4 The Event Processor........................................................................................................................85
4.4.1 Initializing the State Machine: The init() Method..................................................................85
4.4.2 Dispatching Events: The dispatch() Method..........................................................................86
4.4.3 Static and Dynamic State Transitions: Macros Q_TRAN() and Q_TRAN_DYN()..............87
Practical Statecharts in C/C++: Quantum Programming for Embedded Systems
ii
Table of Contents
Chapter 4: Implementing Behavioral Inheritance
4.4.4 Dynamic State Transition: The tran() Method.......................................................................88
4.4.5 Static State Transition: The tranStat() Method and the Tran Class........................................92
4.4.6 Initializing the QTran Object: The tranSetup() Method.........................................................93
4.5 C Implementation............................................................................................................................95
4.5.1 QHsm Class in "C+"...............................................................................................................96
4.5.2 QHsm Constructor and Destructor.........................................................................................96
4.5.3 State Handler Methods and Pointer−to−Member Functions..................................................97
4.5.4 QHsm Methods.......................................................................................................................97
4.5.5 Statechart Example in C.........................................................................................................98
4.6 Caveats.............................................................................................................................................99
Chapter 5: State Patterns...............................................................................................................................102
Overview..............................................................................................................................................102
5.1 Ultimate Hook................................................................................................................................103
5.1.1 Intent.....................................................................................................................................103
5.1.2 Problem................................................................................................................................103
5.1.3 Solution................................................................................................................................103
5.1.4 Sample Code.........................................................................................................................104
5.1.5 Consequences.......................................................................................................................106
5.2 Reminder........................................................................................................................................106
5.2.1 Intent.....................................................................................................................................106
5.2.2 Problem................................................................................................................................107
5.2.3 Solution................................................................................................................................107
5.2.4 Sample Code.........................................................................................................................107
5.2.5 Consequences.......................................................................................................................110
5.3 Deferred Event...............................................................................................................................111
5.3.1 Intent.....................................................................................................................................111
5.3.2 Problem................................................................................................................................111
5.3.3 Solution................................................................................................................................111
5.3.4 Sample Code.........................................................................................................................112
5.3.5 Consequences.......................................................................................................................114
5.4 Orthogonal Component..................................................................................................................115
5.4.1 Intent.....................................................................................................................................115
5.4.2 Problem................................................................................................................................115
5.4.3 Solution................................................................................................................................115
5.4.4 Sample Code.........................................................................................................................117
5.4.5 Consequences.......................................................................................................................121
5.5 Transition to History......................................................................................................................122
5.5.1 Intent.....................................................................................................................................122
5.5.2 Problem................................................................................................................................123
5.5.3 Solution................................................................................................................................123
5.5.4 Sample Code.........................................................................................................................123
5.5.5 Consequences.......................................................................................................................125
5.6 Summary........................................................................................................................................126
Practical Statecharts in C/C++: Quantum Programming for Embedded Systems
iii
Table of Contents
Chapter 6: Inheriting State Models...............................................................................................................127
Overview..............................................................................................................................................127
6.1 Statechart Refinement Example in C++........................................................................................128
6.1.1 How Does It Work?..............................................................................................................131
6.2 Statechart Refinement Example in C.............................................................................................134
6.2.1 Preparing a "C+" State Machine for Polymorphism............................................................134
6.2.2 Inheriting and Refining the "C+" State Machine.................................................................135
6.3 Caveats...........................................................................................................................................137
6.3.1 Static versus Dynamic State Transitions..............................................................................137
6.3.2 Multiple Inheritance.............................................................................................................137
6.3.3 Heuristics for Inheriting and Refining Statecharts...............................................................138
6.4 Summary........................................................................................................................................140
Part II: Quantum Framework.......................................................................................................................142
Chapter List..........................................................................................................................................142
Chapter 7: Introducing the Quantum Framework......................................................................................143
Overview..............................................................................................................................................143
7.1 Conventional Approach to Multithreading....................................................................................144
7.1.1 Dining Philosophers − Conventional Approach...................................................................144
7.1.2 Therac−25 Story...................................................................................................................147
7.2 Computing Model of the QF..........................................................................................................148
7.2.1 Active Object−Based Multithreading...................................................................................149
7.2.2 Quantum Analogy................................................................................................................150
7.2.3 Publish−Subscribe Event Delivery.......................................................................................151
7.2.4 General Structure..................................................................................................................152
7.2.5 Dining Philosophers Revisited.............................................................................................152
7.3 Roles of the QF..............................................................................................................................154
7.3.1 Source of Conceptual Integrity.............................................................................................155
7.3.2 RTOS Abstraction Layer......................................................................................................155
7.3.3 Software Bus........................................................................................................................156
7.3.4 Platform for Highly Parallel Computing..............................................................................157
7.3.5 Basis for Automatic Code Generation..................................................................................158
7.4 Summary........................................................................................................................................159
Chapter 8: Design of the Quantum Framework..........................................................................................161
Overview..............................................................................................................................................161
8.1 Embedded Real−Time Systems.....................................................................................................161
8.2 Handling Errors and Exceptional Conditions................................................................................163
8.2.1 Design by Contract...............................................................................................................164
8.2.2 State−Based Handling of Exceptional Conditions...............................................................166
8.3 Memory Management....................................................................................................................168
8.3.1 A Heap of Problems.............................................................................................................168
8.3.2 Memory Management in the QF..........................................................................................170
8.4 Mutual Exclusion and Blocking....................................................................................................171
8.4.1 Perils of Mutual Exclusion...................................................................................................172
8.4.2 Blocking in Active Object−Based Systems.........................................................................174
8.5 Passing Events...............................................................................................................................175
Practical Statecharts in C/C++: Quantum Programming for Embedded Systems
iv
