4 ms·

Lucy: A concise language for describing Finite State Machines

126 points by whatever3 2y ago

mbitard 2y ago
This is an abandonned project :(
- masklinn 2y ago
  Oh yeah, it's more than just dead, the repo is actually archived.
whilenot-dev 2y ago
A DSL for XState[0] by the co-creator of astro.build[1], cool! But the repo[2] has been archived and there is an active FSM library from the same developer called robot[3]. [0]: https://xstate.js.org/ https://xstate.js.org/ [1]: https://astro.build/ https://astro.build/ [2]: https://github.com/lucydsl/liblucy https://github.com/lucydsl/liblucy [3]: https://github.com/matthewp/robot https://github.com/matthewp/robot
- mentalgear 2y ago
  robot seems interesting, but I wonder why they didn't stick with the elegance of the Lucy language.
  - MatthewPhillips 2y ago
    Writing a language, even a DSL is a lot of work. It's not enough to just make a good language, there's also a whole world of tooling support that people expect nowadays. Also ultimately it was hard to sell the idea of living in a different file format from the rest of your code. This is always a tough sell for DSLs. Even languages as good as CSS and SQL struggle with this for a lot of devs.
    - whilenot-dev 2y ago
      A JavaScript-only implementation of robot suffers a similar fate as a DSL without proper tooling, as states and actions are just some custom strings that need to be repeated, no? An implmenetation with good types would provide useful autocompletion, and I can see there was a similar conclusion and types have been implemented with generics. Haven't used it yet to confirm the behavior (at a first glance it seems like a few more strings would need to be inferred), but it would be helpful to mention this somewhere for us TypeScript folks.
- CGamesPlay 2y ago
  Robot, in turn, links to [0], which has a nice section that goes over an example of when all this is useful (which was missing from the Lucy page). [0]: https://thisrobot.life https://thisrobot.life
  - whilenot-dev 2y ago
    And the following part Instead of conforming to an XML specification created decades ago, Robot takes the best ideas from both academia and real-world usage of finite state machines. This makes state machines easy to read and understand, as there is only one way to do most common tasks. ...is hinting at some disagreements with XState's approach. Would be nice to have a visualization tool, like the kind XState has, for any FSM library (like robot) though.
    - steve_adams_86 2y ago
      The visualization tool goes a long way in helping non-developers understand what logic is actually doing, from a relatively wide perspective. It’s valuable for sure
    - codethief 2y ago
      Where do you see the disagreement with XState's approach?
      - whilenot-dev 2y ago
        XState famously always conformed to the SCXML spec[0]. It isn't mentioned anymore in the current version anywhere(?), but you can still see it in the v4 docs[1]. [0]: https://www.w3.org/TR/scxml/ https://www.w3.org/TR/scxml/ [1]: https://stately.ai/docs/xstate-v4/xstate/advanced/scxml https://stately.ai/docs/xstate-v4/xstate/advanced/scxml
        codethief 2y ago
        Thanks!
zokier 2y ago
One thing that saddens me is how Ragel petered out, I guess they got bit too ambitious with the Colm rewrite. But it was a state machine language that saw a blip of usage at one point
aziis98 2y ago
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").
TypingOutBugs 2y ago
> This repository has been archived by the owner on Dec 12, 2023. It is now read-only. Hasn't been updated in 4 years, and is now archived, so I assume this project is dead. Looks good though!
v9v 2y ago
I quite like the concise state machine definitions used in Rodney Brooks' "A Robust Layered Control System for a Mobile Robot"[0]. The first element is the state name, and whatever is returned is the next state. (defmodule avoid :inputs (force heading) :outputs (command) :instance-vars (resultforce) :states ((nil (event-dispatch (and force heading) plan)) (plan (setf resultforce (select-direction force heading)) go) (go (conditional-dispatch (significant-force-p resultforce 1.0) start nil)) (start (output command (follow-force resultforce)) nil))) [0] https://www.semanticscholar.org/paper/A-robust-layered-control-system-for-a-mobile-robot-Brooks/fb39b30187babe9bee4afb30b034b5f93b74859a https://www.semanticscholar.org/paper/A-robust-layered-contr...
jesuslop 2y ago
There is also vintageish SCXML underwritten by the w3c, with the panoply of xml friends (an xsd schema hence validator, xpath queries and xslt transforms). Also being part of the uml chart family it should be xmi-borne, if you wondered.
shaftway 2y ago
At one point I built a type-based state machine core for Java. The idea was to use interfaces and classes as the basis for defining what transitions are allowed, and as a way to store the associated fields. It relied on Java's type-checking to guide you into using it correctly. public interface TurnstileState {} public interface LockedState extends TurnstileState {} public class UnlockedState implements TurnstileState { public final int credits; public UnlockedState(int credits) { this.credits = credits; } } public static final LockedState LOCKED = new LockedState() {}; StateMachine<TurnstileState> turnstile = StateMachine.<TurnstileState>.newBuilder() .addValidTransition(LockedState.class, UnlockedState.class) .addValidTransition(UnlockedState.class, LockedState.class) .addValidTransition(UnlockedState.class, UnlockedState.class) .buildWithInitialState(LOCKED); turnstile.transition(new UnlockedState(1)); I never got around to building out examples in Kotlin. I feel like the type checking there would streamline a ton of this even further. https://github.com/Hounshell/st8 https://github.com/Hounshell/st8 if anyone wants to see the gory bits.

126 points by whatever3 2y ago

mbitard 2y ago

This is an abandonned project :(

masklinn 2y ago
Oh yeah, it's more than just dead, the repo is actually archived.

whilenot-dev 2y ago

A DSL for XState[0] by the co-creator of astro.build[1], cool! But the repo[2] has been archived and there is an active FSM library from the same developer called robot[3]. [0]: https://xstate.js.org/ https://xstate.js.org/ [1]: https://astro.build/ https://astro.build/ [2]: https://github.com/lucydsl/liblucy https://github.com/lucydsl/liblucy [3]: https://github.com/matthewp/robot https://github.com/matthewp/robot

mentalgear 2y ago
robot seems interesting, but I wonder why they didn't stick with the elegance of the Lucy language.
- MatthewPhillips 2y ago
  Writing a language, even a DSL is a lot of work. It's not enough to just make a good language, there's also a whole world of tooling support that people expect nowadays. Also ultimately it was hard to sell the idea of living in a different file format from the rest of your code. This is always a tough sell for DSLs. Even languages as good as CSS and SQL struggle with this for a lot of devs.
  - whilenot-dev 2y ago
    A JavaScript-only implementation of robot suffers a similar fate as a DSL without proper tooling, as states and actions are just some custom strings that need to be repeated, no? An implmenetation with good types would provide useful autocompletion, and I can see there was a similar conclusion and types have been implemented with generics. Haven't used it yet to confirm the behavior (at a first glance it seems like a few more strings would need to be inferred), but it would be helpful to mention this somewhere for us TypeScript folks.
CGamesPlay 2y ago
Robot, in turn, links to [0], which has a nice section that goes over an example of when all this is useful (which was missing from the Lucy page). [0]: https://thisrobot.life https://thisrobot.life
- whilenot-dev 2y ago
  And the following part Instead of conforming to an XML specification created decades ago, Robot takes the best ideas from both academia and real-world usage of finite state machines. This makes state machines easy to read and understand, as there is only one way to do most common tasks. ...is hinting at some disagreements with XState's approach. Would be nice to have a visualization tool, like the kind XState has, for any FSM library (like robot) though.
  - steve_adams_86 2y ago
    The visualization tool goes a long way in helping non-developers understand what logic is actually doing, from a relatively wide perspective. It’s valuable for sure
  - codethief 2y ago
    Where do you see the disagreement with XState's approach?
    - whilenot-dev 2y ago
      XState famously always conformed to the SCXML spec[0]. It isn't mentioned anymore in the current version anywhere(?), but you can still see it in the v4 docs[1]. [0]: https://www.w3.org/TR/scxml/ https://www.w3.org/TR/scxml/ [1]: https://stately.ai/docs/xstate-v4/xstate/advanced/scxml https://stately.ai/docs/xstate-v4/xstate/advanced/scxml
      - codethief 2y ago
        Thanks!

zokier 2y ago

One thing that saddens me is how Ragel petered out, I guess they got bit too ambitious with the Colm rewrite. But it was a state machine language that saw a blip of usage at one point

aziis98 2y ago

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

TypingOutBugs 2y ago

> This repository has been archived by the owner on Dec 12, 2023. It is now read-only. Hasn't been updated in 4 years, and is now archived, so I assume this project is dead. Looks good though!

v9v 2y ago

I quite like the concise state machine definitions used in Rodney Brooks' "A Robust Layered Control System for a Mobile Robot"[0]. The first element is the state name, and whatever is returned is the next state. (defmodule avoid :inputs (force heading) :outputs (command) :instance-vars (resultforce) :states ((nil (event-dispatch (and force heading) plan)) (plan (setf resultforce (select-direction force heading)) go) (go (conditional-dispatch (significant-force-p resultforce 1.0) start nil)) (start (output command (follow-force resultforce)) nil))) [0] https://www.semanticscholar.org/paper/A-robust-layered-control-system-for-a-mobile-robot-Brooks/fb39b30187babe9bee4afb30b034b5f93b74859a https://www.semanticscholar.org/paper/A-robust-layered-contr...

jesuslop 2y ago

There is also vintageish SCXML underwritten by the w3c, with the panoply of xml friends (an xsd schema hence validator, xpath queries and xslt transforms). Also being part of the uml chart family it should be xmi-borne, if you wondered.

shaftway 2y ago

At one point I built a type-based state machine core for Java. The idea was to use interfaces and classes as the basis for defining what transitions are allowed, and as a way to store the associated fields. It relied on Java's type-checking to guide you into using it correctly. public interface TurnstileState {} public interface LockedState extends TurnstileState {} public class UnlockedState implements TurnstileState { public final int credits; public UnlockedState(int credits) { this.credits = credits; } } public static final LockedState LOCKED = new LockedState() {}; StateMachine<TurnstileState> turnstile = StateMachine.<TurnstileState>.newBuilder() .addValidTransition(LockedState.class, UnlockedState.class) .addValidTransition(UnlockedState.class, LockedState.class) .addValidTransition(UnlockedState.class, UnlockedState.class) .buildWithInitialState(LOCKED); turnstile.transition(new UnlockedState(1)); I never got around to building out examples in Kotlin. I feel like the type checking there would streamline a ton of this even further. https://github.com/Hounshell/st8 https://github.com/Hounshell/st8 if anyone wants to see the gory bits.