Finite State Machines

There is probably no concept more fundamental to computer science than the Finite State Machine (FSM). Variants of this concept came early enough in computer science that they actually predate electronic computers. The state machine has, in the modern day, become a very common software pattern.

The FSM is a highly practical pattern which can be used to simplify code, and accurately represent a number of fairly complex systems in a maintainable and idiomatic way. I’m assuming the reader will know what a FSM is, at least approximately, although I’ve written an overview of the concept below. I am also assuming that the reader is sufficiently capable of implementing one for themselves, or at least can find out about how to do that elsewhere.

What this piece is concerned with, is why you should use them, not how you can.

Finite State Machines

A FSM is defined by a list of its States, and the list of transitions. The current state of the machine starts in the initial state (of which there is usually exactly one), and can change when the conditions for the transitions are met.

They can be used to categorise data - Regular Expressions can be implemented as a state machine - or used to simulate any number of simple(ish!) systems - like animation trees, behaviour states, and so on.

For some systems, a FSM is an obviously good fit, for example fish behaviour, which has states for Swimming, Beached, Startled, Curious, Hooked, and Dead. These states are all mutually exclusive, and in the confines of the behaviour, the conditions for the transitions between them are exact and simple.

But there are other articles about how best to use them for this, and how best to implement them. The major benefit of FSM which applies much more widely is bug reduction, and code simplification (and hence, improved maintainability).

Bug Reduction

Frequently in code you’ll see complex functions with forms something like:

class someClass {
	void someFunc() {
		if(someBool) {
			/* do stuff */
		} else {
			/* other stuff */
		}

		/* common code */

		if(someBool) {
			/* more stuff */
			if(SomeConditionIsMet()) {
				/* do some setup */
				someBool = true;
			}
		} else {
			/* even more stuff */
		}
	}
};

This isn’t too bad as code goes, but it’s not resilient to changes. Say when someBool is set, the code in «common code» needs to do something slightly different. The maintainer has to remember to wrap that code in if(someBool) { } or it will affect both of the states. Worse, if another boolean or similar becomes part of the code you get further issues, as you have to be sure that the function does the right thing for every combination of states it could be in, and in the event that the state becomes an error state by a set of flags or enums being in a combination not expected or designed for.

For example, you might have someOtherBool which when it is set should supercede someBool being set. Now you have to update every conditional which checks someBool to make sure it respects both pieces of data. The more booleans or other dividing conditions you add, the more complex the relationship between the states of those data becomes. The more complex the conditions for that code gets, the easier it is to write bugs, and the harder it is to successfully maintain the codebase.

A state machine can fix this. Not in every case, and when it can it might not be the perfect solution, it’s not a magic bullet. But lets say instead of someBool and ifs we used states. The above code could look like this:

class someClass {
	struct someClassState : public State {
		virtual void someFunc() = 0;
	};

	struct StateA : public someClassState {
		void someFunc() override {
			/* stateA code */

			if(SomeConditionIsMet()) {
				EnterState<StateB>();
			}
		}
	};

	struct StateB : public someClassState {
		void Enter() override {
			/* StateB setup */
		}
	
		void someFunc() override {
			/* stateB code */
		}
	}

	void someFunc() {
		curState->someFunc();
	}

private:
	using initialState = StateA;
	StateMachine<someClassState, initialState> curState;
};

This code is logically equivalent to the previous sample. The benefits: States are distinct from each other. Each state’s functions are clearly separated from one another, both logically by the object structure, and physically in the source code. Adding States or changing the states’ interactions has more obvious results.

The Enter() function here is called when a state machine enters that state, no matter what. This means in the first code sample, any of the setup code that precedes someBool = true; which needed to be set alongside someBool is handled, and a maintainer doesn’t have to remember or check what that might be. With a little work it’s possible to have EnterState accept arguments for the new State’s constructor as well, to handle any data that needs to be passed around (or just have the interface like EnterState(new StateX(args, go here)) or similar)

Downsides

There are a few downsides I can think of, but some of them may be mitigated, somewhat. They are:

Verbosity

This one is the hardest to contest. Compared to a badly written ad-hoc state machine, the verbosity isn’t particularly significant. In a large complex system, it’s probably dwarfed by the actual code. In a small system, however, it can be a problem. I can only say that terse code is rarely as clear. If tersity is an absolute requirement, then don’t use this method. But I’ve never worked in a codebase where tersity was valued over clarity and maintainability.

Complexity

The state machine seems like a more complex system. It’s an extra layer of abstraction, and requires your library to have a decent implementation of a state machine for you to work with. That said, just because you aren’t using an explicit FSM system, doesn’t mean you haven’t written an FSM accidentally. Ad-hoc state machines appear in code all the time, and they’re just as complex as the explicit state machine which is their equivalent, however that complexity is hidden, and not in a good way.

Using an FSM says to a maintainer ‘this system is a little complex’, but it also says ‘this complexity was planned and necessary’. It gives the maintainer a clearer idea of where the dividing lines in the states are, allowing them to navigate the complexity in a reasonable way.

Insufficient Complexity

State machines can only model certain specific classes of systems. Sufficiently complex systems might need multiple state machines to represent them accurately, or they might need a more complex type of machine entirely. Luckily there are Hierarchical State Machines, which give states base states and add all kinds of possibilities. There are also Push Down Automaton, which allow the state machine to retain a history of its states in a stack. They are very practical for menu systems, and many other things.

Virtual Calls

This complaint is a complex one. Compared to a badly written ad-hoc FSM, the number of branches, and switches and other crap that might make up the code being replaced which just disappear when you write an explicit FSM, the virtual jump cost disappears. Compared to the exact same code written as something like:

void someFunc() {
	switch(stateEnum) {
	case State1:
		State1someFunc();
		break;
	case State2:
		State2someFunc();
		break;
	case State3:
		State3someFunc();
		break;
	default:
		assert(false);
}

and an accompanying SetStateTo(newVal) to replicate Enter() and such… then yes, you’re paying for a virtual call you might not have had to. Of course, in the above version you’re paying for a lookup and jump which is really just an adhoc virtual call, and while I haven’t profiled even a toy version of this, I suspect the cost is similar.

Obviously given the whole point of this post is ‘Ad-hoc systems are not as good as explicit ones’ I’m going to say that an ad-hoc virtual table is not as good as an actual virtual table. Explicit FSMs and explicit virtual table systems are good idiomatic code. They tell the maintainer exactly what you’re up to, and they save time and effort down the road.

Use them.