Hacker News new | past | comments | ask | show | jobs | submit login
C++ State Machines (tuxen.de)
94 points by qznc 46 days ago | hide | past | web | favorite | 28 comments



Simulink, and specifically stateflow, is commonly used in the aerospace industry to graphically create state machines that can be autocoded into high performance C or C++ code. I use simulink and stateflow everyday to create flight control software. I feel like more software engineers should learn how to use graphical coding tools, as IMO it's so much easier to represent complex state machines graphically.

It's a shame that Mathworks is essentially the only game in town though, and their software licenses are fairly expensive.


I'd rather have tools that can take code which implements a state machine and produce a statechart than go the other way around. There are a few tools which will go from statecharts to code and they've been around a while but never seemed to get very popular. I think dealing with a complex system as a statechart is potentially harder than dealing with code.

That said, my friend works on satellite software implemented with state machines. He was saying the high reliability of the system is mainly attributed to the requirement that systems be designed as statecharts first, which forces the designs to remain simple and analyzable.


> the high reliability of the system is mainly attributed to the requirement that systems be designed as statecharts first, which forces the designs to remain simple and analyzable.

This can also be due to the fact that statecharts inherently require every transition and event to be mapped, which is more up-front work than most programmers do on their state machines. Need a feature that requires a new state? Instead of glomming it onto the code (and, in a complex codebase, probably missing one transition or another), you have to do the work of putting it into the state diagram and handling every transition into and out of that state (from every one of the connecting states in the graph). From there, you have a much more completely accounted list of the changes that have to be made to other states, in addition to a more complete list for testing the resulting code.

> dealing with a complex system as a statechart is potentially harder than dealing with code.

Yes, but it strikes me as harder in the same way that it's more difficult to get code to build when you have a strict linter and a strict static analysis tool in the pipeline; when reliability is worth a bit of developer-convenience-cost, we add procedures such that making changes takes more work at the beginning.


>Mathworks

I used Simulink and Speedgoat (and LabView!) for many years. Oh how I long to create a startup that would improve on all of these dinosaur-like tools. Seriously if anyone wants to disrupt these entrenched, inertial companies, look me up. There are sooo many places to improve and you're right there's almost no competition. Trust me, I looked for it every few months when I ran into the limitations of these packages. I accept them for what they are, but they could be so much better!


Working on this with XState! Let's talk.


I've just started working in a safety critical field where Simulink model driven design is heavily used.

My previous first impression was that auto generated code was not very efficent and could easily create mangled unreadiable code. I assume this would be OK for prototyping something quickly but not for production grade applications.

From your understanding is Simulink + code generation a fairly common toolchain in industry? I would imagine that MathWorks would have to go through some serious certification exercise specially for code generation?


Matlab/Simulink models are also heavily used in automotive ECUs. I'm not sure about space coding standards, but the code generated from Simulink can be, if selected, MISRA compliant and optimized for speed, accuracy, etc.


scxmlcc (http://scxmlcc.org) can translate state machines into high performance C++, and it is free.


For his logical combination problem, I think the solution is to use enums:

   State nextState(bool a, bool b, bool c, bool d)
   {
      enum A { A_NO = 0, A_YES = 1 } As[] = { A_NO, A_YES };
      enum B { B_NO = 0, B_YES = 2 } Bs[] = { B_NO, B_YES };
      enum C { C_NO = 0, C_YES = 4 } Cs[] = { C_NO, C_YES };
      enum D { D_NO = 0, D_YES = 8 } Ds[] = { D_NO, D_YES };
      switch (As[a]) + Bs[b] + Cs[c] + Ds[d])
      {
         case A_NO  + B_NO  + C_NO  + D_NO : return X; // 0
         case A_NO  + B_NO  + C_NO  + D_YES: return X; // 1
         case A_NO  + B_NO  + C_YES + D_NO : return X; // 2
         case A_NO  + B_NO  + C_YES + D_YES: return X; // 3
         case A_NO  + B_YES + C_NO  + D_NO : return X; // 4
         case A_NO  + B_YES + C_NO  + D_YES: return X; // 5
         case A_NO  + B_YES + C_YES + D_NO : return X; // 6
         case A_NO  + B_YES + C_YES + D_YES: return X; // 7
         case A_YES + B_NO  + C_NO  + D_NO : return X; // 8
         case A_YES + B_NO  + C_NO  + D_YES: return X; // 9
         case A_YES + B_NO  + C_YES + D_NO : return X; // 10
         case A_YES + B_NO  + C_YES + D_YES: return X; // 11
         case A_YES + B_YES + C_NO  + D_NO : return X; // 12
         case A_YES + B_YES + C_NO  + D_YES: return X; // 13
         case A_YES + B_YES + C_YES + D_NO : return X; // 14
         case A_YES + B_YES + C_YES + D_YES: return X; // 15
      }
   }
Let the compiler reorgonise the switch for efficiency. Do not: skip combination. Do not: reorder. Do not: remove the number that help see we got all cases. The compiler will error out if a case is duplicated. I wish we could make it detect missing cases too!


If you're not willing to develop all the boilerplate code to encode your states, transitions, etc. Boost has two libraries to offer : Boost Statechart and Meta State Machine. One of my favorite question on Stack Overflow compares both: https://stackoverflow.com/questions/4275602/boost-statechart....

As with most Boost libraries, you're in for some serious headache if you decide to use them (or is it just me?) but it's very rewarding in the end.


Boost.SML (which is experimental) has garnered a lot of attention lately as a modern take on C++ state machines that can replace both of the options you raised.

