FSL: A programming language to make complex finite state machines easy to create

State machines are a great way to control defects by producing states which are only able to mutate in certain specific pre-defined ways

The defacto example is usually a traffic light. Green is permitted to transition to yellow, but never to red; a state machine makes a bug of that form impossible

Obviously, it's nominally used for more complex stuff, but in general, all of your appliances are state machines. Your microwave especially.

The problem is that this uses your new custom language which is not yet documented. I had seen this, I asked for alternatives because it doesn't seem to be an option yet.

The examples in your README also seem very limited, with no guards/actions/recursion/parallelism (correct me if I'm wrong). The last two I can do without but it seems overly simplistic as of now.

Yes. ♥ Target compilers for languages and other FSM libraries are a core goal, and I believe this is probably the single most important thing my language needs (comparables in portable external hooks and user-defined state datatypes.) I want the frontend and backend (and the database and the PaaS and the orbital weapons platform and the barbeque) to run the same machine, even when they aren't the same language.

A bunch of these, and some I haven't listed yet due to sloth, are already implemented and just not published yet because they're not satisfactorily tested, and because I still don't know what I'm doing about portable hooks

https://github.com/StoneCypher/fsl/issues/418

https://github.com/StoneCypher/fsl/issues?q=is%3Aissue+is%3A...

https://github.com/StoneCypher/fsl/issues?q=is%3Aissue+is%3A...

There are, actually, things like what you describe already - SMC, Canopy, and Ragel, by example, and depending on how you look at it, there's sort of an argument for Drakon and some others. I'm making mine because they don't fit my needs, but if you need something right now, they're options.

SMC is probably the best of those in my opinion. It reaches 14 languages including most of the stuff you'll actually want, is durable, near-zero-bug once you learn what it means by its phrasings, reasonably fast, and does mostly everything you're likely to want in practice. It is entirely adequate from basically every angle, something very few state machines can say (mine cannot.)

But also I'm hungry for users, so please try mine and let me know how you think I could improve. I believe that my ease of use characteristics are pretty nice, and my opinion is that ease of use is probably the Genuinely Big Barrier to fsm usage.

My opinion is that mine is simple enough that people who don't know these things can often see the value. To me, that seems important.

  import { sm } from 'jssm';
  
  const coworker = sm`
    not_convinced -> [whats_a_fsm dont_like_fsm js_has_no_lib];
    whats_a_fsm   -> this -> try_it -> ok;
    dont_like_fsm -> why -> [complicated boring intimidating];
     complicated   -> compare_machine_to_code -> oh;
     boring        -> are_case_blocks_a_party -> oh;
     intimidating  -> but_you_can_read_this -> and_you_dont_speak_this -> oh;
    js_has_no_lib -> tons_of_them -> jssm_is_an_easy_one -> oh;
    oh            -> ok -> ill_try_jssm;
  `;

Try giving them this and the resulting graph, and when they look at you funny, afterwards, give them some beefy awful thing with a bunch of control logic from your existing product, rewritten in a state machine, also with the resulting graph

The resulting graph: https://stonecypher.github.io/jssm-viz-demo/graph_explorer.h...

If they're still on the fence, ask them how TCP works and give them a machine to read

TCP machine to read: https://stonecypher.github.io/jssm-viz-demo/graph_explorer.h...

One dollar on PayPal says they'll come around fast

> The examples in your README also seem very limited

Agreed.

.

> with no guards

It's not entirely clear what you mean by a guard. Isn't the entirety of a state machine a guard?

If you mean transitions that are disallowed due to embedded mealy values, that's meant to be handled by the return value from hooks. That runs but isn't published yet because the test cases aren't yet adequate

.

> actions

  const yeah_huh = sm`has_actions 'tell_em' -> neat;`;

or less glibly

  const matter = sm`
  
                   solid  'melt' 
     'freeze'   liquid 'boil' 
     'condense' gas    'ionize' 
     'deionize' plasma;
  
  `;

.

> recursion

State machines don't have control behavior and in general should not have direct expression of "recursion," unless I misunderstand what you mean

If you mean machines self-embedding, that is planned, and I don't know of anyone else who does that

.

> parallelism

Nothing stops you from putting a machine in each of a bunch of threads or web workers or whatever. By example, if you were making a Roller Coaster Tycoon style game, having one FSM to model each park visitor or each ride or each garbage pile or whatever would actually be fairly reasonable.

Granted, I'd probably just make an array of them and process them serially in a single web worker, because you'd want the world synchronized and fast, but, it's doable.

The core concept of a finite state machine has no direct association with process control and within a single finite state machine it's not actually clear to me what parallelism would mean within a single FSM. I've never seen this in any other state machine library. If this is what you mean, I'd like to hear more, possibly including an example API.

It's possible that I misunderstand you.

.

> it seems overly simplistic as of now.

If you can find a finite state machine with more features, please let me know where.

> Respectfully, no, it sounds like you write them yourself, instead

I write them myself and prove them, and then use them.

Or, more likely, I take code from elsewhere, reduce it to its core, prove that — if possible; it often isn't, because code from elsewhere is often fundamentally Turing-hard — and then, if I was able to prove it, use it.

Or, even more likely, I use a library of self-contained code that lives inside the prover's model, that someone else already did all the hard work of getting the prover to accept.

Think of it like this: would you call an arbitrary utility function from an HTTP library inside a reference implementation of a cryptographic cipher?

No, because that arbitrary utility function has no abstract-mathematical equivalent. You can't prove anything about code that contains a black-box like that. The code, with the call to the HTTP library inside it, isn't a discrete-mathematics-specified-in-procedural-language proof of anything any more.

If you want to prove anything about code, the code needs to 1. live inside your proof (along with all its transitive dependencies), and 2. be modified such that all its base types are types that have complete models in your chosen prover's algebra (e.g. no non-fixed-size bit-vectors.)

> I apologize, but you and I have strongly contrasting opinions here.

What are FSMs "for" in your mind, then?

I use them when I want to be able to prove the behavior of something formally, and then reuse the proof as a production-quality implementation of that thing as-is. This allows the design↔implementation equivalent of "documentation drift" to be avoided — you don't have to trust that the programmer that translated the math into code did it correctly this time; you just have to trust a single compiler/code generator (that itself can have been proof-verified.)

I use FSMs for the same reason I use PEGs, or cellular automata, or other such formalisms, in place of just trying to prove an abstract Turing machine: because there are known ways to prove certain properties of these low-power formalisms in bounded time, while there's no known (or sometimes, no possible) equivalent for Turing machines generally.

> My library, and finite state machines, which are the superfamily containing DFA and a great many other things. DFA is not a common interpretation of the phrase FSM; usually that phrase means a Mealy machine or a Moore machine, or maybe a Harel machine.

You're being a lot more pedantic here than I was attempting to be. I meant to refer to "deterministic finite-state transducers" — the class of thing to which Mealy machines are a subset. But people on HN don't know what those are, while they do generally know what a DFA is. And a DFA has the same computational power as a Mealy machine generally; it's just a special construction of one (like a Binary Search Tree is just a special construction of a Binary Tree.)

I was trying to contrast with NFAs, which aren't FSMs (deterministic finite-state transducers) at all, but rather are computationally-equivalent to pushdown automata.

Maybe, rather than a DFA, I should have made the analogy to LR parsing, which also has equivalent abstract-computational-power requirements.