How I Learned to Stop Worrying and Love the State Machine

I remember that the canonical one was always the Quantum framework, but I never wanted to deal with the licensing aspect of it.

Plenty of other stuff I have worked on would have benefited from this as well.

Plenty of stuff I am going to work on in the future will benefit from this.

the top few comments i find compellingly skeptical.

https://news.ycombinator.com/item?id=15835482

https://news.ycombinator.com/item?id=15835666

Because state machines are a weaker computational model they are easier to reason about, you can prove things on state machines you can't prove on a general program, you can do things like state minimization etc.

Same for me. In university you really just a get a taste of them, usually limited to one section of a design patterns course. But man, for certain cases they really make it easy to reason about complex workflows, that otherwise would be buried in generic flow control statements spread across multiple classes, or modules. In our app, there was a flaky and bug-prone area. It wasn't always like that. It started very simple but as feature grew the workflow become more complex. Anytime someone added anything related to that module it almost always broke something else, or introduce a leak that we found 3 months later. It was an area where you really had to focus whenever you made a change and even code reviews would miss it.

It took me about a week to document the implicit state machine, another week to roll my own state machine implementation tailored for that component, and one more week to refactor the code. It's been 5 years, our dev team tripled in size and it's been probably the most rock-solid module in that time. I'm not worried that some junior dev will introduce some esoteric regression issue downstream.

Eric Lippert is smart, I love his Stack Overflow answers.

When I'm stuck on a software design problem, pick some random part of the program and see what happens if I make it first class.

In this case, Eric takes the game rules and turns them into objects. (Essentially the Command pattern[1], which is close to my heart[2].)

You can go overboard with this, of course, but I've found time and again if it seems like I can't get my code to hang together, it's usually because I'm missing a noun — a reification of some part of my problem that I can pass around and do stuff with.

[1]: https://en.wikipedia.org/wiki/Command_pattern

[2]: http://gameprogrammingpatterns.com/command.html

PS: Another solution to Eric's initial problem with warriors, wizards, swords, and staves is to be more precise about what capability Player has. If Warriors can only wield Swords and Wizards can only wield Staves, then it's not the case that Player's Weapon field can be set with any weapon.

So one option is to make Weapon an abstract getter in Player. Then add setters and fields in Wizard and Warrior for the specific types. If all you have is a Player, you can see what their wielding, but not change it. Then, to wield something, you need to know what kind of player you're dealing with first.

Of course, that doesn't scale very well to lots and lots of business rules as in later in the series. But it works if you have a relatively small number of constraints in your subclasses — you just push them up such that the superclass API only exposes the intersection of all of the subclasses' allowed operations.

I am suspicious any time I see inheritance in my C# code base. It's rarely needed and causes a lot of pain when used extensively. I'm looking at you Credit Note and Invoice!

Oddly Eric never mentions ECS or SoA in the series, even though it solves the problem. (He only suggests in part 5 to use a Rule Engine, instead of inheritance)

