Petr Jakes wrote:
Hello,
I am trying to study/understand OOP principles using Python. I have
found following code http://tinyurl.com/a4zkn about FSM (finite state
machine) on this list, which looks quite useful for my purposes. As
this code was posted long time ago (November 1998) I would like to ask
if the principles used in this code are still valid in the "modern"
Python and if/how it can be improved (revrited) using futures of
current version of Python.
Thanks for your comments for a "newbie" and for your patience.
Petr Jakes
Python has no goto.
If you think about the possible execution paths through a function, you
can represent that as a finite state machine: A FSM is just a graph, and
in a function, you get a FSM by treating each statement as a node, and
statements that can follow that statement (in the execution order) have
a (directed) edge to them (let's ignore exceptions for the moment). So for:
a=b
if a == 3:
z = 0
else:
z = 1
print 'spam'
we get:
(a=b) -> (if a == 3) -> (z = 0)
| |
(z = 1) -> (print 'spam)
Now, when we want to emulate a FSM in a function directly (rather than
some slower table-driven scheme), we need to use the constructs provided
by the language. But simple 'if' statements just don't cut it. We end up
with:
while state != 'final':
if state == 1:
# do state 1 stuff here
state = 3
elif state == 2:
# if cond:
state == 1
else:
state == 99
elif
...
else:
# unknown state
Problem with this approach is that, on average, you'll have n/2
comparisons of the state variable. What you want is to jump directly
from state 1 to state 3 without having to go anywhere else. You want a goto.
Another goto-less way is with functions. Each function is a state, which
sets a global function variable to the next state-function:
def f_state_1():
global func
# do state 1
func = f_state_3
def f_state_2():
global func
# do state_2 stuff
if cond:
func = f_state_1
else:
func = f_state_99
#etc.
func = f_state_1 # start_state
while func != None:
func()
We've eliminated the numerous comparisons, and it is, arguably, more
pythonic. But now you have a function-call overhead on each state
transition, and any information shared between states has to be in an
enclosing scope.
We want a goto.
Unfortunately, this is about the only problem I can think of where gotos
are useful. And for reasons well explained elsewhere, gotos are Not Good.
I've solved this in a very efficient, but rather unpythonic way.
First, you write (or generate) the code in the first way indicated
above. Lots of inefficient 'if' statements in one big function (say,
'fsm'). Then, you write another function (say 'gotoize') which takes fsm
as an argument, and *changes the byte code* of the fsm code object to
add JUMP_ABSOLUTE bytecodes (i.e. gotos) where the 'state' variable gets
reassigned.
fsm can then be decorated with gotoize, and you have a very fast (for
python) FSM. You are, essentially, doing some (fairly simple) byte-code
optimisation.
I can dig out the code if you are interested (except it's pretty untidy
at the moment. I'd be ashamed to show it in it's current state :-)
Ooops. I just reread your post and you claim (or is that plead?)
"newbie" status. Sorry if this is over your head. Hope it helps anyway.
Cheers,
Carl.