https://boost-experimental.github.io/sml/

Unfortunately I haven't seen any compelling real world usage of any of these libraries, and the documentation for SML leaves a lot to be desired.


I have been using SML in production for a little over a year now without issues, mostly for protocol machines.

I agree the documentation is not great though, you kind of have to go over the example code and try to figure things out on your own.

Using embedded data for keeping state (e.g. counters, etc; see https://boost-experimental.github.io/sml/examples/index.html...) along with injecting std::functions to use as actions is pretty powerful.

Here's a basic example I wrote some months ago showing a hierarchical machine (https://gist.github.com/indiosmo/08ab24181770125d5a2448d27f6...).

Also please note my usage is pretty basic as I usually have the same machine ported to C# and Python so I tend to use the smallest subset of functionality supported by all the libraries in each language.


I didn’t find a good way to handle unexpected events with SML. I know there is supposed to be a special catch all event which can do that, but that’s only for the case the event is not used in the entire FSM, which makes it pretty useless. Thinking of rolling my own based on std::variant now.


Thank you, indeed I was not aware of that one. I'll have a look.


Seeing those examples made me realize how much I hate Modern C++, or just C++ in general.

This is so belaboured; there's an abundance of what looks like line noise to me. It lacks any sense of grace whatsoever.


Last I looked at Boost's offerings for state machines, my team and I found the offerings lacking. I forget exactly what it was missing (it's been 6-7 years and 4 jobs ago). May have been needing to perform actions on leaving a state, but not sure.

Edit: Boost is my first stop for non-standard C++ libs, but this time the offering was lacking. Previously also had issues with the date/time libs. Like they got 90% of the way there, and then didn't quite finish. Example: time zone handling. Has all of the infrastructure to support it, but no facility to really provide the necessary data. Also, their CSV of timezones was not historical, so broke down trying to do historical work for something like an energy contract in finance, where it was necessary to know if there were 23, 24 or 25 hours in a calendar day (or other value!) in a given year. Also, the interfaces for posix_time and local_date_time are a little clunky. I ended up with a facade that exposed an API more like Python's datetime lib. We also had a timezone loader to handle Olson TZ databases for the historical TZ info (and future updates) for both Linux and Windows.


There's an excellent book (and associated open source project) on using state machines for reactive systems or embedded systems in general: "Practical UML Statecharts in C/C++, 2nd Edition: Event-Driven Programming for Embedded Systems" by Miro Samek. Here's a link to the site where you can download it from (https://www.state-machine.com/psicc2).


Harel Statecharts are mentioned elsewhere in this thread, and I endorse them. IMO they're a really great way to model your design.

IIRC Quantum Leaps [Samek; also mentioned in this thread] is similar to statecharts.

I've used Rational Rhapsody for C++ and I think it's actually pretty good. But there be dragons there. UML alone is a tough sell to some engineering crowds, much less generating code from diagrams. Holy wars abounds.

While searching for related info to this post I discovered that W3 has a relevant specification [1]. But I suppose it makes sense, IBM is a player here and they love XML there.

[1] https://www.w3.org/TR/scxml/


State machines are at the core of event-driven programming, but I often find coroutines to be a better, cleaner alternative. See this HN thread: https://news.ycombinator.com/item?id=7676691


I have worked with generative hierarchical state machine engines for years, mostly for medical devices. It's relatively easy to "roll your own" finite state machine, but it gets unwieldy quickly for anything other than the most basic problem. The two classic approaches, tables and nested switch statements are hard to read. You need a drawing, and one from which executable code is generated.

Hierarchical state machine drawings are the way to go but it's generally not practical to build one on your own. That said, I wrote my own anyway: OOSMOS, the Object-Oriented State Machine Operating System (https://www.oosmos.com). It generates object oriented C from a state chart drawn with the open source drawing tool UMLet. OOSMOS is open source.


Well another OO way would be to add a state member to the Heroine class and create a state class for every possible state (X,Y,Z). Each state can then be responsible for interpreting the input and transitioning to the next appropriate state (if any)


How do you manage combinatorial explosion as states increase?


The proposed state table is hardly more scalable. It's obviously not infinitely scalable but In my proposed way, you only have to specify the cases where a state transition actually occurs.


What you describe feels more like case classes.


one possibility is to use hierarchical-state-machines (HSM), which allow (encourage even ?) the decomposition of state-machine into common behavior for reuse across states.

HSM have been there for a while, being proposed in '84 (!) by David Harel under the name 'statecharts'


It sounds like he just re-discovered that a Moore machine is simpler to implement than a Mealy machine.


Every computer, and every program, is a state machine. We invented machine language, and increasingly higher-level languages, specifically to provide a better way to program than making raw state machines.

When you find yourself using a high-level language to emulate, badly, a below-machine-language-level state machine, you should recognize that you are in a state of sin, and ask where you have gone wrong in life.

Thus spake the Voice of Experience.


I don't agree at all, and your baseless assertions misrepresent both history and technical requirements.

Contrary to your baseless claims, programming languages were not developed to avoid writing state machines. They were developed to provide programmers with convenient abtractions that made them more productive and helped them implement what they wanted to implement. Back in the real world state machines, either generated from a DSL or hand-rolled by developers, are still the standard solution to implement a lot of mundane components such as network protocols, language parsers, user interfaces, and even control systems. We're talking about applications where the state changes depending on inputs in spite of where the control flow might be. If your experience hasn't taught you that then you should not be paying attention to its voice.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: