A Painless Introduction To Finite State Machines

Lamson uses the concept of a Finite State Machine to do the internal processing
and keep track of what it should do next. You don’t necessarily need to know
the details of how a FSM works, but it helps you if you want to know enough
about Lamson to do advanced work. Most people could be blissfully unaware of
state machines and still do plenty of work with Lamson.

Your Computer Science Class Sucked

When I say “finite state machine” everyone reads it as:

FINITE STATE MACHINE!!!!! OMGWTFBBQ THOSE ARE HARD!!!!”

Yes, the way your professor explained FSM makes them much harder than they are
in practice. You were probably thrown fairly random sounding terms like
“edge”, “node”, “transitions”, “acceptors”, “recognizers”, and “transducers”.
You were probably shown graphs with lines and circles and told confusingly that
the lines were edges and the circles were nodes, but that the edges were states
unless you used this kind where the edges were transitions and that kind where
the circles were states.

Alright, just forget about that because they aren’t really that complicated. A
practical finite state machine is basically four things:

That is really all there is to every FSM. Sure you can change around what a
state is, add code that runs on a transition, or make FSM that “inherit” from
other FSM, but in the end they are all:

functions, events, states, transitions

That is all there is to it, no matter how you slice these or dice these up.

Implementing A Practical FSM

Now that we’ve brought the fear level down, let’s actually make one. This will
be a little toy FSM, but it will get you started and it won’t be too far off
from what Lamson uses.

We are going to implement your classic email confirmation system. This system
usually works like this:

  1. You receive an email at some service, let’s say users-subscribe@test.com.
  2. You reply to the sender with a confirmation message.
  3. They reply with an email to your confirmation’s random address.
  4. You receive this, approve the handshake, and make them subscribed with a welcome email.
  5. They send an email, and since they are subscribed, you post it to the list.

This is a typical operation on most mailing lists, but with a state machine it
turns out to be fairly trivial to implement.

First, we need to look at the above conversation and think about what is more
clear: states the user will be in, or events that they will generate. In this
case I’d go with the states they will be in during the conversation:

Notice I gave each state a verb. You are saying what state this user is in.
“They are currently posting.” You don’t say what they “did”. Now, sometimes
it just makes sense to do it differently, so don’t be a slave to this setup.
I’ve just found it helps keep things consistent if you name the states after
what they are currently doing.

Now that we know what kind of states we’re dealing with we need to solve the
next two parts of the puzzle: events or transitions. In an email application
I like to start with the events, as these are the email addresses and messages
they will be sending me. What we do now is for each state, list the addresses
we’ll consider an “event” for that state.

This is all the “events” we need right now, written out as email addresses.

If we were to add the ability to unsubscribe, then we would add an event
for (list_name)-unsubscribe@test.com to POSTING so that we could transition them from POSTING to say, SLEEPING.

We now have our states, and the events that each state answers. Last step is
to figure out what state “transitions” to which other state.

Write The Functions

At this point, our FSM is simple enough that we could just write the functions,
and the logic of each function would dictate the transitions. However, if you
had a larger number of states and events you would want to sit down and draw a
diagram or a make a table of the transitions before you wrote some code.

To start our functions we’ll just name them after the states and put the events
they handle at the top as pseudo code event decorators:


