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.

 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

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)