Révision | de487fa932d9abaa2ab6a68c11d6c66483d57d03 (tree) |
---|---|
l'heure | 2022-10-02 21:51:50 |
Auteur | Albert Mietus < albert AT mietus DOT nl > |
Commiter | Albert Mietus < albert AT mietus DOT nl > |
~Finished 8.ConcurrentComputingConcepts (CCC)
@@ -131,13 +131,16 @@ | ||
131 | 131 | ready to use; not more manual scanning and parsing. And when the file-structure is slightly updated, you just add a few |
132 | 132 | details to the grammer. |
133 | 133 | |
134 | -Castle, has it build-in | |
135 | -======================= | |
134 | +Castle has it build-in | |
135 | +====================== | |
136 | + | |
137 | +Grammars makes reading text easy. Define the structure, call the “main rule” and use the values. Castle makes that | |
138 | +simple! | |
136 | 139 | |
137 | 140 | .. use:: Castle has build-in grammers support |
138 | 141 | :ID: U_Grammers |
139 | 142 | |
140 | - In Castle one can define a grammer, directly into the source-code; the syntax supports that. As shown above. | |
143 | + In Castle one can define a grammer directly into the source-code; as :ref:`grammmar-code`! | |
141 | 144 | |
142 | 145 | And, like many other details, the language is hiding the nasty details of parsing-strategies. There is no need to |
143 | 146 | generating, compiling, and use that code, with external tools. All that clutter is gone. |
@@ -152,11 +155,10 @@ | ||
152 | 155 | |
153 | 156 | To use the grammar you simply call one of those rules as a function: pass the input (string) and it will return a |
154 | 157 | (generic) tree-structure. |
158 | +When you simple like to verify the syntax is correct: use the tree as a boolean: when it not-empty the input is valid. | |
155 | 159 | |BR| |
156 | -When you simple like to verify the syntax is correct: use the tree as a boolean: when it not-empty the input is valid. | |
160 | +Typically however, you traverse that tree, like you do in many situations. | |
157 | 161 | |
158 | -But typically you proces/use that tree: like you do in many situations. Read the configuration values, walk over the | |
159 | -tree, of traverse it as-if it is a DOM. You can even use Castle’s :ref:`matching-statements` to simply that. | |
160 | - | |
161 | -Grammars makes reading text easy. Define the structure, call the “main rule” and use the values. Castle makes that simple! | |
162 | - | |
162 | +To read that early configuration: parse the file and walk over the tree. Or use it “ala a DOM” by using Castle’s | |
163 | +:ref:`matching-statements` to simply. Curious on how that works: continue reading in :ref:`grammmar-code`. | |
164 | +Or skip to “Why there are :ref:`G2C-actions`”. |
@@ -178,12 +178,12 @@ | ||
178 | 178 | event *TurnOff* will turn-off the system -- but you only need to add one rule! |
179 | 179 | |
180 | 180 | |
181 | -Concurent states (Orthogonal regions) | |
182 | --------------------------------------- | |
183 | -Concurent states are more complex as super/subs-states. It are kind of local states are active | |
181 | +Concurrent states (Orthogonal regions) | |
182 | +--------------------------------------- | |
183 | +Concurrent states are more complex as super/subs-states. It are kind of local states are active | |
184 | 184 | *simultaneously*. `Wikipedia <https://en.wikipedia.org/wiki/UML_state_machine#Orthogonal_regions>`__ has a nice example |
185 | 185 | with the num-lock and caps-lock key: both change ``state`` -- one to select capital on/of, and one to prefer arrow over |
186 | -number -- but those ``states`` are *independent* and **concurent**. | |
186 | +number -- but those ``states`` are *independent* and **concurrent**. | |
187 | 187 | |
188 | 188 | Again, the advantage is it makes the “FSM table” shorter and better to maintain. |
189 | 189 |
@@ -242,7 +242,7 @@ | ||
242 | 242 | #. Epsilon transitions |
243 | 243 | #. *‘Instantly’* transitions (see above: a special kind of :math:`\epsilon`\-transition) |
244 | 244 | #. Hierarchically superstates (or sub-states) |
245 | - #. Concurent states (Orthogonal regions) | |
245 | + #. Concurrent states (Orthogonal regions) | |
246 | 246 | #. Moore_ and Mealy_ transitions |
247 | 247 | #. Entry and Leave transitions |
248 | 248 |
@@ -0,0 +1,311 @@ | ||
1 | +.. include:: /std/localtoc.irst | |
2 | + | |
3 | +.. _BusyCores: | |
4 | + | |
5 | +====================== | |
6 | +Keep those cores busy! | |
7 | +====================== | |
8 | + | |
9 | +.. post:: 2022/07/06 | |
10 | + :category: Castle, Usage | |
11 | + :tags: Castle, Concurrency | |
12 | + | |
13 | + I always claim that most computers will have 1024 or more cores before my retirement. And that most embedded systems | |
14 | + will have even more, a decade later. However, it’s not easy to write technical software for those “massive-parallel | |
15 | + embedded computers”, not with the current languages -- simple because a developer has to put in too many details. | |
16 | + Accordingly, the “best, ever” programming language should facilitate and support “natural concurrency”. | |
17 | + | |
18 | + In Castle, you can easily write code that can run efficiently on thousands of cores. | |
19 | + | |
20 | +Why do we get more and more cores? | |
21 | +================================== | |
22 | + | |
23 | +Moore `observed already in 1965 <https://en.wikipedia.org/wiki/Moore's_law>`_ that the number of transistors on a chip | |
24 | +doubles every 2 years. That made memory cheaper and computers faster. For years we have seen that: CPUs have grown from | |
25 | +4-bit to 8, 16, 32, and now 64-bit; and the ‘clock-frequently’ has risen into the giga-hertz. This comes (almost) for | |
26 | +free when the *‘gate-size’ dropped* -- roughly, a ‘gate’ is the smallest “pixel” when a chip is manufactured. By | |
27 | +shrinking the gates one can put more transistors on a chip and at the same time those chips become faster and use less | |
28 | +power --this comes automatically; as you may remember from your (advanced) physics lessons. | |
29 | + | |
30 | +But there are limits: transistors can’t switch much faster than a few billion times a second. When we crossed that | |
31 | +border, just making gates smaller didn't increase the CPU’s speed. But there are other tricks; like huge caches very | |
32 | +close to (or ‘in’) the CPU. Again it made computers faster, without much work for the SW developer. | |
33 | +Another limit is the number of transistors you can utilize in a CPU (or the cache). One can double the number of | |
34 | +transistors almost without limit, but does it again double your CPU-speed? *No*, not anymore, that threshold is passed a | |
35 | +few years back. | |
36 | + | |
37 | +A new trick was needed: put more CPUs onto *one* chip. Essentially that is what Multi-Core_ does: every core is | |
38 | +fundamentally an independent CPU - but as we used that word already, we use ‘core’ for those copies. The amount of work | |
39 | +a chip can do with two cores doubles — at least potentially. Using Moore’s low, the number of cores will double be every | |
40 | +18-24 months; or 30 times more in a decade. Currently, many (mobile phone) SoCs already have more than 10 cores — when | |
41 | +counting both GPUs & CPUs. That is 300 in 10 years, and 9-thousand in 20 years! | |
42 | + | |
43 | +Programming many cores | |
44 | +====================== | |
45 | + | |
46 | +Although the promise of Multi-Core_ is an unlimited expansion of speed, it requires us to adapt our programming | |
47 | +abilities. Transitional “sequential” programs take for granted that the CPU can do only one thing at a time; at many | |
48 | +levels. With Multi-Core_ this fundamentally changed. There is no speed up when we don’t use all cores. This is not much | |
49 | +of an issue for a low number of cores; there are plenty of other/background tasks. Even ‘single threaded’ code will | |
50 | +run faster when “your core” isn’t interrupted; when those auxiliary processes can run in parallel on another core. | |
51 | + | |
52 | +When the number of cores rises this does not scale; more and more cores become idle. Now, your code has to use both | |
53 | +concurrency_ and parallelism_. But also handle Critical-Sections_, Semaphores_ (and friends) to synchronise tasks. | |
54 | + | |
55 | + | |
56 | +.. include:: BusyCores-sidebar-CPython_threads.irst | |
57 | + | |
58 | +Threading | |
59 | +--------- | |
60 | + | |
61 | +Threads_ have become popular to accomplish parallelism_ but have drawbacks too. They originated (long, long back) in | |
62 | +“real-time & embedded” programming; -- those systems didn't have an OS nor processes and used a concept that resembles | |
63 | +threads. Other computers (mostly Unix/Posix) used “processes” to run many tasks --Windows/Dos wasn't relevant; it was | |
64 | +(mostly) single-user. Mid 199x threads_ become available as “real-time extensions”; initially within a single process — | |
65 | +and so running on a single core. Al this was long before Multi-Core_ hardware was accessible, and studies started on how | |
66 | +to combine threads & processes — should the kernel handle that or not, and how to avoid overhead. This all changed with | |
67 | +Multi-Core_; need threads_ that can run in parallel on multiple cores. | |
68 | + | |
69 | +Still, it is not trivial to programming with (raw) threads. | |
70 | + | |
71 | +Bugs | |
72 | +~~~~ | |
73 | +A lot of new bugs popped up when developers started to use threads_. One had to learn about concurrency_, parallelism_, | |
74 | +and their difference. And that two threads can be intertwined in not foreseen ways; multiple threads_ can access | |
75 | +the same variable. A single line became suddenly not atomic anymore -- even a single assignment is not. | |
76 | +|BR| | |
77 | +We mastered that today, at least mostly. There are still many quizzes about that, and many do not pass the tricky | |
78 | +ones. More bothersome is that no one knows how to compose tests to verify the absents of this kind of Heisenbugs_ | |
79 | + | |
80 | +Overhead | |
81 | +~~~~~~~~ | |
82 | +Threads_ have more handicaps: it is hard to gain the speed up aiming for. Partly because threads_ themself have a lot of | |
83 | +overhead (especially to start/stop them). But it is also hard to “get” the right number of threads_. Many opinions on | |
84 | +this exist -- like one thread per core [#wrong]_ -- but hardly (or non) theory on this. | |
85 | + | |
86 | +A bigger factor is indirect overhead; especially in CPU-bound (see below) systems. Then, the outcome of a calculation in | |
87 | +one thread is routinely needed for an algorithm in another thread -- if not, why use threads? That involves sharing data [#share]_ | |
88 | + | |
89 | +Scaling | |
90 | +~~~~~~~ | |
91 | +When we get more and more cores, we need more and more concurrent task to get the speed up we like. With (raw) threads_ | |
92 | +this becomes more and more an issue. More threads_ may imply more bugs; notably hard to find Heisenbugs_. More threads_ | |
93 | +make is harder to limit the overhead. | |
94 | + | |
95 | +To summaries: Threads_ do no scale well; there is a limit to the number of threads we can manage as a | |
96 | +software-developers. So, a new “trick” is needed. | |
97 | + | |
98 | + | |
99 | +IO vs CPU Bound | |
100 | +--------------- | |
101 | + | |
102 | +Another --often overlooked, but important-- aspect is ‘how & why’ threads are used. Many applications interact with a | |
103 | +user and/or have lots of other IO. Input & output is slow compared with (the GigaHertz of) the CPU itself. The result is that | |
104 | +“the computer” has to wait on the user, on the network or disk [#SDD]_; this is called *IO-bound* | |
105 | +|BR| | |
106 | +With threads_, it’s easy to speed up IO-bound systems. Then (only) a single thread is waiting; all other threads can | |
107 | +continue. This works even on a single-core. This IO-bound aspect was (one of) the primary ambitions when introducing | |
108 | +“real-time” threads. With Multi-Core_ this scales quite well; peculiarly when most threads do about the same. As in a | |
109 | +web server for instance. | |
110 | + | |
111 | +Technical, embedded applications generally differ. They are mostly *CPU-bound*; as there is nothing to be waiting on. In | |
112 | +the extreme case, the processor is constantly busy, say doing calculations. | |
113 | +|BR| | |
114 | +Then, just adding threads will not lead to speed up; as the processor is busy anyhow; more processor power is | |
115 | +needed! Along with a gentle distribution of the work gently over the available cores. Ideally, all cores should do an | |
116 | +even part of that calculation. | |
117 | + | |
118 | +Using threads_ with CPU-bound systems is much harder. It is complicated to split the work, it’s backbreaking to allot | |
119 | +the tasks over the cores equally, and troublesome to minimize the overhead. But easy to introduce flaw ... | |
120 | +|BR| | |
121 | +The center of attraction in this blog(s) is those knotty, “mostly CPU-bound”, technical, modern-embedded systems, as | |
122 | +you already expected. | |
123 | + | |
124 | + | |
125 | +Alternatives | |
126 | +============ | |
127 | + | |
128 | +Raw threads_, as in pthreads_, are not the only option; there are contemporary alternatives. For the most part, | |
129 | +they use threads to implement a more abstract interface; to unburden developers for those technicalities. | |
130 | + | |
131 | +We introduce a few but leave the details to the next blog: the study on :ref:`ConcurrentComputingConcepts`. | |
132 | + | |
133 | +Thread-Pools | |
134 | +------------ | |
135 | + | |
136 | +Starting & stopping a thread is relatively costly; this makes them less suited for short-running tasks --then the relative | |
137 | +overhard is big. The Thread-Pool_ design pattern tackles this by creating (long-running) “worker threads” and a “task | |
138 | +queue(s)”. Running many (small) tasks in the same thread reduces the overhead. Also, the task will start (and end) | |
139 | +a bit earlier; as threads are pre-created | |
140 | + | |
141 | +.. tip:: | |
142 | + | |
143 | + I have given a “Design Workshop” on the `“ThreadPoolExecutor” | |
144 | + <http://mess.softwarebetermaken.nl/en/latest/SoftwareCompetence/DesignWorkShops/TPE/>`_, in another series, | |
145 | + Have a look when you like to learn more about this pattern. | |
146 | + | |
147 | +Some languages support this concept naturally; in others, it is more like an add-on option on threads. Besides | |
148 | +depending on the language implementation (compiler and runtime libraries), it may or *may not* have the speeding-up | |
149 | +benefit when using many cores. For example, the python “ThreadPoolExecutor” is a likable, sound example; but as | |
150 | +(C)Python can’t run multiple threads simultaneously, you will not gain a speed up on CPU-bound systems. Still, we can | |
151 | +use it as inspiration. | |
152 | + | |
153 | +The Thread-Pool_ pattern gives us a simple alternative to (raw) threads; especially when the thread-part is buried and | |
154 | +not visible to the developer. Then the programmer can focus on defining small (concurrent) tasks and the “computer” | |
155 | +can add details such as how many threads, on which core(s), and manage them. | |
156 | + | |
157 | +GCD (LibDispatch) | |
158 | +----------------- | |
159 | + | |
160 | +Grand Central Dispatch, or GCD_, is a technology invented by Apple add developed as open-source, that takes the idea of | |
161 | +Thread-Pools a step further. Therefore they added an extension to the C-language too: “blocks_” -- A kind of anonymously (unnamed), | |
162 | +inline, nested functions, that act as a closure. It sounds a bit complicated, but most developers find it easy to use | |
163 | +[#bold-on]_. | |
164 | + | |
165 | +A “block” is like a function, that can be dispatched (scheduled) for independent execution. Typical a block is | |
166 | +small --so we have lots of capability for simultaneous execution-- without introducing much overhead [#one-percent]_. | |
167 | + | |
168 | +.. seealso:: | |
169 | + | |
170 | + * The GCD “scheduler” is available as `libdispatch <https://github.com/apple/swift-corelibs-libdispatch>`_. | |
171 | + * The blocks_ extension is available for LLVM. Apparently, GCC is not supporting it (anymore). | |
172 | + | |
173 | +GCD_ also supports Objective-C, C++, and Swift. Then, the language semantics differ a bit (making it | |
174 | +easier to use); but the concept is the same: Store the “environment” (see: closure_) of the lexical scope of the nested | |
175 | +function-block in a task-object, and put them on (FIFO) queue. And have some long-running (raw, invisible) threads | |
176 | +processing those task-objects. As those tasks are isolated, running them is easy. | |
177 | +|BR| | |
178 | +The developer is hidden from the threads -- (s)he is not even aware of them! Or actually, there is just this general | |
179 | +understanding the “raw threads” are used in the background, but that is not required. Any “scheduler” will do! | |
180 | + | |
181 | + | |
182 | +.. _BC-events: | |
183 | + | |
184 | +Events (interrupts) | |
185 | +------------------- | |
186 | + | |
187 | +Events are a completely contrasting approach, avoiding threads at all. They are also known as *interrupts* for low-level | |
188 | +close-to-hardware developers. Events are primarily introduced for “Windowing programming [#Windowing]_. Up to then, a | |
189 | +program stared at ``main()``, jumping to subroutines in the order the programmers has written them. For GUIs (or | |
190 | +Windowing-application, as we called them), that was inconvenient -- the user should be in control. When “pressing a | |
191 | +button (or “Widget”) the system generated an “event”. | |
192 | +|BR| | |
193 | +The developers had to write “event-handlers” --functions, but with a predefined signature-- and register each, passing | |
194 | +the kind of event(s) they should active them. This was new, completely different (and strange, back then). A function got | |
195 | +names as ``OnButton_XXX_Press(event)``, and where called “automagically”. | |
196 | + | |
197 | +You can imagen the implementation now: a queue and an event-loop. But this concept shows something else too, as a | |
198 | +side-effect: (virtual) concurrent programming. | |
199 | + | |
200 | +Event- (handlers) are small “task alike” independent routines, that become active when needed: when some input-data becomes | |
201 | +available. All those “tasks” are atomic (short living) and where the controll-flow is not specified. It appears as if | |
202 | +all those small, little task can run concurrent -- as the user can quickly trigger many event “at once”. In modern | |
203 | +systems the results of the events emerge even “asynchronous” -- then we often call it “reactive”. | |
204 | +|BR| | |
205 | +This really happens for “hardware interrupts”. Those interrupts truly are asynchronous of the “main code”. And one has | |
206 | +to handle them immediacy (or the input is gone, and a result will be wrong!). An “interrupt-handler” is very alike an | |
207 | +event-loop-handler; albeit at another scale. | |
208 | + | |
209 | +Both variants shows in there function-names how many developers would like to deal with asynchronous, concurrent “tasks”: | |
210 | +:samp:`On {EventType} Run {{Code}}`. | |
211 | + | |
212 | + | |
213 | +Castle activates all cores | |
214 | +========================== | |
215 | + | |
216 | +An “*ideal language*” should make it easy to distribute the load over many processors. That should come | |
217 | +automatically; without the developer has to put a load of effort in. That is also one of the aspect :ref:`CC` is | |
218 | +enabling --and as Castle supports :ref:`CC` (and is the best language, ever -- so quite close to “ideal”)-- the language | |
219 | +should be designed to enable this. | |
220 | + | |
221 | +.. use:: In Castle is easy to use thousands of cores | |
222 | + :ID: U_ManyCore | |
223 | + | |
224 | + A “CC Castle” program can run on many cores, without the developer needs to describe “manually” how to do that. | |
225 | + | |
226 | + At the same time it should run efficiently. The goals is **not** to keep all cores *busy*, but to use (all) cores to | |
227 | + gain maximal speed up. | |
228 | + | |
229 | +Distributing tasks over multiple cores (or even distributed computers) [#web]_ is not new. In | |
230 | +:ref:`ConcurrentComputingConcepts` we describe some (common, theoretical) concepts, especially the | |
231 | +:ref:`CCC-Actors`. What we like to use for CCastle. | |
232 | + | |
233 | +---------- | |
234 | + | |
235 | +.. rubric:: Footnotes | |
236 | + | |
237 | +.. [#python27-outdated] | |
238 | + Both the Jython and Iron-Python implementations are effectively dead as there is only support for Python-2.7. That | |
239 | + however is ortogonal on the (alternative) way it handles threads. | |
240 | + | |
241 | +.. [#GIL-speed] | |
242 | + Using the GIL was not a bad option. It made code fast, both for non-threading as for threading! | |
243 | + |BR| | |
244 | + Many attempt have made to “remove the GIL”: all failed. Not because removing the GIL (itself) is hard, but as the | |
245 | + replacements made the code slower. Always for single-threaded applications; but sometimes the extra overhead was even | |
246 | + bigger then the speed up when using all cores. And even that was mainly in the “first tackle”, let it be a lesson | |
247 | + for “Busy Cores”: | |
248 | + | |
249 | + *It not about using all cores, it about the speed up!* | |
250 | + | |
251 | +.. [#CS-link] | |
252 | + See :ref:`ConcurrentComputingConcepts` for more on Critical-Sections_ and other well-know concepts and how they relate. | |
253 | + | |
254 | + | |
255 | +.. [#web] | |
256 | + A trivial example of dividing work over multiple computers (and so cores) is the “Web”. You have at least two | |
257 | + concurrent (active) components: the server and the brouwer. Usually there a more. By example, the server-side run’s | |
258 | + the application- a web-, and database-server. And “the web itself” has many active components, like routers, ect. And | |
259 | + all are programmed in a style that the developer doesn't need to know all those details(!). | |
260 | + | |
261 | +.. [#wrong] | |
262 | + Having a 1:1 relation is very populair point of view, at some places. But most probably wrong -- although that is an | |
263 | + assumption too. In addition, it does not scale (what when the number of core double?), and hard to manage. | |
264 | + |BR| | |
265 | + Also see: the section about IO- vs CPU bound. | |
266 | + | |
267 | +.. [#share] | |
268 | + Sharing can be done by a shared-data or by sending messages. For the developer the latter has the advantage that no | |
269 | + (synchronised) shared, variables are needed. But that us just an abstraction; at a lower level there is some memory | |
270 | + that is written by one an read by another thread -- and so need synchronisation and exclusiveness. | |
271 | + | |
272 | +.. [#SDD] | |
273 | + Even the fasterst “SSD-disks” are slow. Although they are a hundred times faster them *platters*, with accesstimes in | |
274 | + the *micro-seconds range*. That is a thousand times slower as the *nano-seconds* a processors is working in. | |
275 | + | |
276 | +.. [#bold-on] | |
277 | + This “C-blocks” concept however is common in other language; its very common java-script code. For C feels a bit as | |
278 | + “bolded-on” on the existing language -- and it is. When using it in Objective-C (and C++), it is still “bold-on”, but | |
279 | + more natural due the OO-aspect. And in Swift, which is designed with this concept from day 1, is just a part of the | |
280 | + language. | |
281 | + |BR| | |
282 | + Something similar will apply to Castle too: by design a language with fine-grained concurrency, we can learn from | |
283 | + existing concepts, combine them and make it trivial to use. | |
284 | + | |
285 | +.. [#one-percent] | |
286 | + By hearsay, GCD_ introduces a about a dozen instruction per dispatched “block”. So, when the blocks are about a | |
287 | + thousand instructions, that results in about 1%; which is acceptable. | |
288 | + Still, when googling, you will find people that try to dispatch a hand-full on instructions (like a single | |
289 | + statement); it works (as the result is correct), but doesn't (as it is slowish). Although, when you would do that | |
290 | + with raw-threads (create/stop a pthreads pro statement) you will really notice the slow-down! | |
291 | + | |
292 | +.. [#Windowing] | |
293 | + Both `X-Window <https://en.wikipedia.org/wiki/X_Window_System>`_ (or “X11”) and `MS-Windows | |
294 | + <https://en.wikipedia.org/wiki/Windows_1.0x>`_ heavily depend on this (then new, 1984 resp 1985) concept of an | |
295 | + “event-loop”. | |
296 | + | |
297 | + application be | |
298 | + | |
299 | +.. _Multi-Core: https://en.wikipedia.org/wiki/Multi-core_processor | |
300 | +.. _Concurrency: https://en.wikipedia.org/wiki/Concurrency_(computer_science) | |
301 | +.. _parallelism: https://en.wikipedia.org/wiki/Parallel_computing | |
302 | +.. _Critical-Sections: https://en.wikipedia.org/wiki/Critical_section | |
303 | +.. _Semaphores: https://en.wikipedia.org/wiki/Semaphore_(programming) | |
304 | +.. _Threads: https://en.wikipedia.org/wiki/Thread_(computing) | |
305 | +.. _Heisenbugs: https://en.wikipedia.org/wiki/Heisenbug | |
306 | +.. _pthreads: https://en.wikipedia.org/wiki/Pthreads | |
307 | +.. _Thread-Pool: https://en.wikipedia.org/wiki/Thread_pool | |
308 | +.. _GCD: https://en.wikipedia.org/wiki/Grand_Central_Dispatch | |
309 | +.. _blocks: https://en.wikipedia.org/wiki/Blocks_(C_language_extension) | |
310 | +.. _closure: https://en.wikipedia.org/wiki/Closure_(computer_programming) | |
311 | +.. _ |
@@ -0,0 +1,35 @@ | ||
1 | +.. -*- rst -*- | |
2 | + included in `4.FSMs-are-needed.rst` | |
3 | + | |
4 | +.. _Threads-in-CPython: | |
5 | +.. sidebar:: Threads in CPython | |
6 | + | |
7 | + Python_ was conceived in early 198X when the word was single-core. And even though there were already debates on very | |
8 | + advanced `M:N <https://en.wikipedia.org/wiki/Thread_(computing)#M:N_(hybrid_threading)>`__ models, threads_ were | |
9 | + singular. When one thread is running, “all cores” are busy... | |
10 | + |BR| | |
11 | + Back then, CPython_ made the design choice to use the now-famous GIL_ [#GIL-speed]_ to implement Critical-Sections_ | |
12 | + [#CS-link]_. | |
13 | + | |
14 | + In hindsight, that was maybe not the best approach. Although the Python developer can use sound threads, and | |
15 | + CPython_ implements them using a pthreads_\-thread for every python-thread, this GIL results in no speed-up on a | |
16 | + Multi-Core_ system. As many studies show: all cores will be used(!) but only one at a time. At any moment, only one | |
17 | + core is active. | |
18 | + |BR| | |
19 | + A clear example, showing that *“keeping the cores busy”* is not trivial. | |
20 | + | |
21 | + And remember: it’s not a flaw of Python_. Other implementations --like, Jython_ [#python27-outdated]_ using the | |
22 | + JAVA-VM runtime and IronPython_ [#python27-outdated]_ that uses the .Net environment-- use another (more modern) | |
23 | + design; in both cases, we get the Multi-Core_ speed-up that we expect. | |
24 | + | |
25 | + | |
26 | + | |
27 | + | |
28 | + | |
29 | + | |
30 | +.. _CPython: https://en.wikipedia.org/wiki/CPython | |
31 | +.. _Python: https://en.wikipedia.org/wiki/Python_(programming_language)#History | |
32 | +.. _pthreads: https://en.wikipedia.org/wiki/Pthreads | |
33 | +.. _GIL: https://en.wikipedia.org/wiki/Global_interpreter_lock | |
34 | +.. _Jython: https://en.wikipedia.org/wiki/Jython | |
35 | +.. _IronPython: https://en.wikipedia.org/wiki/IronPython |
@@ -17,7 +17,11 @@ | ||
17 | 17 | |
18 | 18 | * Replace the “actions” in a grammar. |
19 | 19 | |
20 | - .. seealso:: :ref:`G2C-actions` | |
20 | + .. seealso:: | |
21 | + | |
22 | + * :ref:`G2C-actions` | |
23 | + * :ref:`CyclicWoods` | |
24 | + | |
21 | 25 | |
22 | 26 | .. _Declarative-programming: |
23 | 27 |
@@ -35,3 +39,37 @@ | ||
35 | 39 | * Argparse (vs loop over argv) is a second example |
36 | 40 | |
37 | 41 | .. note:: CCastle: blog: “(1) declare what you need”. Declarative style programing. Eg loop over Argv vs argparse, makefiles |
42 | + | |
43 | + | |
44 | +.. _CyclicWoods: | |
45 | + | |
46 | +Cyclic woods (todo) | |
47 | +=================== | |
48 | + | |
49 | +.. todo:: Generalise and abstract the famous tree-structure and allow cycles | |
50 | + | |
51 | + E.g. a AST is tree with “cycles”: Each var is defined and used. Use “href” alike | |
52 | + | |
53 | + .. seealso:: Its is (maybed) related to :ref:`matching-statements` | |
54 | + | |
55 | +.. _CC: | |
56 | + | |
57 | +Concurrent//Connected Components (ToDo) | |
58 | +======================================= | |
59 | + | |
60 | +.. todo:: Write a few blog about the CC-concept | |
61 | + | |
62 | +.. _XXX: | |
63 | + | |
64 | +XXX (ToDo) | |
65 | +========== | |
66 | + | |
67 | +.. _CC-example-Sieve: | |
68 | + | |
69 | +Sieving Prime components (ToDo) | |
70 | +=============================== | |
71 | + | |
72 | +.. _Castle-Tools: | |
73 | + | |
74 | +Castle Tools (ToDo) | |
75 | +=================== |
@@ -0,0 +1,235 @@ | ||
1 | +.. include:: /std/localtoc.irst | |
2 | + | |
3 | +.. _grammmar-code: | |
4 | + | |
5 | +=============== | |
6 | +Grammar is code | |
7 | +=============== | |
8 | + | |
9 | +.. post:: 2022/05/14 | |
10 | + :category: Castle, DesignStudy | |
11 | + :tags: Castle, Grammar, PEG | |
12 | + | |
13 | + In :ref:`Castle-CompilerCompiler` we have seen that we can define a grammar within a Castle-program. And we have | |
14 | + argued that each grammars-rule can be considered as a function. | |
15 | + | |
16 | + In this post, we look into de details of how this works. And will confirm grammars is code ... | |
17 | + | |
18 | +Let’s start with an example. The grammer below is a simplified description of how a (PEG) parsing-rule looks like. The | |
19 | +syntax in Castle is a bit more complicated, by having more details and options; but very simular. Most of the | |
20 | +Caste-grammers can be parsed by the grammer below! | |
21 | + | |
22 | +.. code-block:: PEG | |
23 | + | |
24 | + PEG_rule <- rule_name '<-' expression ';' ; | |
25 | + expression <- ordered_choice+ ; | |
26 | + ordered_choice <- sequence ( '|' sequence)* ; | |
27 | + sequence <- group | atom ; | |
28 | + group <- '(' expression ')' ; | |
29 | + atom <- rule_xref | str_lit | regexp ; | |
30 | + str_lit <- '"' /[^"]* '"' ; | |
31 | + regexp <- '/' /[^/]* '/' ; | |
32 | + rule_name <- ID ; | |
33 | + rule_xref <- ID ; | |
34 | + | |
35 | +With this grammer we can read and check whether an a string is a valid rule by simply calling: | |
36 | +:math:`ast:=PEG\_rule(single\_line)`. When not, ``ast`` is :math:`False`, else ``ast`` has 4 children (or fields). | |
37 | +Where :data:`ast[0]` represent the ``rule_name``, :data:`ast[2]` is an ``expression``; which is a sequence of | |
38 | +``ordered_choice``\(s). | |
39 | +|BR| | |
40 | +As the rule has two constants :data:`ast[1]` and :data:`ast[3]` will always match the strings *‘<-’* and *‘;’*. | |
41 | + | |
42 | + | |
43 | +Grammar to code | |
44 | +=============== | |
45 | + | |
46 | +Before we study how Castle *expands* a grammar to code, let examine how to do that by manually crafted code, or using a | |
47 | +external compiler-compiler. In both cases, we will focus on the “validation” part only. And we skip a lot of details; | |
48 | +assuming you know a bit of theory of (PEG) parser. When not, read Guido van Rossum’s excellent blog-series `PEG Parsing | |
49 | +Series Overview <https://medium.com/@gvanrossum_83706/peg-parsing-series-de5d41b2ed60>`__ | |
50 | + | |
51 | + | |
52 | +Hand written code | |
53 | +----------------- | |
54 | + | |
55 | +Again, let’s suppost we like to verify a string contains a *peg-rule*. Then we need some functions [#func]_, which signature | |
56 | +are something like: | |
57 | + | |
58 | +.. tabs:: | |
59 | + | |
60 | + .. code-tab:: python | |
61 | + | |
62 | + def PEG_rule(text: str) -> ast : ... | |
63 | + def expression(text: str) -> ast : ... | |
64 | + def ordered_choice(text: str) -> ast : ... | |
65 | + def sequence(text: str) -> ast : ... | |
66 | + ... | |
67 | + | |
68 | + .. code-tab:: c | |
69 | + | |
70 | + ast PEG_rule(char* txt); | |
71 | + ast expression(char* txt); | |
72 | + ast ordered_choice(char* txt); | |
73 | + ast sequence(char* txt); | |
74 | + ... | |
75 | + | |
76 | +Where we assume the type ``ast`` is defined in the chosen language and will be Null/None/Empty to signal :math:`False`: | |
77 | +not valid. | |
78 | + | |
79 | +The implementation of ``PEG_rule()`` checks thats the input-string starts with a ``rule_name``, followed by the literal | |
80 | +string **“<-”**, then has an ``expression`` and finally the literal string **“;”**. When one of those (four) steps fail, | |
81 | +we return :math:`False`. | |
82 | +|BR| | |
83 | +We follow this pattern for all rules. | |
84 | + | |
85 | +This concept is easy to implement: each rule-function calls other rule-functions as defined by the grammar. When we | |
86 | +need to check for a literal string we use :func:`expect(txt: str, literal: str) -> bool`. Also, we need a function to find | |
87 | +an ID; again easy. Sometimes we need to implement a loop --to handle ``*`` and ``+``. Or we need an :math:`or`, to | |
88 | +implement alternatives (``|``). None of that is rocket science. | |
89 | + | |
90 | +A real implementation is a bit harder, as we have to strip spaces (and comments), handle newlines, and need to keep | |
91 | +track of where we are. Typically that is (nowadays) done by embedding those functions in a class; then the “input text” can be | |
92 | +stored in the instance (instead of passing them constantly). That instance also has a ‘cursor’ to the current | |
93 | +location. | |
94 | + | |
95 | +More details | |
96 | +~~~~~~~~~~~~ | |
97 | + | |
98 | +There are a lot of details that make writing a grammer complex. We mention a few, and what it effect is on the (manually | |
99 | +written) code. | |
100 | + | |
101 | +When using alternatives (the ``|`` operator in the grammar), a PEG-parser will always try the first alternative first, | |
102 | +Only when that fails, it back-ups an try the next alternative. Sometimes means (almost) start again, and parse the same file almost | |
103 | +completely again. Therefore the *packrat* algorithm is usually used; using memoization. | |
104 | +|BR| | |
105 | +This is not hard: just add a few lines of boilerplate before and after each call. To store intermediate partial-ast(s) in a | |
106 | +cache. | |
107 | + | |
108 | +Sometimes, we like to use another parser-strategy, like LALR_ (used by Yacc_), GLR_ (e.g Bison, the successor of Yacc_) | |
109 | +or `LL(k)`_ (introduced by ANTLR, which was popular for a while); each one has it pros and cons. Still, all (or almost) | |
110 | +start with the same grammar (although smarter strategies may result is shorter, easier to maintain [#maintain]_ | |
111 | +grammars) [#notation]_. | |
112 | + | |
113 | +For a long time PEG-parsers where not able to handle left recursive rules [#leftStack]_. Until somebody discovered that is not | |
114 | +correct. Grammars in Castle can be left recursive! Both direct and indirect recursion is allowed. | |
115 | + | |
116 | +.. tabs:: | |
117 | + | |
118 | + .. code-tab:: PEG Direct recursion | |
119 | + | |
120 | + expr <- expr '-' term | term | |
121 | + | |
122 | + .. code-tab:: PEG Indirect recursion | |
123 | + | |
124 | + A <- B "a" | "a" | |
125 | + B <- A "b" | "b" | |
126 | + | |
127 | + .. code-tab:: PEG A rewritten grammar | |
128 | + | |
129 | + expr <- term ( '-' term )* | |
130 | + | |
131 | +.. note:: | |
132 | + | |
133 | + It is always possible to rewrite a lef-recursief grammar to one that isn’t. However, that make the grammar harder to | |
134 | + read & maintain (for humans). It does also influence the outcome; the tree will differ. | |
135 | + | |
136 | + By example, an simple calculation as :math:`7-5-3` should result in :math:`((7-5)-3)` but that needs left | |
137 | + recursion. When rewriting it, you must be carefull not to get :math:`(7-(5-3))`! | |
138 | + |BR| | |
139 | + This can be fixes, by adding an extra step. But it is better to use the update PEG-strategy: Just add more boilerplate code! | |
140 | + | |
141 | + For that reason Castle will support recursion! You can write the grammar as you need, as we are generating that extra | |
142 | + boilerplate anyhow. | |
143 | + | |
144 | + | |
145 | +Generating the code | |
146 | +=================== | |
147 | + | |
148 | +You might recognise the pattern: To make the grammer more useful, the algorithms become more complex and adds more | |
149 | +code. This “extra” code, however is not hard; you just need the same (or almost the same) lines at many places. | |
150 | +|BR| | |
151 | +This begs for automation. And that is exactly what most compiler-compilers do. | |
152 | + | |
153 | +A compiler-compilers read the grammar and generates the code. As shown above it will generate (C, C++, C#, Java, | |
154 | +Python, or ...) functions [#OrTables]_ that call each-other. It will also detect left-recursion, and might compensate for | |
155 | +that. The result: more boilerplate-code; but as it is automatically generated this is easy. | |
156 | + | |
157 | +Classic tools | |
158 | +------------- | |
159 | +There are many tools, that we can use for inspiration. A short overview, and how it influences Castle. | |
160 | + | |
161 | +Possible the most famous compiler-compilers is Yacc_. It was developed in 197X and generates C-code that can be compiled | |
162 | +and linked to your code. To parse a string, you had to call ``yyparse())``. It would however be relatively simple to | |
163 | +generate functions with the name of each rule, using the same machinery. In that decade however, the goal was | |
164 | +differently. Memory was limited, what we can also see in the used grammar: one had to craft it carefully as the was no | |
165 | +back-tracking an only a single token look-ahead. | |
166 | + | |
167 | +Bison_ is Gnu reimplementation of Yacc_, but can use several parsing-algorithms.cLike Yacc_, it used a separate Lexer_: | |
168 | +*flex* (whereas Yacc uses *lex*). A lexer_ splits the input-string into a stream of *Tokens* using another (simpler, | |
169 | +but faster) algorithm. In that time that was relevant. | |
170 | +|BR| | |
171 | +As a lexer_ can be implemented with a parsing-algorithm (but not the other-way around), and as the need for speed doesn't | |
172 | +demand a separate lexer_ anymore; modern parsings are often “scannerless”. This removes the need to use two meta-syntaxes | |
173 | +(for the lexer/scanner and the parser) and so is simpler to use. | |
174 | +|BR| | |
175 | +Also Castle use a scannerless approach. | |
176 | + | |
177 | +Castle: rules are functions | |
178 | +=========================== | |
179 | + | |
180 | +.. resolution:: In Castle each rule act as a *callable* | |
181 | + :ID: R_GrammerCallables | |
182 | + :links: U_Grammers | |
183 | + | |
184 | + Each parse-rule that is defined in Castle is a kind of function; more accurately it’s a “callable” | |
185 | + | |
186 | +Also in Castle you can use grammars; but now directly in your program, using the Castle-syntax. And Castle will generate | |
187 | +“code” --Castle-functions that is. But now without an extra tool. | |
188 | +|BR| | |
189 | +This “generate code” is not ‘code as text’. Why should we generate code, to read & parse it back and compile it | |
190 | +directly? It easier to generate the AST, that would be the result of parsing the generated-code, directly. | |
191 | + | |
192 | +But the effect is the same. You create a set of function with this generic “text to tree” signature, by writing some | |
193 | +simle rule. Castle does the rest for you. Easy! | |
194 | + | |
195 | +And in case you are wondering how to use actions is in e.g. YACC: You don’t (need them). See :ref:`G2C-actions` for why | |
196 | +there are outdated and both :ref:`matching-statements`, and :ref:`CyclicWoods` | |
197 | + | |
198 | + | |
199 | +---------- | |
200 | + | |
201 | +.. rubric:: Footnotes | |
202 | + | |
203 | +.. [#func] | |
204 | + Instead of a **function**, it can also be a *method, or any *callable*. We use ‘function’ a generic term, in the | |
205 | + mathematical meaning: some input (parameters) and an output (return value). | |
206 | + | |
207 | +.. [#maintain] | |
208 | + This is not specially for grammers; all it valid for all programming-languages. New languages may introduce new | |
209 | + concepts (like --once-- OO). When the compiler becomes smarter, the programmer can focus in the important bits! | |
210 | + | |
211 | +.. [#notation] | |
212 | + Aside of multiple parser-algorithms, there are also several notation to write the grammar itself; like `EBNF | |
213 | + <https://en.wikipedia.org/wiki/Extended_Backus–Naur_form>`__ `ABNF | |
214 | + <https://en.wikipedia.org/wiki/Augmented_Backus–Naur_form>`__, and `YACC`_ | |
215 | + Most implementations of a given algorithm, use a dialect of a standard one, to enable :ref:`G2C-actions`, or .. | |
216 | + | |
217 | + Also Caste does this: We use the Caste-grammer, which is based on both EBNF and PEG; but using the classic ‘|’ | |
218 | + instead of the ‘\’ for ordered-choice. | |
219 | + | |
220 | +.. [#leftStack] | |
221 | + Without going into details left-recursion is hard for many parsing-algorithms. In the shown approach, a | |
222 | + rule-function (for a rule that is direct left-recurse) will call itself as first step. In this way no progress is | |
223 | + made, and the stack will quickly overrun. | |
224 | + | |
225 | +.. [#OrTables] | |
226 | + Some tools, like Yacc by example, use another approach. Instead of many functions it has a generic (run-time) library | |
227 | + that used code-tables; which are generated by the tool. Still, that is just a implementation detail. | |
228 | + | |
229 | +.. _LALR: https://en.wikipedia.org/wiki/LALR_parser | |
230 | +.. _LALR(1): LALR_ | |
231 | +.. _GLR: https://en.wikipedia.org/wiki/GLR_parser | |
232 | +.. _LL(k): https://en.wikipedia.org/wiki/LL_parser | |
233 | +.. _YACC: https://en.wikipedia.org/wiki/Yacc | |
234 | +.. _Bison: https://en.wikipedia.org/wiki/GNU_Bison | |
235 | +.. _Lexer: https://en.wikipedia.org/wiki/Lexical_analysis |
@@ -0,0 +1,149 @@ | ||
1 | +.. include:: /std/localtoc.irst | |
2 | + | |
3 | +.. _G2C-actions: | |
4 | + | |
5 | +=================== | |
6 | +No *inline* actions | |
7 | +=================== | |
8 | + | |
9 | +.. post:: 2022/05/21 | |
10 | + :category: Castle, DesignStudy | |
11 | + :tags: Castle, Grammar | |
12 | + | |
13 | + In :ref:`grammmar-code` we have mentioned that many compiler-compilers reuse the Yacc invention “actions”. And we | |
14 | + hinted already that Castle prefers an alternative. | |
15 | + | |
16 | + Let’s see why the old concept is outdated ... And what is easier to use. | |
17 | + | |
18 | +Actions, in retrospect | |
19 | +====================== | |
20 | + | |
21 | +When parsing an input with the aspiration to verify the input does matches the grammar only; a result as :math:`True` or | |
22 | +:math:`False` will do. Commonly this is *not* our goal; we want to act on the input. Or at least *read* the content. | |
23 | +|BR| | |
24 | +`Yacc`_ invented *actions*: embedded (C-) code-fragments that are copied into the generated parser. When the parser | |
25 | +reached that point the code as executed. You could anything you like: Build a parse-tree, or directly act on the | |
26 | +(partially) parsed input [#SAXDOM]_. | |
27 | + | |
28 | +It was great (back then). Many, also the more modern, parser-generators use inline-actions -- with the drawback that it | |
29 | +makes the grammer harder to read. In spite of the popularity of actions, I think we can do better, as lot has happend | |
30 | +since then. Most important: parsing-algorithms become a lot smarter. Yacc_ used a simple `LALR(1)`_ pattern; with only 1 | |
31 | +token lookahead. That allowed us to execute an action as soon a the input was read upto that point. Without backtracking | |
32 | +and other “considere alternatives”, that execution is always deterministic. | |
33 | + | |
34 | +Ambiguity | |
35 | +--------- | |
36 | + | |
37 | +With *“backtracking”* (and other *smartness*) this has chanced. Both the compiler-compiler and the resulting parsers | |
38 | +have to consider multiple ways on how to read the input. And may reconsider many tokens and lines later on how to parse | |
39 | +a (earlier) line. When execution actions “in-line”, the can become executed many times -- which probably isn’t what was | |
40 | +ment when specifying the grammer. | |
41 | + | |
42 | +Many strategies exist to solve this ambiguity. Some tools demand that each action have no side-effects. When a | |
43 | +pure-functions (as the are called) many times, the deliver exactly the same result, every time. So the issue is gone; | |
44 | +albeit it limits you in what your actions can do -- strictly speaking even printing a debug message is not allowed. | |
45 | +Others use this effect and cache the first result and reuse the next time(s). Again it works, but it limits on what | |
46 | +actions can do! | |
47 | +|BR| | |
48 | +A tools may also postpone all actions until the parser is confident on how to read (parse) the input -- often when all | |
49 | +input is read. Again it works, unless you expected (debug) output on the fly. | |
50 | + | |
51 | +In short: inline-actions have become more restricted and less useful when parser become smarter. Without solving the | |
52 | +need for maintainable grammers. | |
53 | + | |
54 | +Memory | |
55 | +------ | |
56 | + | |
57 | +Once memory was very restricted; a compiler-compiler that only needed a single token-lookahead was using not more memory | |
58 | +then needed. When needed, the programmer could use inline-actions to build the “parse-tree” on the fly. This has become the | |
59 | +standard. During parsing one builds a tree: a parse-tree. And often we postproces it afterwards [#SAXDOM]_. | |
60 | + | |
61 | +As modern tools need to (be able to) read the whole input anyhow to be able parse it, and the memory-issues is solved | |
62 | +[#fun]_, the need to process “actions” *inline* is gone. But we need a design to act in the input! | |
63 | + | |
64 | + | |
65 | +Visitors | |
66 | +======== | |
67 | + | |
68 | +The de-facto solution is **vistitors**. Remember, back-them the `Visitor Pattern`_ wasn't invented yet! But now | |
69 | +visitors_ are very popular to separates algorithms and data. We like to build the “parse-tree” in one component first | |
70 | +and, act on it with visitors_ (and friend) later; possible in another component. | |
71 | + | |
72 | +.. hint:: Visitors & friends | |
73 | + | |
74 | + There are many kinds of visitors; most (sub)patterns are very interwoven with the language that is used -- although | |
75 | + many programming-language do no have “build in” support for this pattern. It the developer who has to write all. | |
76 | + | |
77 | + In classic OO-languages, one write specially named methods in a class. That are called using single (or double) | |
78 | + dispatch; to handle the data-object ‘D’ the method `visit_D()` is called “automagically”. And for a subclass ‘S’ one | |
79 | + has to implement `visit_S()` -- even when it should do exactly the same as `visit_D()`; no inheritance here. | |
80 | + | |
81 | + Other languages, like CSS, use visitors_ slightly differently. Here `“selectors” | |
82 | + <https://en.wikipedia.org/wiki/CSS#Selector>`__ are use to *select* a part of a tree on which a scripts-alike | |
83 | + “declaration” will act. One can even select multiple parts; the system will interate over them automatically. | |
84 | + |BR| | |
85 | + Also `XLST <https://en.wikipedia.org/wiki/XSLT>`_ uses this approach; here `XPATH | |
86 | + <https://en.wikipedia.org/wiki/XPath>`__ expressions are used to select the data. | |
87 | + |BR| | |
88 | + This kind of visitor needs language-support: to be able to separate which data is to be pick and which actions has to | |
89 | + be performed on all found parts. | |
90 | + | |
91 | + | |
92 | + Most likely there are even more variants of this pattern (and even within the OO-languages, various version | |
93 | + exist). For me, and for now, it are all “**visitors** (or *friends*)”. | |
94 | + |BR| | |
95 | + Castle will have a more advanced version; as it should be easy for developer (and hard to make mistakes). | |
96 | + | |
97 | + | |
98 | +Castle Has build-in visitors | |
99 | +============================ | |
100 | + | |
101 | +.. resolution:: Castle Grammers should not need “inline-actions” | |
102 | + :ID: RG_NoInlineActions | |
103 | + | |
104 | + The traditional inline actions, as one invented by Yacc_, are outdated as the complicate the grammer, modern | |
105 | + parser-strategies need to read all input anyhow and we aren’t that restricted in memory anymore. So, an alternative | |
106 | + that make the code better maintainable is to be preferred. | |
107 | + | |
108 | + .. tip:: It does not imply Castle (or a future version) is not allowed to support inline-actions | |
109 | + | |
110 | + Grammer-tules are just functions; so why not allow pseudo-rules, that act as inline-actions, but are just regular | |
111 | + functions (with the same signature) | |
112 | + | |
113 | +.. Use:: Castle Grammers can use Visitors | |
114 | + :ID: UG_GrammerVisitors | |
115 | + | |
116 | + To act on data, and to separate the data and the action, Castle will support Visitors that can act on Grammers; or | |
117 | + more accurate: on the trees that result from a parser-invocation. | |
118 | + | |
119 | + .. tip:: To enable this, Castle has a (generic, abstract) data-type ``Tree``; see :ref:`tree-type`. | |
120 | + | |
121 | + With (parser)visitors, it should be possible to “select” a (set of) tree-part(s), and “call” an some code that will | |
122 | + act on that data. Typically, that “code” will be a function (or other callable), but it can also be a lambda, or a | |
123 | + “code block”. | |
124 | + | |
125 | +---------------------------- | |
126 | + | |
127 | +.. rubric:: Footnotes | |
128 | + | |
129 | +.. [#SAXDOM] | |
130 | + With hindsight we can compare this how we handled and are handling XML (and/or HTML) now. | |
131 | + | |
132 | + It started with `SAX`_: “events” that act as small *actions* as soon that part was read/parsed (remember: pasting XML | |
133 | + is simple as the tags denote the tree). Nowadays, everybody is using the `DOM`_: the whole input is converted to a | |
134 | + tree first (the `DOM`_) and *visitor-alike* “scripts” will process this `DOM`_ afterwards. | |
135 | + | |
136 | +.. [#fun] | |
137 | + Just for fun: Guess, what is bigger: All source-code of the complete Linux-kernel, or one (high definition) movie? | |
138 | + | |
139 | + | |
140 | +.. _YACC: https://en.wikipedia.org/wiki/Yacc | |
141 | +.. _SAX: https://en.wikipedia.org/wiki/Simple_API_for_XML | |
142 | +.. _DOM: https://en.wikipedia.org/wiki/Document_Object_Model | |
143 | + | |
144 | + | |
145 | +.. _LALR: https://en.wikipedia.org/wiki/LALR_parser | |
146 | +.. _LALR(1): LALR_ | |
147 | + | |
148 | +.. _Visitor Pattern: https://en.wikipedia.org/wiki/Visitor_pattern | |
149 | +.. _Visitors: `Visitor Pattern`_ |
@@ -0,0 +1,442 @@ | ||
1 | +.. include:: /std/localtoc.irst | |
2 | + | |
3 | +.. _eval_FSMs-syntax: | |
4 | + | |
5 | +========================= | |
6 | +FSM syntax, an evaluation | |
7 | +========================= | |
8 | + | |
9 | +.. post:: 2022/06/10 | |
10 | + :category: Castle, Design | |
11 | + :tags: Castle, FSM | |
12 | + | |
13 | + As described in :ref:`FSMs-are-needed` *Finit State Machines* are great and needed -- even tough no (main) programming | |
14 | + language has syntax support for it. But there are other (computer) language that (more-or-less) support the | |
15 | + corresponding `State pattern`_. | |
16 | + |BR| | |
17 | + By example plantUML --very populair by mature developers-- has a syntax to draw them. | |
18 | + | |
19 | + What can we learn from them? That is the topic of this post, before we define the Castle syntax. | |
20 | + | |
21 | + | |
22 | +Goal: Short & Maintainable | |
23 | +************************** | |
24 | + | |
25 | +Before we can define the (Castle) syntax for FSM_\s, we should know where we are aiming for. We need to support “all” | |
26 | +kinds of FSM, as required by [:need:`U_FSM_Syntax`] and refined by [:need:`U_FSM_extensions`]; e.g. the syntax should | |
27 | +allow non-determinism. And like all parts of Castle: maintainability and preventing mistakes is important. | |
28 | +|BR| | |
29 | +For a FSM this means **short**: avoid boilerplate-code. | |
30 | + | |
31 | +The FSM_\`s mathematical model is simple: a set of `states` (‘:math:`S`’), the input `events` (‘:math:`E`’), | |
32 | +the transaction `rules` (‘:math:`R`’), a `start-state` (‘:math:`S0`’), and the `final-states` -- which are not needed | |
33 | +for a SW-FSM [#final-action]_. Usually, a set of `actions` (‘:math:`A`’) is required too. Where this set is implicitly | |
34 | +defined: the actions are listed inside the rules. | |
35 | +|BR| | |
36 | +Each `rule` is relation :math:`R := S * E -> S, A`; this “table” is typically the biggest part of an FSM. | |
37 | + | |
38 | +So, to make a FSM-code compact, we have to focus on the rules. It’s tempting to regard this rule-set as a *matrix*: | |
39 | +with (‘:math:`S`’) and (‘:math:`E`’) on the axes and the next-states [#non-determinism]_ (and actions) inside each | |
40 | +cell. Nevertheless this matrix is huge and probably sparse: most cells are empty, as the combination does not occur. | |
41 | +|BR| | |
42 | +We can describe such a sparse-matrix by listing the cell-value with the coordinates. This boils-down to listing the | |
43 | +rules, one by one .The disadvantage of this that many states and/or events are listed many times. As we will see below, | |
44 | +some languages solve this by factor-out `states` and/or `events`. | |
45 | + | |
46 | +.. hint:: Concurrency is not relevant | |
47 | + | |
48 | + FSM’s can be huge in code but do not need a lot of computer-power. For every *step* --one input-- one state-variable | |
49 | + has to be updated, and the action has to be triggered. That action can be “big” (an can need concurrency), the FSM | |
50 | + itself not. Therefore, the syntax of the FSM doesn't need special attention to make the FSM concurrent. | |
51 | + | |
52 | + | |
53 | +Languages that support the state-pattern | |
54 | +**************************************** | |
55 | + | |
56 | +Some tools support FSMs, the state-pattern, or something that resembles it. We will not evaluate the tool, but focus in | |
57 | +the “input” those tools use. And on what concept we can reuse to design the syntax/grammar that Castle will use for | |
58 | +FSM-support. | |
59 | + | |
60 | +PlantUML | |
61 | +======== | |
62 | + | |
63 | +.. include:: FSM-sidebar-plantUML.irst | |
64 | + | |
65 | +The design-tool plantUML support the UML-FSM_ State diagram with a quite compact syntax. The focus however is on | |
66 | +*drawing* [#plantUML-arrows]_. As one can add text ‘on’ the arrows and ‘in’ the states, events and actions can be | |
67 | +specified. However, the is no specific syntax for that. By example, many add text like :code:`event / action()` to | |
68 | +annotate the transaction with events and actions. But for plantUML it us just text. The same for Moore-actions: It an | |
69 | +convention to add them to a state, with prefixes as **E:** and **L:**. | |
70 | +|BR| | |
71 | +So using this syntax directly isn’t possible. By adding a bit or (formal) grammar is easy. | |
72 | + | |
73 | +PlantUML support all aspects of the UML-FSM_, including super/sub-states (plantUML calles them ‘Composite state’) and | |
74 | +concurrent states. As ‘drawing’ is the main goal, support for :math:`\epsilon`\-transaction, all kind of actions, etc is | |
75 | +solved as described above: by text. | |
76 | + | |
77 | +Super/Sub-states | |
78 | +---------------- | |
79 | +Substates are drawn ‘inside’ a superstate. This is described with a nested structure; a state can have an (optional) | |
80 | +``{} block``. Inside that block, the same syntax is uses as for the main FSM_. | |
81 | + | |
82 | +This part of syntax does not fit the goals of Castle; as it is still *one* piece of code; it does not make the source | |
83 | +“shorter” [#indirect]_. But more important: one would typically like to reuse “sub FSM” and specify those details | |
84 | +later/elsewhere in the program. | |
85 | + | |
86 | +Referring | |
87 | +~~~~~~~~~ | |
88 | + | |
89 | +A developer like to *refer* to other parts; by example to import other modules or *name* those. Not by recode them. This | |
90 | +is not possible (relevant) in plantUML’s state diagrams. Although some do/try by separate the source into multiple | |
91 | +files, and use the “``!include`` preprocessing” options -- a bit like good-old C textual includes. One misses namespaces | |
92 | +and other *modern* features however. | |
93 | + | |
94 | +.. _SMC: | |
95 | + | |
96 | +SMC (State Machine Compiler) & friends | |
97 | +====================================== | |
98 | + | |
99 | +.. include:: FSM-sidebar-SMC.irst | |
100 | + | |
101 | +There are many versions of the “State Machine Compiler”. Most use a text-input-file to specify a FSM_ and *’compile’* | |
102 | +that into programm-code first. Then the normal compiler is used to compile it “asis”. | |
103 | +|BR| | |
104 | +We do not discuss the tools itself, but will examine the input-file. And (when given) the formal grammar. | |
105 | + | |
106 | +Uncle Bobs’s version | |
107 | +--------------------- | |
108 | + | |
109 | +Uncle Bob’s version basically uses a “table” with 4 columns: ``current.state``, ``event``, ``next.state``, ``action``; | |
110 | +separated by whitespace. The name of the FSM, and it initial state are written-down above the tabel. This table is | |
111 | +translated into a class with a nested-switch FSM [#generated]_; the SW-developer should create a subclass that | |
112 | +implements actions (as methods). | |
113 | +|BR| | |
114 | +As SMC will generated the essential code (which should be deterministic), the FSM needs to be deterministic; the syntax | |
115 | +does allow (a bit of) non-determinism however. But by example *epsilon*- (and especially *‘instantly’*) transaction are not | |
116 | +possible. | |
117 | + | |
118 | +It is possible to factor-out some current.states (but not events) by using ``{}-blocks`` --the docs speak about | |
119 | +*“convenient syntactic sugar”*. Equally, one can combine several actions (function-calls) into one: surround | |
120 | +them with braces. | |
121 | +|BR| | |
122 | +This block concept can also be use to describe “abstract states”, which resembles super/sub-states. This is done by the | |
123 | +``:``\-modifier postfixing a state, and putting the abstract-state-name between | |
124 | +parenthesis. | |
125 | +|BR| | |
126 | +It is also possible to specify entry/leave(exit) action, again by postfixing a state with :samp:`‘<’ {entry-action}` | |
127 | +or/and :samp:`‘>’ {exit-action}`. | |
128 | + | |
129 | +The basic syntax is quite simple and readable; although whitespace as separator is not ideally --also as it make it a bit | |
130 | +unclear (hard to remember) what the order is. This readability issues becomes bigger when factoring-out (and the number | |
131 | +of columns decrease), or using state-modifiers. | |
132 | +|BR| | |
133 | +This can easily be improved (for Castle), by adding a bit more grammar-sugar and have several ‘tokens’ between the columns. | |
134 | + | |
135 | +The sytax of this version of SMC allows somethings that resembles hierarchically superstates; although the hierarchy is | |
136 | +“inlined”. | |
137 | +|BR| | |
138 | +For Castle, we cherish the ability to spilt the text over multiple files [#hierarchically-split]_. | |
139 | + | |
140 | + | |
141 | +SMC (sourceforge) version | |
142 | +------------------------- | |
143 | + | |
144 | +This version is derived from an early variant of (Uncle) Bob Martin’s (see above), according to its `documentation | |
145 | +<http://smc.sourceforge.net/SmcManual.htm>`__ The basic input-syntax is equally; although a lot “target-language details | |
146 | +are added to the header (like file-names etc)-- for Castle this is not relevant. | |
147 | + | |
148 | +The syntax is updated. By example, to describe Moore actions the keywords `Entry` and `Leave` are used with | |
149 | +``{}-blocks`` surrounding the action (even for a single call). In general, those ``{}-blocks`` has become compulsory; | |
150 | +every state has such a block., as has every action. This makes the syntax more regulair and readable for C/etc | |
151 | +programmers. | |
152 | +|BR| | |
153 | +But all those braces makes that the compact “table alike” structure for the rules is gone. | |
154 | + | |
155 | +guards & parameters | |
156 | +~~~~~~~~~~~~~~~~~~~ | |
157 | + | |
158 | +A new feature is **“guards”**: a boolean expression-postfix on events (in square-Brackets: ``[<guard>]``). The specified | |
159 | +transaction will only happen when and that event happens and the guard is true. The same event without a guard will act | |
160 | +as a kind of default/fall-through transaction. | |
161 | + | |
162 | +Another feature are **event-parameters** (called “Transition Arguments”; as the words event and transition are not used | |
163 | +consistently). In all examples this event-parameter is used in the guard; it’s not clear (Nore relevant) the tool can | |
164 | +also use it elsewhere. | |
165 | + | |
166 | + | |
167 | +more changes | |
168 | +~~~~~~~~~~~~ | |
169 | + | |
170 | +It support also a few notations, that do (IMHO) not fit in the FSM_ notion; like having a stack (that makes it a | |
171 | +stack-machine or `PDA <https://en.wikipedia.org/wiki/Pushdown_automaton>`__). But it has a nice feature to generate | |
172 | +(graphviz) diagrams; this really is convenient for the developer. Even one nowadays probably would prefer to see plantUML | |
173 | +State diagrams, as they are more standard. | |
174 | + | |
175 | +And again, for castle we like to be able to “distribute” details over multiple files. | |
176 | + | |
177 | +.. _SCXML: | |
178 | + | |
179 | +State Chart XML (SCXML): State Machine Notation for Control Abstraction | |
180 | +======================================================================= | |
181 | + | |
182 | +.. include:: FSM-sidebar-SCXML.irst | |
183 | + | |
184 | +SCXML is a (XML-based) standard “language” [#voice]_ to describe (more-or-less) an UML-FSM_. | |
185 | +|BR| | |
186 | +Surely, the XML-part is not applicable for Castle. Still, XML describes a tree (structure) -- like the Castle text | |
187 | +format will be converted into an AST (so, also a tree). So there we can learn (or at least try). | |
188 | + | |
189 | +This format treads *events* as attributes of a transition. See the disadvantage of this in `Remarks (general)`), below. | |
190 | + | |
191 | +Harel StateCharts (aka UML-FSM_) are supported. Both by being able to nest states; using the power of XML: Any | |
192 | +``<state>`` elements may have (other) ``state`` elements as children. And by having ``<parallel>`` elements, that can | |
193 | +contain (multiple) ``<state>`` elements -- here, each of those parallel states act as a “small FSMs” that are all active | |
194 | +when the parent state is active. This is an elegant way to describe “Orthogonal regions” (aka “Concurrent states”). | |
195 | + | |
196 | +Concurrent sub-states | |
197 | +--------------------- | |
198 | + | |
199 | +Like a regulair ``<state>``, a ``<parallel>`` element has an ID (attribute), that act as name -- showing a bit of | |
200 | +similarity between normal states and concurrent-substates. This approach can be usable for Castle. | |
201 | + | |
202 | +Possible, two concurrent states can also be seen in a hierarchical way. At the top level is just one state, that is | |
203 | +active or not. And when we dive into de details, it *can* have substates (like normal a hierarchy); only here some | |
204 | +states can be active concurrently. As SCXML describes it, the “upper” state (nor the rest of the FSM) does not have to | |
205 | +know about this concurrency. | |
206 | +|BR| | |
207 | +Additionally, those concurren “substates” do not *exist*, whe the upper state is passive ... | |
208 | + | |
209 | +.. tip:: Have to give this a tought ... | |
210 | + | |
211 | + When ``state`` can act a small FSM_ internally, we can possible define a “concurrent state class” too. That class | |
212 | + act as state, and can have “two” (or more) FSM’s inside ... | |
213 | + | |
214 | + The inheritance-order/tree becomes complex however; `Liskov | |
215 | + <https://en.wikipedia.org/wiki/Liskov_substitution_principle>`__ should not be violated. | |
216 | + | |
217 | + * ``FSM`` is s subtype of ``state``. (as a state, is only active or not). | |
218 | + * The “concurrent one`` is also a subtype of ``state``, not containing some ``FSM``\s | |
219 | + | |
220 | + *Or, should we not inherited, but always aggregate? Sometimes 1, sometimes more...* | |
221 | + | |
222 | + | |
223 | +No Referring | |
224 | +------------ | |
225 | +Although XML has many options to refer other docs, SCXML does use none... Except for one place; the “G.1” example in the | |
226 | +w3-specification refers to another (scxml-) file, using XInclude! Without any explaining text nor semantics. I guess the | |
227 | +semantics is like a textual preprocessor: all text in that file should be read as if it was typed-in. That does not | |
228 | +help (me) [#google]_. | |
229 | + | |
230 | + | |
231 | +Some other relevant languages | |
232 | +***************************** | |
233 | + | |
234 | +There are more tools (and there input languages) that can inspire us. They do not directly define a FSM_, but can be | |
235 | +used to visualize it, or use FSMs as part of the languages. | |
236 | + | |
237 | +DOT/graphviz | |
238 | +============ | |
239 | + | |
240 | +.. sidebar:: Links | |
241 | + | |
242 | + * `https://en.wikipedia.org/wiki/DOT_(graph_description_language) | |
243 | + <https://en.wikipedia.org/wiki/DOT_(graph_description_language)>`__ | |
244 | + * https://en.wikipedia.org/wiki/Graphviz | |
245 | + * https://www.graphviz.org | |
246 | + | |
247 | +DOT is language --introduced & used by tool Graphviz-- to describe (mathematical) graphs. It’s a very flexible language: | |
248 | +both undirected and directed “edges” between “nodes” are possible; one can describe trees “woods” and more, which can | |
249 | +be cyclic (or not). When introduced (together with the autorouters graphviz), over 30 years ago, it hit the marked ... | |
250 | +|BR| | |
251 | +Suddenly we could describe & show anything ... Including state-diagrams. | |
252 | + | |
253 | +DOT, as a language, can’t define a FSM -even we can show the state-transitions. And nowadays one would prefer plantUML | |
254 | +(which used graphviz) to that. | |
255 | +|BR| | |
256 | +But it has learned us that state-transition (arrows, or edges in a graph) can be described in text as simple as | |
257 | +:samp:`{current} --> {next}`. A syntax we will reuse in Castle. | |
258 | + | |
259 | +.. _Dezyne: | |
260 | + | |
261 | +Verum’s Dezyne | |
262 | +============== | |
263 | + | |
264 | +.. sidebar:: Links | |
265 | + | |
266 | + - https://dezyne.org | |
267 | + - https://gitlab.com/dezyne | |
268 | + - https://verum.com/discover-dezyne/ | |
269 | + - https://dezyne.org/dezyne/manual/dezyne/html_node/A-Simple-State-Machine.html | |
270 | + | |
271 | +Dezyne (now open-source) is a programming language (with a set of tools) to implement (embedded) controll software. One | |
272 | +can also create state-machines with it. So that part of the language can inspire Castle. We use `this Tutorial | |
273 | +<https://dezyne.org/dezyne/manual/dezyne/html_node/A-Simple-State-Machine.html>`__ example as reference. | |
274 | + | |
275 | +In this example the `behavior` is described in an (mostly) `“Imperative” | |
276 | +<https://en.wikipedia.org/wiki/Imperative_programming>`__ (normal) style of programming [#dezyne-semantics]_, mixed with | |
277 | +events (``on`` keywords) and guards (:samp:`[{bool-expr}]`, like above). Therefore this simple FSM is implemented in a | |
278 | +phraseology that is very close to the nested-switch one. The outer switch is replaced by pillar of guards (The lines starting | |
279 | +with ``[]`` can we top-levels cases); the inner switch by ``on`` “event-handler”. | |
280 | + | |
281 | +|BR| | |
282 | +Not shown in this example, but one use the reverted style (as far as I know). | |
283 | + | |
284 | +In away, it also resembles the “factor the state out” style as described above in the “tables” -- although de developer | |
285 | +has to use an assign-statement to change state; unlike above where naming the new state will do [#dezyne-state]_. | |
286 | +|BR| | |
287 | +Assuming one can use the “reverted” (nested-switch) style too, it is in Dezyne possible to (“in a way”) factor-out the | |
288 | +inputs (instead of the state). None of the examples above where able to this. | |
289 | + | |
290 | +For Castle, if (and only if) we enable this factor-out option (even when we do not endorse it), I would prefer to have | |
291 | +this symmetry (as in Dezyne): one can factor-out both state and/or inputs! As shown in the example, the syntax for both | |
292 | +switches is a differs a bit. By such a contrast in syntax, its become cleare wich “ID” is state an which one it de | |
293 | +“input”. And thus we can allow to swap the order, and so, it becomes possible to factor-out both. #Nice | |
294 | + | |
295 | +BTW, Dezyne uses both “declarative” and “imperative” statements. As we describe in :ref:`Declarative-programming` Castle | |
296 | +will promote this declarative style; it’s great to declare a FSM (over implement it in an imperative style). And I have | |
297 | +no glue why Dezyne made another choice... | |
298 | + | |
299 | +Ragel | |
300 | +===== | |
301 | + | |
302 | +.. sidebar:: Links | |
303 | + | |
304 | + - https://en.wikipedia.org/wiki/Ragel | |
305 | + - http://www.colm.net/open-source/ragel/ | |
306 | + - https://en.wikipedia.org/wiki/Thompson%27s_construction | |
307 | + | |
308 | +Ragel is also a FSM-compiler, but unlike SMC_ is does not need ``rules`` as input. It uses RegExps as input! | |
309 | +|BR| | |
310 | +There is not a lot of documentation on the input however. But is has a interesting approach. | |
311 | + | |
312 | +It looks like one can define “paths” [#path-vs-step]_ by specifying some RegExps. Regel builds a NFA_ by using | |
313 | +`Thompson's construction algorithm <https://en.wikipedia.org/wiki/Thompson%27s_construction>`__, out of those | |
314 | +RegExps. So, the developer doesn't need tho specify which ``states`` nor ``rules`` are needed; only all the allowed | |
315 | +paths (or routes). | |
316 | + | |
317 | +Actions are also possible. They are “added” to the route (but do not consume input, so like a | |
318 | +:math:`\epsilon`-transition. | |
319 | + | |
320 | + | |
321 | +Remarks (general) | |
322 | +****************** | |
323 | +Based on the evaluation of these tools/languages, we can make some general remarks. Especially where relevant for the | |
324 | +design of the syntax of Castle. | |
325 | + | |
326 | +Transitions & Symmetry | |
327 | +====================== | |
328 | + | |
329 | +Many tools use a syntax (and/or terminology) that is not inline with the (original) FSM_ (mathematical) model; | |
330 | +especially for a “transition”: | |
331 | +|BR| | |
332 | +(We ignore the ``actions`` for a while, here). | |
333 | + | |
334 | +* Tools like SMC_ and SCXML_ see **the transition** as *“the arrow between 2 states”* The input-event is then like a | |
335 | + attribute of that transition. | |
336 | + |BR| | |
337 | + So we have ``states`` and ``transition``. | |
338 | + | |
339 | +* Whereas others -- like Dezyne_ and plantUML_\-- (and the theory) sees **transitions** as *the relation between 3 | |
340 | + parts*: from ``state`` and ``input (event)`` toward the next ``state``. | |
341 | + |BR| | |
342 | + So we have ``states``, ``inputs/events`` and ``transitions`` (or rules). | |
343 | + | |
344 | +The implication of “employing an events as attribute of a transition”, is that one can factor-out states, but nog events | |
345 | +anymore. Wheres when using ``state`` and ``event`` as more symmetrical pair; one can factor-out either the state, *or* | |
346 | +the event -- as shown in e.g. the “revered” code example. | |
347 | + | |
348 | +* The (basic) UncleBob’s version of SMC uses this more symmetrical model -- which leads to compact table. | |
349 | + |BR| | |
350 | + But as the whitespace formating, does not allow to change the order of state/event; only factoring-out over the 1ste | |
351 | + is possible. | |
352 | + | |
353 | +Hierarchy | |
354 | +========= | |
355 | + | |
356 | +Several formats do kind-of embrace the hierarchical states, but only in an inline-notation. Which effectively cancel the | |
357 | +effect of hierarchy. A figure that displays states “nested” inside states (as plantUML can produce) is showning | |
358 | +hierarchy. But not the kind of hierarchy that we need/like to construct a complex FSM_ | |
359 | + | |
360 | +To construct a hierarchical FSM, we like to: | |
361 | + | |
362 | +#. Define a “main” FSM with states in one place | |
363 | +#. Consider each (or some) state of that (upper) FSM as “lower” sub-FSMs itself | |
364 | +#. Add (later, and “in another file”) sub-states by adding details to *only* that state. | |
365 | +#. Are able to add more and more details, by “redefining” a state as small FSM in itself. | |
366 | + | |
367 | +Independent of those “isolated details”, it would be nice when ‘Castle’ can flaten-out the hierarchy and draw the | |
368 | +“nested” variant. Or even beter: can display a partial flattened-out one; depending on the focus the developer has on | |
369 | +that comment. | |
370 | + | |
371 | +Compactness | |
372 | +=========== | |
373 | + | |
374 | +Inline with the general need as described in :ref:`Declarative-programming`, we can already conclude that a declarative | |
375 | +style for FSM_\s is more compact then a imperative style where one (also) ahs to specify some implementation details | |
376 | +(like: assigning the next state). | |
377 | + | |
378 | +A style as used in Ragel_ --to specify paths, not steps--, is potential even more compact. Especially when the input are | |
379 | +characters -- which is not ge the general case. | |
380 | +|BR| | |
381 | +It may be also one step to far, as in MAYA (Most Advanced Yet Acceptable). | |
382 | + | |
383 | + | |
384 | +------- | |
385 | + | |
386 | +.. rubric:: Footnotes | |
387 | + | |
388 | +.. [#final-action] | |
389 | + The final-states are used by mathematics to verify/accept an input. Whereas a SW-FSM is typically used to control a | |
390 | + system; and run *forever*. When a “final state” is needed in a SW-FSM, typical a “final-action” is used. | |
391 | + | |
392 | +.. [#non-determinism] | |
393 | + Remember, we have to support non-determinism! Each cell in the matrix can have multiple “next states” (and | |
394 | + corresponding actions). | |
395 | + | |
396 | +.. [#plantUML-arrows] | |
397 | + By example: the *arrows* in plantUML can have varions lengths (`->` , `-->`, `--->`) to hint plantUML how to draw; | |
398 | + this has no (functional) meaning. This is very conviant for a *drawing tool*, not for a programming-language. | |
399 | + | |
400 | +.. [#indirect] | |
401 | + This is not completely correct. By ‘nesting’ one has the advantages of sharing higher rules. | |
402 | + | |
403 | +.. [#generated] | |
404 | + This is generated code, and should not be touched. Therefor the maintainability-issue does not occur; just | |
405 | + re-renerate the class! | |
406 | + | |
407 | +.. [#hierarchically-split] | |
408 | + IMHO the goal of the hierarchy is to be able to split the “source” of the main-state/FSM and the | |
409 | + detailed-states. Developers are used to devide functionality over modules/components -- and so text-files. And | |
410 | + practice this every time details are added. | |
411 | + | |
412 | +.. [#voice] | |
413 | + As a practical limitation one should mention that both the standard and may examples have a voice (over IP) | |
414 | + background. Which makes the understandability for the *general* case a bit hard. | |
415 | + | |
416 | +.. [#google] | |
417 | + When `googling for scxml + xinclude <https://www.google.com/search?q=scxml+xinclude>`__ one find a few hits. Like | |
418 | + the comment/question “is it an omission” (as it was descriped in a draft), or “is it removed” from the spec (and | |
419 | + *forgotten* to update the example)? | |
420 | + |BR| | |
421 | + There is no clear answer, but is appears that `XInclude` is kind of a general XML-facility; that have to be applied | |
422 | + first (before using scxml). Which resembles the preprocessor. So I give up [#xml-more]_ | |
423 | + | |
424 | +.. [#xml-more] | |
425 | + I was kind of hoping that one coud refer to a part in another file. Like we have a common “library” scxml-file and | |
426 | + use (the definitions of) a few “states” in that file. Apparently not ... | |
427 | + | |
428 | +.. [#dezyne-semantics] | |
429 | + Notice that the style of Dezyne resembles (or “feels as”) imperative programming, but the semantics do differ! | |
430 | + | |
431 | +.. [#dezyne-state] | |
432 | + Dezyne has no “states” (at tupe/words) -- at least not in the found FSMs. Is create state by assigning value to | |
433 | + variable; that act as stare (like in C). Probably one can use the Enum type to define (simulate) state; but still one | |
434 | + has to assign that value to a variable. | |
435 | + | |
436 | +.. [#path-vs-step] | |
437 | + In a FSM (diagram) there are “steps” to go from one state to another. A “path” is a sequence of such a steps. | |
438 | + | |
439 | +.. _FSM: https://en.wikipedia.org/wiki/Finite-state_machine | |
440 | +.. _State pattern: https://en.wikipedia.org/wiki/State_pattern | |
441 | +.. _UML-FSM: https://en.wikipedia.org/wiki/UML_state_machine | |
442 | +.. _NFA: https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton |
@@ -0,0 +1,24 @@ | ||
1 | +FSMs vs Grammars | |
2 | +================= | |
3 | + | |
4 | +In case you are wondering: *“Are FSMs and Grammars related, or the same?”* | |
5 | + | |
6 | +The are related, but not equal. | |
7 | + | |
8 | +As discovered by `Chomsky <https://en.wikipedia.org/wiki/Noam_Chomsky>`__ there is a `hierarchy <https://en.wikipedia.org/wiki/Chomsky_hierarchy>`__ of languages (or actually grammars). As Chomsky was studying all kind of languages, include natural “human” language, his perception differs from our interpretation. |BR| When we (SW/Engineers) speak about grammars, we typically refer to “Context free grammars” (`CFG <https://en.wikipedia.org/wiki/Context-free_grammar>`__) -- Chomsky classify them as “Type-2”. | |
9 | + | |
10 | +A non-deterministic PushDown machine (`PDA <https://en.wikipedia.org/wiki/Pushdown_automaton>`__) is needed to | |
11 | +recognise a “Type-2” (CFG) Grammar. (Which is a simple version of a stack-machine, which is lot more restricted then a Turing Machine). | |
12 | +|BR| | |
13 | +And as a FSM is one of the most restricted machines that exist --it can recognise only “Type-3” `Regular grammar | |
14 | +<https://en.wikipedia.org/wiki/Regular_grammar>`__-- a FSM can’t be used to recognise a (CFG) grammar. | |
15 | + | |
16 | +.. seealso:: | |
17 | + | |
18 | + .. postlist:: | |
19 | + :category: Castle | |
20 | + :tags: FSM | |
21 | + | |
22 | + .. postlist:: | |
23 | + :category: Castle | |
24 | + :tags: Grammar |
@@ -0,0 +1,489 @@ | ||
1 | +.. include:: /std/localtoc2.irst | |
2 | + | |
3 | +.. _ConcurrentComputingConcepts: | |
4 | + | |
5 | +============================= | |
6 | +Concurrent Computing Concepts | |
7 | +============================= | |
8 | + | |
9 | +.. post:: 2022/09/30 | |
10 | + :category: Castle DesignStudy | |
11 | + :tags: Castle, Concurrency | |
12 | + | |
13 | + Sooner as we realize, even embedded systems will have piles & heaps of cores, as I described in | |
14 | + “:ref:`BusyCores`”. Castle should make it easy to write code for all of them: not to keep them busy, but to maximize | |
15 | + speed up [useCase: :need:`U_ManyCore`]. I also showed that threads_ do not scale well for CPU-bound (embedded) | |
16 | + systems. Last, I introduced some (more) concurrency abstractions. Some are great, but they often do not fit | |
17 | + nicely in existing languages. | |
18 | + |BR| | |
19 | + Still, as Castle is a new language, we have the opportunity to select such a concept and incorporate it into the | |
20 | + language. | |
21 | + | |
22 | + In this blog, we explore a bit of theory. I will focus on semantics and the possibilities to implement them | |
23 | + efficiently. The exact syntax will come later. | |
24 | + | |
25 | +Basic terminology | |
26 | +================= | |
27 | + | |
28 | +Many theories are available, as are some more practical expertise, regrettably hardly non of them share a common | |
29 | +vocabulary. For that reason, I first describe some basic terms, and how they are used in these blogs. As always, we use Wikipedia | |
30 | +as common ground and add links for a deep dive. | |
31 | +|BR| | |
32 | +Again, we use ‘task’ as the most generic term for work-to-be-executed; that can be (in) a process, (on) a thread, (by) a | |
33 | +computer, etc. | |
34 | + | |
35 | +.. include:: CCC-sidebar-concurrency.irst | |
36 | + | |
37 | +Concurrent | |
38 | +---------- | |
39 | + | |
40 | +Concurrency_ is the **ability** to “compute” multiple *tasks* at the same time. | |
41 | +|BR| | |
42 | +Designing concurrent software isn’t that complicated but; demands another mindset than when we write software that does | |
43 | +one task after the other. | |
44 | + | |
45 | +A typical example is a loop: suppose we have a sequence of numbers and we like to compute the square of each one. Most | |
46 | +developers will loop over those numbers, get one number, calculate the square, store it in another list, and continue. | |
47 | +It works, but we have also instructed the computer to do it in sequence. Especially when the task is a bit more | |
48 | +complicated, the compiler does know whether the ‘next task’ depends on the current one, and can’t optimize it. | |
49 | + | |
50 | +A better plan is to tell the compiler about different tasks. Most are independent: square a number. There is also one | |
51 | +that has to be run at the end: combine the results into a new list. And one is a bit funny: distribute the elements over | |
52 | +the “square tasks”. Clearly one has to start with this one, but it can be concurrent with many others too. | |
53 | +|BR| | |
54 | +This is *not* a parallel algorithm. When not specifying the order, we allow parallel execution. We do not demand it, | |
55 | +sequential execution is allowed too. | |
56 | + | |
57 | + | |
58 | +Parallelism | |
59 | +----------- | |
60 | + | |
61 | +Parallelism_ is about executing multiple tasks (seemingly) at the same time. We will on focus running many multiple | |
62 | +concurrent tasks (of the same program) on *“as many cores as possible”*. When we assume a thousand cores, we need a | |
63 | +thousand independent tasks (at least) to gain maximal speed up. A thousand at any moment! | |
64 | +|BR| | |
65 | +It’s not only about doing a thousand tasks at the same time (that is not too complicated, for a computer) but also — | |
66 | +probably: mostly — about finishing a thousand times faster… | |
67 | + | |
68 | +With many cores, multiple “program lines” can be executed at the same time, which can introduce unforeseen effects: | |
69 | +changing the same variable, accessing the same memory, or competing for new, “free” memory. And when solving that, we | |
70 | +introduce new hazards: like deadlocks_ and even livelocks_. | |
71 | + | |
72 | + | |
73 | +Distributed | |
74 | +~~~~~~~~~~~ | |
75 | + | |
76 | +A special form of parallelism is Distributed-Computing_: computing on many computers. Many experts consider this | |
77 | +an independent field of expertise. Still --as Multi-Core_ is basically “many computers on a chip”-- it’s an | |
78 | +available, adjacent [#DistributedDiff]_ theory, and we should use it, to design our “best ever language”. | |
79 | + | |
80 | + | |
81 | +.. include:: CCC-sidebar-CS.irst | |
82 | + | |
83 | +Communication Efficiently | |
84 | +========================= | |
85 | + | |
86 | +When multiple tasks run concurrently, they have to communicate to pass data and control progress. Unlike in a | |
87 | +sequential program -- where the control is trivial, as is sharing data-- this needs a bit of extra effort. | |
88 | +|BR| | |
89 | +There are two main approaches: shared-data of message-passing; we will introduce them below. | |
90 | + | |
91 | +Communication takes time, especially *wall time* [#wall-time]_ (or clock time), and may slow down computing. Therefore | |
92 | +communication has to be efficient. This is an arduous problem and becomes harder when we have more communication, more | |
93 | +concurrency, more parallelism, and/or those tasks are short living. Or better: it depends on the ratio of | |
94 | +time-between-communications and the time-between-two-communications. | |
95 | + | |
96 | + | |
97 | +Shared Memory | |
98 | +------------- | |
99 | + | |
100 | +In this model all tasks (usually threads or processes) have some shared/common memory; typically “variables”. As the access | |
101 | +is asynchronous, the risk exists the data is updated “at the same time” by two or more tasks. This can lead to invalid | |
102 | +data and so Critical-Sections_ are needed. | |
103 | +|BR| | |
104 | +This is a very basic model which assumes that there is physical memory that can be shared. In distributed systems this | |
105 | +is uncommon, but for threads it’s straightforward. | |
106 | + | |
107 | +An advantage of shared memory is the fast *communication-time*. The wall-time and CPU-time are roughly the same: the | |
108 | +time to write & read the variable added to the (overhead) time for the critical section -- which is typically the | |
109 | +bigger part. | |
110 | +|BR| | |
111 | +The big disadvantage of this model is that is hazardous: The programmer needs to insert Critical_Sections into his code | |
112 | +at all places that *variable* is used. Even a single access to a shared variable, that is not protected by a | |
113 | +Critical-Section_, can (will) break the whole system [#OOCS]_. | |
114 | + | |
115 | + | |
116 | +Messages | |
117 | +-------- | |
118 | + | |
119 | +A more modern approach is Message-Passing_: a task sends some information to another; this can be a message, some data, | |
120 | +or an event. In all cases, there is a distinct sender and receiver -- and apparently no common/shared memory-- so no | |
121 | +Critical-Sections [#MPCS]_ are needed; at least not explicitly. Messages are easier to use and more generic: they can be | |
122 | +used in single-, multi-, and many-core systems. Even distributed systems are possible -- then the message (and its data) | |
123 | +is serialised, transmitted over a network, and deserialised. | |
124 | + | |
125 | +As you may have noticed, there is an analogy between Message-Passing_ and Events_ (in an event-loop). They have separate | |
126 | +histories but are quite similar in nature. Like a “message”, the “event” is also used to share data (& control) to | |
127 | +isolated “tasks”. | |
128 | + | |
129 | +.. warning:: | |
130 | + | |
131 | + Many people use the networking mental model when they think about Message-Passing_, and *wrongly* assume there is | |
132 | + always serialisation (and network) overhead. This is not needed for parallel cores as they typically have shared | |
133 | + (physical) memory. | |
134 | + | |
135 | + Then, we can use the message abstraction at developer-level, and let the compiler translate that into shared | |
136 | + memory instructions for the processor level. | |
137 | + |BR| | |
138 | + Notice: As the compiler will insert the (low level) Semaphores_, the risk that a developer forgets one is gone! | |
139 | + | |
140 | + | |
141 | +.. include:: CCC-sidebar-MA-links.irst | |
142 | +.. _MPA: | |
143 | + | |
144 | +Messaging Aspects | |
145 | +================= | |
146 | + | |
147 | +There are many variants of messaging, mostly combinations of some fundamental aspects. Let mentions some basic ones. | |
148 | + | |
149 | +(A)Synchronous | |
150 | +-------------- | |
151 | + | |
152 | +**Synchronous** messages resemble normal function calls. Typically a “question” is sent, the call awaits the | |
153 | +answer message, and that answer is returned. This can be seen as a layer on top of the more fundamental send/receive | |
154 | +calls. A famous example is RPC_: the Remote Procedure Call. | |
155 | + | |
156 | +**Asynchronous** messages are more basic: a task sends a message and continues. That message can be “data”, an “event”, | |
157 | +a “command”, or a “query”. Only in the latter case, some response is essential. With async messages, there is no desire | |
158 | +to get the answer immediately. | |
159 | + | |
160 | +As an example: A task can send many queries (and/or other messages) to multiple destinations at once, then go into | |
161 | +*listen-mode*, and handle the replies in the order they are received (which can be different than as sent). Typically, | |
162 | +this speeds up (wall) time, and is only possible with async messages. Notice: the return messages need to carry an “ID” | |
163 | +of the initial messages to keep track -- often that is the query itself. | |
164 | + | |
165 | + | |
166 | +(Un)Buffered | |
167 | +------------ | |
168 | + | |
169 | +Despite it is not truly a characteristic of the message itself, messages can be *buffered*, or not. It is about | |
170 | +the plumbing to transport the message: can this “connection” (see below) *contain/save/store* messages? When there is no | |
171 | +storage at all the writer and reader need to rendezvous: send and receive at the same (wall) time. | |
172 | +|BR| | |
173 | +With a buffer (often depicted as a queue) multiple messages may be sent before they need to be picked up by the | |
174 | +receiver; the number depends on the size of the buffer. | |
175 | + | |
176 | +Note: this is always asymmetric; messages need to be sent before they can be read. | |
177 | + | |
178 | +Connected Channels (or not) | |
179 | +--------------------------- | |
180 | + | |
181 | +Messages can be sent over (pre-) *connected channels* or to freely addressable end-points. Some people use the term | |
182 | +“connection-oriented” for those connected channels, others use the term “channel” more generic and for any medium that | |
183 | +is | |
184 | +transporting messages. I try to use “*connected-channel”* when is a *pre-connected* channel. | |
185 | + | |
186 | +When using connected channels, one writes the message to the channel; there is no need to add the receiver to the | |
187 | +message. Also when reading, the sender is clear. | |
188 | +|BR| | |
189 | +Clearly, the channel has to be set up before it can be used. | |
190 | + | |
191 | +Without connected channels, each message needs a recipient; often that receiver is added (“carried”) to the message | |
192 | +itself. | |
193 | +|BR| | |
194 | +A big advantage is, that one does not need to create channels and end-points first -- which especially counts when a low | |
195 | +number (possible one) of messages are sent to the same receiver, and/or many receivers exist (which would lead to a huge | |
196 | +number of channels). | |
197 | + | |
198 | + | |
199 | +(Non-) Blocking | |
200 | +--------------- | |
201 | + | |
202 | +Both the writer and the reader can be *blocking* (or not); which is a facet of the function-call. A blocking reader it | |
203 | +will always return when a message is available -- and will pause until then. Equally, the write-call can block: pause | |
204 | +until the message can be sent -- e.g. the reader is available (rendezvous) or a message buffer is free. | |
205 | + | |
206 | +When the call is non-blocking, the call will return without waiting and yield a flag whether it was successful or not. | |
207 | +Then, the developer will commonly “cycle” to poll for a profitable call; and let the task do some other/background work | |
208 | +as well. | |
209 | + | |
210 | +Futures (or promises) | |
211 | +~~~~~~~~~~~~~~~~~~~~~ | |
212 | + | |
213 | +A modern variant of non-blocking makes use of “Futures_”. The call will always return this opaque data structure | |
214 | +immediately. It may be a blank -- but the procedure can continue. Eventually, that data will be filled in “by the | |
215 | +background”. It also contains a flag (like ``done``), so the programmer can check (using an if) [#future-CS]_ whether | |
216 | +the data is processed. | |
217 | + | |
218 | + | |
219 | +Uni/Bi-Directional, Many/Broad-cast | |
220 | +----------------------------------- | |
221 | + | |
222 | +Messages can be sent to one receiver, to many, or even to everybody. Usually, this is modeled as a characteristic of the | |
223 | +channel. At the same time, that channel can be used to send messages in one or two directions. | |
224 | + | |
225 | +It depends on the context of the exact intent. For example in (TCP/IP) `networking, ‘Broadcasting’ | |
226 | +<https://en.wikipedia.org/wiki/Broadcasting_(networking)>`__ (all not point-to-point variants) focus on reducing the | |
227 | +amount of data on the network itself. In `distributed computing ‘Broadcasting’ | |
228 | +<https://en.wikipedia.org/wiki/Broadcast_(parallel_pattern)>`__ is a parallel design pattern. Whereas the `‘Broadcast’ | |
229 | +flag <https://en.wikipedia.org/wiki/Broadcast_flag>`_ in TV steaming is completely different: is it allowed to save | |
230 | +(record) a broadcast... | |
231 | + | |
232 | +We use those teams with a functional aim. We consider the above-mentioned RCP connection as **Unidirectional** -- even | |
233 | +the channel can carry the answer. When both endpoints can take the initiative to send messages, we call it | |
234 | +**Bidirectional**. | |
235 | +|BR| | |
236 | +With only 2 endpoints, we call the connection **Point-to-Point** (*p2p*). When more endpoints are concerned, it’s | |
237 | +**Broadcast** when a message is sent to all others (on that channel), and **Manycast** when the user (the programmer) can | |
238 | +(somehow) select a subset. | |
239 | + | |
240 | + | |
241 | +Reliability & Order | |
242 | +------------------- | |
243 | + | |
244 | +Especially when studying “network messages”, we have to consider Reliability_ too. Many developers assume that a send | |
245 | +message is always received and that when multiple messages are sent, they are received in the same order. In most | |
246 | +traditional --single-core-- applications this is always the chase. With networking applications, this is not always | |
247 | +true. Messages can get lost, received out of order, or even read twice. Although it is always possible to add a | |
248 | +“reliability layer”. | |
249 | +|BR| | |
250 | +Such a layer makes writing the application easier but introduces overhead too. And therefore not always the right | |
251 | +solution. | |
252 | + | |
253 | +In Castle, we have “active components”: many cores are running parallel, all doing a part of the overall (concurrent) | |
254 | +program. This resembles a networking application -- even while there is no real network -- where at least three nodes | |
255 | +are active. | |
256 | + | |
257 | +This is a bit more complicated, so let us start with an example. Say, we have 3 components ``A``, ``B1``, and | |
258 | +``B2``. All are connected to all others. We assume that messages are unbuffered, non-blocking, never got lost, and that | |
259 | +two messages over the same channel are never out-of-order. Sound simple, isn’t it? | |
260 | +|BR| | |
261 | +Now state that ``A`` send a message (`m1`) to ``B1`` and then one (`m2`) to ``B1``. The “B components” will --on | |
262 | +receiving a message from ``A`` -- send a short message to the other one (`m3` and `m4`). And that message triggers | |
263 | +(again both in ``B1`` and ``B2``) to send an answer to ``A``; so `m5` and `m6`. | |
264 | + | |
265 | +Now the question is: in which order those answers (in ``A``) are received? The real answer is: **You don’t know!** | |
266 | +|BR| | |
267 | +It’s clear that ``A`` will get `m5` and `m6` -- given that all messages (aka channels) are reliable. But there are many | |
268 | +ways those messages may receive in the opposite order. Presumably, even in more ways, than you can imagine. For example, | |
269 | +``B1`` might process `m4` before it processes `m1`! This can happen when channel ``A->B1`` is *slow*, or when ``B2`` | |
270 | +gets CPU-time before ``B1``, or... | |
271 | + | |
272 | +When we add buffering, more connected components, etc this *“network”* acts less reliable than we might aspect (even | |
273 | +though each message is reliable). When we add some real-time demands (see below), the ability to use/model a solution | |
274 | +using an unreliable message becomes attractive ... | |
275 | +|BR| | |
276 | +It’s not that you should always favor unreliable, out-of-order messages. Without regard, No! We are designing a new | |
277 | +language, however --one that should run efficiently on thousands of core, in a real-time embedded system-- then the | |
278 | +option to utilize them may be beneficial. | |
279 | + | |
280 | + | |
281 | +.. hint:: | |
282 | + | |
283 | + As a simple example to demonstrate the advantage of an “unreliable connection”, let us consider an audio (bidirectional) | |
284 | + connection, that is not 100% reliable. | |
285 | + |BR| | |
286 | + When we use it “as is”, there will be a bit of noise, and even some hick-ups. For most people, this is acceptable, | |
287 | + when needed they will use phrases such as *“Can you repeat that?”*. | |
288 | + | |
289 | + To make that connection reliable, we need checksums, low-level confirmation messages, and once in a while have to send | |
290 | + a message again. This implies some buffering (at both sides), and so the audio stream will have a bit of delay. | |
291 | + This is a common solution for unidirectional PODcasts, and such. | |
292 | + | |
293 | + For a bidirectional conversation, however, this buffering is not satisfactory. It makes the *slow*, people have to wait | |
294 | + on each other and will interrupt one other. | |
295 | + |BR| | |
296 | + Then, a *faster* conversation with a bit of noise is commonly preferred. | |
297 | + | |
298 | + | |
299 | +Process calculus & more | |
300 | +======================= | |
301 | + | |
302 | +After studying many concurrent concepts, we need to address one more, before we can *design* the Castle language. That is | |
303 | +“*How do we determine what is ‘best’ (ever)*”? Can we *calculate* the performance of every aspect? The answer is no; | |
304 | +but there are formal systems that can help: Process-Calculus_ (or -Algebra). | |
305 | +|BR| | |
306 | +Unfortunately, there are many of them. And I like to avoid the recursions-trap: study them all, find a meta-calculus | |
307 | +to determine the best, etc. | |
308 | + | |
309 | +So let us give a quick overview. And recall, the term ‘process’ is pretty general: it denotes the *behavior of a | |
310 | +system*, not the more limited practice most software developers use. | |
311 | + | |
312 | +.. include:: CCC-sidebar-calc-demo.irst | |
313 | + | |
314 | +Mathematical models | |
315 | +------------------- | |
316 | + | |
317 | +Many Process-Calculus_\es are invented around 1980. As often, those traditional ones focus on the issues that were current | |
318 | +back then. And although they are still useful, they might be unaware of modern aspects of computing -- like huge code | |
319 | +bases, and over a thousand cores. | |
320 | + | |
321 | +Petri Ne | |
322 | +~~~~~~~~~ | |
323 | + | |
324 | +Probably the oldest mathematical model to describe distributed systems is the Petri-Net_, invented in 1962 -- some claim | |
325 | +it even started in 1939(!). In its graphical representation, it looks like a network of circles (‘places’) and bars, | |
326 | +(‘actions’) connected by arrows (‘arcs’). It also contains ‘tokens’ -- zero or more dots inside a circle. They can | |
327 | +flow through the network and kind of represent the (global) state. | |
328 | +|BR| | |
329 | +There is an extensive, complex mathematical model behind this. Which makes Petri-Net_\s very powerful. | |
330 | + | |
331 | +A drawback however is, that all tokens have to move to the next place at the same time. When using Petri-Net_\s as a | |
332 | +calculus, this is not an issue. But it becomes impossible to execute that in a distributed (or Multi-Core) environment, | |
333 | +or a base of a language. | |
334 | + | |
335 | +Communicating sequential processes | |
336 | +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | |
337 | + | |
338 | +CSP_ is probably the best-known *formal* language to describe (patterns in) concurrent systems. It started in 1978 as a | |
339 | +kind of programming language and has evolved since then. Occam_ --the language to program the once famous Transputer_-- | |
340 | +is based on CSP_. | |
341 | + | |
342 | +Also ‘Go_’ (the language) is influenced by CSP_. A sign the CSP_ isn’t too old. | |
343 | + | |
344 | +Calculus of Communicating Systems | |
345 | +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | |
346 | + | |
347 | +CCS_ is also quite old (1980) and quite useful to calculate deadlocks_ and livelocks_ | |
348 | + | |
349 | +Algebra of Communicating Processes | |
350 | +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | |
351 | + | |
352 | +Also, ACP_ dates back from 1982 and is a real algebra -- it probably contrived the general term Process-Calculus_. Like | |
353 | +any algebra, it has (transformation) “rules” [#bool-algebra]_. | |
354 | +|BR| | |
355 | +By those *rules*, one can convert (“transform”) a process of concurrent and/or sequential actions into other, equivalent | |
356 | +processes -- and prove they are the same (or nor). And look for patterns that should not (never) happen; like deadlocks_ | |
357 | +and livelocks_. | |
358 | + | |
359 | +I like this algebra aspect, as we can use it inside some :ref:`Castle-Tools` to validate the design is sound. | |
360 | + | |
361 | +Π-calculus | |
362 | +~~~~~~~~~~ | |
363 | + | |
364 | +Pi-Calculus_ is a more recent (1992) addition to the family of Process-Calculus_\es. It allows some dynamic behavior; | |
365 | +like transmitting the names of the channel -- which facilitates the growth & reconfiguration of the network during execution. | |
366 | +|BR| | |
367 | +That expect, for example, is needed for the :ref:`CC-example-Sieve`. | |
368 | +|BR| | |
369 | +It also shows some of the shortcomings of “traditional” models, as hinted above. | |
370 | + | |
371 | +As it is a small (but expressive) “language”, that resembles λ-calculus a bit, it has some omissions too: no numbers, | |
372 | +no functions, not even an `if-statement` (all quite fundamental for a programming language). It is based on **names**, | |
373 | +which mirror both *variables* and *channels*. | |
374 | + | |
375 | +.. _CCC-Actors: | |
376 | + | |
377 | +The Actor Model | |
378 | +--------------- | |
379 | + | |
380 | +The Actor-Model_ is strictly speaking not a Process-Calculus_, but it has many similarities. A big dissimilarity is its | |
381 | +inspiration; where a Process-Calculus_ are based on mathematics, the Actor-Model_ is inspirited by physics. See | |
382 | +Calculus-vs-Actors_ for more on their (dis)similarities. | |
383 | +|BR| | |
384 | +The Actor-Model_ began in 1973, matured in the '80s, and become fashionable when “cloud computing” started. There are | |
385 | +many “bold-on” actor packages for almost all popular languages. They focus mostly on *robust, scalable, distributed | |
386 | +applications*; less on the speed-up of a single program. Still, the :ref:`”Many-Core” concept<CC>` we use for Castle | |
387 | +is closely related. | |
388 | + | |
389 | +Being inspired by physics, which is concurrent by nature, the perception differs. An *actor* is local, “active”, and | |
390 | +independent. It can only act on the messages that it receives, sent new messages, and/or create new actors. It (typically) | |
391 | +has an internal state, but that is completely internal (or *private*, as developers call it). | |
392 | +|BR| | |
393 | +There is no global state, no central synchronisation, no “shared memory”, and no (overall) orchestration. Everything is | |
394 | +decentral. | |
395 | + | |
396 | +One can model many well-known software systems as an Actor-Model_: like email, SOAP, and other web services. Also, | |
397 | +interrupt-handling can be modeled with actors: An extern message triggers the “*interrupt-handler* actor” --async of the | |
398 | +main code; another *actor*-- which has to send data (aka a message) to the main actor. | |
399 | + | |
400 | +Another interesting dissimilarity is that the Actor-Model_, and the Actor-Model-Theory_, are also influent by | |
401 | +SW-Engineering and their languages. This probably made is also convenient to design new programming languages on this | |
402 | +theory. | |
403 | + | |
404 | +.. resolution:: Castle will use Actors as the main Concurrent Computing Concept | |
405 | + :ID: R_CCC-Actors | |
406 | + :links: U_ManyCore | |
407 | + | |
408 | +.. tip:: Unlike Process-Calculus_\es, there is only one Actor-Model_ | |
409 | + | |
410 | +---------- | |
411 | + | |
412 | +.. rubric:: Footnotes | |
413 | + | |
414 | +.. [#DistributedDiff] | |
415 | + There a two (main) differences between Distributed-Computing_ and Multi-Core_. Firstly, all “CPUs” in | |
416 | + Distributed-Computing_ are active, independent, and asynchronous. There is no option to share a “core” (as | |
417 | + commonly/occasionally done in Multi-process/Threaded programming); nor is there “shared memory” (one can only send | |
418 | + messages over a network). | |
419 | + |BR| | |
420 | + Secondly, collaboration with (network-based) messages is a few orders slower than (shared) memory communication. This | |
421 | + makes it harder to speed up; the delay of messaging shouldn't be bigger than the acceleration when doing things in | |
422 | + parallel. | |
423 | + |BR| | |
424 | + But that condition does apply to Multi-Core_ too. Although the (timing) numbers do differ. | |
425 | + | |
426 | +.. [#wall-time] | |
427 | + As a reminder: We speak about *CPU-time* when we count the cycles that make a core busy; so when a core is waiting, no | |
428 | + CPU-time is used. And we use *wall-time* when we time according to “the clock on the wall”. | |
429 | + | |
430 | +.. [#OOCS] | |
431 | + The brittleness of Critical-Sections_ can be reduced by embedding (the) (shared-) variable in an OO abstraction. By | |
432 | + using *getters and *setters*, that control the access, the biggest risk is (mostly) gone. That does not, however, | |
433 | + prevent deadlocks_ or livelocks_. | |
434 | + |BR| | |
435 | + And still, all developers have to be disciplined to use that abstraction ... *always*. | |
436 | + | |
437 | +.. [#MPCS] | |
438 | + This is not completely correct; Message-Passing_ can be implemented on top of shared memory. Then, the implementation | |
439 | + of this (usually) OO-abstraction contains the Critical-Sections_; a bit as described in the footnote above. | |
440 | + | |
441 | +.. [#timesCPU] | |
442 | + And the overhead will grow when we add more cores. Firstly while more “others” have to wait (or spin), and secondly | |
443 | + that the number of communications will grow with the number of cores too. As described in the :ref:`sidebar | |
444 | + <Threads-in-CPython>` within :ref:`BusyCores` solving this can give more overhead than the speed we are aiming for. | |
445 | + | |
446 | +.. [#future-CS] | |
447 | + Remember: to be able to “fill in” that Future-object “by the background” some other thread or so is needed. And so, a | |
448 | + Critical-Section_ is needed. For the SW-developer the interface is simple: read a flag (e.g. ``.done()``. But using | |
449 | + that too often can result in a slow system. | |
450 | + | |
451 | +.. [#anycast] | |
452 | + Broadcasting_ is primarily known for “network messages”; where it has many variants -- mostly related to the | |
453 | + physical network abilities, and the need to save bandwidth. As an abstraction, they can be used in “software messages” | |
454 | + (aka message passing) too. | |
455 | + | |
456 | +.. [#bool-algebra] | |
457 | + Those ‘rules’ resembles the boolean algebra, that most developers know: `NOT(x OR y) == NOT(x) AND NOT(y)`. See | |
458 | + Wikipedia for examples of ACP_. | |
459 | + | |
460 | +.. _ACP: https://en.wikipedia.org/wiki/Algebra_of_communicating_processes | |
461 | +.. _Actor-Model-Theory: https://en.wikipedia.org/wiki/Actor_model_theory | |
462 | +.. _Actor-Model: https://en.wikipedia.org/wiki/Actor_model | |
463 | +.. _Broadcasting: https://en.wikipedia.org/wiki/Broadcasting_(networking) | |
464 | +.. _CCS: https://en.wikipedia.org/wiki/Calculus_of_communicating_systems | |
465 | +.. _CSP: https://en.wikipedia.org/wiki/Communicating_sequential_processes | |
466 | +.. _Calculus-vs-Actors: https://en.wikipedia.org/wiki/Actor_model_and_process_calculi | |
467 | +.. _Concurrency: https://en.wikipedia.org/wiki/Concurrency_(computer_science) | |
468 | +.. _Critical-Section: https://en.wikipedia.org/wiki/Critical_section | |
469 | +.. _Critical-Sections: Critical-Section_ | |
470 | +.. _Distributed-Computing: https://en.wikipedia.org/wiki/Distributed_computing | |
471 | +.. _Events: https://en.wikipedia.org/wiki/Event_(computing) | |
472 | +.. _Futures: https://en.wikipedia.org/wiki/Futures_and_promises | |
473 | +.. _Go: https://en.wikipedia.org/wiki/Go_(programming_language) | |
474 | +.. _Message-Passing: https://en.wikipedia.org/wiki/Message_passing | |
475 | +.. _Multi-Core: https://en.wikipedia.org/wiki/Multi-core_processor | |
476 | +.. _Occam: https://en.wikipedia.org/wiki/Occam_(programming_language) | |
477 | +.. _Petri-Net: https://en.wikipedia.org/wiki/Petri_net | |
478 | +.. _Pi-Calculus: https://en.wikipedia.org/wiki/Π-calculus | |
479 | +.. _Process-Calculus: https://en.wikipedia.org/wiki/Process_calculus | |
480 | +.. _RPC: https://en.wikipedia.org/wiki/Remote_procedure_call | |
481 | +.. _Reliability: https://en.wikipedia.org/wiki/Reliability_(computer_networking) | |
482 | +.. _Semaphores: https://en.wikipedia.org/wiki/Semaphore_(programming) | |
483 | +.. _Spinlocking: https://en.wikipedia.org/wiki/ | |
484 | +.. _Threads: https://en.wikipedia.org/wiki/Thread_(computing) | |
485 | +.. _Transputer: https://en.wikipedia.org/wiki/Transputer | |
486 | +.. _deadlocks: https://en.wikipedia.org/wiki/Deadlock | |
487 | +.. _livelocks: https://en.wikipedia.org/wiki/Deadlock#Livelock | |
488 | +.. _parallelism: https://en.wikipedia.org/wiki/Parallel_computing | |
489 | +.. _pthreads: https://en.wikipedia.org/wiki/Pthreads |
@@ -0,0 +1,31 @@ | ||
1 | +.. -*-rst-*- | |
2 | + included in `8.BusyCores-concepts.rst` | |
3 | + | |
4 | +.. sidebar:: About Critical Sections | |
5 | + | |
6 | + For those, who are not familiar with Critical-Sections_ or Semaphores_, here is a short intro. | |
7 | + | |
8 | + .. rubric:: Dilemma: Statements are not atomic. | |
9 | + | |
10 | + Unlike some developers presume, *“code lines”* are not *‘atomic’*: they can be interrupted. When using (e.g.) threads_, | |
11 | + the “computer” can pause one thread halfway through a statement to run another one temporally and continue a millisecond | |
12 | + later. When it happens during writing or reading a variable, and the other thread also accesses the same shared-memory, | |
13 | + the result is unpredictable. To prevent that, we need to control the handling of that variable: make it a | |
14 | + Critical-Section_. | |
15 | + | |
16 | + .. rubric:: Solve it by marking sections *‘exclusive’*. | |
17 | + | |
18 | + Essentially, we need to tell the “computer” that a line (or a few lines) is *atomic*. To enforce the access is | |
19 | + exclusive, the compiler will add some fundamental instructions (specific for that type of CPU) to assure this. A | |
20 | + check is inserted just before the section, which can suspend the thread when another task is in the CS. When access | |
21 | + is granted, a bit of bookkeeping is needed -- so that the “check” in other threads will halt). That bookkeeping is | |
22 | + updated when leaving, along with more bookkeeping to un-pause the suspended threads. | |
23 | + | |
24 | + .. rubric:: Complication: overhead! | |
25 | + | |
26 | + As you can imagine, this “bookkeeping” is extra complicated on a Multicore system; some global data structure is | |
27 | + needed, which is a Critical-Section_ in itself. | |
28 | + |BR| | |
29 | + There are many algorithms to solve this. All with the same disadvantage: it takes a bit of time -- possible by | |
30 | + “Spinlocking_” all other cores (for a few nanoseconds). As Critical-Sections a usually short (e.g. one assignment, or | |
31 | + a few lines) the overhead can be (relatively) huge [#timesCPU]_! |
@@ -0,0 +1,56 @@ | ||
1 | +.. -*-rst-*- | |
2 | + included in `8.BusyCores-concepts.rst` | |
3 | + | |
4 | +.. sidebar:: More on Messages | |
5 | + | |
6 | + There are two ways to look at messages: *“vertically”* [#V]_ or *“horizontally”* [#H]_. The first concentrates on the | |
7 | + endpoint: How does a programmer use the (API) interface? Alternatively, one can concentrate on the channel between the | |
8 | + endpoints --ignoring lower implementation details. | |
9 | + | |
10 | + More in this, and all kinds of aspects, and many more views can be found --as usual-- on Wikipedia. | |
11 | + | |
12 | + .. tabs:: | |
13 | + | |
14 | + .. tab:: Endpoints | |
15 | + | |
16 | + Words such as *synchronous*, *asynchronous* (and the popular ``async`` keyword) can have many intents -- all more or less | |
17 | + related (on basic fundamental theories) but can be very dissimilar in practical applications. Besides, most theories assume a | |
18 | + *communication* background, not a (software) engineering one, and certainly not an abstraction -- but still, it is a sound base. | |
19 | + | |
20 | + * `Asynchrony Computer Programming <https://en.wikipedia.org/wiki/Asynchrony_(computer_programming)>`_ | |
21 | + * `Asynchronous communication <https://en.wikipedia.org/wiki/Asynchronous_communication>`_ | |
22 | + * `Synchronous serial communication <https://en.wikipedia.org/wiki/Synchronous_serial_communication>`_ | |
23 | + * `Synchronisation (as a generic term) <https://en.wikipedia.org/wiki/Synchronization>`_ | |
24 | + | |
25 | + .. tab:: Channels | |
26 | + | |
27 | + Some aspects are more related to the *channel* used to transmit the message than how end-points act. | |
28 | + | |
29 | + Traditionally, *blocking* used to be applied to I/O operations. Nowadays, it’s more generic: how to behave | |
30 | + when immediate execution is impossible. Although often, IO is involved deep down -- ``printf`` is an example; | |
31 | + it will *pauze* until the line can be published, ot there is space in a buffer. | |
32 | + | |
33 | + * `Communication channel <https://en.wikipedia.org/wiki/Communication_channel>`_ | |
34 | + * `Blocking <https://en.wikipedia.org/wiki/Blocking_(computing)>`_ | |
35 | + * `Buffers <https://en.wikipedia.org/wiki/Data_buffer>`_ | |
36 | + * `Reliable <https://en.wikipedia.org/wiki/Reliability_(computer_networking)>`_ | |
37 | + * `Connection-Oriented <https://en.wikipedia.org/wiki/Connection-oriented_communication>`_ | |
38 | + * `Packet-Oriented <https://en.wikipedia.org/wiki/Packet_switching>`_ | |
39 | + | |
40 | + .. tab:: disambiguation | |
41 | + | |
42 | + Wikipedia has more; even pages that collect pages with more: | |
43 | + | |
44 | + * `Async <https://en.wikipedia.org/wiki/Asynchrony>`_ | |
45 | + * `Sync <https://en.wikipedia.org/wiki/Sync>`_ | |
46 | + * `Synchronization (disambiguation) <https://en.wikipedia.org/wiki/Synchronization_(disambiguation)>`_ | |
47 | + | |
48 | + | |
49 | + | |
50 | + .. [#V] | |
51 | + It is called “vertical” as this interface/function will use other functions, deeper in the | |
52 | + communication-stack. So, the flow is downwards (or upwards on the other side). | |
53 | + | |
54 | + .. [#H] | |
55 | + The “horizontal” direction does not follow the call-stack, but (virtually) connects two stack-levels in different | |
56 | + environments. |
@@ -0,0 +1,48 @@ | ||
1 | +.. -*-rst-*- | |
2 | + included in `8.BusyCores-concepts.rst` | |
3 | + | |
4 | +.. sidebar:: Some examples/Demos | |
5 | + | |
6 | + .. tabs:: | |
7 | + | |
8 | + .. tab:: Petri Net | |
9 | + | |
10 | + .. figure:: Wikipedia-PetriNet.gif | |
11 | + | |
12 | + A trivail PetriNet; image by `Wikipedia <https://commons.wikimedia.org/wiki/File:Animated_Petri_net_commons.gif>`__ | |
13 | + | |
14 | + .. tab:: ACP | |
15 | + | |
16 | + .. rubric:: Basic rules | |
17 | + | |
18 | + .. math:: | |
19 | + | |
20 | + x + y &=& y + x | |
21 | + | |
22 | + (x+y)+z&=& x+(y+z) | |
23 | + | |
24 | + x+x&=&x | |
25 | + | |
26 | + (x+y)\cdot z &=& (x\cdot z) + (y\cdot z) | |
27 | + | |
28 | + (x \cdot y)\cdot z &=& x \cdot (y \cdot z) | |
29 | + | |
30 | + .. rubric:: Deadlock | |
31 | + | |
32 | + .. math:: | |
33 | + | |
34 | + \delta + x &=& x | |
35 | + | |
36 | + \delta \cdot x &=& \delta | |
37 | + | |
38 | + All formulas from `wikipedia <https://en.wikipedia.org/wiki/Algebra_of_communicating_processes>`__ | |
39 | + | |
40 | + .. tab:: Π-calculus | |
41 | + | |
42 | + .. rubric:: Creation of a name | |
43 | + | |
44 | + Create the *name* ``x`` that acts as a (new) communication channel. This is done *process* ``P``. | |
45 | + | |
46 | + .. math:: \left(\nu x\right)P | |
47 | + | |
48 | + |
@@ -0,0 +1,35 @@ | ||
1 | +.. -*-rst-*- | |
2 | + included in `8.BusyCores-concepts.rst` | |
3 | + | |
4 | +.. sidebar:: | |
5 | + | |
6 | + .. tabs:: | |
7 | + | |
8 | + .. tab:: Sequential | |
9 | + | |
10 | + Here, the programmer has (unwittingly) defined a sequential order. | |
11 | + | |
12 | + .. code-block:: python | |
13 | + | |
14 | + L2 = [] | |
15 | + for n in L1: | |
16 | + L2.append(power(n)) | |
17 | + | |
18 | + .. note:: As ``power()`` could have side effects, the compiler **must** keep the defined order! | |
19 | + | |
20 | + .. tab:: Concurrent | |
21 | + | |
22 | + Now, without a specified order, the same functionality has become concurrent. | |
23 | + | |
24 | + .. code-block:: python | |
25 | + | |
26 | + L2 = [power(n) for n in L1] | |
27 | + | |
28 | + .. note:: | |
29 | + | |
30 | + Although (current) python-compilers will run it sequentially, it is *allowed* to distribute it; even when | |
31 | + ``power()`` has side effects! | |
32 | + |BR| | |
33 | + As long as *python* put the results in the correct order in list ``L2`` **any order** is allowed. “Out of | |
34 | + order” side effects are allowed by this code. | |
35 | + |
@@ -0,0 +1,34 @@ | ||
1 | +.. -*- rst -*- | |
2 | + included in `5.eval-syntax.rst` | |
3 | + | |
4 | +.. sidebar:: | |
5 | + | |
6 | + .. tabs:: | |
7 | + | |
8 | + .. code-tab:: xml Example | |
9 | + | |
10 | + <?xml version="1.0" encoding="UTF-8"?> | |
11 | + <scxml xmlns="http://www.w3.org/2005/07/scxml" version="1.0" initial="ready"> | |
12 | + <state id="ready"> | |
13 | + <transition event="watch.start" target="running" /> | |
14 | + </state> | |
15 | + <state id="running"> | |
16 | + <transition event="watch.split" target="paused" /> | |
17 | + <transition event="watch.stop" target="stopped" /> | |
18 | + </state> | |
19 | + <state id="paused"> | |
20 | + <transition event="watch.stop" target="stopped" /> | |
21 | + <transition event="watch.unsplit" target="running" /> | |
22 | + </state> | |
23 | + <state id="stopped"> | |
24 | + <transition event="watch.reset" target="ready" /> | |
25 | + </state> | |
26 | + </scxml> | |
27 | + | |
28 | + .. tab:: Links | |
29 | + | |
30 | + .. seealso:: | |
31 | + | |
32 | + * wikipedia https://en.wikipedia.org/wiki/SCXML | |
33 | + * W3 (specification): https://www.w3.org/TR/scxml/ | |
34 | + * `Source of shown example <https://blogs.itemis.com/en/custom-code-generator-scxml>`__ (itemis blog) |
@@ -0,0 +1,84 @@ | ||
1 | +.. -*- rst -*- | |
2 | + included in `5.eval-syntax.rst` | |
3 | + | |
4 | +.. sidebar:: | |
5 | + | |
6 | + .. tabs:: | |
7 | + | |
8 | + .. tab:: SMC (example) | |
9 | + :selected: | |
10 | + | |
11 | + .. code:: | |
12 | + | |
13 | + Initial: Locked | |
14 | + FSM: Turnstile | |
15 | + { | |
16 | + Locked Coin Unlocked unlock | |
17 | + Locked Pass Locked alarm | |
18 | + Unlocked Coin Unlocked thankyou | |
19 | + Unlocked Pass Locked lock | |
20 | + } | |
21 | + | |
22 | + --- source: `Uncle Bob <https://github.com/unclebob/CC_SMC/blob/master/README.md>`__. | |
23 | + |BR| | |
24 | + Showing a basic FSM only; see the website for more examples. | |
25 | + | |
26 | + | |
27 | + .. tab:: Grammars (BNF) | |
28 | + | |
29 | + UncleBob’s version | |
30 | + | |
31 | + .. code:: BNF | |
32 | + | |
33 | + <FSM> ::= <header>* <logic> | |
34 | + <header> ::= <name> ":" <name> | |
35 | + <logic> ::= "{" <transition>* "}" | |
36 | + <transition> ::= <state-spec> <subtransition> | |
37 | + | <state-spec> "{" <subtransition>* "}" | |
38 | + <state-spec> ::= <state> <state-modifier>* | |
39 | + <state> ::= <name> | |
40 | + | "(" <name> ")" | |
41 | + <state-modifier> ::= ":" <name> | |
42 | + | "<" <name> | |
43 | + | ">" <name> | |
44 | + <subtransition> :: <event> <next-state> <action> | |
45 | + <action> ::= <name> | "{" <name>* "}" | "-" | |
46 | + <next-state> ::= <state> | "-" | |
47 | + <event> :: <name> | "-" | |
48 | + | |
49 | + SMC (sourceforge) version [edited & shortened]. | |
50 | + | |
51 | + .. code:: BNF | |
52 | + | |
53 | + <FSM> ::= <%headers> <map>+ | |
54 | + <%headers> ::= ...Not shown here ... | |
55 | + <map> ::= '%map' <word> '%%' <states> '%%' | |
56 | + <states> ::= <word> <entry>? <exit>? '{' <transitions>* '}' | |
57 | + <entry> ::= 'Entry {' <action>* '}' | |
58 | + <exit> ::= 'Exit {' <action>* '}' | |
59 | + <transitions> ::= <word> <args>? <guard>? <next-state> '{' <action>* '}' | |
60 | + <args> ::= '(' <parameter>+ ')' | |
61 | + <parameter> ::= <word> ':' <raw-code> | |
62 | + <guard> ::= '[' <raw-code> ']' | |
63 | + <next-state> ::= <word> | 'nil' | |
64 | + <action> ::= <word> '(' <arguments>* ')' | |
65 | + <raw-code> ::= ...Not shown here ... | |
66 | + | |
67 | + .. tab:: Links | |
68 | + | |
69 | + .. admonition:: UncleBobVideo version | |
70 | + | |
71 | + * source: https://github.com/unclebob/CC_SMC | |
72 | + * Grammar: https://github.com/unclebob/CC_SMC/blob/master/README.md#BNF | |
73 | + | |
74 | + .. admonition:: SMC | |
75 | + | |
76 | + * source: http://smc.sourceforge.net | |
77 | + * Tutorial: http://smc.sourceforge.net/slides/SMC_Tutorial.pdf | |
78 | + * Grammar http://smc.sourceforge.net/SmcManAppendixA.htm | |
79 | + | |
80 | + .. admonition:: other friend | |
81 | + | |
82 | + * With XML-input https://github.com/jp-embedded/scxmlcc | |
83 | + | |
84 | + |
@@ -0,0 +1,25 @@ | ||
1 | +.. -*- rst -*- | |
2 | + included in `5.eval-syntax.rst` | |
3 | + | |
4 | +.. sidebar:: | |
5 | + | |
6 | + .. tabs:: | |
7 | + | |
8 | + .. tab:: plantUML | |
9 | + | |
10 | + .. uml:: /CCastle/shared/FSM-plantUML-demo.puml | |
11 | + :scale: 78% | |
12 | + | |
13 | + .. tab:: syntax | |
14 | + :selected: | |
15 | + | |
16 | + .. literalinclude :: /CCastle/shared/FSM-plantUML-demo.puml | |
17 | + :lines: 5-22 | |
18 | + | |
19 | + .. tab:: Links | |
20 | + | |
21 | + .. seealso:: | |
22 | + | |
23 | + * wikipedia https://en.wikipedia.org/wiki/PlantUML | |
24 | + * plantuml https://plantuml.com/state-diagram | |
25 | + |
@@ -0,0 +1,12 @@ | ||
1 | +==================== | |
2 | +Analyse & Evaluation | |
3 | +==================== | |
4 | + | |
5 | +When designing Castle, we can learn from other systems. You will find my notes here | |
6 | + | |
7 | +.. toctree:: | |
8 | + :maxdepth: 2 | |
9 | + :titlesonly: | |
10 | + :glob: | |
11 | + | |
12 | + * |
@@ -1,442 +0,0 @@ | ||
1 | -.. include:: /std/localtoc.irst | |
2 | - | |
3 | -.. _eval_FSMs-syntax: | |
4 | - | |
5 | -========================= | |
6 | -FSM syntax, an evaluation | |
7 | -========================= | |
8 | - | |
9 | -.. post:: 2022/06/10 | |
10 | - :category: Castle, Design | |
11 | - :tags: Castle, FSM | |
12 | - | |
13 | - As described in :ref:`FSMs-are-needed` *Finit State Machines* are great and needed -- even tough no (main) programming | |
14 | - language has syntax support for it. But there are other (computer) language that (more-or-less) support the | |
15 | - corresponding `State pattern`_. | |
16 | - |BR| | |
17 | - By example plantUML --very populair by mature developers-- has a syntax to draw them. | |
18 | - | |
19 | - What can we learn from them? That is the topic of this post, before we define the Castle syntax. | |
20 | - | |
21 | - | |
22 | -Goal: Short & Maintainable | |
23 | -************************** | |
24 | - | |
25 | -Before we can define the (Castle) syntax for FSM_\s, we should know where we are aiming for. We need to support “all” | |
26 | -kinds of FSM, as required by [:need:`U_FSM_Syntax`] and refined by [:need:`U_FSM_extensions`]; e.g. the syntax should | |
27 | -allow non-determinism. And like all parts of Castle: maintainability and preventing mistakes is important. | |
28 | -|BR| | |
29 | -For a FSM this means **short**: avoid boilerplate-code. | |
30 | - | |
31 | -The FSM_\`s mathematical model is simple: a set of `states` (‘:math:`S`’), the input `events` (‘:math:`E`’), | |
32 | -the transaction `rules` (‘:math:`R`’), a `start-state` (‘:math:`S0`’), and the `final-states` -- which are not needed | |
33 | -for a SW-FSM [#final-action]_. Usually, a set of `actions` (‘:math:`A`’) is required too. Where this set is implicitly | |
34 | -defined: the actions are listed inside the rules. | |
35 | -|BR| | |
36 | -Each `rule` is relation :math:`R := S * E -> S, A`; this “table” is typically the biggest part of an FSM. | |
37 | - | |
38 | -So, to make a FSM-code compact, we have to focus on the rules. It’s tempting to regard this rule-set as a *matrix*: | |
39 | -with (‘:math:`S`’) and (‘:math:`E`’) on the axes and the next-states [#non-determinism]_ (and actions) inside each | |
40 | -cell. Nevertheless this matrix is huge and probably sparse: most cells are empty, as the combination does not occur. | |
41 | -|BR| | |
42 | -We can describe such a sparse-matrix by listing the cell-value with the coordinates. This boils-down to listing the | |
43 | -rules, one by one .The disadvantage of this that many states and/or events are listed many times. As we will see below, | |
44 | -some languages solve this by factor-out `states` and/or `events`. | |
45 | - | |
46 | -.. hint:: Concurrency is not relevant | |
47 | - | |
48 | - FSM’s can be huge in code but do not need a lot of computer-power. For every *step* --one input-- one state-variable | |
49 | - has to be updated, and the action has to be triggered. That action can be “big” (an can need concurrency), the FSM | |
50 | - itself not. Therefore, the syntax of the FSM doesn't need special attention to make the FSM concurent. | |
51 | - | |
52 | - | |
53 | -Languages that support the state-pattern | |
54 | -**************************************** | |
55 | - | |
56 | -Some tools support FSMs, the state-pattern, or something that resembles it. We will not evaluate the tool, but focus in | |
57 | -the “input” those tools use. And on what concept we can reuse to design the syntax/grammar that Castle will use for | |
58 | -FSM-support. | |
59 | - | |
60 | -PlantUML | |
61 | -======== | |
62 | - | |
63 | -.. include:: sidebar-plantUML.irst | |
64 | - | |
65 | -The design-tool plantUML support the UML-FSM_ State diagram with a quite compact syntax. The focus however is on | |
66 | -*drawing* [#plantUML-arrows]_. As one can add text ‘on’ the arrows and ‘in’ the states, events and actions can be | |
67 | -specified. However, the is no specific syntax for that. By example, many add text like :code:`event / action()` to | |
68 | -annotate the transaction with events and actions. But for plantUML it us just text. The same for Moore-actions: It an | |
69 | -convention to add them to a state, with prefixes as **E:** and **L:**. | |
70 | -|BR| | |
71 | -So using this syntax directly isn’t possible. By adding a bit or (formal) grammar is easy. | |
72 | - | |
73 | -PlantUML support all aspects of the UML-FSM_, including super/sub-states (plantUML calles them ‘Composite state’) and | |
74 | -concurent states. As ‘drawing’ is the main goal, support for :math:`\epsilon`\-transaction, all kind of actions, etc is | |
75 | -solved as described above: by text. | |
76 | - | |
77 | -Super/Sub-states | |
78 | ----------------- | |
79 | -Substates are drawn ‘inside’ a superstate. This is described with a nested structure; a state can have an (optional) | |
80 | -``{} block``. Inside that block, the same syntax is uses as for the main FSM_. | |
81 | - | |
82 | -This part of syntax does not fit the goals of Castle; as it is still *one* piece of code; it does not make the source | |
83 | -“shorter” [#indirect]_. But more important: one would typically like to reuse “sub FSM” and specify those details | |
84 | -later/elsewhere in the program. | |
85 | - | |
86 | -Referring | |
87 | -~~~~~~~~~ | |
88 | - | |
89 | -A developer like to *refer* to other parts; by example to import other modules or *name* those. Not by recode them. This | |
90 | -is not possible (relevant) in plantUML’s state diagrams. Although some do/try by separate the source into multiple | |
91 | -files, and use the “``!include`` preprocessing” options -- a bit like good-old C textual includes. One misses namespaces | |
92 | -and other *modern* features however. | |
93 | - | |
94 | -.. _SMC: | |
95 | - | |
96 | -SMC (State Machine Compiler) & friends | |
97 | -====================================== | |
98 | - | |
99 | -.. include:: sidebar-SMC.irst | |
100 | - | |
101 | -There are many versions of the “State Machine Compiler”. Most use a text-input-file to specify a FSM_ and *’compile’* | |
102 | -that into programm-code first. Then the normal compiler is used to compile it “asis”. | |
103 | -|BR| | |
104 | -We do not discuss the tools itself, but will examine the input-file. And (when given) the formal grammar. | |
105 | - | |
106 | -Uncle Bobs’s version | |
107 | ---------------------- | |
108 | - | |
109 | -Uncle Bob’s version basically uses a “table” with 4 columns: ``current.state``, ``event``, ``next.state``, ``action``; | |
110 | -separated by whitespace. The name of the FSM, and it initial state are written-down above the tabel. This table is | |
111 | -translated into a class with a nested-switch FSM [#generated]_; the SW-developer should create a subclass that | |
112 | -implements actions (as methods). | |
113 | -|BR| | |
114 | -As SMC will generated the essential code (which should be deterministic), the FSM needs to be deterministic; the syntax | |
115 | -does allow (a bit of) non-determinism however. But by example *epsilon*- (and especially *‘instantly’*) transaction are not | |
116 | -possible. | |
117 | - | |
118 | -It is possible to factor-out some current.states (but not events) by using ``{}-blocks`` --the docs speak about | |
119 | -*“convenient syntactic sugar”*. Equally, one can combine several actions (function-calls) into one: surround | |
120 | -them with braces. | |
121 | -|BR| | |
122 | -This block concept can also be use to describe “abstract states”, which resembles super/sub-states. This is done by the | |
123 | -``:``\-modifier postfixing a state, and putting the abstract-state-name between | |
124 | -parenthesis. | |
125 | -|BR| | |
126 | -It is also possible to specify entry/leave(exit) action, again by postfixing a state with :samp:`‘<’ {entry-action}` | |
127 | -or/and :samp:`‘>’ {exit-action}`. | |
128 | - | |
129 | -The basic syntax is quite simple and readable; although whitespace as separator is not ideally --also as it make it a bit | |
130 | -unclear (hard to remember) what the order is. This readability issues becomes bigger when factoring-out (and the number | |
131 | -of columns decrease), or using state-modifiers. | |
132 | -|BR| | |
133 | -This can easily be improved (for Castle), by adding a bit more grammar-sugar and have several ‘tokens’ between the columns. | |
134 | - | |
135 | -The sytax of this version of SMC allows somethings that resembles hierarchically superstates; although the hierarchy is | |
136 | -“inlined”. | |
137 | -|BR| | |
138 | -For Castle, we cherish the ability to spilt the text over multiple files [#hierarchically-split]_. | |
139 | - | |
140 | - | |
141 | -SMC (sourceforge) version | |
142 | -------------------------- | |
143 | - | |
144 | -This version is derived from an early variant of (Uncle) Bob Martin’s (see above), according to its `documentation | |
145 | -<http://smc.sourceforge.net/SmcManual.htm>`__ The basic input-syntax is equally; although a lot “target-language details | |
146 | -are added to the header (like file-names etc)-- for Castle this is not relevant. | |
147 | - | |
148 | -The syntax is updated. By example, to describe Moore actions the keywords `Entry` and `Leave` are used with | |
149 | -``{}-blocks`` surrounding the action (even for a single call). In general, those ``{}-blocks`` has become compulsory; | |
150 | -every state has such a block., as has every action. This makes the syntax more regulair and readable for C/etc | |
151 | -programmers. | |
152 | -|BR| | |
153 | -But all those braces makes that the compact “table alike” structure for the rules is gone. | |
154 | - | |
155 | -guards & parameters | |
156 | -~~~~~~~~~~~~~~~~~~~ | |
157 | - | |
158 | -A new feature is **“guards”**: a boolean expression-postfix on events (in square-Brackets: ``[<guard>]``). The specified | |
159 | -transaction will only happen when and that event happens and the guard is true. The same event without a guard will act | |
160 | -as a kind of default/fall-through transaction. | |
161 | - | |
162 | -Another feature are **event-parameters** (called “Transition Arguments”; as the words event and transition are not used | |
163 | -consistently). In all examples this event-parameter is used in the guard; it’s not clear (Nore relevant) the tool can | |
164 | -also use it elsewhere. | |
165 | - | |
166 | - | |
167 | -more changes | |
168 | -~~~~~~~~~~~~ | |
169 | - | |
170 | -It support also a few notations, that do (IMHO) not fit in the FSM_ notion; like having a stack (that makes it a | |
171 | -stack-machine or `PDA <https://en.wikipedia.org/wiki/Pushdown_automaton>`__). But it has a nice feature to generate | |
172 | -(graphviz) diagrams; this really is convenient for the developer. Even one nowadays probably would prefer to see plantUML | |
173 | -State diagrams, as they are more standard. | |
174 | - | |
175 | -And again, for castle we like to be able to “distribute” details over multiple files. | |
176 | - | |
177 | -.. _SCXML: | |
178 | - | |
179 | -State Chart XML (SCXML): State Machine Notation for Control Abstraction | |
180 | -======================================================================= | |
181 | - | |
182 | -.. include:: sidebar-SCXML.irst | |
183 | - | |
184 | -SCXML is a (XML-based) standard “language” [#voice]_ to describe (more-or-less) an UML-FSM_. | |
185 | -|BR| | |
186 | -Surely, the XML-part is not applicable for Castle. Still, XML describes a tree (structure) -- like the Castle text | |
187 | -format will be converted into an AST (so, also a tree). So there we can learn (or at least try). | |
188 | - | |
189 | -This format treads *events* as attributes of a transition. See the disadvantage of this in `Remarks (general)`), below. | |
190 | - | |
191 | -Harel StateCharts (aka UML-FSM_) are supported. Both by being able to nest states; using the power of XML: Any | |
192 | -``<state>`` elements may have (other) ``state`` elements as children. And by having ``<parallel>`` elements, that can | |
193 | -contain (multiple) ``<state>`` elements -- here, each of those parallel states act as a “small FSMs” that are all active | |
194 | -when the parent state is active. This is an elegant way to describe “Orthogonal regions” (aka “Concurent states”). | |
195 | - | |
196 | -Concurent sub-states | |
197 | --------------------- | |
198 | - | |
199 | -Like a regulair ``<state>``, a ``<parallel>`` element has an ID (attribute), that act as name -- showing a bit of | |
200 | -similarity between normal states and concurent-substates. This approach can be usable for Castle. | |
201 | - | |
202 | -Possible, two concurent states can also be seen in a hierarchical way. At the top level is just one state, that is | |
203 | -active or not. And when we dive into de details, it *can* have substates (like normal a hierarchy); only here some | |
204 | -states can be active concurrently. As SCXML describes it, the “upper” state (nor the rest of the FSM) does not have to | |
205 | -know about this concurrency. | |
206 | -|BR| | |
207 | -Additionally, those concurren “substates” do not *exist*, whe the upper state is passive ... | |
208 | - | |
209 | -.. tip:: Have to give this a tought ... | |
210 | - | |
211 | - When ``state`` can act a small FSM_ internally, we can possible define a “concurrent state class” too. That class | |
212 | - act as state, and can have “two” (or more) FSM’s inside ... | |
213 | - | |
214 | - The inheritance-order/tree becomes complex however; `Liskov | |
215 | - <https://en.wikipedia.org/wiki/Liskov_substitution_principle>`__ should not be violated. | |
216 | - | |
217 | - * ``FSM`` is s subtype of ``state``. (as a state, is only active or not). | |
218 | - * The “concurrent one`` is also a subtype of ``state``, not containing some ``FSM``\s | |
219 | - | |
220 | - *Or, should we not inherited, but always aggregate? Sometimes 1, sometimes more...* | |
221 | - | |
222 | - | |
223 | -No Referring | |
224 | ------------- | |
225 | -Although XML has many options to refer other docs, SCXML does use none... Except for one place; the “G.1” example in the | |
226 | -w3-specification refers to another (scxml-) file, using XInclude! Without any explaining text nor semantics. I guess the | |
227 | -semantics is like a textual preprocessor: all text in that file should be read as if it was typed-in. That does not | |
228 | -help (me) [#google]_. | |
229 | - | |
230 | - | |
231 | -Some other relevant languages | |
232 | -***************************** | |
233 | - | |
234 | -There are more tools (and there input languages) that can inspire us. They do not directly define a FSM_, but can be | |
235 | -used to visualize it, or use FSMs as part of the languages. | |
236 | - | |
237 | -DOT/graphviz | |
238 | -============ | |
239 | - | |
240 | -.. sidebar:: Links | |
241 | - | |
242 | - * `https://en.wikipedia.org/wiki/DOT_(graph_description_language) | |
243 | - <https://en.wikipedia.org/wiki/DOT_(graph_description_language)>`__ | |
244 | - * https://en.wikipedia.org/wiki/Graphviz | |
245 | - * https://www.graphviz.org | |
246 | - | |
247 | -DOT is language --introduced & used by tool Graphviz-- to describe (mathematical) graphs. It’s a very flexible language: | |
248 | -both undirected and directed “edges” between “nodes” are possible; one can describe trees “woods” and more, which can | |
249 | -be cyclic (or not). When introduced (together with the autorouters graphviz), over 30 years ago, it hit the marked ... | |
250 | -|BR| | |
251 | -Suddenly we could describe & show anything ... Including state-diagrams. | |
252 | - | |
253 | -DOT, as a language, can’t define a FSM -even we can show the state-transitions. And nowadays one would prefer plantUML | |
254 | -(which used graphviz) to that. | |
255 | -|BR| | |
256 | -But it has learned us that state-transition (arrows, or edges in a graph) can be described in text as simple as | |
257 | -:samp:`{current} --> {next}`. A syntax we will reuse in Castle. | |
258 | - | |
259 | -.. _Dezyne: | |
260 | - | |
261 | -Verum’s Dezyne | |
262 | -============== | |
263 | - | |
264 | -.. sidebar:: Links | |
265 | - | |
266 | - - https://dezyne.org | |
267 | - - https://gitlab.com/dezyne | |
268 | - - https://verum.com/discover-dezyne/ | |
269 | - - https://dezyne.org/dezyne/manual/dezyne/html_node/A-Simple-State-Machine.html | |
270 | - | |
271 | -Dezyne (now open-source) is a programming language (with a set of tools) to implement (embedded) controll software. One | |
272 | -can also create state-machines with it. So that part of the language can inspire Castle. We use `this Tutorial | |
273 | -<https://dezyne.org/dezyne/manual/dezyne/html_node/A-Simple-State-Machine.html>`__ example as reference. | |
274 | - | |
275 | -In this example the `behavior` is described in an (mostly) `“Imperative” | |
276 | -<https://en.wikipedia.org/wiki/Imperative_programming>`__ (normal) style of programming [#dezyne-semantics]_, mixed with | |
277 | -events (``on`` keywords) and guards (:samp:`[{bool-expr}]`, like above). Therefore this simple FSM is implemented in a | |
278 | -phraseology that is very close to the nested-switch one. The outer switch is replaced by pillar of guards (The lines starting | |
279 | -with ``[]`` can we top-levels cases); the inner switch by ``on`` “event-handler”. | |
280 | - | |
281 | -|BR| | |
282 | -Not shown in this example, but one use the reverted style (as far as I know). | |
283 | - | |
284 | -In away, it also resembles the “factor the state out” style as described above in the “tables” -- although de developer | |
285 | -has to use an assign-statement to change state; unlike above where naming the new state will do [#dezyne-state]_. | |
286 | -|BR| | |
287 | -Assuming one can use the “reverted” (nested-switch) style too, it is in Dezyne possible to (“in a way”) factor-out the | |
288 | -inputs (instead of the state). None of the examples above where able to this. | |
289 | - | |
290 | -For Castle, if (and only if) we enable this factor-out option (even when we do not endorse it), I would prefer to have | |
291 | -this symmetry (as in Dezyne): one can factor-out both state and/or inputs! As shown in the example, the syntax for both | |
292 | -switches is a differs a bit. By such a contrast in syntax, its become cleare wich “ID” is state an which one it de | |
293 | -“input”. And thus we can allow to swap the order, and so, it becomes possible to factor-out both. #Nice | |
294 | - | |
295 | -BTW, Dezyne uses both “declarative” and “imperative” statements. As we describe in :ref:`Declarative-programming` Castle | |
296 | -will promote this declarative style; it’s great to declare a FSM (over implement it in an imperative style). And I have | |
297 | -no glue why Dezyne made another choice... | |
298 | - | |
299 | -Ragel | |
300 | -===== | |
301 | - | |
302 | -.. sidebar:: Links | |
303 | - | |
304 | - - https://en.wikipedia.org/wiki/Ragel | |
305 | - - http://www.colm.net/open-source/ragel/ | |
306 | - - https://en.wikipedia.org/wiki/Thompson%27s_construction | |
307 | - | |
308 | -Ragel is also a FSM-compiler, but unlike SMC_ is does not need ``rules`` as input. It uses RegExps as input! | |
309 | -|BR| | |
310 | -There is not a lot of documentation on the input however. But is has a interesting approach. | |
311 | - | |
312 | -It looks like one can define “paths” [#path-vs-step]_ by specifying some RegExps. Regel builds a NFA_ by using | |
313 | -`Thompson's construction algorithm <https://en.wikipedia.org/wiki/Thompson%27s_construction>`__, out of those | |
314 | -RegExps. So, the developer doesn't need tho specify which ``states`` nor ``rules`` are needed; only all the allowed | |
315 | -paths (or routes). | |
316 | - | |
317 | -Actions are also possible. They are “added” to the route (but do not consume input, so like a | |
318 | -:math:`\epsilon`-transition. | |
319 | - | |
320 | - | |
321 | -Remarks (general) | |
322 | -****************** | |
323 | -Based on the evaluation of these tools/languages, we can make some general remarks. Especially where relevant for the | |
324 | -design of the syntax of Castle. | |
325 | - | |
326 | -Transitions & Symmetry | |
327 | -====================== | |
328 | - | |
329 | -Many tools use a syntax (and/or terminology) that is not inline with the (original) FSM_ (mathematical) model; | |
330 | -especially for a “transition”: | |
331 | -|BR| | |
332 | -(We ignore the ``actions`` for a while, here). | |
333 | - | |
334 | -* Tools like SMC_ and SCXML_ see **the transition** as *“the arrow between 2 states”* The input-event is then like a | |
335 | - attribute of that transition. | |
336 | - |BR| | |
337 | - So we have ``states`` and ``transition``. | |
338 | - | |
339 | -* Whereas others -- like Dezyne_ and plantUML_\-- (and the theory) sees **transitions** as *the relation between 3 | |
340 | - parts*: from ``state`` and ``input (event)`` toward the next ``state``. | |
341 | - |BR| | |
342 | - So we have ``states``, ``inputs/events`` and ``transitions`` (or rules). | |
343 | - | |
344 | -The implication of “employing an events as attribute of a transition”, is that one can factor-out states, but nog events | |
345 | -anymore. Wheres when using ``state`` and ``event`` as more symmetrical pair; one can factor-out either the state, *or* | |
346 | -the event -- as shown in e.g. the “revered” code example. | |
347 | - | |
348 | -* The (basic) UncleBob’s version of SMC uses this more symmetrical model -- which leads to compact table. | |
349 | - |BR| | |
350 | - But as the whitespace formating, does not allow to change the order of state/event; only factoring-out over the 1ste | |
351 | - is possible. | |
352 | - | |
353 | -Hierarchy | |
354 | -========= | |
355 | - | |
356 | -Several formats do kind-of embrace the hierarchical states, but only in an inline-notation. Which effectively cancel the | |
357 | -effect of hierarchy. A figure that displays states “nested” inside states (as plantUML can produce) is showning | |
358 | -hierarchy. But not the kind of hierarchy that we need/like to construct a complex FSM_ | |
359 | - | |
360 | -To construct a hierarchical FSM, we like to: | |
361 | - | |
362 | -#. Define a “main” FSM with states in one place | |
363 | -#. Consider each (or some) state of that (upper) FSM as “lower” sub-FSMs itself | |
364 | -#. Add (later, and “in another file”) sub-states by adding details to *only* that state. | |
365 | -#. Are able to add more and more details, by “redefining” a state as small FSM in itself. | |
366 | - | |
367 | -Independent of those “isolated details”, it would be nice when ‘Castle’ can flaten-out the hierarchy and draw the | |
368 | -“nested” variant. Or even beter: can display a partial flattened-out one; depending on the focus the developer has on | |
369 | -that comment. | |
370 | - | |
371 | -Compactness | |
372 | -=========== | |
373 | - | |
374 | -Inline with the general need as described in :ref:`Declarative-programming`, we can already conclude that a declarative | |
375 | -style for FSM_\s is more compact then a imperative style where one (also) ahs to specify some implementation details | |
376 | -(like: assigning the next state). | |
377 | - | |
378 | -A style as used in Ragel_ --to specify paths, not steps--, is potential even more compact. Especially when the input are | |
379 | -characters -- which is not ge the general case. | |
380 | -|BR| | |
381 | -It may be also one step to far, as in MAYA (Most Advanced Yet Acceptable). | |
382 | - | |
383 | - | |
384 | -------- | |
385 | - | |
386 | -.. rubric:: Footnotes | |
387 | - | |
388 | -.. [#final-action] | |
389 | - The final-states are used by mathematics to verify/accept an input. Whereas a SW-FSM is typically used to control a | |
390 | - system; and run *forever*. When a “final state” is needed in a SW-FSM, typical a “final-action” is used. | |
391 | - | |
392 | -.. [#non-determinism] | |
393 | - Remember, we have to support non-determinism! Each cell in the matrix can have multiple “next states” (and | |
394 | - corresponding actions). | |
395 | - | |
396 | -.. [#plantUML-arrows] | |
397 | - By example: the *arrows* in plantUML can have varions lengths (`->` , `-->`, `--->`) to hint plantUML how to draw; | |
398 | - this has no (functional) meaning. This is very conviant for a *drawing tool*, not for a programming-language. | |
399 | - | |
400 | -.. [#indirect] | |
401 | - This is not completely correct. By ‘nesting’ one has the advantages of sharing higher rules. | |
402 | - | |
403 | -.. [#generated] | |
404 | - This is generated code, and should not be touched. Therefor the maintainability-issue does not occur; just | |
405 | - re-renerate the class! | |
406 | - | |
407 | -.. [#hierarchically-split] | |
408 | - IMHO the goal of the hierarchy is to be able to split the “source” of the main-state/FSM and the | |
409 | - detailed-states. Developers are used to devide functionality over modules/components -- and so text-files. And | |
410 | - practice this every time details are added. | |
411 | - | |
412 | -.. [#voice] | |
413 | - As a practical limitation one should mention that both the standard and may examples have a voice (over IP) | |
414 | - background. Which makes the understandability for the *general* case a bit hard. | |
415 | - | |
416 | -.. [#google] | |
417 | - When `googling for scxml + xinclude <https://www.google.com/search?q=scxml+xinclude>`__ one find a few hits. Like | |
418 | - the comment/question “is it an omission” (as it was descriped in a draft), or “is it removed” from the spec (and | |
419 | - *forgotten* to update the example)? | |
420 | - |BR| | |
421 | - There is no clear answer, but is appears that `XInclude` is kind of a general XML-facility; that have to be applied | |
422 | - first (before using scxml). Which resembles the preprocessor. So I give up [#xml-more]_ | |
423 | - | |
424 | -.. [#xml-more] | |
425 | - I was kind of hoping that one coud refer to a part in another file. Like we have a common “library” scxml-file and | |
426 | - use (the definitions of) a few “states” in that file. Apparently not ... | |
427 | - | |
428 | -.. [#dezyne-semantics] | |
429 | - Notice that the style of Dezyne resembles (or “feels as”) imperative programming, but the semantics do differ! | |
430 | - | |
431 | -.. [#dezyne-state] | |
432 | - Dezyne has no “states” (at tupe/words) -- at least not in the found FSMs. Is create state by assigning value to | |
433 | - variable; that act as stare (like in C). Probably one can use the Enum type to define (simulate) state; but still one | |
434 | - has to assign that value to a variable. | |
435 | - | |
436 | -.. [#path-vs-step] | |
437 | - In a FSM (diagram) there are “steps” to go from one state to another. A “path” is a sequence of such a steps. | |
438 | - | |
439 | -.. _FSM: https://en.wikipedia.org/wiki/Finite-state_machine | |
440 | -.. _State pattern: https://en.wikipedia.org/wiki/State_pattern | |
441 | -.. _UML-FSM: https://en.wikipedia.org/wiki/UML_state_machine | |
442 | -.. _NFA: https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton |
@@ -1,68 +0,0 @@ | ||
1 | -======================= | |
2 | -Castle FSM syntax tries | |
3 | -======================= | |
4 | - | |
5 | -.. note:: Based on some experiments we select “a” language to highlight the examples. | |
6 | - Its just try&error; there is no relation with that language, Castle or a FSM! | |
7 | - | |
8 | -Try 1 | |
9 | -===== | |
10 | - | |
11 | -.. code:: ReasonML | |
12 | - | |
13 | - FSM AB { | |
14 | - state A, B, C; | |
15 | - | |
16 | - A + event_1 -> state_B, action_I; | |
17 | - A + event_2 -> state_C, action_II; | |
18 | - B + event_1 -> state_D, action_III; | |
19 | - Z1 + event_1 -> state_Z2; // No action | |
20 | - Z1 + event_1 -> ,action_only; // Empty state: do not change | |
21 | - Z1 + event_1 -> action_only; // No new state | |
22 | - // Note: In the last line Castle knows it only an action, as “action_only” is not a state! | |
23 | - // Potentially it conflict with the “redundancy rule” | |
24 | - Z1 + event_1 -> None, action_only; // None-state: do not change | |
25 | - } | |
26 | - | |
27 | -Variant a | |
28 | ---------- | |
29 | -Actions with ``(`` `parameters-list` ``)``. **Question**: Do we know those parameters here. Or are the default? | |
30 | - | |
31 | -.. code:: ReasonML | |
32 | - | |
33 | - FSM AB { | |
34 | - state A, B, C; | |
35 | - | |
36 | - A + event_1 -> state_B, action_I(p1,p2, p3); | |
37 | - A + event_2 -> state_C, action_II(); | |
38 | - B + event_1 -> state_D, action_III(); | |
39 | - Z1 + event_1 -> state_Z2; // No action | |
40 | - Z1 + event_1 -> ,action_only(); // Empty state: do not change | |
41 | - Z1 + event_1 -> action_only(); // No new state | |
42 | - // Note: In the last line Castle knows it only an action, as “action_only” is not a state! | |
43 | - // Potentially it conflict with the “redundancy rule” | |
44 | - Z1 + event_1 -> None, action_only(); // None-state: do not change | |
45 | - | |
46 | - } | |
47 | - | |
48 | - | |
49 | -Variant b | |
50 | ---------- | |
51 | -No FSM/State prequel nor block | |
52 | - | |
53 | -.. code:: ReasonML | |
54 | - | |
55 | - state A, B, C; | |
56 | - | |
57 | - A + event_1 -> state_B, action_I; | |
58 | - A + event_2 -> state_C, action_II; | |
59 | - B + event_1 -> state_D, action_III; | |
60 | - Z1 + event_1 -> state_Z2; // No action | |
61 | - Z1 + event_1 -> ,action_only; // Empty state: do not change | |
62 | - Z1 + event_1 -> action_only; // No new state | |
63 | - // Note: In the last line Castle knows it only an action, as “action_only” is not a state! | |
64 | - // Potentially it conflict with the “redundancy rule” | |
65 | - Z1 + event_1 -> None, action_only; // None-state: do not change | |
66 | - | |
67 | - | |
68 | - |
@@ -1,12 +0,0 @@ | ||
1 | -================ | |
2 | -Evaluation Notes | |
3 | -================ | |
4 | - | |
5 | -When designing Castle, we can learn from other systems. You will find my notes here | |
6 | - | |
7 | -.. toctree:: | |
8 | - :maxdepth: 2 | |
9 | - :titlesonly: | |
10 | - :glob: | |
11 | - | |
12 | - * |
@@ -1,34 +0,0 @@ | ||
1 | -.. -*- rst -*- | |
2 | - included in `5.eval-syntax.rst` | |
3 | - | |
4 | -.. sidebar:: | |
5 | - | |
6 | - .. tabs:: | |
7 | - | |
8 | - .. code-tab:: xml Example | |
9 | - | |
10 | - <?xml version="1.0" encoding="UTF-8"?> | |
11 | - <scxml xmlns="http://www.w3.org/2005/07/scxml" version="1.0" initial="ready"> | |
12 | - <state id="ready"> | |
13 | - <transition event="watch.start" target="running" /> | |
14 | - </state> | |
15 | - <state id="running"> | |
16 | - <transition event="watch.split" target="paused" /> | |
17 | - <transition event="watch.stop" target="stopped" /> | |
18 | - </state> | |
19 | - <state id="paused"> | |
20 | - <transition event="watch.stop" target="stopped" /> | |
21 | - <transition event="watch.unsplit" target="running" /> | |
22 | - </state> | |
23 | - <state id="stopped"> | |
24 | - <transition event="watch.reset" target="ready" /> | |
25 | - </state> | |
26 | - </scxml> | |
27 | - | |
28 | - .. tab:: Links | |
29 | - | |
30 | - .. seealso:: | |
31 | - | |
32 | - * wikipedia https://en.wikipedia.org/wiki/SCXML | |
33 | - * W3 (specification): https://www.w3.org/TR/scxml/ | |
34 | - * `Source of shown example <https://blogs.itemis.com/en/custom-code-generator-scxml>`__ (itemis blog) |
@@ -1,84 +0,0 @@ | ||
1 | -.. -*- rst -*- | |
2 | - included in `5.eval-syntax.rst` | |
3 | - | |
4 | -.. sidebar:: | |
5 | - | |
6 | - .. tabs:: | |
7 | - | |
8 | - .. tab:: SMC (example) | |
9 | - :selected: | |
10 | - | |
11 | - .. code:: | |
12 | - | |
13 | - Initial: Locked | |
14 | - FSM: Turnstile | |
15 | - { | |
16 | - Locked Coin Unlocked unlock | |
17 | - Locked Pass Locked alarm | |
18 | - Unlocked Coin Unlocked thankyou | |
19 | - Unlocked Pass Locked lock | |
20 | - } | |
21 | - | |
22 | - --- source: `Uncle Bob <https://github.com/unclebob/CC_SMC/blob/master/README.md>`__. | |
23 | - |BR| | |
24 | - Showing a basic FSM only; see the website for more examples. | |
25 | - | |
26 | - | |
27 | - .. tab:: Grammars (BNF) | |
28 | - | |
29 | - UncleBob’s version | |
30 | - | |
31 | - .. code:: BNF | |
32 | - | |
33 | - <FSM> ::= <header>* <logic> | |
34 | - <header> ::= <name> ":" <name> | |
35 | - <logic> ::= "{" <transition>* "}" | |
36 | - <transition> ::= <state-spec> <subtransition> | |
37 | - | <state-spec> "{" <subtransition>* "}" | |
38 | - <state-spec> ::= <state> <state-modifier>* | |
39 | - <state> ::= <name> | |
40 | - | "(" <name> ")" | |
41 | - <state-modifier> ::= ":" <name> | |
42 | - | "<" <name> | |
43 | - | ">" <name> | |
44 | - <subtransition> :: <event> <next-state> <action> | |
45 | - <action> ::= <name> | "{" <name>* "}" | "-" | |
46 | - <next-state> ::= <state> | "-" | |
47 | - <event> :: <name> | "-" | |
48 | - | |
49 | - SMC (sourceforge) version [edited & shortened]. | |
50 | - | |
51 | - .. code:: BNF | |
52 | - | |
53 | - <FSM> ::= <%headers> <map>+ | |
54 | - <%headers> ::= ...Not shown here ... | |
55 | - <map> ::= '%map' <word> '%%' <states> '%%' | |
56 | - <states> ::= <word> <entry>? <exit>? '{' <transitions>* '}' | |
57 | - <entry> ::= 'Entry {' <action>* '}' | |
58 | - <exit> ::= 'Exit {' <action>* '}' | |
59 | - <transitions> ::= <word> <args>? <guard>? <next-state> '{' <action>* '}' | |
60 | - <args> ::= '(' <parameter>+ ')' | |
61 | - <parameter> ::= <word> ':' <raw-code> | |
62 | - <guard> ::= '[' <raw-code> ']' | |
63 | - <next-state> ::= <word> | 'nil' | |
64 | - <action> ::= <word> '(' <arguments>* ')' | |
65 | - <raw-code> ::= ...Not shown here ... | |
66 | - | |
67 | - .. tab:: Links | |
68 | - | |
69 | - .. admonition:: UncleBobVideo version | |
70 | - | |
71 | - * source: https://github.com/unclebob/CC_SMC | |
72 | - * Grammar: https://github.com/unclebob/CC_SMC/blob/master/README.md#BNF | |
73 | - | |
74 | - .. admonition:: SMC | |
75 | - | |
76 | - * source: http://smc.sourceforge.net | |
77 | - * Tutorial: http://smc.sourceforge.net/slides/SMC_Tutorial.pdf | |
78 | - * Grammar http://smc.sourceforge.net/SmcManAppendixA.htm | |
79 | - | |
80 | - .. admonition:: other friend | |
81 | - | |
82 | - * With XML-input https://github.com/jp-embedded/scxmlcc | |
83 | - | |
84 | - |
@@ -1,25 +0,0 @@ | ||
1 | -.. -*- rst -*- | |
2 | - included in `5.eval-syntax.rst` | |
3 | - | |
4 | -.. sidebar:: | |
5 | - | |
6 | - .. tabs:: | |
7 | - | |
8 | - .. tab:: plantUML | |
9 | - | |
10 | - .. uml:: /CCastle/shared/FSM-plantUML-demo.puml | |
11 | - :scale: 78% | |
12 | - | |
13 | - .. tab:: syntax | |
14 | - :selected: | |
15 | - | |
16 | - .. literalinclude :: /CCastle/shared/FSM-plantUML-demo.puml | |
17 | - :lines: 5-22 | |
18 | - | |
19 | - .. tab:: Links | |
20 | - | |
21 | - .. seealso:: | |
22 | - | |
23 | - * wikipedia https://en.wikipedia.org/wiki/PlantUML | |
24 | - * plantuml https://plantuml.com/state-diagram | |
25 | - |
@@ -1,38 +0,0 @@ | ||
1 | -==================== | |
2 | -CCastle Design Notes | |
3 | -==================== | |
4 | - | |
5 | -Castle has to be designed. Not only the “compiler”, but also the language itself. And the **“CC” concept**, And .... | |
6 | - | |
7 | -.. toctree:: | |
8 | - :maxdepth: 2 | |
9 | - :titlesonly: | |
10 | - :glob: | |
11 | - | |
12 | - */index | |
13 | - zz.todo | |
14 | - | |
15 | -.. note:: In case you are wondering: *“Are FSMs and Grammars related, or the same?”* | |
16 | - | |
17 | - The are related, but not equal. As discovered by `Chomsky <https://en.wikipedia.org/wiki/Noam_Chomsky>`__ there is a | |
18 | - `hierarchy <https://en.wikipedia.org/wiki/Chomsky_hierarchy>`__ of languages (or actually grammars). As Chomsky was | |
19 | - studying all kind of languages, include natural “human” language, his perception differs from our interpretation. | |
20 | - |BR| | |
21 | - When we (SW/Engineers) speak about grammars, we typically refer to “Context free grammars” (`CFG | |
22 | - <https://en.wikipedia.org/wiki/Context-free_grammar>`__) -- Chomsky classify them as “Type-2”. | |
23 | - | |
24 | - A non-deterministic Push~Down machine (`PDA <https://en.wikipedia.org/wiki/Pushdown_automaton>`__) is needed to | |
25 | - recognise a “Type-2” (CFG) Grammar. (Which is a simple version of a stack-machine, which is lot more restricted then a Turing Machine). | |
26 | - |BR| | |
27 | - And as a FSM is one of the most restricted machines that exist --it can recognise only “Type-3” `Regular grammar | |
28 | - <https://en.wikipedia.org/wiki/Regular_grammar>`__-- a FSM can’t be used to recognise a (CFG) grammar. | |
29 | - | |
30 | - .. seealso:: | |
31 | - | |
32 | - .. postlist:: | |
33 | - :category: Castle | |
34 | - :tags: FSM | |
35 | - | |
36 | - .. postlist:: | |
37 | - :category: Castle | |
38 | - :tags: Grammar |
@@ -1,231 +0,0 @@ | ||
1 | -.. include:: /std/localtoc.irst | |
2 | - | |
3 | -.. _grammmar-code: | |
4 | - | |
5 | -=============== | |
6 | -Grammar is code | |
7 | -=============== | |
8 | - | |
9 | -.. post:: 2022/05/14 | |
10 | - :category: Castle, DesignStudy | |
11 | - :tags: Castle, Grammar, PEG | |
12 | - | |
13 | - In :ref:`Castle-CompilerCompiler` we have seen that we can define a grammar within a Castle-program. And we have | |
14 | - argued that each grammars-rule can be considered as a function. | |
15 | - | |
16 | - In this post, we look into de details of how this works. And will confirm grammars is code ... | |
17 | - | |
18 | -Let’s start with an example. The grammer below is a simplified description of how a (PEG) parsing-rule looks like. The | |
19 | -syntax in Castle is a bit more complicated, by having more details and options; but very simular. Most of the | |
20 | -Caste-grammers can be parsed by the grammer below! | |
21 | - | |
22 | -.. code-block:: PEG | |
23 | - | |
24 | - PEG_rule <- rule_name '<-' expression ';' ; | |
25 | - expression <- ordered_choice+ ; | |
26 | - ordered_choice <- sequence ( '|' sequence)* ; | |
27 | - sequence <- group | atom ; | |
28 | - group <- '(' expression ')' ; | |
29 | - atom <- rule_xref | str_lit | regexp ; | |
30 | - str_lit <- '"' /[^"]* '"' ; | |
31 | - regexp <- '/' /[^/]* '/' ; | |
32 | - rule_name <- ID ; | |
33 | - rule_xref <- ID ; | |
34 | - | |
35 | -With this grammer we can read and check whether an a string is a valid rule by simply calling: | |
36 | -:math:`ast:=PEG\_rule(single\_line)`. When not, ``ast`` is :math:`False`, else ``ast`` has 4 children (or fields). | |
37 | -Where :data:`ast[0]` represent the ``rule_name``, :data:`ast[2]` is an ``expression``; which is a sequence of | |
38 | -``ordered_choice``\(s). | |
39 | -|BR| | |
40 | -As the rule has two constants :data:`ast[1]` and :data:`ast[3]` will always match the strings *‘<-’* and *‘;’*. | |
41 | - | |
42 | - | |
43 | -Grammar to code | |
44 | -=============== | |
45 | - | |
46 | -Before we study how Castle *expands* a grammar to code, let examine how to do that by manually crafted code, or using a | |
47 | -external compiler-compiler. In both cases, we will focus on the “validation” part only. And we skip a lot of details; | |
48 | -assuming you know a bit of theory of (PEG) parser. When not, read Guido van Rossum’s excellent blog-series `PEG Parsing | |
49 | -Series Overview <https://medium.com/@gvanrossum_83706/peg-parsing-series-de5d41b2ed60>`__ | |
50 | - | |
51 | - | |
52 | -Hand written code | |
53 | ------------------ | |
54 | - | |
55 | -Again, let’s suppost we like to verify a string contains a *peg-rule*. Then we need some functions [#func]_, which signature | |
56 | -are something like: | |
57 | - | |
58 | -.. tabs:: | |
59 | - | |
60 | - .. code-tab:: python | |
61 | - | |
62 | - def PEG_rule(text: str) -> ast : ... | |
63 | - def expression(text: str) -> ast : ... | |
64 | - def ordered_choice(text: str) -> ast : ... | |
65 | - def sequence(text: str) -> ast : ... | |
66 | - ... | |
67 | - | |
68 | - .. code-tab:: c | |
69 | - | |
70 | - ast PEG_rule(char* txt); | |
71 | - ast expression(char* txt); | |
72 | - ast ordered_choice(char* txt); | |
73 | - ast sequence(char* txt); | |
74 | - ... | |
75 | - | |
76 | -Where we assume the type ``ast`` is defined in the chosen language and will be Null/None/Empty to signal :math:`False`: | |
77 | -not valid. | |
78 | - | |
79 | -The implementation of ``PEG_rule()`` checks thats the input-string starts with a ``rule_name``, followed by the literal | |
80 | -string **“<-”**, then has an ``expression`` and finally the literal string **“;”**. When one of those (four) steps fail, | |
81 | -we return :math:`False`. | |
82 | -|BR| | |
83 | -We follow this pattern for all rules. | |
84 | - | |
85 | -This concept is easy to implement: each rule-function calls other rule-functions as defined by the grammar. When we | |
86 | -need to check for a literal string we use :func:`expect(txt: str, literal: str) -> bool`. Also, we need a function to find | |
87 | -an ID; again easy. Sometimes we need to implement a loop --to handle ``*`` and ``+``. Or we need an :math:`or`, to | |
88 | -implement alternatives (``|``). None of that is rocket science. | |
89 | - | |
90 | -A real implementation is a bit harder, as we have to strip spaces (and comments), handle newlines, and need to keep | |
91 | -track of where we are. Typically that is (nowadays) done by embedding those functions in a class; then the “input text” can be | |
92 | -stored in the instance (instead of passing them constantly). That instance also has a ‘cursor’ to the current | |
93 | -location. | |
94 | - | |
95 | -More details | |
96 | -~~~~~~~~~~~~ | |
97 | - | |
98 | -There are a lot of details that make writing a grammer complex. We mention a few, and what it effect is on the (manually | |
99 | -written) code. | |
100 | - | |
101 | -When using alternatives (the ``|`` operator in the grammar), a PEG-parser will always try the first alternative first, | |
102 | -Only when that fails, it back-ups an try the next alternative. Sometimes means (almost) start again, and parse the same file almost | |
103 | -completely again. Therefore the *packrat* algorithm is usually used; using memoization. | |
104 | -|BR| | |
105 | -This is not hard: just add a few lines of boilerplate before and after each call. To store intermediate partial-ast(s) in a | |
106 | -cache. | |
107 | - | |
108 | -Sometimes, we like to use another parser-strategy, like LALR_ (used by Yacc_), GLR_ (e.g Bison, the successor of Yacc_) | |
109 | -or `LL(k)`_ (introduced by ANTLR, which was popular for a while); each one has it pros and cons. Still, all (or almost) | |
110 | -start with the same grammar (although smarter strategies may result is shorter, easier to maintain [#maintain]_ | |
111 | -grammars) [#notation]_. | |
112 | - | |
113 | -For a long time PEG-parsers where not able to handle left recursive rules [#leftStack]_. Until somebody discovered that is not | |
114 | -correct. Grammars in Castle can be left recursive! Both direct and indirect recursion is allowed. | |
115 | - | |
116 | -.. tabs:: | |
117 | - | |
118 | - .. code-tab:: PEG Direct recursion | |
119 | - | |
120 | - expr <- expr '-' term | term | |
121 | - | |
122 | - .. code-tab:: PEG Indirect recursion | |
123 | - | |
124 | - A <- B "a" | "a" | |
125 | - B <- A "b" | "b" | |
126 | - | |
127 | - .. code-tab:: PEG A rewritten grammar | |
128 | - | |
129 | - expr <- term ( '-' term )* | |
130 | - | |
131 | -.. note:: | |
132 | - | |
133 | - It is always possible to rewrite a lef-recursief grammar to one that isn’t. However, that make the grammar harder to | |
134 | - read & maintain (for humans). It does also influence the outcome; the tree will differ. | |
135 | - | |
136 | - By example, an simple calculation as :math:`7-5-3` should result in :math:`((7-5)-3)` but that needs left | |
137 | - recursion. When rewriting it, you must be carefull not to get :math:`(7-(5-3))`! | |
138 | - |BR| | |
139 | - This can be fixes, by adding an extra step. But it is better to use the update PEG-strategy: Just add more boilerplate code! | |
140 | - | |
141 | - For that reason Castle will support recursion! You can write the grammar as you need, as we are generating that extra | |
142 | - boilerplate anyhow. | |
143 | - | |
144 | - | |
145 | -Generating the code | |
146 | -=================== | |
147 | - | |
148 | -You might recognise the pattern: To make the grammer more useful, the algorithms become more complex and adds more | |
149 | -code. This “extra” code, however is not hard; you just need the same (or almost the same) lines at many places. | |
150 | -|BR| | |
151 | -This begs for automation. And that is exactly what most compiler-compilers do. | |
152 | - | |
153 | -A compiler-compilers read the grammar and generates the code. As shown above it will generate (C, C++, C#, Java, | |
154 | -Python, or ...) functions [#OrTables]_ that call each-other. It will also detect left-recursion, and might compensate for | |
155 | -that. The result: more boilerplate-code; but as it is automatically generated this is easy. | |
156 | - | |
157 | -Classic tools | |
158 | -------------- | |
159 | -There are many tools, that we can use for inspiration. A short overview, and how it influences Castle. | |
160 | - | |
161 | -Possible the most famous compiler-compilers is Yacc_. It was developed in 197X and generates C-code that can be compiled | |
162 | -and linked to your code. To parse a string, you had to call ``yyparse())``. It would however be relatively simple to | |
163 | -generate functions with the name of each rule, using the same machinery. In that decade however, the goal was | |
164 | -differently. Memory was limited, what we can also see in the used grammar: one had to craft it carefully as the was no | |
165 | -back-tracking an only a single token look-ahead. | |
166 | - | |
167 | -Bison_ is Gnu reimplementation of Yacc_, but can use several parsing-algorithms.cLike Yacc_, it used a separate Lexer_: | |
168 | -*flex* (whereas Yacc uses *lex*). A lexer_ splits the input-string into a stream of *Tokens* using another (simpler, | |
169 | -but faster) algorithm. In that time that was relevant. | |
170 | -|BR| | |
171 | -As a lexer_ can be implemented with a parsing-algorithm (but not the other-way around), and as the need for speed doesn't | |
172 | -demand a separate lexer_ anymore; modern parsings are often “scannerless”. This removes the need to use two meta-syntaxes | |
173 | -(for the lexer/scanner and the parser) and so is simpler to use. | |
174 | -|BR| | |
175 | -Also Castle use a scannerless approach. | |
176 | - | |
177 | -Castle: rules are functions | |
178 | -=========================== | |
179 | - | |
180 | -.. resolution:: In Castle each rule act as a *callable* | |
181 | - :ID: R_GrammerCallables | |
182 | - | |
183 | - Each parse-rule that is defined in Castle is a kind of function; more accurately it’s a “callable” | |
184 | - | |
185 | -Also in Castle you can use grammars; but now directly in your program, using the Castle-syntax. And Castle will generate | |
186 | -“code” --Castle-functions that is. But now without an extra tool. | |
187 | -|BR| | |
188 | -This “generate code” is not ‘code as text’. Why should we generate code, to read & parse it back and compile it | |
189 | -directly? It easier to generate the AST, that would be the result of parsing the generated-code, directly. | |
190 | - | |
191 | -But the effect is the same. You create a set of function with this generic “text to tree” signature, by writing some | |
192 | -simle rule. Castle does the rest for you. Easy! | |
193 | - | |
194 | - | |
195 | ----------- | |
196 | - | |
197 | -.. rubric:: Footnotes | |
198 | - | |
199 | -.. [#func] | |
200 | - Instead of a **function**, it can also be a *method, or any *callable*. We use ‘function’ a generic term, in the | |
201 | - mathematical meaning: some input (parameters) and an output (return value). | |
202 | - | |
203 | -.. [#maintain] | |
204 | - This is not specially for grammers; all it valid for all programming-languages. New languages may introduce new | |
205 | - concepts (like --once-- OO). When the compiler becomes smarter, the programmer can focus in the important bits! | |
206 | - | |
207 | -.. [#notation] | |
208 | - Aside of multiple parser-algorithms, there are also several notation to write the grammar itself; like `EBNF | |
209 | - <https://en.wikipedia.org/wiki/Extended_Backus–Naur_form>`__ `ABNF | |
210 | - <https://en.wikipedia.org/wiki/Augmented_Backus–Naur_form>`__, and `YACC`_ | |
211 | - Most implementations of a given algorithm, use a dialect of a standard one, to enable :ref:`G2C-actions`, or .. | |
212 | - | |
213 | - Also Caste does this: We use the Caste-grammer, which is based on both EBNF and PEG; but using the classic ‘|’ | |
214 | - instead of the ‘\’ for ordered-choice. | |
215 | - | |
216 | -.. [#leftStack] | |
217 | - Without going into details left-recursion is hard for many parsing-algorithms. In the shown approach, a | |
218 | - rule-function (for a rule that is direct left-recurse) will call itself as first step. In this way no progress is | |
219 | - made, and the stack will quickly overrun. | |
220 | - | |
221 | -.. [#OrTables] | |
222 | - Some tools, like Yacc by example, use another approach. Instead of many functions it has a generic (run-time) library | |
223 | - that used code-tables; which are generated by the tool. Still, that is just a implementation detail. | |
224 | - | |
225 | -.. _LALR: https://en.wikipedia.org/wiki/LALR_parser | |
226 | -.. _LALR(1): LALR_ | |
227 | -.. _GLR: https://en.wikipedia.org/wiki/GLR_parser | |
228 | -.. _LL(k): https://en.wikipedia.org/wiki/LL_parser | |
229 | -.. _YACC: https://en.wikipedia.org/wiki/Yacc | |
230 | -.. _Bison: https://en.wikipedia.org/wiki/GNU_Bison | |
231 | -.. _Lexer: https://en.wikipedia.org/wiki/Lexical_analysis |
@@ -1,149 +0,0 @@ | ||
1 | -.. include:: /std/localtoc.irst | |
2 | - | |
3 | -.. _G2C-actions: | |
4 | - | |
5 | -=================== | |
6 | -No *inline* actions | |
7 | -=================== | |
8 | - | |
9 | -.. post:: 2022/05/21 | |
10 | - :category: Castle, DesignStudy | |
11 | - :tags: Castle, Grammar | |
12 | - | |
13 | - In :ref:`grammmar-code` we have mentioned that many compiler-compilers reuse the Yacc invention “actions”. And we | |
14 | - hinted already that Castle prefers an alternative. | |
15 | - | |
16 | - Let’s see why the old concept is outdated ... And what is easier to use. | |
17 | - | |
18 | -Actions, in retrospect | |
19 | -====================== | |
20 | - | |
21 | -When parsing an input with the aspiration to verify the input does matches the grammar only; a result as :math:`True` or | |
22 | -:math:`False` will do. Commonly this is *not* our goal; we want to act on the input. Or at least *read* the content. | |
23 | -|BR| | |
24 | -`Yacc`_ invented *actions*: embedded (C-) code-fragments that are copied into the generated parser. When the parser | |
25 | -reached that point the code as executed. You could anything you like: Build a parse-tree, or directly act on the | |
26 | -(partially) parsed input [#SAXDOM]_. | |
27 | - | |
28 | -It was great (back then). Many, also the more modern, parser-generators use inline-actions -- with the drawback that it | |
29 | -makes the grammer harder to read. In spite of the popularity of actions, I think we can do better, as lot has happend | |
30 | -since then. Most important: parsing-algorithms become a lot smarter. Yacc_ used a simple `LALR(1)`_ pattern; with only 1 | |
31 | -token lookahead. That allowed us to execute an action as soon a the input was read upto that point. Without backtracking | |
32 | -and other “considere alternatives”, that execution is always deterministic. | |
33 | - | |
34 | -Ambiguity | |
35 | ---------- | |
36 | - | |
37 | -With *“backtracking”* (and other *smartness*) this has chanced. Both the compiler-compiler and the resulting parsers | |
38 | -have to consider multiple ways on how to read the input. And may reconsider many tokens and lines later on how to parse | |
39 | -a (earlier) line. When execution actions “in-line”, the can become executed many times -- which probably isn’t what was | |
40 | -ment when specifying the grammer. | |
41 | - | |
42 | -Many strategies exist to solve this ambiguity. Some tools demand that each action have no side-effects. When a | |
43 | -pure-functions (as the are called) many times, the deliver exactly the same result, every time. So the issue is gone; | |
44 | -albeit it limits you in what your actions can do -- strictly speaking even printing a debug message is not allowed. | |
45 | -Others use this effect and cache the first result and reuse the next time(s). Again it works, but it limits on what | |
46 | -actions can do! | |
47 | -|BR| | |
48 | -A tools may also postpone all actions until the parser is confident on how to read (parse) the input -- often when all | |
49 | -input is read. Again it works, unless you expected (debug) output on the fly. | |
50 | - | |
51 | -In short: inline-actions have become more restricted and less useful when parser become smarter. Without solving the | |
52 | -need for maintainable grammers. | |
53 | - | |
54 | -Memory | |
55 | ------- | |
56 | - | |
57 | -Once memory was very restricted; a compiler-compiler that only needed a single token-lookahead was using not more memory | |
58 | -then needed. When needed, the programmer could use inline-actions to build the “parse-tree” on the fly. This has become the | |
59 | -standard. During parsing one builds a tree: a parse-tree. And often we postproces it afterwards [#SAXDOM]_. | |
60 | - | |
61 | -As modern tools need to (be able to) read the whole input anyhow to be able parse it, and the memory-issues is solved | |
62 | -[#fun]_, the need to process “actions” *inline* is gone. But we need a design to act in the input! | |
63 | - | |
64 | - | |
65 | -Visitors | |
66 | -======== | |
67 | - | |
68 | -The de-facto solution is **vistitors**. Remember, back-them the `Visitor Pattern`_ wasn't invented yet! But now | |
69 | -visitors_ are very popular to separates algorithms and data. We like to build the “parse-tree” in one component first | |
70 | -and, act on it with visitors_ (and friend) later; possible in another component. | |
71 | - | |
72 | -.. hint:: Visitors & friends | |
73 | - | |
74 | - There are many kinds of visitors; most (sub)patterns are very interwoven with the language that is used -- although | |
75 | - many programming-language do no have “build in” support for this pattern. It the developer who has to write all. | |
76 | - | |
77 | - In classic OO-languages, one write specially named methods in a class. That are called using single (or double) | |
78 | - dispatch; to handle the data-object ‘D’ the method `visit_D()` is called “automagically”. And for a subclass ‘S’ one | |
79 | - has to implement `visit_S()` -- even when it should do exactly the same as `visit_D()`; no inheritance here. | |
80 | - | |
81 | - Other languages, like CSS, use visitors_ slightly differently. Here `“selectors” | |
82 | - <https://en.wikipedia.org/wiki/CSS#Selector>`__ are use to *select* a part of a tree on which a scripts-alike | |
83 | - “declaration” will act. One can even select multiple parts; the system will interate over them automatically. | |
84 | - |BR| | |
85 | - Also `XLST <https://en.wikipedia.org/wiki/XSLT>`_ used this approach; here `XPATH | |
86 | - <https://en.wikipedia.org/wiki/XPath>`__ expressions are used to select the data. | |
87 | - |BR| | |
88 | - This kind of visitor needs language-support: to be able to separate which data is to be pick and which actions has to | |
89 | - be performed on all found parts. | |
90 | - | |
91 | - | |
92 | - Most likely there are even more variants of this pattern (and even within the OO-languages, various version | |
93 | - exist). For me, and for now, it are all “**visitors** (or *friends*)”. | |
94 | - |BR| | |
95 | - Castle will have a more advanced version; as it should be easy for developer (and hard to make mistakes). | |
96 | - | |
97 | - | |
98 | -Castle Has build-in visitors | |
99 | -============================ | |
100 | - | |
101 | -.. resolution:: Castle Grammers should not need “inline-actions” | |
102 | - :ID: RG_NoInlineActions | |
103 | - | |
104 | - The traditional inline actions, as one invented by Yacc_, are outdated as the complicate the grammer, modern | |
105 | - parser-strategies need to read all input anyhow and we aren’t that restricted in memory anymore. So, an alternative | |
106 | - that make the code better maintainable is to be preferred. | |
107 | - | |
108 | - .. tip:: It does not imply Castle (or a future version) is not allowed to support inline-actions | |
109 | - | |
110 | - Grammer-tules are just functions; so why not allow pseudo-rules, that act as inline-actions, but are just regular | |
111 | - functions (with the same signature) | |
112 | - | |
113 | -.. Use:: Castle Grammers can use Visitors | |
114 | - :ID: UG_GrammerVisitors | |
115 | - | |
116 | - To act on data, and to separate the data and the action, Castle will support Visitors that can act on Grammers; or | |
117 | - more accurate: on the trees that result from a parser-invocation. | |
118 | - | |
119 | - .. tip:: To enable this, Castle has a (generic, abstract) data-type ``Tree``; see :ref:`tree-type`. | |
120 | - | |
121 | - With (parser)visitors, it should be possible to “select” a (set of) tree-part(s), and “call” an some code that will | |
122 | - act on that data. Typically, that “code” will be a function (or other callable), but it can also be a lambda, or a | |
123 | - “code block”. | |
124 | - | |
125 | ----------------------------- | |
126 | - | |
127 | -.. rubric:: Footnotes | |
128 | - | |
129 | -.. [#SAXDOM] | |
130 | - With hindsight we can compare this how we handled and are handling XML (and/or HTML) now. | |
131 | - | |
132 | - It started with `SAX`_: “events” that act as small *actions* as soon that part was read/parsed (remember: pasting XML | |
133 | - is simple as the tags denote the tree). Nowadays, everybody is using the `DOM`_: the whole input is converted to a | |
134 | - tree first (the `DOM`_) and *visitor-alike* “scripts” will process this `DOM`_ afterwards. | |
135 | - | |
136 | -.. [#fun] | |
137 | - Just for fun: Guess, what is bigger: All source-code of the complete Linux-kernel, or one (high definition) movie? | |
138 | - | |
139 | - | |
140 | -.. _YACC: https://en.wikipedia.org/wiki/Yacc | |
141 | -.. _SAX: https://en.wikipedia.org/wiki/Simple_API_for_XML | |
142 | -.. _DOM: https://en.wikipedia.org/wiki/Document_Object_Model | |
143 | - | |
144 | - | |
145 | -.. _LALR: https://en.wikipedia.org/wiki/LALR_parser | |
146 | -.. _LALR(1): LALR_ | |
147 | - | |
148 | -.. _Visitor Pattern: https://en.wikipedia.org/wiki/Visitor_pattern | |
149 | -.. _Visitors: `Visitor Pattern`_ |
@@ -1,11 +0,0 @@ | ||
1 | -================ | |
2 | -About the syntax | |
3 | -================ | |
4 | - | |
5 | -.. toctree:: | |
6 | - :maxdepth: 2 | |
7 | - :titlesonly: | |
8 | - :glob: | |
9 | - | |
10 | - * | |
11 | - |
@@ -1,18 +0,0 @@ | ||
1 | -TODO (Design) | |
2 | -************* | |
3 | - | |
4 | -Tree as std data-structure | |
5 | -========================== | |
6 | - | |
7 | -.. todo:: | |
8 | - | |
9 | - * .. seealso: :ref:`matching-statements` | |
10 | - | |
11 | - * Allow (aside of trees), also non-cyclic graps? | |
12 | - | |
13 | - * Allow (local) “links” in the tree | |
14 | - | |
15 | - - ala html: a/href | |
16 | - - ala xlm: XLINK | |
17 | - - Use XPATH/CSS alike syntax | |
18 | - - Use ‘id’ |
@@ -0,0 +1,68 @@ | ||
1 | +======================= | |
2 | +Castle FSM syntax tries | |
3 | +======================= | |
4 | + | |
5 | +.. note:: Based on some experiments we select “a” language to highlight the examples. | |
6 | + Its just try&error; there is no relation with that language, Castle or a FSM! | |
7 | + | |
8 | +Try 1 | |
9 | +===== | |
10 | + | |
11 | +.. code:: ReasonML | |
12 | + | |
13 | + FSM AB { | |
14 | + state A, B, C; | |
15 | + | |
16 | + A + event_1 -> state_B, action_I; | |
17 | + A + event_2 -> state_C, action_II; | |
18 | + B + event_1 -> state_D, action_III; | |
19 | + Z1 + event_1 -> state_Z2; // No action | |
20 | + Z1 + event_1 -> ,action_only; // Empty state: do not change | |
21 | + Z1 + event_1 -> action_only; // No new state | |
22 | + // Note: In the last line Castle knows it only an action, as “action_only” is not a state! | |
23 | + // Potentially it conflict with the “redundancy rule” | |
24 | + Z1 + event_1 -> None, action_only; // None-state: do not change | |
25 | + } | |
26 | + | |
27 | +Variant a | |
28 | +--------- | |
29 | +Actions with ``(`` `parameters-list` ``)``. **Question**: Do we know those parameters here. Or are the default? | |
30 | + | |
31 | +.. code:: ReasonML | |
32 | + | |
33 | + FSM AB { | |
34 | + state A, B, C; | |
35 | + | |
36 | + A + event_1 -> state_B, action_I(p1,p2, p3); | |
37 | + A + event_2 -> state_C, action_II(); | |
38 | + B + event_1 -> state_D, action_III(); | |
39 | + Z1 + event_1 -> state_Z2; // No action | |
40 | + Z1 + event_1 -> ,action_only(); // Empty state: do not change | |
41 | + Z1 + event_1 -> action_only(); // No new state | |
42 | + // Note: In the last line Castle knows it only an action, as “action_only” is not a state! | |
43 | + // Potentially it conflict with the “redundancy rule” | |
44 | + Z1 + event_1 -> None, action_only(); // None-state: do not change | |
45 | + | |
46 | + } | |
47 | + | |
48 | + | |
49 | +Variant b | |
50 | +--------- | |
51 | +No FSM/State prequel nor block | |
52 | + | |
53 | +.. code:: ReasonML | |
54 | + | |
55 | + state A, B, C; | |
56 | + | |
57 | + A + event_1 -> state_B, action_I; | |
58 | + A + event_2 -> state_C, action_II; | |
59 | + B + event_1 -> state_D, action_III; | |
60 | + Z1 + event_1 -> state_Z2; // No action | |
61 | + Z1 + event_1 -> ,action_only; // Empty state: do not change | |
62 | + Z1 + event_1 -> action_only; // No new state | |
63 | + // Note: In the last line Castle knows it only an action, as “action_only” is not a state! | |
64 | + // Potentially it conflict with the “redundancy rule” | |
65 | + Z1 + event_1 -> None, action_only; // None-state: do not change | |
66 | + | |
67 | + | |
68 | + |
@@ -0,0 +1,14 @@ | ||
1 | +=============== | |
2 | +Language Design | |
3 | +=============== | |
4 | + | |
5 | +Castle has to be designed. Not only the “compiler”, but also the language itself. And the **“CC” concept**, And .... | |
6 | + | |
7 | +.. toctree:: | |
8 | + :maxdepth: 2 | |
9 | + :titlesonly: | |
10 | + :glob: | |
11 | + | |
12 | + * | |
13 | + | |
14 | + |
@@ -0,0 +1,18 @@ | ||
1 | +TODO (Design) | |
2 | +************* | |
3 | + | |
4 | +Tree as std data-structure | |
5 | +========================== | |
6 | + | |
7 | +.. todo:: | |
8 | + | |
9 | + * .. seealso: :ref:`matching-statements` | |
10 | + | |
11 | + * Allow (aside of trees), also non-cyclic graps? | |
12 | + | |
13 | + * Allow (local) “links” in the tree | |
14 | + | |
15 | + - ala html: a/href | |
16 | + - ala xlm: XLINK | |
17 | + - Use XPATH/CSS alike syntax | |
18 | + - Use ‘id’ |
@@ -10,8 +10,8 @@ | ||
10 | 10 | |
11 | 11 | --ALbert Mietus |
12 | 12 | |
13 | -It’s also the first programming-language that support **CC**: Connected Components. Where `CC` is kind of of the | |
14 | -successor of OO: active ‘things’ that communicate (solely) by input *and* output ports ... | |
13 | +It’s also the first programming-language that support **CC**: Connected Components (or *Concurrent Components*). Where | |
14 | +`CC` is kind of of the successor of OO: active ‘things’ that communicate (solely) by input *and* output ports ... | |
15 | 15 | |BR| |
16 | 16 | *(Yes, I know, ambition and reality are not always aligned...)* |
17 | 17 |
@@ -32,7 +32,7 @@ | ||
32 | 32 | ‘One day’ the pages will be incorporated into the (docs of, the source of) `CCastle2 <https://osdn.net/users/albertmietus/pf/CCastle2>`_ |
33 | 33 | |
34 | 34 | .. toctree:: |
35 | - :maxdepth: 2 | |
35 | + :maxdepth: 3 | |
36 | 36 | :titlesonly: |
37 | 37 | :glob: |
38 | 38 |
@@ -47,3 +47,11 @@ | ||
47 | 47 | **2017**). which has no theme and other support to make it more nice-looking. Therefore all those “lines” are comment |
48 | 48 | out (or rewritten) |
49 | 49 | |
50 | + | |
51 | +Needs (index) | |
52 | +============== | |
53 | + | |
54 | +.. needtable:: | |
55 | + :style: table | |
56 | + :sort: title | |
57 | + |
@@ -52,4 +52,7 @@ | ||
52 | 52 | |
53 | 53 | wc: |
54 | 54 | @echo "lines words file" |
55 | - @wc -lw `find CCastle/ -iname \*rst`|sort -r | |
55 | + @wc -lw `find CCastle/ -iname \*rst`|sort -r | grep -v /index.rst | grep -v /zz.todo.rst | |
56 | + | |
57 | +sidebar: | |
58 | + @grep "include::" `find CCastle/ -type f -name \*.rst` /dev/null | grep sidebar| sort| sed 's/:../:\t\t ../' |
@@ -73,3 +73,26 @@ | ||
73 | 73 | .rst-content .localtoc.sidebar { |
74 | 74 | max-width:40%; width: auto; |
75 | 75 | } |
76 | +.rst-content h5, | |
77 | +.rst-content h6 { | |
78 | + margin-bottom: 0; | |
79 | + color: #000066; | |
80 | +} | |
81 | + | |
82 | +.rst-content a.external { | |
83 | + color: inherit; | |
84 | + border: 0.5px solid #d6d6d6; | |
85 | + text-decoration: underline; | |
86 | + text-decoration-color: #d6d6d6; | |
87 | +} | |
88 | +.rst-content a.external:visited { color:inherit;} | |
89 | +.rst-content a.external:hover { | |
90 | + color:#000066; | |
91 | + text-decoration: underline; | |
92 | + text-decoration-color: #000066; | |
93 | +} | |
94 | +aside.sidebar { line-height: inherit; } | |
95 | +aside.sidebar .rubric { | |
96 | + margin-bottom: 0; | |
97 | + color: #000066; | |
98 | +} |
@@ -0,0 +1,11 @@ | ||
1 | +.. -*- rst -*- | |
2 | + USE AS: | |
3 | + .. include:: /std/localtoc2.irst | |
4 | + | |
5 | +.. sidebar:: On this page | |
6 | + :class: localtoc | |
7 | + | |
8 | + .. contents:: | |
9 | + :depth: 2 | |
10 | + :local: | |
11 | + :backlinks: none |