7 ms·
C++ State Machines
- dimitrov 8y agoWell 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)
- eismcc 8y agoHow do you manage combinatorial explosion as states increase?
- dimitrov 8y agoThe 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.
- eismcc 8y agoWhat you describe feels more like case classes.
- signa11 8y agoone 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'
- lgeorget 8y agoIf 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-vs-meta-state-machine 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.
- nly 8y agoBoost.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/ 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.
- indiosmo 8y agoI 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#data 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/08ab24181770125d5a2448d27f6ae99f 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.
- ephimetheus 8y agoI 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.
- analognoise 8y agoSeeing 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.
- 8y ago
- neodypsis 8y agoThere'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 https://www.state-machine.com/psicc2).
- mike4921 8y agoSimulink, 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.
- 01100011 8y agoI'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.
- InitialLastName 8y ago> 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.
- wyldfire 8y agoHarel 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/ https://www.w3.org/TR/scxml/
- pierrebai 8y agoFor 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!
- decker 8y agoIt sounds like he just re-discovered that a Moore machine is simpler to implement than a Mealy machine.
- ncmncm 8y agoEvery 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.
- geezerjay 8y agoI 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.
- dnlgl 8y agoState 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 https://news.ycombinator.com/item?id=7676691
- zzglenm 8y agoI 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 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.