Statecharts: A Visual Formalism for Complex Systems (1987) [pdf] | Hacker News Reader

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

inf.ed.ac.uk

142 pointsCieplak64 comments

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/

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

Thanks for the kind words about XState (creator here)!

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.

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.

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!

I just tried to read that code, and perhaps I'm missing something, but wouldn't coroutines/generators be a much better approach of keeping state confined to a local process, and wouldn't that make the code for managing state look more like normal code?

Sure, but then you're missing out on the ability to visualize your states and transitions, much less statically analyze your state machines, generate tests for them, etc. etc.

There's a lot of potential goodness that you lose when you drop down to "normal code" as opposed to a formalized structure.

This is one of the things that is preached pretty often in the Clojure community: it’s all about the data

Describing your application behaviour in data not only allows for all sorts of static analysis (as David mentioned above) but also the ability to change the behaviour without changing code. You could describe multiple different workflows in your application as different state machines, save them to a data store, and load them up dynamically depending on the situation/user.

I’m going off topic, but this approach goes beyond state machines. Focusing on a data driven approach allows you to do some pretty interesting stuff, like designing whole APIs and UIs using data only: https://youtu.be/BNkYYYyfF48

Is Clojure better for applying linting to more benefit than other languages then?

I developed my own statechart lib many years ago (before React, but I used it with Angular) and used it for the high-level state that drove the application. It worked really well. Redux, etc have always seemed like a step backwards for high-level application state. https://github.com/gregwebs/statetree

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

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?

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.

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

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.

Can webhooks come into play nicely with state machine models?

The thing is, wont calling a blocking api block a lot of things the statchart is supposed to be doing at the same time?

It’s easier when you write your application in Elixir or Erlang. Those are practically DSLs for state machines that also double as general purpose programming languages.

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

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/

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.

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

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.

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.

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

It also provides a test suite that implementations can use to check compliance:

https://www.w3.org/Voice/2013/scxml-irp/

There are a number of conforming implementations in various programming languages.

Statecharts are in fact descriptions of state machines. They are just not ordinary state machine diagrams based on a single, scalar state variable.

The state expressed in Statechart could be turned into a single variable, and the chart could be refactored into a flat state transition diagram.

But that diagram would potentially be huge compared to the state chart description.

The state chart condenses that description by avoiding the duplication of some sub-state-machine for every change of some variable which is irrelevant to it.

E.g. suppose a device has two master modes of operation, A and B, in which it responds to inputs in totally different ways. Suppose that mode A and B retain their internal state when the mode switch takes place.

If we don't use a hierarchical state chart, we end up having to represent what happens when a certain input arrives in a state under mode B, for every possible state in mode A which is not actually in effect and irrelevant. Basically, we have to deal with the product state space, in which the explosion leads to numerous identical combinations.

State machines as formally defined are incredibly low level, lacking even things like guards (predicated transitioning) and transition actions.

So Statecharts adds a lot on top of them, but yeah, the foundation is FSMs.

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.

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.

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.

To give another data point: https://ossia.io had three different tentatives for implementing its UI manipulation "manually" before reaching for (indeed complex) state machines which I spent at least 4-5 full-time days specifiying on paper for all their cases (following days of meetings trying to define informal specs).

It's the thing that ended up working, and still works 4-5 years after the fact & numerous modifications / improvements / new features. Also Qt with GammaRay allows to visualize them "live" which was an immensely useful feature to debug them during development.

Good insight. I think it's a blessing and a curse. currently i think me and my team have trouble identifying all those states and thus mis-understand or under-understand the complexity of some features. I want to use state charts to force us to look at all the states.

Of course I expect everyone will soon get annoyed at all these states we are tracking.

I agree too. I assume that state machines (SMs) are underrated because they are used in a "wrong" way which makes building them impossible: I mean most authors focus on listing and naming all the states, but in fact, they should not do that (IMO) but rather focus on events, conditions, and actions, which cause state transitions. Secondly, they should use hierarchical grouping the reduce number of edges in the state graph.

There are concepts like workflow engines and FLUX architecture which help in designing simpler SMs. For example, by limiting state transitions to events similar to how modern microservices communicate there will be less events. And actually many workflows themselves are implemented in (smaller) state machines.

A modern elaboration is 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!

Thanks! See also https://xstate.js.org/docs/#why

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

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

I quite like 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/

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.

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

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.

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?

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.

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

Ad-hoc is a great term for this, thanks.

I would call the former an implicit state machine, while the latter is an explicit state machine.

This is perfect, thanks!

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.

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.

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

Relevant: https://en.wikipedia.org/wiki/UML_state_machine

(Article references the above paper as citation #2).

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/)

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.

> 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

Here is the paper: 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/) 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.

sorry, can't really find anything about graphs in there. how would use TN to represent a graph like this?

  A --> B --> C
  ^           |
  |           |
  +-----------+

A few options, depends on design of Tree Language. Here are a few programs using grammars following traditional top to bottom, left to right flows.

