9 ms·

Statecharts: A Visual Formalism for Complex Systems (1987) [pdf]

142 points by Cieplak 6y ago

kejaed 6y ago
I've worked in the past with code bases that have what were called 'state machines' implemented with at best switch statements and at worse a lot of if's and else's and some state variables. I've also worked with code bases with a formally defined state machine object/concept, with pre-defined states, events, and state transitions driven by events. Question for the crowd: what would you call the non-state machine state machine in the first case?
- brentm 6y ago
  You'd probably still call it a state machine if that is what it's doing. Maybe not well implemented but it also depends. State machines are tricky to get right.
- carapace 6y ago
  > what would you call the non-state machine state machine in the first case? Ad hoc state-machines? I don't think there's a formal name for them.
  - kejaed 6y ago
    Ad-hoc is a great term for this, thanks.
- zanecodes 6y ago
  I would call the former an implicit state machine, while the latter is an explicit state machine.
  - kejaed 6y ago
    This is perfect, thanks!
- vbtemp 6y ago
  State machines implemented in-line with code usually end up as a mess. It's best if they are factored out, and implemented as a DSL inside a true state machine engine running as a somewhat independent service or library.
sktrdie 6y ago
Harel's recent work (which evolve from Statecharts) is so called Scenario-based programming. If interested I follow his work very closely and showcase his techniques in this article about bthreads: https://lmatteis.github.io/react-behavioral/ https://lmatteis.github.io/react-behavioral/
- jarym 6y ago
  Maybe I'm just super dumb but I don't get why such simple examples should be made so difficult. Take for instance the following: "Here were are introducing the 3 main critical pillars of Behavioral Programming; the request, wait and block semantics.". Except the previous block of code does not exhibit the 'block' semantic at all.
- anentropic 6y ago
  There is something weird in the implementation... > Try adding two X's in a row. It will not work. It's waiting for an O, and once that is triggered it waits for an X and so on. If you try to make a move out of turn it seems like the illegal move is still "queued up" somehow. So as soon as you make a legal move the previously attempted illegal one occurs, as it's now legal. In fact, this resulted in an interesting game where both sides won: { type: "X", payload: 0 } { type: "O", payload: 8 } { type: "X", payload: 1 } { type: "O", payload: 2 } { type: "X", payload: 3 } { type: "O", payload: 6 } { type: "X", payload: 7 } { type: "O", payload: 5 } { type: "X", payload: 4 } { type: "XWins" } { type: "OWins" } I guess it needs a few more behaviours...
  - sktrdie 6y ago
    Which version outputs this behavior? The earlier ones are on purpose buggy. As the computer bthread is added there's no way for it to start at tile 8. The point was to show how by adding new bthreads the system gets smarter and less buggy.
jarirajari 6y ago
Was also inspired by the Statecharts long time ago, and then saw an opportunity to go deeper into how server-side web applications could be implemented as state machines, and how it would ultimately lead into easier/faster programming where correct/complex patterns emerge from events, conditions, and actions. Wrote about it here: https://jarirajari.wordpress.com/2014/01/03/ecas-hierarchical-aspect-state-machine-aka-ecas-hasm/ https://jarirajari.wordpress.com/2014/01/03/ecas-hierarchica...
vbtemp 6y ago
People who gloss over this do so at your own risk. This technique is applicable for so, so many applications - even when it doesn't appear obvious at first. Factoring out complex control system logic into these (and related) formalisms dramatically enhances testability, substantially reduces code volume, and eliminates huge swaths of possible defects (not to mention seriously enhances formal verification and model checking). The "code" part for applications should basically be for data plumbing, and all decision-making and control logic should be factored into these. Thanks for posting this!!
- billfruit 6y ago
  Yes, but the heavy lifting required behind the scenes to make statecharts work seems quite elaborate, moreover it could be problematic to use blocking apis, like sockets etc with statecharts, perhaps?
  - mr_olive 6y ago
    On the contrary, in my experience such stateful APIs are a great use case for state machines. You just approach them differently. Instead of doing a blocking call, you introduce a "waiting for <something>" state. You leave the "blocking" state when the correct event comes, or after a timeout. And while you are waiting for the event, you don't just burn CPU cycles, but yield control quickly, so that other threads can execute in the meantime.
    - chrisweekly 6y ago
      I don't have much experience w them yet, but found the xstate lib well-documented, and also like swizec's take: https://swizec.com/blog/when-your-brain-is-breaking-try-xstate/ https://swizec.com/blog/when-your-brain-is-breaking-try-xsta...
    - adamkl 6y ago
      Additionally, you can use state machines server side to track stateful processes by simply serializing the “current” state of the machine and storing it somewhere. With the next request, reload the “current” state of the machine and transition to the next based on the incoming request. Rinse/repeat.
