Python code written in 1998, how to improve/change it?

[Petr Jakes]

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

[Steve Holden]

Re: Python code written in 1998, how to improve/change it?

Petr Jakes wrote:[color=blue]
> 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.[/color]

Python places great store on backwards-compatibility. Consequently I'd
suggest you try the code out, and report any problems you find back on
this list. I'd give you odds it will work.

regards
Steve
--
Steve Holden +44 150 684 7255 +1 800 494 3119
Holden Web LLC www.holdenweb.com
PyCon TX 2006 www.python.org/pycon/

[Carl Cerecke]

Re: Python code written in 1998, how to improve/change it?

Petr Jakes wrote:[color=blue]
> 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
>[/color]

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.

[Dan Sommers]

Re: Python code written in 1998, how to improve/change it?

On Fri, 20 Jan 2006 10:27:58 +1300,
Carl Cerecke <cdc@maxnet.co. nz> wrote:
[color=blue]
> Petr Jakes wrote:[/color]

[ a query regarding some 1998 python code that implements a finite state
machine ]
[color=blue]
> Python has no goto.[/color]

Thank goodness!
[color=blue]
> func = f_state_1 # start_state[/color]
[color=blue]
> while func != None:
> func()[/color]
[color=blue]
> We've eliminated the numerous comparisons, and it is, arguably, more
> pythonic ...[/color]

Agreed.
[color=blue]
> ... now you have a function-call overhead on each state transition ...[/color]

Have you profiled your code and demonstrated that this particular
function call consumes too much time?

If you can't stand the overhead of one [extra, parameterless] function
call per transition, especially *after* having eliminated the numerous
comparisons, then Python may not be the best tool for the job.
[color=blue]
> ... and any information shared between states has to be in an
> enclosing scope.[/color]

Well, no, not exactly. Consider an instance of a class that contains
its own data (and perhaps some of its own transition functions) but
inherits the basic state machine machinery from a finite state machine
class (or simply passes itself to a function that implements a finite
state machine by examining attributes of its argument).

And then there are (or should be!) purists who will claim that if your
state machine requires information to be shared between states, then you
don't have enough states! ;-)
[color=blue]
> We want a goto.[/color]

No, we don't.

Regards,
Dan

--
Dan Sommers
<http://www.tombstoneze ro.net/dan/>

[Dave Hansen]

Re: Python code written in 1998, how to improve/change it?

On Fri, 20 Jan 2006 10:27:58 +1300 in comp.lang.pytho n, Carl Cerecke
<cdc@maxnet.co. nz> wrote:

[...][color=blue]
>
>Python has no goto.[/color]

+1

[...][color=blue]
>
>We want a goto.[/color]

-1

Regards,
-=Dave

--
Change is inevitable, progress is not.

[Steven Bethard]

[OT] no goto (WAS: Python code written in 1998...)

Carl Cerecke wrote:[color=blue]
> Python has no goto.[/color]

Not in the standard library. You have to download the module:

http://www.entrian.com/goto/

;)

STeVe

[Carl Cerecke]

Goto in python - NO! (was Re: Python code written in 1998, how toimprove/change it?)

Dave Hansen wrote:[color=blue]
> On Fri, 20 Jan 2006 10:27:58 +1300 in comp.lang.pytho n, Carl Cerecke
> <cdc@maxnet.co. nz> wrote:
>
> [...]
>[color=green]
>>Python has no goto.[/color]
>
>
> +1
>
> [...]
>[color=green]
>>We want a goto.[/color]
>
>
> -1[/color]

I agree entirely. My (rather unclearly made) point was that, for the
particular application (FSM), an unrestricted jump is really handy. Not
that we want goto in python (Eurghhhh!!) just to make this one case easier.

I learnt programming on a Commodore-64 where BASIC programs where
required to be liberally sprinkled with gotos (No else. Only one,
global, scope. No real functions). I know first hand the pain gotos can
inflict. We don't want to go back there.

But. They are still really handy for directly implementing a FSM in
code! Hence my JUMP_ABSOLUTE bytecode rewrite hack for FSMs.

Cheers,
Carl.

[Carl Cerecke]

Re: Python code written in 1998, how to improve/change it?

Dan Sommers wrote:[color=blue]
> On Fri, 20 Jan 2006 10:27:58 +1300,
> Carl Cerecke <cdc@maxnet.co. nz> wrote:[/color]
[color=blue][color=green]
>>... now you have a function-call overhead on each state transition ...[/color]
>
>
> Have you profiled your code and demonstrated that this particular
> function call consumes too much time?[/color]

Yes. For a parser reading a reasonable size input file, the difference
is large enough to be noticeable.
[color=blue]
> If you can't stand the overhead of one [extra, parameterless] function
> call per transition, especially *after* having eliminated the numerous
> comparisons, then Python may not be the best tool for the job.[/color]

Maybe. Except the bytecode *is* quite fast enough. There is just no way
of writing python code so the compiler can generate that bytecode. Hence
the JUMP_ABSOLUTE bytecode rewrite hack.

Cheers,
Carl.

[Petr Jakes]

Re: Python code written in 1998, how to improve/change it?

Thanks for your comments,
The mentioned "8 years old" code actually works somehow.

I am trying to solve very similar problem about FSM as the code in the
example does and I do not want to be overburden by the if/elif stuff or
by declaring state functions (which IMHO is very similar approach as
if/elif).

Because of above mentioned, something like FSM-generator looks as a way
to go for me (if I can judge with my poor skills).

