Differences between revisions 10 and 12 (spanning 2 versions)
Revision 10 as of 2010-04-24 22:21:05
Size: 4127
Editor: VinaySajip
Comment:
Revision 12 as of 2010-04-24 23:57:42
Size: 2175
Comment: Clean up - point at my implementation, add structural markup instead of just using bold text as headings
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
This is a summary of FSM implementations in Python right now. Licensing remains unclear. <<TableOfContents>>

== Introduction ==

This is a summary of FSM implementations in Python right now. Licensing
remains unclear.
Line 8: Line 13:
<<TableOfContents>> == Finite State Machine Editor ==
Line 10: Line 15:
'''[[http://fsme.sourceforge.net/|Finite State Machine Editor]]''' [[http://fsme.sourceforge.net/|FSME]] is a tool where you can draw FSM
diagrams, and then compile to a Python module (or C++ code.) It also makes
an XML description of the FSM.
Line 12: Line 19:
This is a tool where you can draw FSM diagrams, and then compile to a Python module (or C++ code.) It also makes an XML description of the FSM. Requires QT for the editor. (Not the compiler, though, which probably reads
XML.)
Line 14: Line 22:
Requires QT for the editor. (Not the compiler, though, which probably reads XML.)

* [[http://fsme.sourceforge.net/doc/tutorial.html|tutorial]]
* [[http://fsme.sourceforge.net/phpwiki/|project wiki]]
 * [[http://fsme.sourceforge.net/doc/tutorial.html|tutorial]]
 * [[http://fsme.sourceforge.net/phpwiki/|project wiki]]
Line 20: Line 26:
'''[[http://osteele.com/software/python/fsa/|FSA - Finite State Automation in Python]]''' == FSA - Finite State Automation in Python ==
Line 22: Line 28:
This seems to be all about '''making''' FSMs, but I don't see a whole lot on how to ''use'' them! [[http://osteele.com/software/python/fsa/|FSA]] seems to be all about
cre
ating finite state machines, but I don't see a whole lot on how to use
them.
Line 24: Line 32:
== Noah Spurrier's FSM ==
Line 25: Line 34:
'''[[http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/146262|Noah Spurrier's FSM]]''' http://www.noah.org/python/FSM/
Line 27: Line 36:
This is one found on ActiveState; It's purely Python code. You init an FSM, register transitions, and then throw inputs at it. States and inputs must be hashable.

You can also [[http://www.noah.org/python/FSM/|find it on his website.]]
Noah's implementation is pure Python code. You init an FSM, register
transitions, and then throw inputs at it. States and inputs must be
hashable.
Line 33: Line 42:
'''[[http://www.research.att.com/projects/mohri/fsm/doc4/fsmpy.html|fsmpy module]]''' == fsmpy ==
Line 35: Line 44:
This seems to be a Python wrapper around [[http://www.research.att.com/projects/mohri/fsm/|AT&T's FSM library.]] It's all oriented around "weighted" finite state machines, so I'm not so sure how suitable it is if you just want to use unweighted FSM. [[http://www.research.att.com/projects/mohri/fsm/doc4/fsmpy.html|fsmpy module]]
Line 37: Line 46:
This seems to be a Python wrapper around
[[http://www.research.att.com/projects/mohri/fsm/|AT&T's FSM library.]] It's
all oriented around "weighted" finite state machines, so I'm not so sure how
suitable it is if you just want to use unweighted FSM.
Line 38: Line 51:
'''[[http://wiki.python.org/moin/PythonDecoratorLibrary/|Decorator based FSM]]''' == Decorator-based FSM ==
Line 40: Line 53:
A decorator based FSM can be found in the Decorator Library on this site. The module simplifies implementaion of FSM's based on UML 2.0 state diagrams. The FSM is implemented as a class, with methods of the class associated with transitions or with states. The design is not the best for constructing FSMs to parse text being somewhat slower than alternatives. A [[http://wiki.python.org/moin/PythonDecoratorLibrary/|decorator-based
FSM]] is in the Decorator Library on this site. The module simplifies
implementat
ion of FSM's based on UML 2.0 state diagrams. The FSM is
implemented as a class, with methods of the class associated with
transitions or with states.
The design is not the best for constructing
FSMs to parse text being somewhat slower than alternatives.
Line 42: Line 60:
== Skip Montanaro's FSM ==
Line 43: Line 62:
'''SkipMontanaro's FSM'''

[[http://www.python.org/search/hypermail/python-recent/0667.html|From an e-mail.]]
[[http://www.smontanaro.net/python/fsm.py|fsm.py.]]
Line 48: Line 65:

I've re-interpreted the code, adding formatting lost in e-mail, and PythonStyle-itizing it a bit.

{{{
#!python
"""Finite state machine, featuring transition actions."""

FSMError = 'Invalid input to finite state machine'

class FSM:

    """Finite state machine, featuring transition actions.

    The class stores a dictionary of (state, input) keys,
    and (state, action) values.

    When a (state, input) search is performed:
    * an exact match is checked first,
    * (state, None) is checked next.

    The action is of the following form:
    * function(current_state, input)
    """
    
    def __init__(self):
        self.states = {}
        self.state = None
        self.dbg = None

    def add(self, state, input, newstate, action):
        """Add a transition to the FSM."""
        self.states[(state, input)] = (newstate, action)

    def execute(self, input):
        """Perform a transition and execute action."""
        si = (self.state, input)
        sn = (self.state, None)
        # exact state match?
        if si in self.states:
            newstate, action = self.states[si]
        # no, how about a None (catch-all) match?
        elif sn in self.states:
            newstate, action = self.states[sn]
        if self.dbg != None:
            self.dbg.write('State: %s / Input: %s /'
                           'Next State: %s / Action: %s\n' %
                           (self.state, input, newstate, action))
        action(self.state, input)
        self.state = newstate

    def start(self, state):
        """Define the start state.

        Actually, this just resets the current state.
        """
        self.state = state

    def debug(self, out):
        """Assign a writable file to log transitions."""
        self.dbg = out
}}}

Introduction

This is a summary of FSM implementations in Python right now. Licensing remains unclear.

For general information about finite state machines, see:

Finite State Machine Editor

FSME is a tool where you can draw FSM diagrams, and then compile to a Python module (or C++ code.) It also makes an XML description of the FSM.

Requires QT for the editor. (Not the compiler, though, which probably reads XML.)

FSA - Finite State Automation in Python

FSA seems to be all about creating finite state machines, but I don't see a whole lot on how to use them.

Noah Spurrier's FSM

http://www.noah.org/python/FSM/

Noah's implementation is pure Python code. You init an FSM, register transitions, and then throw inputs at it. States and inputs must be hashable.

It's fairly similar to Skip's implementation (below).

fsmpy

fsmpy module

This seems to be a Python wrapper around AT&T's FSM library. It's all oriented around "weighted" finite state machines, so I'm not so sure how suitable it is if you just want to use unweighted FSM.

Decorator-based FSM

A [[http://wiki.python.org/moin/PythonDecoratorLibrary/|decorator-based FSM]] is in the Decorator Library on this site. The module simplifies implementation of FSM's based on UML 2.0 state diagrams. The FSM is implemented as a class, with methods of the class associated with transitions or with states. The design is not the best for constructing FSMs to parse text being somewhat slower than alternatives.

Skip Montanaro's FSM

fsm.py.

Features transition actions.

FiniteStateMachine (last edited 2014-09-06 09:12:52 by IoannisFilippidis)

Unable to edit the page? See the FrontPage for instructions.