1. 10

  2. 4

    Harel’s “classic” book on statecharts is freely available here: http://www.wisdom.weizmann.ac.il/~harel/reactive_systems.html

    1. 2


      The mathematician in me is always vaguely irritated by FSM’s.

      They are clearly isomorphic to threads.

      ie. Everything you can implement in a collection of FSM’s, you can implement straightforwardly in a collection of an equal number of threads and vice versa. (Yes, that includes thread races, priority inversions and deadlocks!)

      The only advantage (or disadvantage depending on your view) is the complexity of your solution tends to slap you in the face (OMG! You have sooo many states! Have you really thought about every transition!?) when you look at the FSM version.

      If you really want to piss me off, claim “I’m single threaded so I can’t have threading issues and don’t have the complication of a scheduler” and then show me a huge pile of half arsed interacting FSM’s.

      The mathematician in me says, yes you do, and you’ve just written a half arsed scheduler by hand.

      Every time I look at this FSM stuff, I’m convinced the main advantage is you can go to your product manager with this insane tangled graph and say, hand on heart, no we can’t add that additional feature. It’s too complicated.

      1. 4

        Harel, who’s very much a mathematician, might beg to differ… but his use cases might not be what you’re describing. He’s up to some interesting stuff with his dynamic logic and more recently live state charts.

        Anyway, just because two representations are formally isomorphic doesn’t mean that one isn’t better for some cognitive purpose than the other. Maybe you’re just more familiar or comfortable with thread models. It sounds like you have a specific annoying example or two in mind. Fair enough. But be careful of generalizing too early and thus judging on too little evidence!

        1. 4

          Actually, I suspect he wouldn’t differ.

          Actually I have been wrangling both FSM and threaded systems for decades and too little evidence is definitely not my problem in life. Way way way too much maybe.

          Both Hierarchical State Charts and and Multi Threading require stern discipline to achieve bug free implementation.

          Alas, as Alastair Cockburn so rightly says…. “Lack of consistency is a common failure mode of humans. Methodologies that require consistency of action, I call “high-discipline” methodologies. The project interviews indicate high-discipline methodologies as being fragile, although they have been brought to work in some projects.”

          Inevitably the gnarliest of bugs I have met in both styles (threaded and FSM) have been due to very human failing of “Lack of Consistency”.

          To achieve the claimed benefits of HSM’s, you need the high discipline of moulding all your state machines into the single HSM.

          As soon as you have a half arse collection of half arsed HSM’s interacting in a half arsed manner…. Guess what. None of the claim benefits of HSM materialize. You’re in pretty much the same shit as a multi threaded approach, and in worse shit than a truly disciplined multi threaded approach.

          Alas, being truly disciplined about multi-threading seems beyond human capacity (mere mortal me included, and even beyond some of the so called “programming gods” as evinced by a truly mournful catalogue of bugs they have produced.)

          Those systems that thrive in the world of concurrency / low latency like Erlang / Clojure usually impose the even higher discipline of immutability.

          Ok. So maybe some of my scar tissue is showing. :-)

        2. 1

          If you really want to piss me off, claim “I’m single threaded so I can’t have threading issues and don’t have the complication of a scheduler” and then show me a huge pile of half arsed interacting FSM’s.

          Interestingly, the PlusCal subset of TLA+ looks very close to Abstract, State Machines (ASM’s) that interact with each other. The use of them over regular programs lets one spot errors in distributed systems hard to find with testing. Likewise for single-threaded, one use of FSM’s is for implementations that can be more exhaustively analysed for correctness. They can also be matched against abstract ones in formal specifications for increase assurance code is doing what verified abstraction says it is. They’re also extremely easy to implement or synthesize versus many notations into both software and hardware.

          I’m sure people can write garbage in them like anything else but they have quite a bit of value. Many high-assurance, secure systems (esp security kernels) in the past were done in a ASM/FSM style.

          1. 2

            implementations that can be more exhaustively analysed for correctness

            That basically comes down to “I have exhaustively enumerated the states I can be in, and the state transitions I can make”. Which the threaded versions tend to hide from you…

            However, to achieve the same functionality as some of the threaded code…. you often need to explode the complexity of the FSM until you are not any better off.

            ie. It really boils down to ye olde “Simplicity is the price of reliability…”

        3. 1

          This is a good write-up on a technique I previously said was used in high-assurance security. I got this one off HN. User wyldfire also had this link to a framework for doing stuff like this in embedded:


          1. 1

            Samek’s book on this (statecharts) is also good. I’m a little sad that there isn’t much written about this.