Does anyone know a good code example (preferably C# but anything similar would do) of a rules system like what he describes in the final part?

OO is fundamentally about messaging not abstract data types. So if you start your design from trying to determine ADTs instead of trying to work out the kinds of message conversations that need to go on you end up with mess of types.

In the wizards and warriors we see a large amount of modelling of a domain with rules. But we, even at the end, still have little idea of what messaging is going to be going on, there is a hint about attacking werewolves. But we've already made a lot of assumptions about what our first class entites are. Often what can happen is we find, while we thought we modelled it ok and even sorted out a rule based system, it still seems difficult for our objects to have conversations.

maybe what would be better is some thing that can attack other things and wizards, weapons, and warriors are all simply modelled by some composable set of stat modifiers.

    protocol Weapon {}
    class Staff: Weapon {}
    class Sword: Weapon {}

    protocol Player {
       associatedtype T: Weapon
       var weapon: T  { get set } 
    }

    class Wizard: Player {
       var weapon = Staff()
    }

    class Warrior: Player {
       var weapon = Sword()
    }

What i would do is simply have Item (base for Weapon, Potion, etc) have a "IsUsableBy(Player p)" which returns true in the default implementation (which would be the case for the majority of items) and the objects that have special considerations check the player class themselves.

Similarly an Animal (or Entity or Organism or whatever) class would have a "OnDamage(Animal source, int damage)" that by default calls -say- "ApplyDamage(int damage)", but special animals - like the werewolves - may want to filter the result so that the damage is doubled when they are on holy ground or when the class of source is Paladin.

Also the IsUsableBy and OnDamage functions could check against Item objects in an inventory (e.g. Item could also provide a "FilterDamage" and "VetoUsageOf" so that an HolyCross can multiply all damage from Undead enemies by 0.25 but veto using any UnholyItem based class - truth be told here, you probably need a tag system for some of that stuff instead of relying on classes alone) and on an active Effect list (would also be able to do the same sort of vetoing and filtering and the Animal class could also provide a HasEffect method for use by the other classes to make decisions about - e.g. a PaperDoll might refuse to talk to you if you have the OnFireEffect :-P).

To me that sort of setup feels more natural and intuitive than the user-command-state-rule stuff mentioned in the article. You can't really generalize it in a way that applies to other things (e.g. a MagicSpell would need its own set of functions and such) but i believe that there is a thing as too much generalization.

(note that the above are when talking about the common Java/C++/C#/etc like OOP languages, in something like C i'd go with a more data and/or script driven approach...)

* A Sword is a type of weapon.

* A Fire Sword is a type of Sword.

* A Mace is a type of weapon.

* A Mace of Ice is a type of Mace.

* A Sword of Ice and Fire is a type of Sword.

If given

1. Player can have a Weapon

2. Sword is a Weapon

3. Wizard is a Player

The from the statement "Wizard cannot have a Sword" follows a contradiction that "Player cannot have a Sword".

The first post talks about the difficulty of getting compile time errors for Wizard wielding a Sword

The last post completely abandons the notion of statically checking anything about the Weapon assigned to a Player(beyond the most general case of is Player and is Weapon).

I don't actually have enough experience with Erlang/Elixir to know but I thought their function overloading (http://raganwald.com/2014/06/23/multiple-dispatch.html) still provides multiple dispatch with compile time checks?

The proposed Rules solution is more elegant to use(for the programmer, if not the person defining the Rules) but it does nothing(or at least very little) to help you check that the business logic is correctly encoded. Yes, you're likely going to avoid your program crashing, but that's just because you've given up on encoding the business logic entirely. At least where compile time checking is concerned.

Maybe I'm expecting too much of the type system and that's the actual lesson of the blog posts.

    new state = old state + message

In that particular example, I'd just like to point out how super clever it is to put `NUM_STATES` at the end of the enum in the first line. I'm fairly comfortable in C, but I never really used it with/around people who have been using it forever, so I love seeing these little tricks.

I'd be curious to hear anyone's thoughts/opinions on the desirability/feasibility of these, or any other suggestions. Thanks!

Operator pushes Start

Turn motor on

Motion triggers switch to ON state

Motion triggers switch to OFF state

Turn motor off

Machine changes state to RUNNING

The time between pushing Start and RUNNING is only a couple seconds, but there's a chance that something could jam, the switches could fail, or something I have no knowledge of could go wrong. Question becomes, do I now need an intermediate "In Motion" state for the six or so cases where this happens?

In the end, I decided no, because there was no other transition out of that state than the expected behaviors, so modeling the intermediate state didn't offer me any benefit[1]. Failure to get to OFF state within a certain time puts the system into a global error condition that required manual intervention to fix.

I don't have a real comment here :-) other than to back up your point that modeling isn't as obvious as it first appears to be.

[1] I would have created this intermediate state if this was a complex controller that was likely to have new rules added later. However, knowing it was a simple one-off, I'd just be giving myself extra work for no benefit if I did it now.

The words "event loop" probably mean you need a state machine.

If "time" is an input variable, you probably have a state machine.

SDL is widely used in telecom and datacom systems to develop the control plane. Most tools are of the draw your code-type, which ends up being a unmanagable mess in direct contrast to what management thinks. But the tools will generate state machines that pass messages between eachother and to controlling interfaces based on states an inputs.

The point being made for SDL is that you can easily simulate the whole system and watch/test that the control plane will work as intended before the HW has been built.

I've been meaning to write a letter to the CS department of one UC school: What the hell are they teaching in CS nowadays? If presented with a situation where the user can create circular references, there's one UC school that produces graduates with high 3.8+ GPAs, virtually none of whom I've interviewed can give you an implementable description of how to detect circular references. As a general pattern, they also tend to say silly things, like that a null pointer member of a structure uses up no data. I can go on and on. It seems to me they are being taught by TAs who would also flub such points in an interview.

It's the most powerful realizable automaton (although it's not even fully physically realizable because of the infinite tape), but people have studied far more powerful automata:

https://en.wikipedia.org/wiki/Turing_jump

https://en.wikipedia.org/wiki/Oracle_machine

https://en.wikipedia.org/wiki/Arithmetical_hierarchy

In these models the oracle is so called by analogy to prophetic oracles of antiquity, who were believed to obtain reliable information from an incomprehensible and supernatural source. :-)

  > they go to the same dusty corner where so many other CS
  > topics that are never used in practice lie already.

If you think that's a head-scratcher, the fact that senior developers consistently do the exact same thing must really confuse you!

1) How would you describe the reason for using state machines over handling the state and transitions through if-statements and sprinklings of booleans? The best I can come up with is that it allows you to be explicit about which states exist, how they can be moved between, and what other code should execute when transitioning. It basically comes down to the architectural principle of 'cohesion': put related things nearby one another. This is pretty fuzzy until you've actually had concrete experience getting bitten by the lack of cohesion and attendant unmanageable complexity. To sum up, it's something you need to learn through experience—especially because another aspect of the problem is identifying situations where it really make sense rather than some simplistic heuristic about using state machines is better than not.