I am using Steve's book "Python Web Programming" which is actually the
best I have found about OOP, classes etc. but as a newbie I am just
lost with subclass and mapping attributes etc. while trying to study
the code in the example (http://tinyurl.com/a4zkn).

All I wanted to know, if, thanks to the improvements in the Python
functionality over the years, it is possible to simplify somhow the old
code.

Otherwise I have to dig through :)

Petr Jakes

PS:
I agree and I do understand the reasons why NOT to use GOTO statements
in the code (aka spaghetti code).

[Carl Cerecke]

Re: [OT] no goto (WAS: Python code written in 1998...)

Steven Bethard wrote:[color=blue]
> Carl Cerecke wrote:
>[color=green]
>> Python has no goto.[/color]
>
>
> Not in the standard library. You have to download the module:
> http://www.entrian.com/goto/[/color]

Haha! Sure. But have you seen how it's implemented? I don't think it
will win many performace prizes. Nifty hack though.

Cheers,
Carl.

[Chris Mellon]

Re: Python code written in 1998, how to improve/change it?

On 19 Jan 2006 15:53:54 -0800, Petr Jakes <petr@tpc.cz> wrote:[color=blue]
> Thanks for your comments,
> The mentioned "8 years old" code actually works somehow.
>
> I am trying to solve very similar problem about FSM as the code in the
> example does and I do not want to be overburden by the if/elif stuff or
> by declaring state functions (which IMHO is very similar approach as
> if/elif).
>[/color]

I'm not sure why nobody else in this thread said it, but the most
common way of implementing state machines I've seen in Python (unless
theres only a couple states you can manage with if/elif) is to use a
dict to map states to callables.


[color=blue]
> Because of above mentioned, something like FSM-generator looks as a way
> to go for me (if I can judge with my poor skills).
>
> I am using Steve's book "Python Web Programming" which is actually the
> best I have found about OOP, classes etc. but as a newbie I am just
> lost with subclass and mapping attributes etc. while trying to study
> the code in the example (http://tinyurl.com/a4zkn).
>
> All I wanted to know, if, thanks to the improvements in the Python
> functionality over the years, it is possible to simplify somhow the old
> code.
>
> Otherwise I have to dig through :)
>
> Petr Jakes
>
> PS:
> I agree and I do understand the reasons why NOT to use GOTO statements
> in the code (aka spaghetti code).
>
> --
> http://mail.python.org/mailman/listinfo/python-list
>[/color]

[Carl Cerecke]

Re: Python code written in 1998, how to improve/change it?

Chris Mellon wrote:
[color=blue]
> I'm not sure why nobody else in this thread said it, but the most
> common way of implementing state machines I've seen in Python (unless
> theres only a couple states you can manage with if/elif) is to use a
> dict to map states to callables.[/color]

Ah. Well, my post suggested, as one option, the callables call
each other directly. No mapping required. But if you want a dict
in there somewhere, feel free to put one in :-)

I was complaining about the function-call overhead of this method
though, which can be quite significant for a FSM where each state
does only a little processing, and there are many transitions -
such as in a parser reading in a large file.

The byte-code rewriting hack mentioned in a previous post
eliminates this overhead. But, I concede, is somewhat ugly.

Cheers,
Carl.

[Carl Cerecke]

Re: Python code written in 1998, how to improve/change it?

Carl Cerecke wrote:[color=blue]
> Chris Mellon wrote:
>[color=green]
>> I'm not sure why nobody else in this thread said it, but the most
>> common way of implementing state machines I've seen in Python (unless
>> theres only a couple states you can manage with if/elif) is to use a
>> dict to map states to callables.[/color]
>
>
> Ah. Well, my post suggested, as one option, the callables call
> each other directly.[/color]

Doh! No I didn't. And they shouldn't. Otherwise the call stack
gets out of hand. But I did suggest that each callable representing a
state set a global variable, just before it returns, to the callable
representing the next state to be called. Still no map required. Just a
while loop. In any case, the function call/return is wasted cycles.

Cheers,
Carl.

[Peter Hansen]

Re: Python code written in 1998, how to improve/change it?

Carl Cerecke wrote:[color=blue]
> Carl Cerecke wrote:[color=green]
>>Ah. Well, my post suggested, as one option, the callables call
>>each other directly.[/color]
>
> Doh! No I didn't. And they shouldn't. Otherwise the call stack
> gets out of hand. But I did suggest that each callable representing a
> state set a global variable, just before it returns, to the callable
> representing the next state to be called. Still no map required. Just a
> while loop. In any case, the function call/return is wasted cycles.[/color]

I believe the more modern approach to this is to use generators in some
way, yield each other as the next state. This way you avoid all almost
all the function call overhead (the part that takes significant time,
which is setting up the stack frame) and don't have to resort to
bytecode hacks for better performance.

Of course, if you have a state machine with many small states each doing
a tiny bit of processing and you're still concerned over performance,
you probably should be looking into Pysco or Pyrex and avoid making your
code really unreadable.

-Peter

[skip@pobox.com]

Re: Python code written in 1998, how to improve/change it?


Petr> Hello, I am trying to study/understand OOP principles using
Petr> Python. I have found following code http://tinyurl.com/a4zkn about
Petr> FSM (finite state machine) on this list, which looks quite useful
Petr> for my purposes. As this code was posted long time ago (November
Petr> 1998) I would like to ask if the principles used in this code are
Petr> still valid in the "modern" Python and if/how it can be improved
Petr> (revrited) using futures of current version of Python.

A more up-to-date version of my finite state machine class (referenced in
the 1998 post you refer to) is available here:

http://orca.mojam.com/~skip/python/fsm.py

It's still in use, though I haven't written anything new with it in a year
or so.

Skip