Lucy: A concise language for describing Finite State Machines | Hacker News Reader

Lucy: A concise language for describing Finite State Machines

pkg.spooky.click

126 pointswhatever328 comments

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/

[1]: https://astro.build/

[2]: https://github.com/lucydsl/liblucy

[3]: https://github.com/matthewp/robot

robot seems interesting, but I wonder why they didn't stick with the elegance of the Lucy language.

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.

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.

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

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.

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

Where do you see the disagreement with XState's approach?

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/

[1]: https://stately.ai/docs/xstate-v4/xstate/advanced/scxml

Thanks!

I'm on my phone right now, so can't try Robot but I'm wondering what the type safety story looks like. For instance, in the example in "Getting started" the variable `users` is defined irrespective of the state, even though it is only available in the `loaded` state.

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

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.

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

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

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/

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

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-contr...

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 if anyone wants to see the gory bits.

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

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.

This is an abandonned project :(

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

> 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!

Reply on news.ycombinator.com