2) The way they're taught in school is generally about theory of automata, or they're used to diagram the behavior of some simple little system. Using them to control state transitions in applications is unlikely taught at all, and isn't really directly implied by the seemingly related things which are taught.

It's not just juniors. The only times I've encountered state machines in the wild are almost exclusively games and virtual machines/interpreters.

The reason, to me at least, is pretty clear. In both games and VMs, you mostly know the rules ahead of time. You have a clear picture of the opcodes you want to implement (add, mul, call, jump, etc.) or the game rules you need.

But for most development, especially with multiple stakeholders or customers and multiple developers working independently, the rules aren't known at the start. In fact, the majority of requirements are brought up months or years after the first line of code is even written. It's like the parable of the blind men and the elephant (https://en.wikipedia.org/wiki/Blind_men_and_an_elephant). Each person, working separately, has a different idea of what this thing is that you're creating. Communication being an incredibly difficult thing, the requirements are never fully rendered coherent by the entire team at the moment where it would benefit them most (i.e. the beginning).

But having also blogged for a while... There are no good examples that are complex enough to be realistic and yet simple enough that we can concentrate on the programming principle and not be distracted by the thing being modelled :-D

Now as to one or two state machines... This has not been my experience. I have worked on some systems that had dozens of state machines, nearly every domain model was a state machine of some kind.

This example is very reductive. In a rich and constantly changing domain like banking using a state machine to model core entities like an Account almost always ends in disaster. It simply doesn't work because businesses are complex and ever-changing. Virtually every time I've seen a 'STATE' property in a core entity, especially if it's a public property, it has evolved over time to become a horrendous thing that nobody really understands but it is now integrated throughout so many codebases that people have no choice but to continue supporting it. Ugh.

The real point here is that state machines are mathematical, highly specified constructs. They do not change well. If you are working on a protocol that can be specified precisely, sure use a state machine. If you're working on a business entity think long and hard about whether these requirements are truly fundamental and will never change. And if you really do think you have a state machine at least don't make it public.

However... A blog post with the stated aim of alerting programmers to the opportunities for refactoring a convoluted domain model into something with more structure has to start somewhere, and leave something out.

The great thing about discussions like this is that more experienced programmers such as yourself can chime in with exactly this kind of observation.

I invite you to post a link or two for others to read. I'm sure the community will appreciate it.

But giving your classes explicit state is certainly very valuable. I even wrote a tool that would take an ASCII-art diagram of a PN embedded in the comments of a class, and generate the state definitions and methods within the class.

I wonder how those map to "Behavior Trees" in game development?

I think the only course where I explicitly designed programs using state machines was compilers (other than writing things to simulate state machines in my theory courses).

I did both EE and CS undergrad (we didn't have Computer Engineering at the time). In EE we started talking about FSMs very early on, in quite a bit of depth. In CS though, we didn't really talk about them until the Computability course in 3rd or 4th year, and even then it was in the very theoretical Finite Automata sense; applying FSMs to software design wasn't really a thing that was ever covered.

From the EE material, I started loosely applying those concepts to software design, but it wasn't until my first job in industry where I was lucky enough to be exposed to a system that was very deliberately designed as a system of FSMs.

We based the design of ours off of a pretty famous paper, whose name is entirely escaping me at the moment. Damn.

  > Another in the series "Show HN what is it that people
  > actually learn in their first two years of undegrad CS"

Thankfully I enjoyed screwing around with game programming, and picked up Matt Buckland's Programming Game AI by Example[1]. I've used essentially the same FSM design described there over and over in my career.

[1] http://amzn.to/2FxZ54c

There's CS and there are coding jobs. And sometimes they don't overlap...

So there's learning about state machines in that context and then there's learning about state machines by actually building them in complex pieces of software, or replacing spaghetti code with FSMs. That's when I personally realized how valuable they are.

That is something I never learned in school - and something I learned throughout a career of experimenting, making mistakes, reading from books like http://gameprogrammingpatterns.com, learning from peers, and reading articles like this.

Finite state machines as used to accomplish practical computing tasks other than grammar recognition were something I didn't see at all in undergrad CS (with the very slight exception of networking where we did see a state diagram for TCP).

(Also, I did my CS undergrad at UC Berkeley and I don't recall ever studying state machines. All the useful engineering bits and design patterns I picked up after getting my first job.)

https://github.com/jdque/royal/blob/master/test.js

I agree with your colleague somewhat. If you have a system where every domain object is inextricably linked to every other domain object, then you're going to have a state explosion trying to capture the states and transitions.

My gut reaction looking at a system like that is to start decomposing it, looking for accidental coupling that doesn't need to be there.

I guess domain-specific transitions like undo and cohesion mean similar things to state machines: requirements that don't cleanly fit into conventional state machine models.