4054
Comment: Add link to Decorator based FSM
|
3180
Added fysom
|
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. | <<TableOfContents>> == Introduction == This is a summary of FSM implementations in Python right now. Licensing remains unclear. |
Line 5: | Line 10: |
* [wiki:WikiPedia/Finite_state_machine Wikipedia:Finite_state_machine] -- B) ''excellent!'' B) * [wiki:Wiki/FiniteStateMachine Wiki:FiniteStateMachine] |
* [[WikiPedia:Finite_state_machine|Wikipedia:Finite_state_machine]] -- B) ''excellent!'' B) * [[Wiki:FiniteStateMachine|Wiki:FiniteStateMachine]] |
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 creating 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. | 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 29: | Line 40: |
You can also [http://www.noah.org/python/FSM/ find it on his website.] | It's fairly similar to Skip's implementation (below). |
Line 31: | Line 42: |
== fsmpy == | |
Line 32: | Line 44: |
'''[http://www.research.att.com/projects/mohri/fsm/doc4/fsmpy.html fsmpy module]''' | [[http://www.research.att.com/projects/mohri/fsm/doc4/fsmpy.html|fsmpy module]] |
Line 34: | 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. | 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 36: | Line 51: |
== Decorator-based FSM == | |
Line 37: | Line 53: |
'''[http://wiki.python.org/moin/PythonDecoratorLibrary/ Decorator based FSM]''' | An [[http://wiki.python.org/moin/State Machine via Decorators|example using decorators]] 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. |
Line 39: | Line 59: |
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. | == Skip Montanaro's FSM == |
Line 41: | Line 61: |
'''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-fsm FSM module with PyGraphViz support == |
Line 50: | Line 67: |
{{{ #!python """Finite state machine, featuring transition actions.""" |
An concise yet comprehensive implementation based on Wikipedia spec of Finite State Machines. The module can be used to build and further describe finite state automata with DOT graphs. It implements acceptors and transducers (Moore and Mealy machines) and provides an straight-forward way to inject and execute state change actions for entry, exit, input and transition. |
Line 54: | Line 69: |
FSMError = 'Invalid input to finite state machine' | Licensed under the new BSD license. |
Line 56: | Line 71: |
class FSM: | [[http://code.google.com/p/python-fsm/]] |
Line 58: | Line 73: |
"""Finite state machine, featuring transition actions. | == fysom == |
Line 60: | Line 75: |
The class stores a dictionary of (state, input) keys, and (state, action) values. |
A port of Jake Gordon's [[https://github.com/jakesgordon/javascript-state-machine|javascript-state-machine]]. The module lets the user define callbacks for before/after events as well as callbacks on entering/leaving states. Events are exposed as object methods which when called, causes the appropriate state transition. The module also provides asynchronous callback functionality which allows delaying a state transition. |
Line 63: | Line 77: |
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 self.states.has_key(si): newstate, action = self.states[si] # no, how about a None (catch-all) match? elif self.states.has_key(sn): 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)) apply(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 }}} |
[[https://github.com/oxplot/fysom]] |
Contents
Introduction
This is a summary of FSM implementations in Python right now. Licensing remains unclear.
For general information about finite state machines, see:
Wikipedia:Finite_state_machine -- excellent!
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
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
An example using decorators 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
Features transition actions.
python-fsm FSM module with PyGraphViz support
An concise yet comprehensive implementation based on Wikipedia spec of Finite State Machines. The module can be used to build and further describe finite state automata with DOT graphs. It implements acceptors and transducers (Moore and Mealy machines) and provides an straight-forward way to inject and execute state change actions for entry, exit, input and transition.
Licensed under the new BSD license.
http://code.google.com/p/python-fsm/
fysom
A port of Jake Gordon's javascript-state-machine. The module lets the user define callbacks for before/after events as well as callbacks on entering/leaving states. Events are exposed as object methods which when called, causes the appropriate state transition. The module also provides asynchronous callback functionality which allows delaying a state transition.