john-tells-all 6y ago
A modern elaboration is https://statecharts.github.io/ https://statecharts.github.io/ - very clear explanation of statecharts, and why you'd want to use them (they're an elaboration of state machines) - and why you wouldn't want to use them very interesting, thanks to OP!
- chrisweekly 6y ago
  Thanks! See also https://xstate.js.org/docs/#why https://xstate.js.org/docs/#why
spinningslate 6y ago
I have mixed feeling about the hierarchical facility in statecharts. I've certainly found it helpful in some cases; for example, handling "cancel" events that apply to a group of states. I've also seen huge, multi-level, multiple-parallel-region monsters that were impenetrable. Now, no formalism is immune to abuse: "just because you can, doesn't mean you should". But I've often found that the simpler state model formalism - without hierarchy - has led to cleaner design and better separation of logic. More generally though I do think state machines are somewhat underrated tools in the programmer's toolbox.
- adamkl 6y ago
  Agree. I’m a huge fan of this approach when developing complex UIs, but you can definitely run into “state explosion”. When you rigorously enumerate all the implicit states in your system you quickly realize that your system can have a lot of states. It’s a balancing act. How much rigour do you need vs. how much code are you willing to deal with. The implicit states will always be there whether you make them explicit via a state chart or not. But for simple things, it may not be worth the overhead.
  - specialist 6y ago
    Me three. Ages ago, I implemented an Illustrator style direct manipulation user interface. We had spent so much time analyzing, documenting, specifying in prep. My initial implementation, per our "perfect" spec, really sucked. Turns out there's a significant amount of fit and finish to a direct manipulation interface that I wasn't able to handle formally with charts and machines. Ended up with a bunch of special cases. Unanticipated knock on effects were unsatisfying negotiations with QA/Test (how to test) and tech writers (how to describe) our product. I've always wondered about that gap. Was I doing it wrong? Are there better formalisms? How'd Illustrator (and others) do their direct manipulations? With the rise of touch UI, I anticipate the problem space (complexity of the states) has gotten smaller. For instance, no modifier keys. But that's just a guess.
    - jcelerier 6y ago
adamkl 6y ago
This approach is a big boon to the development of complex UIs. If you are tired of littering your React/Angular/Vue/etc code with a litany of state flags (“isLoading”, “isError”, etc)[0] take a look at the de facto canonical state chart implementation for JavaScript, XState: https://xstate.js.org/docs/ https://xstate.js.org/docs/ It’s been a joy to work with and can replace other methods of managing state (i.e. redux) while constraining the behaviour of your UI to predictable states and interactions. [0] https://dev.to/davidkpiano/no-disabling-a-button-is-not-app-logic-598i https://dev.to/davidkpiano/no-disabling-a-button-is-not-app-...
- davidkpiano 6y ago
  Thanks for the kind words about XState (creator here)!
  - jen729w 6y ago
    It’s a big boon to the development of tiny simple UIs! I use XState to manage my login state. Not logged in, trying, logged in, log in failed, trying log out, logged out. The thing I love is the confidence the machine gives me. Unless I’ve buggered up completely, it basically can’t be wrong. That’s incredibly reassuring. Thanks for XState and all the work you put in to it. It’s an amazing thing.
    - adamkl 6y ago
      Funny you mentioned login state. I've used it for the exact same thing. I had a "userService" machine (embedded in a React UI) that handled all the legwork of an OAuth2 flow and ended with the user in an "authenticated" state with their details as part of the machine context (for use in any other part of the app via a custom hook). You are absolutely right, it couldn't be wrong. It always just worked exactly the way it was supposed to. I'm now working on a project that handles logins via a set of disconnected boolean flags flowing through redux and it is a mess.
  - compscistd 6y ago
    I didn’t know a thing about state machines and lately would deprioritize your xstate frontendmasters course on my learning queue just out of ignorance. For whatever reason, I just watched your React Rally video and I can think of a bunch of projects where state machines would help get the UI in order! A “legacy” ui we have (much older than a week) has these state flags (and then some): IsConfirmed IsSent IsSentAndConfirmed IsDraft IsLoading IsInTheEther IsError IsNaN I want to rewind the clock for a redo on that mega component but I suppose refactoring will have to do. Again, thank you for that great talk!
