while/break - The pure-python FSM implementation to Rule Them All.

Discussion in 'Python' started by Carl Cerecke, Jan 25, 2006.

  1. Carl Cerecke

    Carl Cerecke Guest

    Well, it doesn't quite rule them all, but it is fast: About three times
    faster than using one function per state. Faster than using generators.
    Faster than using code objects.

    Some, possibly minor, problems:
    1. The generated code is ugly.
    2. The generated code can be quite large, depending on the shape of the
    FSM (Maximum theoretical size left as an exercise for the reader ;-)
    3. Not as fast as byte code hacks, or using pyrex/psyco. Peter Hansen is
    right. One of those is likely a better solution if you don't need pure
    python.

    The example FSM has input alphabet ['a','b','c']
    and looks like:
    state 0:
    a -> 1
    b -> 2
    c -> 1

    state 1:
    a -> 1
    b -> 3
    c -> 2

    state 2:
    a -> 1
    b -> 2
    c -> 3

    state 3:
    a -> 2
    b -> 3
    c -> 0

    The algorithm basically transforms the FSM into a tree of while loops,
    with breaks letting us go back up the tree, and a variable ("goto"!)
    telling us where the chain of breaks should stop.

    Note:
    1. It would be more efficient with a labelled break (or a labelled
    continue) such as is available in Java.
    2. There are some opportunities for optimisation of the generated code.

    Running this code will print out the generated FSM code for both a
    while/break implementation of the FSM and a function-based
    implementation. It then does some timing measurements.

    Cheers,
    Carl.

    #!/usr/bin/env python

    from StringIO import StringIO

    # number of random inputs fed to the FSM (if we are using that input
    generator)
    r = 1000000
    #r = 10

    # specific string of input chars (if we are using the appropriate input
    generator)
    inp = ['a','a','b','a','a','c','b','c','b','c','c','c','c','c','b']

    # list of states, each state is a dict describing transitions to other
    states.
    states = [
    {'a':1,'b':2,'c':1},
    {'a':1,'b':3,'c':2},
    {'a':1,'b':2,'c':3},
    {'a':2,'b':3,'c':0}]

    ind = " "

    class State(object):
    def __init__(self, num):
    self.num = num
    self.gotos = {}

    def show(self, indent = ""):
    '''
    Representaion of this state, and the states 'underneath' it
    '''
    print indent+`self.num`+':'
    for i,g in self.gotos.items():
    if type(g) == State:
    print indent+"-"+i+"->"
    g.show(indent+" ")
    else:
    print indent+"-"+i+"-> "+`g`

    def code(self, out, lvl):
    '''
    Spit out code for a while/break based state machine
    '''
    print >>out,lvl+"while 1: # state",self.num
    print >>out,lvl+ind+"#print '%d'"%self.num
    print >>out,lvl+ind+"n = next()"
    for i,g in self.gotos.items():
    print >>out,lvl+ind+"if n == '"+i+"':"
    if type(g) == State:
    g.code(out,lvl+ind+ind)
    else:
    if g != self.num:
    print >>out,lvl+ind+ind+"goto = "+`g`
    print >>out,lvl+ind+ind+"break"
    else:
    print >>out,lvl+ind+ind+"continue"
    print >>out,lvl+ind+"if n == None: return",self.num
    print >>out,lvl+ind+"if goto != "+`self.num`+":"
    print >>out,lvl+ind+ind+"break"

    def functions(out,states, lvl = ""):
    '''
    Spit out code for a function-based state machine
    '''
    for num,transitions in enumerate(states):
    print >>out,lvl+"def state_"+`num`+"():"
    print >>out,lvl+ind+"#print '%d'"%num
    print >>out,lvl+ind+"n = next()"
    for i,g in transitions.items():
    print >>out,lvl+ind+"if n == '"+i+"':"
    print >>out,lvl+ind+ind+"return state_"+`g`
    print >>out,lvl+ind+"if n == None: return None"


    start = State(0)

    # set up the hierarchy of State objects
    def dfs(state, history):
    for i,s in states[state.num].items():
    if s in history:
    state.gotos = s
    else:
    child = State(s)
    state.gotos = child
    dfs(child, history+)

    dfs(start,[start.num])

    #print start
    #start.show()
    fun = StringIO()
    print >>fun,"def fsm():"
    start.code(fun," ")
    functions(fun,states)
    def next_gen(): # for when we want specific input
    for i in inp:
    print i
    yield i
    yield None

    import random
    def next_genr(): # for when we want lots of input
    for i in range(r):
    n = random.choice(['a','b','c'])
    #print n
    yield n
    yield None

    next = next_genr().next

    # show the generated code of both FSM implementations
    print fun.getvalue()

    exec fun.getvalue()
    import time

    # we want to ignore the cost of getting input, so we measure that first.
    a = time.clock()
    n = 1
    while n:
    n = next()
    z = time.clock()
    in_time = z-a
    print "input time:",in_time


    print "--"
    next = next_genr().next
    a = time.clock()
    f = fsm()
    z = time.clock()
    print "while/break:",z-a-in_time

    next = next_genr().next
    a = time.clock()
    state = state_0
    while state:
    state = state()
    z = time.clock()
    print "functions:",z-a-in_time
     
    Carl Cerecke, Jan 25, 2006
    #1
    1. Advertising

  2. Carl Cerecke

    Paul Rubin Guest

    Carl Cerecke <> writes:
    > 3. Not as fast as byte code hacks, or using pyrex/psyco. Peter Hansen
    > is right. One of those is likely a better solution if you don't need
    > pure python.


    If you don't need pure python than your approach still beats
    everything else. Just generate C code (or assembly code) instead of
    Python.
     
    Paul Rubin, Jan 25, 2006
    #2
    1. Advertising

  3. Carl Cerecke

    Carl Cerecke Guest

    Re: while/break - The pure-python FSM implementation to Rule ThemAll.

    Paul Rubin wrote:
    > Carl Cerecke <> writes:
    >
    >>3. Not as fast as byte code hacks, or using pyrex/psyco. Peter Hansen
    >>is right. One of those is likely a better solution if you don't need
    >>pure python.

    >
    >
    > If you don't need pure python than your approach still beats
    > everything else. Just generate C code (or assembly code) instead of
    > Python.


    If you are generating C code, then you can, instead, use the much
    maligned goto to jump directly between states. All this
    while/break/continue hackery is just to emulate the humble goto.

    Using gotos is probably about as fast as you can get.

    Cheers,
    Carl.
     
    Carl Cerecke, Jan 25, 2006
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Dave Harris

    Tkinter - One Canvas to Rule Them All?

    Dave Harris, May 25, 2004, in forum: Python
    Replies:
    1
    Views:
    296
    Peter Otten
    May 25, 2004
  2. Replies:
    0
    Views:
    1,405
  3. Thomas Kowalski

    Hiding rule and pure virtuals

    Thomas Kowalski, Aug 24, 2006, in forum: C++
    Replies:
    3
    Views:
    380
    Default User
    Aug 24, 2006
  4. Replies:
    10
    Views:
    1,022
    Joseph Kesselman
    Mar 20, 2008
  5. Rainer Weikusat

    One 704 to rule them all

    Rainer Weikusat, Jul 26, 2013, in forum: Perl Misc
    Replies:
    0
    Views:
    196
    Rainer Weikusat
    Jul 26, 2013
Loading...

Share This Page