Warning

This book is new. If you'd like to go through it, then join the Learn Code Forum to get help while you attempt it. I'm also looking for feedback on the difficulty of the projects. If you don't like public forums, then email help@learncodethehardway.org to talk privately.

Exercise 30: Finite State Machines

Whenever you read a book on parsing there's this scary chapter on Finite State Machines (FSM). They go into great detail of "edges" and "nodes" with every combination of possible "automata" being converted into other automata and frankly it's a bit much. There's a simpler explanation of FSMs that makes them practical and understandable while not violating the purist theoretical version of the same topic. Sure you won't get a paper submitted to the ACM because you don't know all of the mathematics behind FSM, but if you just want to use them in your applications then they are simple enough.

An FSM is a way to organize events happening to a set of states. Another way to define an event is an "input trigger", similar to the boolean expressions in an if-statement, but usually less complex. An event could be a button click, receiving a character from a stream, a change in the date or time, and pretty much anything you want to declare an event. A state is then any "position" your FSM stops at while it waits for more events, and at each state you redefine the allowed events (inputs). Events tend to be temporary, while states are usually fixed, and both are data that you can store. Finally, you can attach code to both events or states and even decide if code should run when you enter a state, during the state, or when exiting the state.

An FSM is simply a way to white-list the possible code to run when different events happen in different points in an execution. In an FSM, when you receive an unanticipated event, you get a failure because you have to explicitly say exactly what events (or conditions) are allowed at each state. An if-statement also handles possible branches, but it is a black list of possibilities. If you forget the else clause, then anything not covered by your if-elif conditions falls right through.

Let's break this down then:

  1. You have states, which are a stored indicator of where the FSM is currently positioned. A state can be anything like "started", "key pressed", "aborted", or some similar way to describe how the FSM is positioned in its possible points of execution. Each state implies that it is waiting for something to happen before deciding what to do next.
  2. You have events that can move the FSM from one state to another. An event can be "press a key", "socket connection fails", "file saved", and represent that some external stimuli was received by the FSM so it must decide what to do and what state to enter next. An event can even just go back to the same state, which is how you loop.
  3. FSMs transition from one state to another based on events happening, and only for the exact events given for that state (though one of the events can be defined as "any event"). They don't "accidentally" shift state, and you can track exactly how they moved from one state to another by looking at the events received and the states visited. This makes them very easy to debug.
  4. You have code that can run on each event before, after, and during a state transition. This means that you can run some code when an event is received, then decide what do to based on that event in the state, then run code again before you leave that state. This capability to execute code makes FSM very powerful.
  5. Sometimes "nothing" is also an event. This is powerful because it means you can transition an FSM to a new state even though nothing happened. However, in practical terms "nothing" tends to be the implied event "go again" or "wake up". In other situations nothing means "not sure yet, maybe the next event will tell me what state."

The power of the FSM comes in being able to explicitly state each event and that the events are simply data being received. This makes them incredibly easy to debug, test, and make correct since you know exactly each state possible and what can happen in each state for each event. In this exercise you're going to study an implementation of an FSM library and an FSM that uses it to understand how they work.

Exercise Challenge

I've created an FSM module that handles a few simple events for processing connections to a web server. This is an imaginary FSM to give you an example for how you can write one quickly in Python. It is only the basic skeleton of processing connections that read and write from a socket, and it's missing a few important things, but this is just a small example for you to use.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
def START():
    return LISTENING

def LISTENING(event):
    if event == "connect":
        return CONNECTED
    elif event == "error":
        return LISTENING
    else:
        return ERROR

def CONNECTED(event):
    if event == "accept":
        return ACCEPTED
    elif event == "close":
        return CLOSED
    else:
        return ERROR

def ACCEPTED(event):
    if event == "close":
        return CLOSED
    elif event == "read":
        return READING(event)
    elif event == "write":
        return WRITING(event)
    else:
        return ERROR

def READING(event):
    if event == "read":
        return READING
    elif event == "write":
        return WRITING(event)
    elif event == "close":
        return CLOSED
    else:
        return ERROR

def WRITING(event):
    if event == "read":
        return READING(event)
    elif event == "write":
        return WRITING
    elif event == "close":
        return CLOSED
    else:
        return ERROR

def CLOSED(event):
    return LISTENING(event)

def ERROR(event):
    return ERROR

There is also a tiny test that shows you how to run this FSM:

1
2
3
4
5
6
7
8
9
import fsm

def test_basic_connection():
    state = fsm.START()
    script = ["connect", "accept", "read", "read", "write", "close", "connect"]

    for event in script:
        print(event, ">>>", state)
        state = state(event)

Your challenge in this exercise is to turn this sample module into a more robust and generic FSM Python class. You should use this as a set of clues as to how you can handle events coming in, how states can be Python functions, and how you can do implied transitions. See how sometimes I return the function for the next state, but other times I return a call to that state function? Try to figure out why I'm doing that as it's very important in an FSM.

To complete this challenge you'll need to study the Python inspect module to see what you can do with a Python object and class. There are special variables like __dict__ as well as functions in inspect that help you look into a class or object and find a function.

You may also decide that you want to invert this design. You could have the events be functions in a subclass, and inside the events functions you check for the current self.state to determine what to do next. It all depends on what you are processing, whether you have more events or states, and what makes sense at the time.

Finally, you could go with a design where there is a FSMRunner class that simply knows how to run modules that are designed like this. This has some advantages over a single class that knows how to run instances of itself, but it also can have some problems. For example, how does the FSMRunner keep track of the current state? Is it put in the module or in the instance of FSMRunner.

Study Drills

  1. Make your test more extensive and do an FSM for a totally different domain you're familiar with.
  2. Add an ability to turn on logging of the event run in your implementation. One of the biggest advantages of using an FSM to process events is you can store and log all of the events and states an FSM has received. This lets you debug why it reached a state you don't like.

Further Study

You should definitely read up on the real math behind a Finite State Machine. My little example here is not a fully formalized version of the concept so that you can understand it.

Pre-order Learn More Python The Hard Way

When you pre-order Learn More Python The Hard Way, you'll receive the Python 3 Edition as it's being created. All files are DRM free and you can download them to your computer for offline viewing. Digital Download Only! You do not get a physical book.

$29.00

Buy the Online Course

Or, you can read Learn More Python the Hard Way for free right here, video lectures not included.

Other Buying Options

Other buying options coming soon.

No content available for this exercise. You can view all available downloads at your customer account page.