Hacker News Reader

Comment by aziis98 | Hacker News Reader

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

View on HN

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

2: https://en.wikipedia.org/wiki/UML_state_machine#UML_extensio...

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/

[2] https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d...

[3] https://dsacl3-2018.github.io/xfst-demo/

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

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

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

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/

> - 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").

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"?

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.

Reply on news.ycombinator.com