3 ms·

What I don't like about these state machine DSLs is that they are not really composable at the "machine level". It is a known fact that FSM are equivalent to re

What I don't like about these state machine DSLs is that they are not really composable at the "machine level". It is a known fact that FSM are equivalent to regular expressions [1] Alternatively, a regular language can be defined as a language recognised by a finite automaton. The equivalence of regular expressions and finite automata is known as Kleene's theorem I think a cool state machine language would use this fact as a starting point for it's syntax. Another very useful feature would be "functions" to isolate specific repetitive parts of FSM [1]: https://en.wikipedia.org/wiki/Regular_language https://en.wikipedia.org/wiki/Regular_language

almostgotcaught 2y ago
How would you use this fact to make fsms composable when regexes aren't composable...?
- aziis98 2y ago
  Most common regex implementations are not composable at the language level but there are more modern alternatives like Pomsky [1] that introduce bindings and actually make regexes composable expressions. By the way regular expressions are "composable" by definition as they are defined recursively as (in their simplest form) - ε is the regex that matches the empty string - given regexes A and B we can construct the new regex AB that matches first the regex A followed by B - given regexes A and B we can construct A|B that matches A or B - given a regex A the regex A* matches any number of repeated occurrences of A Then for some reason languages like javascript don't provide a way of constructing /foo/.concat(/bar/) // equivalent to /foobar/ but that is another problem. [1]: https://pomsky-lang.org/ https://pomsky-lang.org/
  - almostgotcaught 2y ago
    > - given regexes A and B we can construct the new regex AB that matches first the regex A followed by B > - given regexes A and B we can construct A|B that matches A or B Concatenation and alternation is not what one typically imagines when they utter the word composition (unless you expect me to understand "composition over inheritance" to mean actually "just use two classes instead of one").
    - mportela 2y ago
      Hmm, concatenation and alternation are exactly what I thought of when reading the work "composition" (I probably had functional programming in mind). I'm curious. What came to your mind for "composition"?
      - deleted 2y ago
        [deleted]
      - almostgotcaught 2y ago
        I already said it: what does the phrase "composition over inheritance" mean? > probably had functional programming in mind Then you should have no trouble recognizing that there is no analog to `f . g . h` for regexes.
LargoLasskhyfv 2y ago
https://en.wikipedia.org/wiki/Ragel https://en.wikipedia.org/wiki/Ragel ?
diggan 2y ago
At a glance, this seems to implement both FSM and Statecharts, and Statecharts are composable AFAIK.
jll29 2y ago
FOMA is a finite state transducer library that creates composable FSTs. FSTs are generlaizations from one-sided FSAs in that while they accept input they also write and output (they are further elegant because they are not only composable but also reversable: switching input and output tames with "up" and "down" is trivial, so the same formalism can be used to analyze and generate). FOMA [1] is an open source clone of the Xerox XFST tools [2,3] developed at Xerox Research Laboratory Europe in Grenoble under the late Prof. Lauri Karttunen. While the FOMA/XFST family of tools are most suitable for linguistic applications and for teaching formal language theory, I have been impressed by the fact that they are the only formalism that permits elegant naming and re-use of sub-automata. [1] https://fomafst.github.io/ https://fomafst.github.io/ [2] https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=81ae62b783db79d7d310399d3a30e0cc24d09edf https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d... [3] https://dsacl3-2018.github.io/xfst-demo/ https://dsacl3-2018.github.io/xfst-demo/
emmanueloga_ 2y ago
xstate and other libraries like it implement Harel's statecharts, which are an extension of FMSs with different semantics and composability (a.k.a. "hierarchy", where machines can embed other machines), so the relationship with regular expressions may not be that useful. "Classic state diagrams require the creation of distinct nodes for every valid combination of parameters. For all but the simplest of systems, this can lead to a very large number of nodes and transitions between nodes (state and transition explosion), which reduces the readability of the state diagram." [1] "What's missing in the traditional state machines is the mechanism for factoring out the common behavior in order to share it across many states. UML state machines address exactly this shortcoming of the conventional FSMs. They provide a number of features for eliminating the repetitions so that the complexity of a UML state machine no longer explodes..." [2] -- 1: https://en.wikipedia.org/wiki/State_diagram#Harel_statechart https://en.wikipedia.org/wiki/State_diagram#Harel_statechart 2: https://en.wikipedia.org/wiki/UML_state_machine#UML_extensions_to_the_traditional_FSM_formalism https://en.wikipedia.org/wiki/UML_state_machine#UML_extensio...

