Commit: d6d4ac508aa513458776610d9de2708fef2cea7d - DocIdeas (hg)

Commit MetaInfo

• Révision: d6d4ac508aa513458776610d9de2708fef2cea7d (tree)
• l'heure: 2022-06-06 19:29:23
• Auteur: Albert Mietus < albert AT mietus DOT nl >
• Commiter: Albert Mietus < albert AT mietus DOT nl >

Message de Log

ASIS: Busy with syntax for FSMs

Change Summary

• modified: CCastle/1.Usage/1.CompilerCompiler.rst
• modified: CCastle/1.Usage/4.FSMs-are-needed.rst
• modified: CCastle/2.Design/eval/FSM/5.eval-syntax.rst
• modified: CCastle/2.Design/index.rst
• modified: CCastle/2.Design/syntax/2.grammar_code.rst
• modified: CCastle/2.Design/syntax/3.NoActions.rst
• modified: Makefile
• add: CCastle/2.Design/syntax/FSM_try_1.rst

Modification

diff -r 5b6aa7194b81 -r d6d4ac508aa5 CCastle/1.Usage/1.CompilerCompiler.rst
--- a/CCastle/1.Usage/1.CompilerCompiler.rst	Sat Jun 04 16:04:15 2022 +0200
+++ b/CCastle/1.Usage/1.CompilerCompiler.rst	Mon Jun 06 12:29:23 2022 +0200
@@ -9,7 +9,7 @@
 
 .. post:: 2022/05/7
    :category: Castle, Usage
-   :tags: Castle, grammar
+   :tags: Castle, Grammar
 
    In Castle you can define a *grammar* directly in your code. The compiler will *translate* them into functions, using
    the build-in (PEG) **compiler-compiler** -- at least that was it called back in the days of *YACC*.

diff -r 5b6aa7194b81 -r d6d4ac508aa5 CCastle/1.Usage/4.FSMs-are-needed.rst
--- a/CCastle/1.Usage/4.FSMs-are-needed.rst	Sat Jun 04 16:04:15 2022 +0200
+++ b/CCastle/1.Usage/4.FSMs-are-needed.rst	Mon Jun 06 12:29:23 2022 +0200
@@ -20,7 +20,6 @@
 FSMs, an intro
 **************
 
