Velocity Reviews > Re: State Machines in Python

# Re: State Machines in Python

D'Arcy J.M. Cain
Guest
Posts: n/a

 09-04-2010
On Sat, 4 Sep 2010 14:36:38 +0100
Jack Keegan <(E-Mail Removed)> wrote:
> Just joined the group. I'm new to Python but been picking it up pretty easy.

Welcome aboard.

> As there is no switch statement in Python, I've been looking around for a
> good implementation. Most of the algorithms I've come across seem to be

There's no switch statement because there's no real need for one.
Check out the following sample code and see if it gives you some ideas.

#! /usr/bin/env python
# -*- coding: utf-8 -*-

# Sample state machine

import sys

data = dict(counter = 0, flag = False)

def state1(d):
d['counter'] += 1
print "In state 1, counter = %(counter)d" % d
if d['flag']: sys.exit(0)
return state2

def state2(d):
d['counter'] += 1
print "In state 2, counter = %(counter)d" % d
return state3

def state3(d):
d['counter'] += 1
d['flag'] = True
print "In state 3, counter = %(counter)d" % d
return state1

state = state1
while True:
state = state(data)

--
D'Arcy J.M. Cain <(E-Mail Removed)> | Democracy is three wolves
http://www.druid.net/darcy/ | and a sheep voting on
+1 416 425 1212 (DoD#0082) (eNTP) | what's for dinner.

Roy Smith
Guest
Posts: n/a

 09-04-2010
In article <(E-Mail Removed)>,
"D'Arcy J.M. Cain" <(E-Mail Removed)> wrote:

> On Sat, 4 Sep 2010 14:36:38 +0100
> Jack Keegan <(E-Mail Removed)> wrote:
> > Just joined the group. I'm new to Python but been picking it up pretty easy.

>
> Welcome aboard.
>
> > As there is no switch statement in Python, I've been looking around for a
> > good implementation. Most of the algorithms I've come across seem to be

>
> There's no switch statement because there's no real need for one.
> Check out the following sample code and see if it gives you some ideas.
>
> #! /usr/bin/env python
> # -*- coding: utf-8 -*-
>
> # Sample state machine
>
> import sys
>
> data = dict(counter = 0, flag = False)
>
> def state1(d):
> d['counter'] += 1
> print "In state 1, counter = %(counter)d" % d
> if d['flag']: sys.exit(0)
> return state2
>
> def state2(d):
> d['counter'] += 1
> print "In state 2, counter = %(counter)d" % d
> return state3
>
> def state3(d):
> d['counter'] += 1
> d['flag'] = True
> print "In state 3, counter = %(counter)d" % d
> return state1
>
> state = state1
> while True:
> state = state(data)

This is the pattern I've always used. Simple and effective for any
state machine which is small enough to code by hand. I generally have
my state methods return (next_state, output) tuples, but that's a detail.

MRAB
Guest
Posts: n/a

 09-04-2010
On 04/09/2010 18:58, Roy Smith wrote:
> In article<(E-Mail Removed)>,
> "D'Arcy J.M. Cain"<(E-Mail Removed)> wrote:
>
>> On Sat, 4 Sep 2010 14:36:38 +0100
>> Jack Keegan<(E-Mail Removed)> wrote:
>>> Just joined the group. I'm new to Python but been picking it up pretty easy.

>>
>> Welcome aboard.
>>
>>> As there is no switch statement in Python, I've been looking around for a
>>> good implementation. Most of the algorithms I've come across seem to be

>>
>> There's no switch statement because there's no real need for one.
>> Check out the following sample code and see if it gives you some ideas.
>>
>> #! /usr/bin/env python
>> # -*- coding: utf-8 -*-
>>
>> # Sample state machine
>>
>> import sys
>>
>> data = dict(counter = 0, flag = False)
>>
>> def state1(d):
>> d['counter'] += 1
>> print "In state 1, counter = %(counter)d" % d
>> if d['flag']: sys.exit(0)
>> return state2
>>
>> def state2(d):
>> d['counter'] += 1
>> print "In state 2, counter = %(counter)d" % d
>> return state3
>>
>> def state3(d):
>> d['counter'] += 1
>> d['flag'] = True
>> print "In state 3, counter = %(counter)d" % d
>> return state1
>>
>> state = state1
>> while True:
>> state = state(data)

>
> This is the pattern I've always used. Simple and effective for any
> state machine which is small enough to code by hand. I generally have
> my state methods return (next_state, output) tuples, but that's a detail.

I suppose that if they are that similar then you could generate the
code from a list or table of the states.

D'Arcy J.M. Cain
Guest
Posts: n/a

 09-04-2010
On Sat, 04 Sep 2010 13:58:00 -0400
Roy Smith <(E-Mail Removed)> wrote:
> > while True:
> > state = state(data)

>
> This is the pattern I've always used. Simple and effective for any
> state machine which is small enough to code by hand. I generally have
> my state methods return (next_state, output) tuples, but that's a detail.

What is "output" for? Is it a string or something else? What do you
do with it? Notice that I create a dictionary which is passed around
so that states can pass whatever information back that they deem useful
and any state can pick up whatever info it needs. for example, in my
sample code every state uses the counter but only two states use the
flag element.

--
D'Arcy J.M. Cain <(E-Mail Removed)> | Democracy is three wolves
http://www.druid.net/darcy/ | and a sheep voting on
+1 416 425 1212 (DoD#0082) (eNTP) | what's for dinner.

D'Arcy J.M. Cain
Guest
Posts: n/a

 09-04-2010
On Sat, 04 Sep 2010 19:13:28 +0100
MRAB <(E-Mail Removed)> wrote:
> I suppose that if they are that similar then you could generate the
> code from a list or table of the states.

They generally aren't as simple as the little example script that I
cobbled together.

--
D'Arcy J.M. Cain <(E-Mail Removed)> | Democracy is three wolves
http://www.druid.net/darcy/ | and a sheep voting on
+1 416 425 1212 (DoD#0082) (eNTP) | what's for dinner.

Stefan Behnel
Guest
Posts: n/a

 09-04-2010
D'Arcy J.M. Cain, 04.09.2010 20:30:
> On Sat, 04 Sep 2010 13:58:00 -0400
> Roy Smith<(E-Mail Removed)> wrote:
>>> while True:
>>> state = state(data)

>>
>> This is the pattern I've always used. Simple and effective for any
>> state machine which is small enough to code by hand. I generally have
>> my state methods return (next_state, output) tuples, but that's a detail.

>
> What is "output" for? Is it a string or something else? What do you
> do with it? Notice that I create a dictionary which is passed around
> so that states can pass whatever information back that they deem useful
> and any state can pick up whatever info it needs. for example, in my
> sample code every state uses the counter but only two states use the
> flag element.

I guess the idea is that each of the states can't arbitrarily modify the
global status (dict) but is restricted to designating a next state and
returning something. So you don't take the risk of introducing side effects
somewhere because all state implementations are pure functions (at least as
far as the state machine itself is concerned).

Stefan

Roy Smith
Guest
Posts: n/a

 09-04-2010
In article <(E-Mail Removed)>,
"D'Arcy J.M. Cain" <(E-Mail Removed)> wrote:

> On Sat, 04 Sep 2010 13:58:00 -0400
> Roy Smith <(E-Mail Removed)> wrote:
> > > while True:
> > > state = state(data)

> >
> > This is the pattern I've always used. Simple and effective for any
> > state machine which is small enough to code by hand. I generally have
> > my state methods return (next_state, output) tuples, but that's a detail.

>
> What is "output" for? Is it a string or something else?

I've often used this pattern for parsing a text file and extracting
interesting data. At various points during the input stream, you will
have read an entire piece of data, and return it as the output of the
state machine. Not every state will result in output being produced.

As a trivial example, let's say I had a file format which stored network
addresses in a deliberately silly style:

--------------------
# This is a comment

host = 10.2.3.4
port = 999
proto = TCP

port = 1001
proto = TCP
host = 192.168.1.1

status = ignore
host = 1.2.3.4
port = 22
host = 127.0.0.1

proto = UDP
port = 1001
host = 192.168.1.1
--------------------

I want to parse out (host, port, proto) triples, i.e. the state machine
should produce the following output:

(10.2.3.4, 9099, TCP)
(192.168.1.1, 1001, TCP)
(192.168.1.1, 1001, UDP)

As the end of each data block is recognized, a 3-tuple would be
returned. Other state transitions would return None as the output.
Then, the main loop can be something like:

state = start
for line in input:
next_state, output = state(line)
if output:
print output
state = next_state

I'm not saying it has to be done that way, just that I've found it a
handy pattern for the stuff I've done.