almostgotcaught 2y ago

How would you use this fact to make fsms composable when regexes aren't composable...?

aziis98 2y ago
Most common regex implementations are not composable at the language level but there are more modern alternatives like Pomsky [1] that introduce bindings and actually make regexes composable expressions. By the way regular expressions are "composable" by definition as they are defined recursively as (in their simplest form) - ε is the regex that matches the empty string - given regexes A and B we can construct the new regex AB that matches first the regex A followed by B - given regexes A and B we can construct A|B that matches A or B - given a regex A the regex A* matches any number of repeated occurrences of A Then for some reason languages like javascript don't provide a way of constructing /foo/.concat(/bar/) // equivalent to /foobar/ but that is another problem. [1]: https://pomsky-lang.org/ https://pomsky-lang.org/
- almostgotcaught 2y ago
  > - given regexes A and B we can construct the new regex AB that matches first the regex A followed by B > - given regexes A and B we can construct A|B that matches A or B Concatenation and alternation is not what one typically imagines when they utter the word composition (unless you expect me to understand "composition over inheritance" to mean actually "just use two classes instead of one").
  - mportela 2y ago
    Hmm, concatenation and alternation are exactly what I thought of when reading the work "composition" (I probably had functional programming in mind). I'm curious. What came to your mind for "composition"?
    - deleted 2y ago
      [deleted]
    - almostgotcaught 2y ago
      I already said it: what does the phrase "composition over inheritance" mean? > probably had functional programming in mind Then you should have no trouble recognizing that there is no analog to `f . g . h` for regexes.

LargoLasskhyfv 2y ago

https://en.wikipedia.org/wiki/Ragel https://en.wikipedia.org/wiki/Ragel ?

diggan 2y ago

At a glance, this seems to implement both FSM and Statecharts, and Statecharts are composable AFAIK.

jll29 2y ago

FOMA is a finite state transducer library that creates composable FSTs. FSTs are generlaizations from one-sided FSAs in that while they accept input they also write and output (they are further elegant because they are not only composable but also reversable: switching input and output tames with "up" and "down" is trivial, so the same formalism can be used to analyze and generate). FOMA [1] is an open source clone of the Xerox XFST tools [2,3] developed at Xerox Research Laboratory Europe in Grenoble under the late Prof. Lauri Karttunen. While the FOMA/XFST family of tools are most suitable for linguistic applications and for teaching formal language theory, I have been impressed by the fact that they are the only formalism that permits elegant naming and re-use of sub-automata. [1] https://fomafst.github.io/ https://fomafst.github.io/ [2] https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=81ae62b783db79d7d310399d3a30e0cc24d09edf https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d... [3] https://dsacl3-2018.github.io/xfst-demo/ https://dsacl3-2018.github.io/xfst-demo/

emmanueloga_ 2y ago

xstate and other libraries like it implement Harel's statecharts, which are an extension of FMSs with different semantics and composability (a.k.a. "hierarchy", where machines can embed other machines), so the relationship with regular expressions may not be that useful. "Classic state diagrams require the creation of distinct nodes for every valid combination of parameters. For all but the simplest of systems, this can lead to a very large number of nodes and transitions between nodes (state and transition explosion), which reduces the readability of the state diagram." [1] "What's missing in the traditional state machines is the mechanism for factoring out the common behavior in order to share it across many states. UML state machines address exactly this shortcoming of the conventional FSMs. They provide a number of features for eliminating the repetitions so that the complexity of a UML state machine no longer explodes..." [2] -- 1: https://en.wikipedia.org/wiki/State_diagram#Harel_statechart https://en.wikipedia.org/wiki/State_diagram#Harel_statechart 2: https://en.wikipedia.org/wiki/UML_state_machine#UML_extensions_to_the_traditional_FSM_formalism https://en.wikipedia.org/wiki/UML_state_machine#UML_extensio...