event("(list_name)-subscribetest.com”)
def START: “”“Initial setup of the user.”“” ...

event("(list_name)-confirm-(id)test.com”)
def PENDING: “”“Waiting for them to confirm.”“” ...

event("(list_name)test.com”)
def POSTING: “”“They are posting, anything they send we post.”“” ...

This is abbreviating the syntax quite a bit, is not functioning Python code but
it is pretty close. Instead of event you would have a route decorator and
it would have a few regexes. Otherwise it’s about the same.

We could also say that each state handles multiple events, which is what
you would do if POSTING handled the “unsubscribe” requests.

Add Logic And Transitions

The final piece, and the part you’ll spend the longest getting right, is
filling in the logic and making the transitions happen. How would you indicate
where each state should go next? Remember that each state is a simple Python
function, and that to “transition” means to change to another state. Well, we
have to tell whatever is running the state machine to run a different
function next time.

Easiest way to do that is for our handlers to just return the next function.
The “runner” will then take that, store it somewhere, and the next time an
event comes the runner will load the next function to run.

Here’s the psuedo code to do just that:


event("(list_name)-subscribetest.com”)
def START: “”“Initial setup of the user.”“” send_confirmation() return PENDING

event("(list_name)-confirm-(id)test.com”)
def PENDING: “”“Waiting for them to confirm.”“” if check_confirmation_is_good(): send_welcome() return POSTING else: ignore_them()

event("(list_name)test.com”)
def POSTING: “”“They are posting, anything they send we post.”“” deliver_message_to_all() return POSTING

Right away you can see that we change to the next state by just returning the
actual function to call next. When the next event comes in, the runner matches
it to the right function, calls it, and then sets up for the next one.

If you look at PENDING, you can see that it either returns POSTING if they
confirm correctly or it just ignores them. You could also transition to
“return ERROR” if you wanted to put them in an error state and send a different
message.

Looking at POSTING, you see that it just keeps returning itself to indicate
that it is staying there. If you had POSTING process “unsubscribes” then it
would simply do the unsubscribe confirm, and then transition to UNSUBSCRIBING.
That state function would then check the confirmation and unsubscribe them,
transitioning to something like DEAD or SLEEPING.

An “optimization” in Lamson is that if a state function doesn’t return
anything then it’s assumed to just want to stay in that state. In this case
POSTING could have no return and it would work the same.

Jump To vs. Transition

You now know pretty much everything you need to handle FSM except for a tiny
corner case. It is typically called the “epsilon transition” which basically
means “transition to that state without an explicit event”. When you use this
is when your event needs to fire off the code for the next transition right
now, rather than waiting for the next event from the user.

In the above pseudo code this is simply done by actually calling that
transition function and returning whatever it returns. Let’s say we wanted to
have PENDING also call POSTING with the original message they sent:


def PENDING: if check_confirmation_is_good(): send_welcome() return POSTING (message): else: ignore_them()

def POSTING: deliver_message_to_all() return POSTING

Notice that we changed the return POSTING to a return POSTING(...) which
returns the results of calling POSTING.

That’s it, you now know epsilon transitions. Man, that was tough.

The danger of this is if you don’t have your FSM carefully mapped out,
then you could call a state that loops back to your state and you’re in an
endless loop. Watch for that.

Why Finite State Machines Anyway

Finite State Machines like this are very powerful because they behave in ways
that are consistent, easily debugged, and intelligent. Because the decision of
how each step in the chain of events is controlled by a constrained set of
states, events, and transitions, you can actually avoid many bugs you’d get in
regular classes and objects.

For example, if you were to receive another subscribe message while there is a
confirmation pending, then that event (email address) isn’t recognize and just
ignored. You would see it in the logs, and see that your FSM stayed in the
PENDING state. If you then wanted PENDING to handle additional requests it’s a
simple matter of adding that event and writing the code.

The way to think of the a FSM is it is like an object that has a white list of
functions, parameters, AND allowed values for its private data. If an FSM
tries to change to a state that doesn’t exist it’s an error. If it gets an
event it doesn’t know it ignores it. If you try to transition wrong you see it
in the logs, or it’s an error.

FSM also have the debugging advantage of showing you the history of not only
what states were called, but why they were called and what they did next.
You will see the entire conversation and can pinpoint exactly where it went
wrong.

However, the most important reason to use FSM is because this is how email and
asynchronous conversations work. When you have a conversation with someone
there is state involved. You don’t have to start the entire conversation from
scratch at the start of each sentence. Instead you remember what the person
said and what state you are in (angry, sad, happy) and that controls what you
do next (punch them, run away, hug them) based on the events they send (“screw
you”, “you’re dead”, “i love you”).

The use of an FSM will make your Lamson applications seem like magic. They
will behave more like smart systems that just seems to know like a wizard what
should happen next, and why it should happen that way.