-
 .. include:: FSM-sidebar-code.irst
 
 The well known `State pattern`_ is basically an FSM_. It has a *finit* (**!**) number of ``states``, ``inputs`` (often

diff -r 5b6aa7194b81 -r d6d4ac508aa5 CCastle/2.Design/eval/FSM/5.eval-syntax.rst
--- a/CCastle/2.Design/eval/FSM/5.eval-syntax.rst	Sat Jun 04 16:04:15 2022 +0200
+++ b/CCastle/2.Design/eval/FSM/5.eval-syntax.rst	Mon Jun 06 12:29:23 2022 +0200
@@ -10,16 +10,109 @@
    :category: Castle, Design
    :tags: Castle, FSM
 
-   As described in `FSMs-are-needed` *Finit State Machines* are great and needed -- even tough no (main) programming
+   As described in :ref:`FSMs-are-needed` *Finit State Machines* are great and needed -- even tough no (main) programming
    language has syntax support for it. But there are other (computer) language that (more-or-less) support the
    corresponding `State pattern`_.
    |BR|
-   By example plantUML_ --very populair by mature developers-- has a syntax to draw them
+   By example plantUML_ --very populair by mature developers-- has a syntax to draw them.
 
-   What can we learn for them? That is the topic of this post, before we define the Castle syntax
+   What can we learn from them? That is the topic of this post, before we define the Castle syntax.
+
+Goal: Short & Maintainable
+**************************
+
+Before we can define the (Castle) syntax for FSM_\s, we should know where we are aiming for. We need to support “all”
+kinds of FSM, as required by :need:`U_FSM_Syntax` and refined by :need:`U_FSM_extensions`. E.g. the syntax should
+allow non-determinism. And like all parts of Castle maintainability and preventing mistakes is important.
+|BR|
+For a FSM this means **short**: avoid boilerplate-code.
+
+The FSM_\`s mathematical model is simple: a set of `states` (‘:math:`S`’), the input `events` (‘:math:`E`’),
+the transaction `rules` (‘:math:`R`’), a `start-state` (‘:math:`S0`’), and the `final-states` -- which are not needed
+for a SW-FSM [#final-action]_. Usually, a set of `actions` (‘:math:`A`’) is required too. Where this set is implicitly
+defined: the actions are listed inside the rules.
+|BR|
+Each `rule` is relation :math:`R := S * E -> S, A`; this “table” is typically the biggest part of an FSM.
+
+So, to make a FSM-code compact, we have to focus on the rules.
+|BR|
+It’s tempting to regard this rule-set as a *matrix*: with (‘:math:`S`’) and (‘:math:`E`’) on the axes and the
+next-states [#non-determinism]_ (and actions) inside each cell. Nevertheless this matrix is huge and probably sparse:
+most cells are empty, as the combination does not occur.
+
+We can describe such a sparse-matrix by listing the cell-value with the coordinates. This boils-down to listing the
+rules, one by one.
+|BR|
+The disadvantage of this that many states and/or events are listed many times. As we will see below, some languages
+solve this by factor-out `states` and/or `events`.
 
 
-**************
+
+
+
+
+
+
+.. hint:: Concurrency is not needed
+
+   FSM’s can be huge in code but do not need a lot of computer-power. For every *step* --one input--, one state-variable
+   has to be updated. And the action has to be triggered. That action can be “big”, the FSM itself not.
+   Therefore, the syntax of the FSM doesn't need special attention to make the FSM concurent.
+
+
+XXXXXX
+********
+
+plantUML: State diagram:
+   - https://en.wikipedia.org/wiki/PlantUML
+   - https://plantuml.com/state-diagram
+
+DOT/graphviz
+   - https://en.wikipedia.org/wiki/DOT_(graph_description_language)
+   - https://www.graphviz.org
+
+State Chart XML (SCXML): State Machine Notation for Control Abstraction
+   - https://www.w3.org/TR/scxml/
+
+Regel
+   - https://en.wikipedia.org/wiki/Ragel
+   - http://www.colm.net/open-source/ragel/
+
+Dezyne (of Verum)
+   - https://verum.com/discover-dezyne/
+   - https://dezyne.org/dezyne/manual/dezyne/html_node/A-Simple-State-Machine.html
+
+Frame
+  - https://modeling-languages.com/designing-hierarchical-state-machines-using-frame-notation/
+
+Thompson's construction (Use a RegExp to construct a NFA)
+   - https://en.wikipedia.org/wiki/Thompson%27s_construction
+
+SMC (State Machine Compiler)
+   - http://smc.sourceforge.net
+   - http://smc.sourceforge.net/slides/SMC_Tutorial.pdf
+   - UncleBobVideo version:  https://github.com/unclebob/CC_SMC
+
+
+
+
+
+
+
+
+
+-------
+
+.. rubric:: Footnotes
+
+.. [#final-action]
+   The final-states are used by mathematics to verify/accept an input. Whereas a SW-FSM is typically used to control a
+   system; and run *forever*. When a “final state” is needed in a SW-FSM, typical a “final-action” is used.
+
+.. [#non-determinism]
+   Remember, we have to support non-determinism! Each cell in the matrix can have multiple “next states” (and
+   corresponding actions).
+
 
 
 

diff -r 5b6aa7194b81 -r d6d4ac508aa5 CCastle/2.Design/index.rst
--- a/CCastle/2.Design/index.rst	Sat Jun 04 16:04:15 2022 +0200
+++ b/CCastle/2.Design/index.rst	Mon Jun 06 12:29:23 2022 +0200
@@ -12,3 +12,28 @@
    *
    */index
 
+
+.. note:: In case you are wondering: *“Are FSMs and Grammars related, or the same?”*
+
+   The are related, but not equal. 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”.
+
+   A non-deterministic Push~Down machine (`PDA <https://en.wikipedia.org/wiki/Pushdown_automaton>`__) is needed to
+   recognise a “Type-2” (CFG) Grammar. (Which is a simple version of a stack-machine, which is lot more restricted then a Turing Machine).
+   |BR|
+   And as a FSM is one of the most restricted machines that exist --it can recognise only “Type-3” `Regular grammar
+   <https://en.wikipedia.org/wiki/Regular_grammar>`__-- a FSM can’t be used to recognise a (CFG) grammar.
+
+   .. seealso::
+
+      .. postlist::
+         :category: Castle
+         :tags: FSM
+
+      .. postlist::
+         :category: Castle
+         :tags:  Grammar

diff -r 5b6aa7194b81 -r d6d4ac508aa5 CCastle/2.Design/syntax/2.grammar_code.rst
--- a/CCastle/2.Design/syntax/2.grammar_code.rst	Sat Jun 04 16:04:15 2022 +0200
+++ b/CCastle/2.Design/syntax/2.grammar_code.rst	Mon Jun 06 12:29:23 2022 +0200
@@ -8,7 +8,7 @@
 
 .. post:: 2022/05/14
    :category: Castle, DesignStudy
-   :tags: Castle, grammar, PEG
+   :tags: Castle, Grammar, PEG
 
    In :ref:`Castle-CompilerCompiler` we have seen that we can define a grammar within a Castle-program. And we have
    argued that each grammars-rule can be considered as a function.

diff -r 5b6aa7194b81 -r d6d4ac508aa5 CCastle/2.Design/syntax/3.NoActions.rst
--- a/CCastle/2.Design/syntax/3.NoActions.rst	Sat Jun 04 16:04:15 2022 +0200
+++ b/CCastle/2.Design/syntax/3.NoActions.rst	Mon Jun 06 12:29:23 2022 +0200
@@ -8,7 +8,7 @@
 
 .. post:: 2022/05/21
    :category: Castle, DesignStudy
-   :tags: Castle, grammar
+   :tags: Castle, Grammar
 
    In :ref:`grammmar-code` we have mentioned that many compiler-compilers reuse the Yacc invention “actions”. And we
    hinted already that Castle prefers an alternative.

diff -r 5b6aa7194b81 -r d6d4ac508aa5 CCastle/2.Design/syntax/FSM_try_1.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/CCastle/2.Design/syntax/FSM_try_1.rst	Mon Jun 06 12:29:23 2022 +0200
@@ -0,0 +1,68 @@
+=======================
+Castle FSM syntax tries
+=======================
+
+.. note:: Based on some experiments we select “a” language to highlight the examples.
+          Its  just try&error; there is  no relation with that language, Castle or a FSM!
+
+Try 1
+=====
+
+.. code:: ReasonML
+
+   FSM AB {
+     state A, B, C;
+
+     A + event_1  ->  state_B, action_I;
+     A + event_2  ->  state_C, action_II;
+     B + event_1  ->  state_D, action_III;
+     Z1 + event_1 ->  state_Z2;            // No action
+     Z1 + event_1 ->  ,action_only;        // Empty state: do not change
+     Z1 + event_1 ->  action_only;  // No new state
+     // Note: In the last line Castle knows it only an action, as “action_only” is not a state!
+     // Potentially it conflict with the “redundancy rule”
+     Z1 + event_1 ->  None, action_only;        // None-state: do not change
+   }
+
+Variant a
+---------
+Actions with ``(`` `parameters-list` ``)``.  **Question**: Do we know those parameters here. Or are the default?
+
+.. code:: ReasonML
+
+   FSM AB {
+     state A, B, C;
+
+     A + event_1  ->  state_B, action_I(p1,p2, p3);
+     A + event_2  ->  state_C, action_II();
+     B + event_1  ->  state_D, action_III();
+     Z1 + event_1 ->  state_Z2;            // No action
+     Z1 + event_1 ->  ,action_only();        // Empty state: do not change
+     Z1 + event_1 ->  action_only();  // No new state
+     // Note: In the last line Castle knows it only an action, as “action_only” is not a state!
+     // Potentially it conflict with the “redundancy rule”
+     Z1 + event_1 ->  None, action_only();        // None-state: do not change
+
+   }
+
+
+Variant b
+---------
+No  FSM/State prequel nor block
+
+.. code:: ReasonML
+
+     state A, B, C;
+
+     A + event_1  ->  state_B, action_I;
+     A + event_2  ->  state_C, action_II;
+     B + event_1  ->  state_D, action_III;
+     Z1 + event_1 ->  state_Z2;            // No action
+     Z1 + event_1 ->  ,action_only;        // Empty state: do not change
+     Z1 + event_1 ->  action_only;  // No new state
+     // Note: In the last line Castle knows it only an action, as “action_only” is not a state!
+     // Potentially it conflict with the “redundancy rule”
+     Z1 + event_1 ->  None, action_only;        // None-state: do not change
+
+
+

diff -r 5b6aa7194b81 -r d6d4ac508aa5 Makefile
--- a/Makefile	Sat Jun 04 16:04:15 2022 +0200
+++ b/Makefile	Mon Jun 06 12:29:23 2022 +0200
@@ -49,3 +49,6 @@
 	@BRANCH=$${BRANCH:-`hg branch`} ;\
 	curl -X POST -d "branches=$${BRANCH}" -d "token=${TOKEN}" ${HOOK}
 	@echo
+
+wc:
+	wc -lw `find CCastle/ -iname \*rst`|sort -r