Hacker News new | past | comments | ask | show | jobs | submit login
How (Not) to Code a Finite State Machine (1988) [pdf] (astate.edu)
13 points by tjalfi 38 days ago | hide | past | favorite | 5 comments



I'm not sure I like the idea of using GOTOs, I'm sure better ways must exist.

But this bit resonated with me very strongly:

> is unfortunate that the majority of the ma- terial written on reducing finite state automata to code is in texts on compiler construction. Finite state machines play a sufficiently impor- tant role in a variety of computing applications to suggest that their use in programs should be introduced in lower level or even introductory programming texts.

So many things are better modeled as state machines, and their use as a programming pattern is rarely taught / seen in the wild.


apache hbase is full of awful state machine code implemented in a slight variant of "the wrong way" described in this paper. it is 100% unreadable spaghetti. here's one example: http://archive.cloudera.com/cdh5/cdh/5/hbase/xref/org/apache...

not sure the goto approach would much better but this approach ends up just being a poor reinvention of goto in java


The GOTO approach is better, so long as the FSM is abstracted away. An FSM implemented as GOTOs is great. An FSM + state internals implemented with GOTOs is a disaster.

You don't want to mix the FSM with the internals of the states. For example:

STATE_1:

result = state1.action();

if result == A THEN GOTO STATE_2

if result == B THEN GOTO STATE_7

Is okay. Complex internal logic is not:

STATE_1:

[ton of actions and logic]

if [ton of logic] THEN GOTO STATE_2

if [ton of logic] THEN GOTO STATE_7

If your states are more complex than that, it's a mess. Or if your language supports it:

STATE_1:

NEXT_STATE = state1.action()

GOTO NEXT_STATE

Again, modern language support is horrible for this sort of thing.

You can go one step up and make a generic FSM, with e.g. a Python dictionary of functions which return future states:

while True:

state = STATES[state.action()]


I agree. I was taught FSMs in my introductory electrical engineering courses but never once in any CS course.

FSMs can work really well for software, but perhaps the complexity of a program would result in a massive number of states. I have also found it is harder to reason about the entire operation of a FSM.


It seems like there can be some advantages to using the traditional structure. The fsm might be implemented in an object that receives input each time it's called, and is itself embedded in a larger loop. In that case, a goto doesn't make much sense, and storing the state of the machine in anticipation of the next call is what is needed.

The loop based implementation also seems more similar to how one would implement an fsm in a hardware description language. A loop that is visited once per clock cycle seems easier to understand and debug.




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

Search: