FSL: A programming language to make complex finite state machines easy to create
fsl.tools
fsl.tools
I'll go change the site. It had never been released, announced, or indicated.
This is being shared because there's a complete programming language in active use by many people
https://github.com/StoneCypher/jssm
It's under the github link under libraries
I added some top material to the site to make what's happening clearer
“Using the live editor” is a Chicken fighting ninja, “What are state machines?” is a black woman singing(the cover is a laughing Jesus, why?), “Why FSL?” is Video unavailable, “Publishing a machine” is The history of Japan.
My guess is something is broken in their back-end, or this got found and posted before the creators were ready for it to get publicity. The sample code also links out to /#todo, so I think my "not quite ready" idea may be what's up.
Shame, this looks like it'd be a cool project.
I just haven't written the site yet
Yeah, I haven't made any of the videos yet. I'm camera shy and it's scary to be on the internet, so I've been dragging my heels.
I didn't expect anyone to find the website so I thought it wasn't a big deal
Ragel compiles its source into a separate file in the target language (C, Ruby, ASM, etc). FSL instead has a library that parses and runs the FSL source at run time.
Ragel supports (or plans to support) C, C++, ASM, Objective C, D, Go, Ruby, and Java. FSL supports (or plans to support) Javascript, C and Erlang.
The live editor does seem to be somewhat unique to FSL. It's at https://stonecypher.github.io/jssm-viz-demo/graph_explorer.h... Try, for example, changing "flow: down" to "flow: right".
I'm not a fan
One thing I've learned personally writing live editors is that while recompile on every key seems neat, in practice it is very jarring to have things jump around every keystroke. The problem with this is that mid-typing you may express an invalid program, so your rendered output jumps wildly from something coherent to something completely wrong, only to resolve itself when you're done typing. This is why I think it's best practice to explicitly recompile on ctrl+enter, even if you have the ability to do it every keystroke.
I didn't expect anyone to find it It's just not done
Workin' on it now ™
.
> This is why I think it's best practice to explicitly recompile on ctrl+enter, even if you have the ability to do it every keystroke.
This is interesting, and I like it
I'm gonna leave it in its current default behavior because I believe that it has a strong impact on ease of onboarding to just see what you did without explicitly requesting it.
But, I think I'm going to make this a configurable option, so that you can have the thing you wanted, and I may even start working this way myself (gonna have to try it and see how it feels.)
Thank you for the idea, and please keep them coming. I appreciate your help.
I am most likely to notice them in the FSL issue tracker: https://github.com/StoneCypher/fsl/issues
An actual, proper language, for making FSMs probably makes more sense. Lol. But still, the conceptual similarity between a thread-of-execution and FSMs must remain in the back of most programmer's minds. All turing machines are FSMs, and your code determines the state. (When executing "foo" function, you're in the "foo" state. And the "foo" function easily tells you either to return to the previous state, or which states to move forward in).
https://github.com/StoneCypher/jssm-viz
If you just want one to use, rather than to embed in your own software, The thing everyone's calling a live editor is actually the JSSM-viz demo. You can use that
https://stonecypher.github.io/jssm-viz-demo/graph_explorer.h...
It's kept outside of the main repo because, like xstate's, it's built on a transcompile of graphviz called viz.js, which is made with emscripten
It's several meg, and not many people want visualization, so I keep them in separate packages
You can get the graphviz code by hitting "dot" at the top, if you want to customize in ways the language doesn't know
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.
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;`;
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.
Parallel states [1] are compound states with multiple distinct regions, where each region transitions separately. It does not necessarily imply threading on the programming side, it might just be multiple separate actors. Both PlantUML and XState support them.
XState: https://xstate.js.org/docs/guides/statenodes.html#state-node... PlantUML: https://plantuml.com/state-diagram
[1]: https://statecharts.github.io/glossary/parallel-state.html
Almost all of the finite state machines use the same underlying graphing tool, "GraphViz," to do their rendering. It sounds like you might want that.
There is an emscripten transcompile for the web called viz.js.
.
> if you have actions/guards that don't appear on the visualization
Actions do appear on the visualization. I'm still not sure what you mean by guards.
.
> imilarly, by recursion I meant putting states inside states (from a behavior perspective you would call them compound states); Both PlantUML and XState supports that. Parallel states [1] are compound states with multiple distinct regions
It looks like one of XState or PlantUML tried to rename Heirarchical Orthogonal State Regions, and the other copied the first one.
.
What you're calling "recursion" is called a Heirarchical State Machine. It appears that XState uses the regular name for these:
https://xstate.js.org/docs/guides/hierarchical.html
External reference:
https://barrgroup.com/embedded-systems/how-to/introduction-h...
.
What you're calling Parallel States is properly called an Orthogonal Region. It's problematic to call these parallel for exactly the following statement, where you suggest that this "doesn't necessarily imply threading;" this wrong name that XState and PlantUML has used has confused you.
*All state machines are by definition single threaded single context. This may not and will never be implemented with threading, nor actors. This has nothing to do with process parallelism. This cannot be implemented in a parallel way by any machine, ever.*
External reference:
https://www.boost.org/doc/libs/1_47_0/libs/msm/doc/HTML/ch02....
https://en.wikipedia.org/wiki/UML_state_machine#Orthogonal_r...
It looks like neither PlantUML nor XState allow for orthogonal regions in a way that copes with superstates, which is a very serious limitation. Their orthogonal regions seem to just subdivide whatever nested state you're currently in. This defies the core concept of an orthogonal region, which is to allow unrelated parallel pseudostates. If the context dominates which pseudostates are actually available, then this is little better than a tagged record.
Respectfully, XState and PlantUML seem to have produced the wrong tool, here. Please look to Boost, instead, which gets this very right.
I'll give two examples: one a silly one, to make what the difference actually is make sense, then a better one, to explain why it should matter.
The silly one is an extension of the keyboard example used in Wikipedia's UML state machine orthogonal region discussion. In brief, they propose a state for a keyboard which treats the main keyboard effectively separately of the numeric keypad. There are relevant separate state bits for each, eg caps lock on left and num lock on right.
To extend this, consider the APL keyboard, which is a programmer's keyboard which can switch between two layouts on the left. One is whatever your local natural language is; the other is a special layout for the programming language APL, which uses a bunch of novelty symbols. You need an actual layout switch because the control keys aren't just in different positions, but are actually different control keys (it uses meta and opt.)
In a UML state machine, the natural thing to do is:
1) Model each language's keyboard left as its own machine; 2) same thing for the APL keyboard; 3) also the keypad; 4) create an orthogonal region with the keypad on the right 5) put an HFSM in the left to swap between APL and whatever natural language(s) you're using
The problem is, if the orthogonal region is just a subdivision of your bottom level organization, step 5 isn't possible.
Worse still, this even still implies a pretty clean division of what's "on the left" and what's "on the right." They're modules that snap together and don't talk to each other.
What if these are power plants? These two over here go down, this one over here has to start up. They have to be able to synchronize (it's a wave, waves cancel.)
When one of these plants goes up and down, it might have multiple reactors. Some of those reactors might have multiple engagements. They might have differential backup. If the coal plant nearby is running, when solar comes online it doesn't need its LNG backup because there's already in-fill.
If these so-called "orthogonal states" are just being able to track several state elements and a contemporary context bit, as this appears to be, then you can't have them switching independently in any meaningful way.
I wish tools like XState and PlantUML wouldn't change the name of primary tools. If they used the correct name for this, you'd realize how wildly limited the thing you're looking at is as compared to what it's supposed to be.
.
Now that I understand where you're getting your terms, I assume that when you say "guards," you mean what XState calls "guarded transitions." That's a simple case of returning 0 from any hook.
Yes, JSSM does this. No, it doesn't render that on the visualization. I'm not sure what that ought to look like, to be frank.
.
With regards to HSMs, I do have a mechanism of this form, but, something significantly more powerful. It is as yet incomplete and as such unreleased. If you need that in your visualization, you're better off with XState (or GraphViz directly, more likely.)
I am fine with a tool using graphviz under the hood for rendering or layout, but I'm not writing my statecharts in graphviz syntax.
I borrowed the term "parallel state" from https://statecharts.github.io/glossary/parallel-state.html. Both XState and MermaidUML support them.
Again, I am concerned with plotting. I am not trying to use the language/library to implement any keyboard or power plant, I just want to get a plot with minimal efforts. Having to edit the SVG or graphviz to "fix" poorly supported advanced features if I ever need them is fine, so long as I can plot most machines and it doesn't take hours. PlantUML is the only tool I've found that fit, which surprises me.
I wish my colleagues knew what an FSM was and how to create one. Getting tired of seeing 400 nested IF statements sprinkled across 10 classes.
Something that makes it easy to create an FSM declaratively for any language might help raise awareness and spur adoption.
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;
`;
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
I'm not affiliated with the project, just found the link among all the other stuff there.
- [0]: https://stonecypher.github.io/jssm-viz-demo/graph_explorer.h...
Aside: I actually think HN might be better if no karma was given for link submissions.
The really nice thing about working with it is that all your components get much simpler about understanding when and how they should render. No longer are you trying to track state through some combination of variables or await statements, you are just asking, "Am I in this state? Great, I'll render." Double if you are managing animations or something else that takes wall clock time.
You also get an amazing visualizer and debug toolset where you can both see your app transition states, and inject the events to watch it transition states easily.
Would highly recommend checking out xstate in front end dev.
Obviously, as the author of one of these things, I'm a pretty big fan of FSMs. And, y'know, even though the entire point of mine is to be easy and convenient to use, I still don't use it very often.
Most jobs aren't for FSMs.
Finite state machines aren't well applied everywhere. There are a lot of cases where you could use a finite state machine, but shouldn't. A chess board is an example: it is a well described state, there's clear right or wrongness to changes, there's no ambiguity or intermediate states, etc. However, managing a board that complicated, dealing with rules like en passant and castling, it'd be a hassle. You don't get enough value out of it, and so it doesn't matter what you're using. Yes, FSMs can handle chess; no, it's not a good choice IMO.
But then, there are times when it's well applied.
When it's something where an FSM is a good choice, and you've used a low-hassle library, my opinion is that they tend to make systems night-and-day simpler.
Consider creating a finite state machine for the state of any single given payment. Now, when the external actor changes their process, the FSM wedges and you get notified, instead of switching to a state that used to be impossible and isn't anymore, in software that isn't ready for that. That's a huge level of immunity to large classes of bugs.
My opinion is that FSMs are well applied when the cost of a state reaching a bad configuration is very high.
You wouldn't use them to manage the image in a paint program.
You would use them to control the airplane's jet being on or off.
If you're in a situation where they're well applied? Now it's going to matter a lot which system you actually use.
I have great respect for `xstate`, by example. It doesn't fit my preferences, but it's fast, robust, and largely bug-free. It's reliable, easy to work with, well documented, and has a good solid community. If you use `xstate` you'll have a good time, most likely.
By contrast, at a previous ruby job, we used a gem I'm not going to name. It was ahem not my favorite. It was slow, it was pretty easy to get it wedged when it shouldn't be, it relied on side state things as storage that weren't fundamental to the language, it was cryptic when it failed, et cetera.
Later, at that job, we switched to a different state machine gem. It was pretty hassle-ful; the datastructures needed to be manually converted because there was a slight difference in how the two gems saw the job which meant automatic conversion wasn't practical.
But we were sure glad we did! Once the other FSM library was in place, things were a breeze, the system was much easier to understand, and to control.
There's more to it than good or bad, though.
If I couldn't use my own, what would I use?
If it was business logic, I'd probably use `stent`. To me it's the easiest to debug, and seems the most robust. Their tracing tools are quite impressive.
If it was a redistributable react control, I'd probably use `fsmx`, or embed a cut-for-case one. Stent is 288k. FSMx is 24k. If it's typescript, I'll probably use `fsmachine` instead, which is 28k.
If I need transactionality, `edium` is my only real world choice.
If I need something that's easy for junior programmers to understand, I'll probably use `javascript-state-machine`.
If I need something to create documentation that's easy for non-programmers to use, it's very likely to be `state-machine-cat`.
And of course, if I could use my own, I'd prioritize it when doing less labor or having a shorter representation of the machine is better. For me, that's pretty much always shrugs `xState`'s light switch is 13 lines; `jssm`'s is a one-liner that's shorter than `xstate`'s import.
So.
What I would recommend is that you pick one that graphs for you, like `stent` or `xState` or `jssm` or `state-machine-cat`, and just try drawing out a rough of your business logic.
Maybe it's well implemented in a state machine. Maybe it isn't.
But once you've tried, it's usually pretty obvious which one it is. And it can be fun to try, y'know? New languages are neat.
If you have a bunch of little moving pieces that follow complicated rules and can't be wrong, there's a pretty solid chance that state machines are for you.
They're one of those tools that the right time isn't common, but when it is the right time, holy WOW do you want them
Many real world string pattern matching engines (regexes) implement features that can't be expressed using regular languages. Backreferences or any context sensitive extensions are not really regal expressions in that sense.
Just a weird thing that I have more than once had to do this in my career when someone dictated something had to be done with regular expressions when the requirements were for something that regular expressions were incapable of.
Generally a fight every time.. the people dictating regular expressions as the solution are picking it as a solution because they fundamentally don't understand the difference between finite/non-finite automata, mostly because there are way too many CS degree programs that award Bachelor's degrees without teaching undergrads what the difference is between a DFA, NFA, and a turing machine.
I just posted some youtube videos I enjoy to make sure the build toolchain was placing youtube videos correctly.
I know that sounds wacky, so let me pitch you on that idea :)
In ‘primitive’ Erlang (i.e. Erlang without OTP), each FSM state is just a function, that can contain its own event loop (`receive` statement) to accept input, and then can transition to a new state based on that input by tail-calling another function.
Such an Erlang module is a direct, 1:1 encoding of the FSM you’d draw on paper — and very readable as such — but is also plain-old executable Erlang code! In fact, this is basically the most idiomatic Erlang code you can write, syntactically. It’s when the language is at its best and most compact/expressive. (It’s also when all of Erlang’s weird syntax choices suddenly make perfect sense.)
You can easily author+maintain an FSM with a large/complex tree of states and sub-states, by just putting each state function with its various sub-state functions into its own module, and then having each module only expose the valid entry states for each sub-state set.
Because each independent FSM exists in its own actor (virtual thread of execution), you don’t need any more than this. You don’t need to worry about the data representation of the FSM — the FSM’s data representation is the actor’s process record + stack. And you don’t need to worry about how to “pump” the FSMs; they’re pumped by the runtime scheduler. (However, if you care about pinning down your concurrency model — e.g. if you’re trying to model a DSP — there are Erlang libraries for specific abstractions like CSP channels that you can use to do so.)
It’s very easy to write a static analysis pass to verify that a primitive Erlang module like this constitutes an FSM “and no more” — i.e. that it could be transpiled into any other formalism that instantiates an FSM (e.g. a regex; a DSP; etc.) Erlang even breaks down its compiler into helpful separate reusable components (all available to any Erlang program) to help you do this. And these components make it just as easy to do the actual transpilation, turning this Erlang code into whatever other kind of encoded formalism you like.
But, unlike most such formalism DSLs, it’s very easy to also break out of the FSM abstraction, and trade it for a more powerful one, if an FSM no longer works for your use-case. You’re working with regular Erlang code. So, if you just do a regular stack-frame-pushing call instead of a tail-call, now your FSM is a pushdown automaton. Or, if you pass a state variable on the stack along with each tail-call, now you’ve got a Turing machine.
Honestly, ignoring all the stuff about concurrency, Erlang source code / BEAM bytecode is an almost perfect abstract machine for reifying various computational formalisms in an externally-verifiable way. If I was working on a computational proof for some CS conjecture, I’d heavily consider 1. writing the problem statement in (primitive, non-OTP) Erlang, and then 2. writing a small transpiler that would convert Erlang to lemmas in Z3 or Coq. (I’ve already done this once or twice, actually.)
And, if I were implementing something like Cloudflare’s Edge Workers “but for FSMs” (e.g. some user-submitted pattern-matching automata for structured data, to filter user subscriptions to that structured data) then it’d be an extremely easy decision to standardize on (a restricted, static-analyzed at submit-time sub-ISA of) BEAM bytecode as the user-submitted program format. I would then just implement my worker server as a regular Erlang server that would load+run those checked BEAM modules.
Could you make a github repo with an example project implementing your solution?
A very nice thing about Rebel is that it can do (bounded) model checking using SMT solvers.
Currently, I believe (Pure) Objects (with restrictions!) are a better approach because it doesn't require a paradigm switch. We already know them and they are also little state machines, right?
If done right, we can also do explicit model checking etc, version control.
Actors/Erlang/Akka is also a good choice, although they add some complexity compared to objects: it's hard to do synchronous calls with Actors for instance.
I can't speak for parent poster, but, I imagine that they mean something like this (which is also almost valid prolog, and mozart/oz, and some others:)
-module(pattern_match_tl_fsm).
-export([ next/1, disable/1, enable/1, enabled/1, may_pass/1, create/0 ]).
next(red) -> green;
next(green) -> yellow; % allow the lack of a match to throw for off; there is
next(yellow) -> red. % no next state for a light that's turned off
enable(off) -> red. % allow the lack of a match to throw for every color;
% only lights turned off may be turned on
disable(red) -> off;
disable(green) -> off; % allow the lack of a match to throw for off; cannot
disable(yellow) -> off. % disable if already disabled
enabled(off) -> false;
enabled(_) -> true.
may_pass(green) -> true;
may_pass(yellow) -> careful;
may_pass(red) -> false;
may_pass(off) -> careful.
create() -> off.
TrafficLight = pattern_match_tl_fsm:create(),
TurnedOn = pattern_match_tl_fsm:enable(TrafficLight),
Step2 = pattern_match_tl_fsm:next(TurnedOn),
etc
import { sm } from 'jssm';
const make_light = () =>
sm`off -> red => green => yellow => red; [red yellow green] ~> off;`,
const safety = { red: false, green: true, yellow: 'careful', off: 'careful' },
enabled = light => light.state() !== 'off',
may_pass = light => safety[light.state()];
export { make_light, enabled, may_pass };
Of course, bringing in an interpreter and/or a compiler isn't zero cost, so if you only have a couple of the straight module ones, the first notation honestly can be a pretty good approach, and given Erlang's module compositional nature, it's frequent to have things that in other languages would be unrealistically simple. By example, the TCP/IP state machine is 11 states and 19 edges, and in my opinion would make sense in the first notation as its own standalone module in erlang. I believe that parent post has a solid point.
The reason one tool hasn't universally won is that there isn't a best way to do this, style of thing. Trade-offs.
Still, with the sm`` notation, I find that I very frequently one-liner state machines with <= 6 states, and that in my head they start to act like something adjacent to types. Like ... behavioral enumerations? Things that simple which behave in a fixed fashion are sorta-types in my head, and they become very easy to use as a structural element. I dunno. They start getting low-ish level-ish to me, especially when they're behind generators, even though in reality that isn't true at all. The library is sufficiently fast and sufficiently tested that I feel comfortable using them that way, at least.
Also, when you start thinking about larger state machines, which sometimes have 50 states and 200 transitions, it is my opinion that that they grow at such different rates can quickly become important. When I say the TCP machine with 11 and 19 makes sense as a standalone, to me, that's getting not too far from the upper limit of where I'd think spelling it out manually was smart. (Still, to be fair, most FSMs are simple, rather than complex, so that's not all that harsh of a cutting criterion in the balance.) Even when hyper-dense, my opinion is that the sm`` arrow notation can easily carry 10x the structure on-screen and be comfortably readable than the typical datastructure based approach.
For me, the `jssm` chain is modifying how I think about code in some subtle ways, and that makes me feel like there might be actual value there. I hope you'll give it a shot and tell me whether or not you agree.
HTH
Kind of, but notice that I mentioned receive statements. Those are important. I'll show what I mean this time, because I guess people aren't picturing what I'm describing:
https://gist.github.com/tsutsu/5543bcaec4448b1de0023fbde31c8...
(Got way too long to fit in an HN comment.)
> they start to act like something adjacent to types
Not just "adjacent"; automata are monoids!
I think I saw a language reify this concept once — where you were able to declare an abstract state-machine interface/protocol, and then the compiler would check that for implementations of that interface/protocol, each function actually has the proper precondition states (i.e. only reachable from those states' functions) and postcondition states (i.e. has live code-paths reaching exactly those functions.)
Interestingly, I think it did this with individual types for each state-transition function, rather than there being a single higher-level type for the digraph of functions.
Anyone know what language (or maybe it was a computational proof assistant) I'm referring to?
Well, there's like 50 others, many of whom are in heavy use in industry, so, I guess I feel like a lot of people think this is useful.
.
> I feel like Erlang is already a great language — almost a DSL — for “making complex finite-state machines easy to create.”
Erlang is almost my favorite language.
I've tried using both of its finite state machine libraries. I do not find them to be usable. The results are extremely verbose, and if one goes over around 30 states, I cease to be able to debug them.
The natural implementation of the TCP/IP state machine in FSL is eight lines; 315 bytes. The TCP/IP Erlang state machine example floating around is like ten times that size.
I find debugging that thing exhausting.
.
> It’s very easy to write a static analysis pass to verify that a primitive Erlang module like this constitutes an FSM “and no more”
It's not clear to me why you would want this
.
> Honestly, ignoring all the stuff about concurrency, Erlang source code / BEAM bytecode is an almost perfect abstract machine for reifying various computational formalisms
It can't implement anything without Okasaki juggling. You and I are in strong disagreement here.
FSMs are a great example. You either need to reach outside the Beam VM with `hipe_bifs:array` or you need to copy the entire machine state every time you want to mutate it.
.
> And, if I were implementing something like Cloudflare’s Edge Workers “but for FSMs”, it’d be an extremely easy decision to standardize on (a restricted, static-analyzed at submit-time sub-ISA of) BEAM bytecode.
At Cloudflare's scale, the inability to implement mutably would become a serious performance problem.
I'm not talking about gen_fsm or gen_statem — note how I said "without OTP" above. I'm talking about writing Erlang the way it was originally conceived before proc_lib existed — where each process has a module that's exclusively responsible for its own receive loop, rather than being a delegate module for a generic receive-loop manager framework (proc_lib).
That kind of Erlang code produces simple, easy-to-analyze bytecode. It doesn't integrate well with supervisors or whatever, but interoperation with the rest of the Erlang/OTP ecosystem isn't the point. You don't call into arbitrary slap-dash non-formalized libraries within code that's supposed to represent a mathematical formalism. (E.g. you wouldn't call an arbitrary library from within a PEG grammar DSL. This is why e.g. Yecc's Erlang callbacks happen after parsing, rather than instead of parsing. If they happened instead of parsing, you'd break the formalism of the parser, and wouldn't be able to trust that your grammar does in practice what it was proven to do in theory any more.)
Instead, you create your own little world inside the formalism, that maybe imports a few reusable pre-proven abstractions compatible with the formalism, or that opaquely maps into pre-proven abstractions that exist within the prover (e.g. Z3's bit-vectors.) Abstractions are available in most-any other interpreter / prover / generator / whatever-er for the same formalism.
> FSMs are a great example. You either need to reach outside the Beam VM with `hipe_bifs:array` or you need to copy the entire machine state every time you want to mutate it.
Why are you mutating something outside the FSM from within the FSM? If the only state isn't "the state" (i.e. what box you're in on the FSM diagram), then what you have is not an FSM (in the computability-theory sense) any more.
The point of an FSM is to reduce the "power" of reasoning needed to prove things about the abstract machine — and so to be able to make guarantees that Turing machines cannot make, like being able to prove termination — by constraining what side-effects an operation within the abstract machine can have. An FSM can only switch its state among one of a usefully-enumerable number of options, e.g. the set of functions in a module, or the possible values of a single machine-register. A pushdown automaton can only switch its state among the sets of all possible sequences of such usefully-enumerable options (i.e. stacks of FSM states.) Etc.
(Note that Erlang/OTP's gen_fsm and gen_statem aren't FSMs in the computability-theory sense, since they pass along a state variable. They can be used as such if you don't put anything in that variable — or even if you put a scalar in that variable and constrain its size — but even if you don't use it, the resulting bytecode still passes that variable along in a way that makes it harder to translate the bytecode into prover lemmas. But all the remote-call stuff to proc_lib code that's not part of the proof already makes that nigh-on impossible, so....)
I think we might be talking about very different things here but both calling them "FSMs." I'm talking about how Erlang's native syntax is really good at expressing https://en.wikipedia.org/wiki/Deterministic_finite_automaton (like non-backtracking regexps) succinctly. What are you talking about?
I apologize for overlooking this
.
> You don't call into arbitrary slap-dash non-formalized libraries
Respectfully, no, it sounds like you write them yourself, instead
.
> > FSMs are a great example. You either need to reach outside the Beam VM with `hipe_bifs:array` or you need to copy the entire machine state every time you want to mutate it. > > Why are you mutating something outside the FSM from within the FSM?
I'm not. I'm talking about the expense of the action of the FSM mutating itself.
.
> The point of an FSM is to reduce the "power" of reasoning needed to prove things about the abstract machine
I apologize, but you and I have strongly contrasting opinions here.
The rest of you trying to teach me what an FSM does is noted. Thank you for your time
.
> I think we might be talking about very different things here but both calling them "FSMs." I'm talking about how Erlang's native syntax is really good at expressing https://en.wikipedia.org/wiki/Deterministic_finite_automaton (like non-backtracking regexps) succinctly. What are you talking about?
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.
I think you're spending more time attempting to force this library to implement some computer science term you're familiar with than is warranted. JSSM doesn't fit any of those labels well.
DFAs are generally a small group of functions meant for parsing strings. JSSM isn't even superficially similar to a DFA, and most state machines in practice aren't implemented that way in my personal experience.
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.
I will attempt to adopt this. I've no idea where even to start
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.
How would you say this compares?
David has done a better job of making a nice setup. His tooling is cleaner. `xState` is slightly faster than `jssm`. `xState` is much more widely used than `jssm` (several orders of magnitude,) meaning that it is more trustworthy. He has more tutorials. He has more community. His documentation is not literally on fire.
I believe that my testing is significantly better. My library offers more features, including some fun exotic stuff like stochastic search. Whereas we both offer datastructure consumers (and they're similar,) I also offer a string DSL that is regularly 1/20 the byte count of the datastructure implementation. Terseness matters a lot to me. My typescript support is better. I have a live editor which I find has high value for understanding and debugging.
I guess in my impression, my biggest thing is the string language (super dense, super easy) and his biggest thing is his community (you can ask people questions)
Otherwise, in my impression we're quite similar. We both offer all the standard things; we both offer a visualizer; our visualizers look pretty similar because they're built on similar underpinnings.
Being honest, I'd say he's winning. But, not by much, and there are clear reasons to choose one over the other according to preferences, so please try both.