Verbose ones:

    ANode
     BNode
      CNode
       Edge ANode


    CAEdge
     ANode
      ABEdge
       BNode
        BCEdge
         CNode

ah sorry, i thought your OP was talking about a more graph-theory-ish thing, some fun bijection between trees and graphs or something, serialization isn't really what i had in mind

re: TN stuff. don't take this the wrong way, but being able to serialize a graph into bunch of IDs+edges isn't very... remarkable. as in, you could also use JSON/YAML/XML/s-exprs or whatever format, they'd be kind of equivalent here (modulo punctuation). i mean, lightweight DSLs and homoiconicity are cool, but not really groundbreaking stuff

---

PS (additional bit of unsolicited advice). afaik you're still looking for TN's "killer app"; i'd consider making something geared towards the org-mode/markdown/plain-text-everything crowd, because TN's advantage is conciseness + ease of input/editing + aesthetics. maybe it could find its niche as a markdown++/org-mode-ish thing where you can freely mix text with structured bits (DSL stuff would be handy here)

I hear what you are saying, but there is a big leap between TN and "JSON/YAML/XML/s-exprs". One is isomorphic to 2 and 3 dimensional structures, and the rest are not, connecting the software world to the physical world. This will turn out to be very important and groundbreaking.

> One is isomorphic to 2 and 3 dimensional structures, and the rest are not

So you're saying your notation can encode graphs that can't be represented as, e.g., JSON? The existence of such a graph would be the real (math-breaking) discovery here, no? I.e., you really should be able to give an example before offering such statements...

> connecting the software world to the physical world

I'm really not following you here.

The fundamental shape of all our current computer languages is one dimensional. You can take any current program/file, "encode it" to lego blocks, and it would be a one-dimensional string. This probably arises because our foundational layer is one dimensional binary.

Tree Notation/2D/3D languages are like a higher dimensional binary. Where you can traverse the program in multiple dimensions. Where physical layout matters.

Now all our current languages can be represented in this way. And that's what most of my stuff focuses on now.

But there are things that you can do with these languages and this style of 2D/3D architecture that you just cannot do with our current 1D register technology. (I mean maybe you could do them, but it would take billions of years to compute).

Wait, am I claiming that 2D/3D computers would be as big a development as Quantum computing?

No, much fucking bigger. Quantum computing is a fucking joke compared to this.

(pardon my french, I just find the occasional f-bomb as a good way to communicate my excitement about the OOM I am seeing)

not really sure what you mean by 2D/3D. if you mean "whitespace sensitive" (≈ effectively laid out in 2D), what about YAML? pretty sure you could just add dashes and get valid YAML representing the same tree:

  - A
  - B
    - C
      - A

to put it bluntly, i'm really not seeing what's so groundbreaking about using indentation to represent nesting – it's a nice concise syntax, but it's just that. if there's cool things you can do using that syntax (AIUI, Tree Languages and tools built around them, which reminds me of racket-lang and their whole "language-oriented programming" idea), that might be interesting; but failing that, people will dismiss your claims of being revolutionary as crankery, which will hurt your project's image.

> not really sure what you mean by 2D/3D.

Turn off the computer and "write" a program by assembling legos. One token is one lego block. So an open quotation mark—"—is one lego block. If you can align all the lego blocks in a single line, and the meaning of the program does not change, you have a 1-D programming language. This is the case for all the languages you mentioned—"JSON/YAML/XML/s-exprs".

This is not the case for Tree Notation/2-D and 3-D languages. Changing the 2-D positioning of the tokens changes the meaning.

Now you might say that this is not the case because you could just have a lego block that equals "\n", and so the parsing would be the same. But the mistake their is to miss the general idea of 2-D languages. While Tree Notation first parses a program linearly from start to end, that's just because it's a limitation based on how our current computers are designed to work, and having multiple read/execute heads starting and moving in different directions across a memory cube is not technology we currently have.

I gave a talk on this putting it another way a few years ago: "https://www.youtube.com/watch?v=ldVtDlbOUMA".

To put it another way: you don't need syntax characters, all you need is space.

> but failing that, people will dismiss your claims of being revolutionary as crankery, which will hurt your project's image.

I figured it would take ~10 years of hard work and dedication to chisel out the core of this idea and make it "just work" for people. I'm about 4 years in, so the bulk of the work and resources to put in are still ahead. I do not want to put so much effort and resources into a novel idea that wouldn't have much of an impact if it turns out to be correct. I give this idea a low probability of being groundbreaking (<10%), but if it is it will fundamentally change our languages and probably make a significant impact across society in many unpredictable ways (probably many orders small than binary notation, but many magnitudes bigger than most things). So I'm happy to sacrifice my "image" for this idea. I want people to be critical, especially now, still in the early days, to figure out the flaws here. I'm still not seeing one. From all the data I've seen so far, these types of languages will be a 10x+ leap in technology. It's a really big idea.

Hands down the best paper in software development.

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

Reply on news.ycombinator.com