bmitc 6y ago
There is an edX course by David Harel (the author of this paper) and Michal Gordon called Programming for Everyone – An Introduction to Visual Programming Languages. I highly recommend it for anyone dealing with state, whether you’re a programmer, designer, engineer, or manager. https://www.edx.org/course/programming-for-everyone-an-introduction-to-visual https://www.edx.org/course/programming-for-everyone-an-intro...
breck 6y ago
Every graph can be represented by a 2-dimensional tree. Hence, every chart in this paper has a 2-D tree representation. You can write that 2-D representation, and then without any type of transforming (keeping the shape of the graph in tree form untouched), you can turn it into a 3-D statechart, via the use of a Tree Language (https://jtree.treenotation.org/designer/ https://jtree.treenotation.org/designer/) So you get a 2-D text encoding of the statechart, editable in any dumb text editor or spreadsheet, isomorphic to the visual circles and lines diagrams they have, just as a 3-D rendering. You could probably put that in a paper.
- uryga 6y ago
  > Every graph can be represented by a 2-dimensional tree. do you have a good reference for this encoding? i vaguely recall seeing something like this in a paper, but can't remember any specifics
  - breck 6y ago
    Here is the paper: https://github.com/treenotation/research/blob/master/papers/paper/treenotation.pdf https://github.com/treenotation/research/blob/master/papers/... It's not that traditional a style as I had no experience in academia until after I published it on arxiv, but I still stand by basically all of it. For the encoding all you need is 3 things: a node delimiter (generally newlines), a cell delimiter (generally tab or space), and an edge delimiter for parent/child relationships (generally reuse the tab or space from above). Think of a spreadsheet as a program, and that's the base encoding. From there you just need to define Grammars to get higher level constructs. This page (https://jtree.treenotation.org/designer/ https://jtree.treenotation.org/designer/) contains ~15 example grammars, including a grammar for grammars (similar to YACC or ANTLR). This is just the tip of the iceberg though, you can do really novel things with these languages that you don't see with all our traditional languages (like having N parse heads that start all over the place and move in all sorts of directions). So if you take these ideas and combine them with this "Statecharts" paper of 1987, what you would do is create a "Statecharts" Tree Language defining all the elements they have in that paper, and then people could write "programs" in this Tree Language, and then you could use the Compiler Compiler I linked to above to generate a compiler that reads those programs and either 1) compiles them to SVGs like they have in their paper or 2) generates 3-D visualizations where the program shape in the focus is unchanged.
fokinsean 6y ago
I'm getting a flashback from Sproutcore JS statecharts, wish I could say they were good times but I'm so glad I'm not developing with them anymore. https://guides.sproutcore.com/getting_started_2.html https://guides.sproutcore.com/getting_started_2.html
_pmf_ 6y ago
Hands down the best paper in software development.
emmanueloga_ 6y ago
When I first saw Statecharts I failed to realize that Statecharts are _NOT_ state machines, state machines are the building block. Quote from the paper: "... a complex system cannot be beneficially described in this naive fashion [state machines], because of the unmanageable, exponentially growing multitude of states, all of which have to be arranged in a ‘flat’ unstratified fashion, resulting in an unstructured, unrealistic, and chaotic state diagram. To be useful, a state/event approach must be modular, hierarchical and well-structured. It must also solve the exponential blow-up problem by somehow relaxing the requirement that all combinations of states have to be represented explicitly." So regular state machines are usable up to only a few states and transitions. Implementing the whole set of Statecharts features is far from the quick exercise of building an ad-hoc, implicit state machine. Fully using Statecharts introduces some overhead. But the true power of Statecharts shows when using hierarchy, parallel states, history and so on, things that build on top of state machines and take a bit more investment to learn how to use. -- Another interesting aspect is the "formal semantics". Quote: "The statechart formalism turns out to be quite a challenge when it comes to providing formal semantics ... The main difficulty is not in the depth of states or the orthogonality constructs themselves; ... The more difficult problems arise with the introduction of events and conditions that are generated within the statechart itself, and are sensed in orthogonal components." So the idea is that given the same Statechart diagrams, two different implementations should end up in the same states when subjected with the very same sequence of events. Perhaps this is less of a problem to build GUIs and other applications that don't have super stringent requirements on safety and verifiability.
- jbeard4 6y ago
  Regarding the "formal semantics", you are correct that different implementations of Statecharts have had different formal semantics, however some effort has been put toward standardization, the main one probably being the W3C SCXML standard, which specifies a pseudocode algorithm for execution of Statecharts: https://www.w3.org/TR/scxml/#AlgorithmforSCXMLInterpretation https://www.w3.org/TR/scxml/#AlgorithmforSCXMLInterpretation It also provides a test suite that implementations can use to check compliance: https://www.w3.org/Voice/2013/scxml-irp/ https://www.w3.org/Voice/2013/scxml-irp/ There are a number of conforming implementations in various programming languages.
maxbendick 6y ago
I've found xstate invaluable for multi-step flows on the front end. Redux and similar libraries are a bit hard to read when making these because representing sequential distinct states is implicit. I.e., have an enum for the "page" and some reducer cases to update the page. With xstate, the order of things is often visually apparent. Not only are distinct states bread-and-butter for statecharts, the machine definition in the code visually jumps out at the reader and screams "these are my states, and here's how to move between them!"
zitterbewegung 6y ago
I have no idea why in university we covered state machines so very little when they solve a host of problems and can replace fundamental ways in designing software. Not only that but it's also compatible with them all. I finally tried using state machines in a hobby project and its much better than just writing a bunch of if then statements in a event loop.
kazinator 6y ago
Relevant: https://en.wikipedia.org/wiki/UML_state_machine https://en.wikipedia.org/wiki/UML_state_machine (Article references the above paper as citation #2).
_aleph2c_ 6y ago
Python statecharts: https://aleph2c.github.io/miros/html/index.html https://aleph2c.github.io/miros/html/index.html
neilv 6y ago
In the SwiftUI app I wrote recently, in an act of desperation, I dusted off my Harel statecharts skills (I used to develop tools like this), and ended up with a huge comment block with an ASCII-art hierarchical state model. Then the code structurese were based on that, and the names generally matched up between code and diagram. The app UI has been solid, even though some of the states are in the canned NFC UI mode, and less in my control.
elviejo 6y ago
Any book recommendations to learn more about state machines, state charts and languages that implement them natively??
sam_bristow 6y ago
I quite like https://sketch.systems/ https://sketch.systems/ as a tool for quickly getting up and running with Statecharts. There's also a good article by Hillel Wayne about using Statecharts and Alloy to formally specify UIs. https://www.hillelwayne.com/post/formally-specifying-uis/ https://www.hillelwayne.com/post/formally-specifying-uis/
jonaias 6y ago
Back in university, I had a course on reactive systems, a whole semester of state machines and statecharts. I can't stress enough how useful it was in my career. I've retrofitted some near unmaintainable embedded systems, and one of the easiest ways to improve spaghetti code is refactoring some of the vars into state machines/statecharts. Btw, state machines play well with event sourcing and clustering.

142 points by Cieplak 6y ago

I've worked in the past with code bases that have what were called 'state machines' implemented with at best switch statements and at worse a lot of if's and else's and some state variables. I've also worked with code bases with a formally defined state machine object/concept, with pre-defined states, events, and state transitions driven by events. Question for the crowd: what would you call the non-state machine state machine in the first case?

brentm 6y ago
You'd probably still call it a state machine if that is what it's doing. Maybe not well implemented but it also depends. State machines are tricky to get right.
carapace 6y ago
> what would you call the non-state machine state machine in the first case? Ad hoc state-machines? I don't think there's a formal name for them.
- kejaed 6y ago
  Ad-hoc is a great term for this, thanks.
zanecodes 6y ago
I would call the former an implicit state machine, while the latter is an explicit state machine.
- kejaed 6y ago
  This is perfect, thanks!
vbtemp 6y ago
State machines implemented in-line with code usually end up as a mess. It's best if they are factored out, and implemented as a DSL inside a true state machine engine running as a somewhat independent service or library.

sktrdie 6y ago

Harel's recent work (which evolve from Statecharts) is so called Scenario-based programming. If interested I follow his work very closely and showcase his techniques in this article about bthreads: https://lmatteis.github.io/react-behavioral/ https://lmatteis.github.io/react-behavioral/

jarym 6y ago
Maybe I'm just super dumb but I don't get why such simple examples should be made so difficult. Take for instance the following: "Here were are introducing the 3 main critical pillars of Behavioral Programming; the request, wait and block semantics.". Except the previous block of code does not exhibit the 'block' semantic at all.
anentropic 6y ago
There is something weird in the implementation... > Try adding two X's in a row. It will not work. It's waiting for an O, and once that is triggered it waits for an X and so on. If you try to make a move out of turn it seems like the illegal move is still "queued up" somehow. So as soon as you make a legal move the previously attempted illegal one occurs, as it's now legal. In fact, this resulted in an interesting game where both sides won: { type: "X", payload: 0 } { type: "O", payload: 8 } { type: "X", payload: 1 } { type: "O", payload: 2 } { type: "X", payload: 3 } { type: "O", payload: 6 } { type: "X", payload: 7 } { type: "O", payload: 5 } { type: "X", payload: 4 } { type: "XWins" } { type: "OWins" } I guess it needs a few more behaviours...
- sktrdie 6y ago
  Which version outputs this behavior? The earlier ones are on purpose buggy. As the computer bthread is added there's no way for it to start at tile 8. The point was to show how by adding new bthreads the system gets smarter and less buggy.

jarirajari 6y ago

Was also inspired by the Statecharts long time ago, and then saw an opportunity to go deeper into how server-side web applications could be implemented as state machines, and how it would ultimately lead into easier/faster programming where correct/complex patterns emerge from events, conditions, and actions. Wrote about it here: https://jarirajari.wordpress.com/2014/01/03/ecas-hierarchical-aspect-state-machine-aka-ecas-hasm/ https://jarirajari.wordpress.com/2014/01/03/ecas-hierarchica...

vbtemp 6y ago

People who gloss over this do so at your own risk. This technique is applicable for so, so many applications - even when it doesn't appear obvious at first. Factoring out complex control system logic into these (and related) formalisms dramatically enhances testability, substantially reduces code volume, and eliminates huge swaths of possible defects (not to mention seriously enhances formal verification and model checking). The "code" part for applications should basically be for data plumbing, and all decision-making and control logic should be factored into these. Thanks for posting this!!

billfruit 6y ago
Yes, but the heavy lifting required behind the scenes to make statecharts work seems quite elaborate, moreover it could be problematic to use blocking apis, like sockets etc with statecharts, perhaps?
- mr_olive 6y ago
  On the contrary, in my experience such stateful APIs are a great use case for state machines. You just approach them differently. Instead of doing a blocking call, you introduce a "waiting for <something>" state. You leave the "blocking" state when the correct event comes, or after a timeout. And while you are waiting for the event, you don't just burn CPU cycles, but yield control quickly, so that other threads can execute in the meantime.
  - chrisweekly 6y ago
    I don't have much experience w them yet, but found the xstate lib well-documented, and also like swizec's take: https://swizec.com/blog/when-your-brain-is-breaking-try-xstate/ https://swizec.com/blog/when-your-brain-is-breaking-try-xsta...
  - adamkl 6y ago
    Additionally, you can use state machines server side to track stateful processes by simply serializing the “current” state of the machine and storing it somewhere. With the next request, reload the “current” state of the machine and transition to the next based on the incoming request. Rinse/repeat.

john-tells-all 6y ago

A modern elaboration is https://statecharts.github.io/ https://statecharts.github.io/ - very clear explanation of statecharts, and why you'd want to use them (they're an elaboration of state machines) - and why you wouldn't want to use them very interesting, thanks to OP!

chrisweekly 6y ago
Thanks! See also https://xstate.js.org/docs/#why https://xstate.js.org/docs/#why

spinningslate 6y ago

I have mixed feeling about the hierarchical facility in statecharts. I've certainly found it helpful in some cases; for example, handling "cancel" events that apply to a group of states. I've also seen huge, multi-level, multiple-parallel-region monsters that were impenetrable. Now, no formalism is immune to abuse: "just because you can, doesn't mean you should". But I've often found that the simpler state model formalism - without hierarchy - has led to cleaner design and better separation of logic. More generally though I do think state machines are somewhat underrated tools in the programmer's toolbox.

adamkl 6y ago
Agree. I’m a huge fan of this approach when developing complex UIs, but you can definitely run into “state explosion”. When you rigorously enumerate all the implicit states in your system you quickly realize that your system can have a lot of states. It’s a balancing act. How much rigour do you need vs. how much code are you willing to deal with. The implicit states will always be there whether you make them explicit via a state chart or not. But for simple things, it may not be worth the overhead.
- specialist 6y ago
  Me three. Ages ago, I implemented an Illustrator style direct manipulation user interface. We had spent so much time analyzing, documenting, specifying in prep. My initial implementation, per our "perfect" spec, really sucked. Turns out there's a significant amount of fit and finish to a direct manipulation interface that I wasn't able to handle formally with charts and machines. Ended up with a bunch of special cases. Unanticipated knock on effects were unsatisfying negotiations with QA/Test (how to test) and tech writers (how to describe) our product. I've always wondered about that gap. Was I doing it wrong? Are there better formalisms? How'd Illustrator (and others) do their direct manipulations? With the rise of touch UI, I anticipate the problem space (complexity of the states) has gotten smaller. For instance, no modifier keys. But that's just a guess.
  - jcelerier 6y ago

adamkl 6y ago

This approach is a big boon to the development of complex UIs. If you are tired of littering your React/Angular/Vue/etc code with a litany of state flags (“isLoading”, “isError”, etc)[0] take a look at the de facto canonical state chart implementation for JavaScript, XState: https://xstate.js.org/docs/ https://xstate.js.org/docs/ It’s been a joy to work with and can replace other methods of managing state (i.e. redux) while constraining the behaviour of your UI to predictable states and interactions. [0] https://dev.to/davidkpiano/no-disabling-a-button-is-not-app-logic-598i https://dev.to/davidkpiano/no-disabling-a-button-is-not-app-...

davidkpiano 6y ago
Thanks for the kind words about XState (creator here)!
- jen729w 6y ago
  It’s a big boon to the development of tiny simple UIs! I use XState to manage my login state. Not logged in, trying, logged in, log in failed, trying log out, logged out. The thing I love is the confidence the machine gives me. Unless I’ve buggered up completely, it basically can’t be wrong. That’s incredibly reassuring. Thanks for XState and all the work you put in to it. It’s an amazing thing.
  - adamkl 6y ago
    Funny you mentioned login state. I've used it for the exact same thing. I had a "userService" machine (embedded in a React UI) that handled all the legwork of an OAuth2 flow and ended with the user in an "authenticated" state with their details as part of the machine context (for use in any other part of the app via a custom hook). You are absolutely right, it couldn't be wrong. It always just worked exactly the way it was supposed to. I'm now working on a project that handles logins via a set of disconnected boolean flags flowing through redux and it is a mess.
- compscistd 6y ago
  I didn’t know a thing about state machines and lately would deprioritize your xstate frontendmasters course on my learning queue just out of ignorance. For whatever reason, I just watched your React Rally video and I can think of a bunch of projects where state machines would help get the UI in order! A “legacy” ui we have (much older than a week) has these state flags (and then some): IsConfirmed IsSent IsSentAndConfirmed IsDraft IsLoading IsInTheEther IsError IsNaN I want to rewind the clock for a redo on that mega component but I suppose refactoring will have to do. Again, thank you for that great talk!

bmitc 6y ago

There is an edX course by David Harel (the author of this paper) and Michal Gordon called Programming for Everyone – An Introduction to Visual Programming Languages. I highly recommend it for anyone dealing with state, whether you’re a programmer, designer, engineer, or manager. https://www.edx.org/course/programming-for-everyone-an-introduction-to-visual https://www.edx.org/course/programming-for-everyone-an-intro...

breck 6y ago

Every graph can be represented by a 2-dimensional tree. Hence, every chart in this paper has a 2-D tree representation. You can write that 2-D representation, and then without any type of transforming (keeping the shape of the graph in tree form untouched), you can turn it into a 3-D statechart, via the use of a Tree Language (https://jtree.treenotation.org/designer/ https://jtree.treenotation.org/designer/) So you get a 2-D text encoding of the statechart, editable in any dumb text editor or spreadsheet, isomorphic to the visual circles and lines diagrams they have, just as a 3-D rendering. You could probably put that in a paper.

uryga 6y ago
> Every graph can be represented by a 2-dimensional tree. do you have a good reference for this encoding? i vaguely recall seeing something like this in a paper, but can't remember any specifics
- breck 6y ago
  Here is the paper: https://github.com/treenotation/research/blob/master/papers/paper/treenotation.pdf https://github.com/treenotation/research/blob/master/papers/... It's not that traditional a style as I had no experience in academia until after I published it on arxiv, but I still stand by basically all of it. For the encoding all you need is 3 things: a node delimiter (generally newlines), a cell delimiter (generally tab or space), and an edge delimiter for parent/child relationships (generally reuse the tab or space from above). Think of a spreadsheet as a program, and that's the base encoding. From there you just need to define Grammars to get higher level constructs. This page (https://jtree.treenotation.org/designer/ https://jtree.treenotation.org/designer/) contains ~15 example grammars, including a grammar for grammars (similar to YACC or ANTLR). This is just the tip of the iceberg though, you can do really novel things with these languages that you don't see with all our traditional languages (like having N parse heads that start all over the place and move in all sorts of directions). So if you take these ideas and combine them with this "Statecharts" paper of 1987, what you would do is create a "Statecharts" Tree Language defining all the elements they have in that paper, and then people could write "programs" in this Tree Language, and then you could use the Compiler Compiler I linked to above to generate a compiler that reads those programs and either 1) compiles them to SVGs like they have in their paper or 2) generates 3-D visualizations where the program shape in the focus is unchanged.

fokinsean 6y ago

I'm getting a flashback from Sproutcore JS statecharts, wish I could say they were good times but I'm so glad I'm not developing with them anymore. https://guides.sproutcore.com/getting_started_2.html https://guides.sproutcore.com/getting_started_2.html

_pmf_ 6y ago

Hands down the best paper in software development.

emmanueloga_ 6y ago

When I first saw Statecharts I failed to realize that Statecharts are _NOT_ state machines, state machines are the building block. Quote from the paper: "... a complex system cannot be beneficially described in this naive fashion [state machines], because of the unmanageable, exponentially growing multitude of states, all of which have to be arranged in a ‘flat’ unstratified fashion, resulting in an unstructured, unrealistic, and chaotic state diagram. To be useful, a state/event approach must be modular, hierarchical and well-structured. It must also solve the exponential blow-up problem by somehow relaxing the requirement that all combinations of states have to be represented explicitly." So regular state machines are usable up to only a few states and transitions. Implementing the whole set of Statecharts features is far from the quick exercise of building an ad-hoc, implicit state machine. Fully using Statecharts introduces some overhead. But the true power of Statecharts shows when using hierarchy, parallel states, history and so on, things that build on top of state machines and take a bit more investment to learn how to use. -- Another interesting aspect is the "formal semantics". Quote: "The statechart formalism turns out to be quite a challenge when it comes to providing formal semantics ... The main difficulty is not in the depth of states or the orthogonality constructs themselves; ... The more difficult problems arise with the introduction of events and conditions that are generated within the statechart itself, and are sensed in orthogonal components." So the idea is that given the same Statechart diagrams, two different implementations should end up in the same states when subjected with the very same sequence of events. Perhaps this is less of a problem to build GUIs and other applications that don't have super stringent requirements on safety and verifiability.

jbeard4 6y ago
Regarding the "formal semantics", you are correct that different implementations of Statecharts have had different formal semantics, however some effort has been put toward standardization, the main one probably being the W3C SCXML standard, which specifies a pseudocode algorithm for execution of Statecharts: https://www.w3.org/TR/scxml/#AlgorithmforSCXMLInterpretation https://www.w3.org/TR/scxml/#AlgorithmforSCXMLInterpretation It also provides a test suite that implementations can use to check compliance: https://www.w3.org/Voice/2013/scxml-irp/ https://www.w3.org/Voice/2013/scxml-irp/ There are a number of conforming implementations in various programming languages.

maxbendick 6y ago

I've found xstate invaluable for multi-step flows on the front end. Redux and similar libraries are a bit hard to read when making these because representing sequential distinct states is implicit. I.e., have an enum for the "page" and some reducer cases to update the page. With xstate, the order of things is often visually apparent. Not only are distinct states bread-and-butter for statecharts, the machine definition in the code visually jumps out at the reader and screams "these are my states, and here's how to move between them!"

zitterbewegung 6y ago

I have no idea why in university we covered state machines so very little when they solve a host of problems and can replace fundamental ways in designing software. Not only that but it's also compatible with them all. I finally tried using state machines in a hobby project and its much better than just writing a bunch of if then statements in a event loop.

kazinator 6y ago

Relevant: https://en.wikipedia.org/wiki/UML_state_machine https://en.wikipedia.org/wiki/UML_state_machine (Article references the above paper as citation #2).

_aleph2c_ 6y ago

Python statecharts: https://aleph2c.github.io/miros/html/index.html https://aleph2c.github.io/miros/html/index.html

neilv 6y ago

In the SwiftUI app I wrote recently, in an act of desperation, I dusted off my Harel statecharts skills (I used to develop tools like this), and ended up with a huge comment block with an ASCII-art hierarchical state model. Then the code structurese were based on that, and the names generally matched up between code and diagram. The app UI has been solid, even though some of the states are in the canned NFC UI mode, and less in my control.

elviejo 6y ago

Any book recommendations to learn more about state machines, state charts and languages that implement them natively??

sam_bristow 6y ago

I quite like https://sketch.systems/ https://sketch.systems/ as a tool for quickly getting up and running with Statecharts. There's also a good article by Hillel Wayne about using Statecharts and Alloy to formally specify UIs. https://www.hillelwayne.com/post/formally-specifying-uis/ https://www.hillelwayne.com/post/formally-specifying-uis/

jonaias 6y ago

Back in university, I had a course on reactive systems, a whole semester of state machines and statecharts. I can't stress enough how useful it was in my career. I've retrofitted some near unmaintainable embedded systems, and one of the easiest ways to improve spaghetti code is refactoring some of the vars into state machines/statecharts. Btw, state machines play well with event sourcing and clustering.