Revisión | e388f6aa409fc1812e0eea779395d9e974959389 (tree) |
---|---|
Tiempo | 2022-06-03 23:20:38 |
Autor | Albert Mietus < albert AT mietus DOT nl > |
Commiter | Albert Mietus < albert AT mietus DOT nl > |
FSMs-are-needed is more-or-less done (still in DRAFT)
@@ -2,11 +2,11 @@ | ||
2 | 2 | |
3 | 3 | .. _FSMs-are-needed: |
4 | 4 | |
5 | -======================= | |
6 | -FSMs are needed (DRAFT) | |
7 | -======================= | |
5 | +=============== | |
6 | +FSMs are needed | |
7 | +=============== | |
8 | 8 | |
9 | -.. post:: 2022/05/28 | |
9 | +.. post:: 2022/06/04 | |
10 | 10 | :category: Castle, Usage |
11 | 11 | :tags: Castle, FSM |
12 | 12 |
@@ -132,14 +132,17 @@ | ||
132 | 132 | Again, it’s main use is to make the “FSM-table” shorter -- albeit one has to add those :math:`\epsilon`\-rules into the |
133 | 133 | table! |
134 | 134 | |
135 | +A curious transition is the “`instantly` :math:`\epsilon`\-transition”; its needs no input -- and so (when used) the FSM_ | |
136 | +becomes a NFA_. But when this is the only ``rule`` for a ``state``; it does not make a FSM_ non-deterministic and is easy | |
137 | +to implement in software: :code:`when state==C: { state:=N; act_appropriate(); }`. This is often easier then removing | |
138 | +that state and combining the actions (one step back in all paths). | |
139 | + | |
135 | 140 | More energetic FSMs |
136 | 141 | ******************* |
137 | 142 | |
138 | -As described above, a non-deterministic NFA_ has more expression-power then a deterministic FSM_ and can be converted | |
139 | -into a deterministic FSM autom statechart automatically . There are more *new* concepts that help developers to model a | |
140 | -FSM_ and make there live easier. | |
141 | -|BR| | |
142 | -Again, we mention a few and link to more theory. | |
143 | +As described above a non-deterministic NFA_ has more expression-power then a deterministic FSM_ and can be converted | |
144 | +into a deterministic FSM automatically. This makes designing a FSM more easy. Likewise, there are more relative *new* | |
145 | +know-how to make the job of the (SW) developers easy. We mention a few and link to more theory. | |
143 | 146 | |
144 | 147 | Statecharts |
145 | 148 | =========== |
@@ -153,21 +156,98 @@ | ||
153 | 156 | Hierarchically superstates |
154 | 157 | -------------------------- |
155 | 158 | |
156 | -When we study (or define) a system we typically start with a few “main statuses”: the system can be ‘off’, ‘working’ | |
157 | -‘halted’ or ‘in-error’, by example. And we change mode with a few event as *TurnOn* *TurnOff*, and *InteralError*. The | |
158 | -‘off’-state is quite clear, but how about ‘on’? And perhaps the are a few steps between ‘off’ and ‘on’ .. | |
159 | +When we study (or define) a system we typically start with a few “main statuses”: the system can be :const:`off`, | |
160 | +:const:`working` :const:`halted` or :const:`in-error`, by example. And we change mode with a few event as *TurnOn* | |
161 | +*TurnOff*, and *InteralError*. The ‘off’-state is quite clear, but how about ‘on’? And perhaps the are a few steps | |
162 | +between :const:`off` and :const:`on`. | |
163 | +|BR| | |
164 | +We can solve this by adding more ``states`` In almost all of those of those ``states``, an event as *TurnOff* can be | |
165 | +expected, and in those cases it should result in :const:`off` --as before. | |
159 | 166 | |
167 | +This does nog make the FSM_ easier to design nor maintain! Wouldn't it be great to a kind generic “on-state” with one | |
168 | +generic *TurnOff* event? And have kind of sub-state of “on-state” that can implement the details? | |
169 | +|BR| | |
170 | +With hierarchically superstates this is possible. One groups a set of states together and call that group a | |
171 | +superstate. One even repeat that process, and add higher-level group -- or most developers prefer: zoom in and create | |
172 | +“sub” states within a state. | |
173 | + | |
174 | +So the :const:`on` state is kind of split in to :const:`booting`, :const:`warming-up` and :const:`operational`. And | |
175 | +:const:`operational` contains :const:`do-prog_1`, :const:`do-prog_2`, :const:`do-prog_3`, ect. And in all cases the | |
176 | +event *TurnOff* will turn-off the system -- but you only need to add one rule! | |
160 | 177 | |
161 | 178 | |
162 | 179 | Concurent states (Orthogonal regions) |
163 | 180 | -------------------------------------- |
164 | 181 | |
165 | -XXXX | |
182 | +Concurent states are more complex as super/subs-states. It are kind of local states are active | |
183 | +*simultaneously*. `Wikipedia <https://en.wikipedia.org/wiki/UML_state_machine#Orthogonal_regions>`__ has a nice example | |
184 | +with the num-lock and caps-lock key: both change state -- one to select capital on/of, and one to prefer arrow over | |
185 | +number -- but the are independent and concurent. | |
166 | 186 | |
167 | -Castle: | |
168 | -********* | |
187 | +All kind of actions | |
188 | +------------------- | |
169 | 189 | |
170 | -XXX | |
190 | +For a SW-designer the main difference between a Moore_ and a Mealy_ is where to put actions, as described above. But why | |
191 | +choose? In software it possible to use both Mealy_ actions (‘on’ the transition) as well as Moore_ actions (‘in’ a | |
192 | +state). And we can even use ‘Entry’ and ‘Leave’ (or *exit* -- but that has the same 1-character abbreviation). | |
193 | + | |
194 | +When using nested-stated we can define all of those kind-of actions on all levels. `David Harel`_ was so kind to define | |
195 | +the sematics. Such that we now agree on the order in which the ``rules`` and ``actions`` should be executed, when many | |
196 | +are valid. The result is quite simple: see UML-FSM_ for the “transition execution sequence”. | |
197 | + | |
198 | + | |
199 | +Castle: Build-in FSM syntax | |
200 | +*************************** | |
201 | + | |
202 | +.. use:: Castle has generic FSM syntax build-in | |
203 | + :ID: U_FSM_Syntax | |
204 | + | |
205 | + In Castle one can defines FSM directly in code. | |
206 | + | |
207 | + As argued above FSMs and the state (design) pattern are wildly used and there a no excuses to not support that in a | |
208 | + modern programming-language. Castle will have syntax this | |
209 | + | |
210 | + For the same reason, there is no need to restrict the syntax to one kind of FSM_ (including the NFA), or prefer one | |
211 | + kind of actions above others. Castle will have syntax support for “all” options (unless this conflicts with other | |
212 | + language-rules). | |
213 | + | |
214 | + .. tip:: non deterministic rules are not excluded | |
215 | + | |
216 | + Having syntax support for non-deterministic NFA_ rules does not imply the “compiler” will resolves all conflicts | |
217 | + (see e.g. [#converted_actions]). But those potential conflicts will not restrict the Castle syntax. | |
218 | + | |
219 | + Compare this by “devision by zero”. Everybody know that isn’t possible, but no language (syntax) will disallow | |
220 | + it. But a compiler may warn for it. | |
221 | + |BR| | |
222 | + Castle has the same approach: the language/syntax allow “the generic case”. The SW-developers are responsible to | |
223 | + define a sound FSM. And Castle will support her/him by doing trivial transformations, and giving errors/warnings | |
224 | + when they cant’ be resolved | |
225 | + | |
226 | +.. use:: Castle supports NFA_ and UML-FSM_ extensions | |
227 | + :ID: U_FSM_extensions | |
228 | + :links: U_FSM_Syntax | |
229 | + | |
230 | + To clarify :need:`U_FSM_Syntax` even more. | |
231 | + | |
232 | + Castle will support: | |
233 | + | |
234 | + #. non-deterministic rules | |
235 | + #. Epsilon transitions | |
236 | + #. Instantly (:math:`/epsilon/`) transitions | |
237 | + #. Hierarchically superstates (or sub-states) | |
238 | + #. Concurent states (Orthogonal ones) | |
239 | + #. Moore_ and Mealy_ transitions | |
240 | + #. Entry and Leave transitions | |
241 | + | |
242 | + This list is not restrictive, and may be extended | |
243 | + | |
244 | +.. tip:: Once ... | |
245 | + | |
246 | + Having syntax-support is meaningless without the proper compile/run-time support. That however is *not* demand is | |
247 | + thise needs. One may expect that early implementations of the Castle-compiler can “parse” all syntax, but ony really | |
248 | + compiler (and/or optimise) the easier parts of NFA_. | |
249 | + |BR| | |
250 | + Once, all will be fully supported! | |
171 | 251 | |
172 | 252 | ---------- |
173 | 253 |
@@ -177,7 +257,7 @@ | ||
177 | 257 | The OO-variants are not shown, as even this 3 by 3 FSM will result is many classes, files an even more lines-of code |
178 | 258 | than the trivial one. When the FSM_ becomes bigger, the OO variants have some advantages; as it scales a bit |
179 | 259 | better. But scatters the FSM-behaviour over many files, and so does hardly solves the problem of understandability. |
180 | - | |
260 | + | |
181 | 261 | .. [#converted_actions] |
182 | 262 | There is still a “small” practical issue we have to consider: **converted-actions**. When converting we got more and |
183 | 263 | other states and transition. Most algorithm kind-of ignore the actions; but we can’t. We have to convert them to; |
@@ -199,12 +279,7 @@ | ||
199 | 279 | day). |
200 | 280 | |BR| |
201 | 281 | There is no way, we can automatically convert that “optimised” NFA_ into a practical one. Therefore we need |
202 | - human-creativity. | |
203 | - | |
204 | - | |
205 | - | |
206 | - | |
207 | - | |
282 | + human-creativity. | |
208 | 283 | |
209 | 284 | |
210 | 285 | .. _FSM: https://en.wikipedia.org/wiki/Finite-state_machine |
@@ -52,8 +52,8 @@ | ||
52 | 52 | A --> B_or_C : Ea |
53 | 53 | B_or_C --> B : Eb /\n act_1() |
54 | 54 | B_or_C --> C : Ec /\n act_2() |
55 | - B --> D : ~~directly~~ /\n act_3() | |
56 | - C --> D : ~~directly~~ /\n act_4() | |
55 | + B --> D : ~~instantly~~ /\n act_3() | |
56 | + C --> D : ~~instantly~~ /\n act_4() | |
57 | 57 | |
58 | 58 | note left of B_or_C #green |
59 | 59 | Input **Ea** always results |
@@ -66,7 +66,7 @@ | ||
66 | 66 | the second input |
67 | 67 | end note |
68 | 68 | note left of D |
69 | - ~~directly~~ is kind of | |
69 | + ~~instantly~~ is kind of | |
70 | 70 | an epsilon transition, |
71 | 71 | but easy to implement |
72 | 72 | end note |