Diseño de la máquina de estado de Python

state-machines fsm

Question

En relación con esta pregunta sobre el desbordamiento de pila (diseño de la máquina en el estado C) , ¿podrían ustedes las personas con desbordamiento de pila compartir sus técnicas de diseño de la máquina en el estado de Python conmigo (y con la comunidad)?

En este momento, voy por un motor basado en lo siguiente:

class TrackInfoHandler(object):
    def __init__(self):
        self._state="begin"
        self._acc=""

    ## ================================== Event callbacks

    def startElement(self, name, attrs):
        self._dispatch(("startElement", name, attrs))

    def characters(self, ch):
        self._acc+=ch

    def endElement(self, name):
        self._dispatch(("endElement", self._acc))
        self._acc=""

    ## ===================================
    def _missingState(self, _event):
        raise HandlerException("missing state(%s)" % self._state)

    def _dispatch(self, event):
        methodName="st_"+self._state
        getattr(self, methodName, self._missingState)(event)

    ## =================================== State related callbacks

Pero estoy seguro de que hay muchas formas de hacerlo mientras se aprovecha la naturaleza dinámica de Python (por ejemplo, el envío dinámico).

Estoy buscando técnicas de diseño para el "motor" que recibe los "eventos" y los "despachos" contra aquellos basados ​​en el "estado" de la máquina.

Answer 1

Creo que la herramienta PySCXML necesita una mirada más cercana.

Este proyecto utiliza la definición de W3C: State Chart XML (SCXML) : Notación de máquina de estado para abstracción de control

SCXML proporciona un entorno de ejecución basado en máquina de estado genérico basado en CCXML y Harel State Tables

Actualmente, SCXML es un borrador de trabajo; pero es muy probable que reciba una recomendación del W3C pronto (es el noveno borrador).

Otro punto interesante a destacar es que hay un proyecto de Apache Commons destinado a crear y mantener un motor Java SCXML capaz de ejecutar una máquina de estados definida usando un documento SCXML, mientras se abstraen las interfaces del entorno ...

Y para algunas otras herramientas, el soporte de esta tecnología surgirá en el futuro cuando SCXML deje su estado de borrador ...

Answer 2

Creo que la respuesta de S. Lott es una forma mucho mejor de implementar una máquina de estados, pero si aún desea continuar con su enfoque, es mejor usar (state,event) como clave para su dict . Modificando su código:

class HandlerFsm(object):

  _fsm = {
    ("state_a","event"): "next_state",
    #...
  }

Answer 3

Definitivamente no recomendaría implementar un patrón tan conocido usted mismo. Simplemente vaya a una implementación de código abierto como transitions y envuelva otra clase a su alrededor si necesita características personalizadas. En este post explico por qué prefiero esta implementación particular y sus características.

Answer 4

El siguiente código es una solución realmente simple. La única parte interesante es:

   def next_state(self,cls):
      self.__class__ = cls

Toda la lógica para cada estado está contenida en una clase separada. El ''estado'' se cambia al reemplazar el '' __class__ '' de la instancia en ejecución.

#!/usr/bin/env python

class State(object):
   call = 0 # shared state variable
   def next_state(self,cls):
      print ''-> %s'' % (cls.__name__,),
      self.__class__ = cls

   def show_state(self,i):
      print ''%2d:%2d:%s'' % (self.call,i,self.__class__.__name__),

class State1(State):
   __call = 0  # state variable
   def __call__(self,ok):
      self.show_state(self.__call)
      self.call += 1
      self.__call += 1
      # transition
      if ok: self.next_state(State2)
      print '''' # force new line

class State2(State):
   __call = 0
   def __call__(self,ok):
      self.show_state(self.__call)
      self.call += 1
      self.__call += 1
      # transition
      if ok: self.next_state(State3)
      else: self.next_state(State1)
      print '''' # force new line

class State3(State):
   __call = 0
   def __call__(self,ok):
      self.show_state(self.__call)
      self.call += 1
      self.__call += 1
      # transition
      if not ok: self.next_state(State2)
      print '''' # force new line

if __name__ == ''__main__'':
   sm = State1()
   for v in [1,1,1,0,0,0,1,1,0,1,1,0,0,1,0,0,1,0,0]:
      sm(v)
   print ''---------''
   print vars(sm

Resultado:

 0: 0:State1 -> State2 
 1: 0:State2 -> State3 
 2: 0:State3 
 3: 1:State3 -> State2 
 4: 1:State2 -> State1 
 5: 1:State1 
 6: 2:State1 -> State2 
 7: 2:State2 -> State3 
 8: 2:State3 -> State2 
 9: 3:State2 -> State3 
10: 3:State3 
11: 4:State3 -> State2 
12: 4:State2 -> State1 
13: 3:State1 -> State2 
14: 5:State2 -> State1 
15: 4:State1 
16: 5:State1 -> State2 
17: 6:State2 -> State1 
18: 6:State1 
---------
{''_State1__call'': 7, ''call'': 19, ''_State3__call'': 5, ''_State2__call'': 7}

Answer 5

En la edición de abril de 2009 de Python Magazine, escribí un artículo sobre cómo incrustar un DSL de estado en Python, usando pyparsing e imputil. Este código le permitiría escribir el módulo trafficLight.pystate:

# trafficLight.pystate

# define state machine
statemachine TrafficLight:
    Red -> Green
    Green -> Yellow
    Yellow -> Red

# define some class level constants
Red.carsCanGo = False
Yellow.carsCanGo = True
Green.carsCanGo = True

Red.delay = wait(20)
Yellow.delay = wait(3)
Green.delay = wait(15)

y el compilador DSL crearía todas las clases necesarias de TrafficLight, Red, Yellow y Green, y los métodos de transición de estado adecuados. El código podría llamar a estas clases usando algo como esto:

import statemachine
import trafficLight

tl = trafficLight.Red()
for i in range(6):
    print tl, "GO" if tl.carsCanGo else "STOP"
    tl.delay()
    tl = tl.next_state()

(Desafortunadamente, el imputil se ha caído en Python 3).

Answer 6

Hay un patrón de diseño para usar decoradores para implementar máquinas de estado. De la descripción en la página:

Los decoradores se utilizan para especificar qué métodos son los controladores de eventos para la clase.

También hay un código de ejemplo en la página (es bastante largo, así que no lo pegaré aquí).

Answer 7

No pensaría buscar una máquina de estados finitos para manejar XML. La forma habitual de hacer esto, creo, es usar una pila:

class TrackInfoHandler(object):
    def __init__(self):
        self._stack=[]

    ## ================================== Event callbacks

    def startElement(self, name, attrs):
        cls = self.elementClasses[name]
        self._stack.append(cls(**attrs))

    def characters(self, ch):
        self._stack[-1].addCharacters(ch)

    def endElement(self, name):
        e = self._stack.pop()
        e.close()
        if self._stack:
            self._stack[-1].addElement(e)

Para cada tipo de elemento, solo necesita una clase que admita los addCharacters , addElement y close .

EDITAR: Para aclarar, sí quiero decir que las máquinas de estados finitos suelen ser la respuesta equivocada, que como una técnica de programación de propósito general son basura y usted debe mantenerse alejado.

Hay algunos problemas realmente bien entendidos y bien delineados para los cuales las FSM son una buena solución. lex , por ejemplo, es algo bueno.

Dicho esto, los FSM normalmente no se enfrentan bien al cambio. Supongamos que algún día usted quiera agregar un poco de estado, tal vez un "¿ya hemos visto el elemento X?" bandera. En el código anterior, agrega un atributo booleano a la clase de elemento adecuada y listo. En una máquina de estados finitos, duplicas el número de estados y transiciones.

Los problemas que requieren un estado finito al principio a menudo evolucionan para requerir incluso más estado, como tal vez un número , en cuyo punto el esquema de FSM está tostado o, peor aún, evoluciona hacia algún tipo de máquina de estado generalizada, y en ese punto estamos realmente en problemas A medida que avanzas, más tus reglas comienzan a actuar como código, pero codifica en un lenguaje de interpretación lenta que inventaste para que nadie más lo sepa, para lo cual no hay depurador ni herramientas.

Answer 8

Otros proyectos relacionados:

• http://fsme.sourceforge.net/

• https://code.google.com/p/visio2python/

Puedes pintar la máquina de estado y luego usarla en tu código.

Answer 9

Probablemente depende de cuán compleja sea su máquina de estados. Para las máquinas de estado simples, un dictado de dictados (de claves de evento a claves de estado para DFA, o claves de evento a listas / conjuntos / tuplas de claves de estado para NFA) probablemente sea lo más simple de escribir y entender.

Para las máquinas de estados más complejas, he escuchado cosas buenas sobre SMC , que puede compilar descripciones de máquinas de estados declarativas para codificar en una amplia variedad de idiomas, incluido Python.

Answer 10

Realmente no entiendo la pregunta. El patrón de diseño del estado es bastante claro. Ver el libro de Patrones de Diseño .

class SuperState( object ):
    def someStatefulMethod( self ):
        raise NotImplementedError()
    def transitionRule( self, input ):
        raise NotImplementedError()

class SomeState( SuperState ):
    def someStatefulMethod( self ):
        actually do something()
    def transitionRule( self, input ):
        return NextState()

Eso es bastante común, usado en Java, C ++, Python (y estoy seguro de que también en otros idiomas).

Si las reglas de transición de su estado resultan ser triviales, hay algunas optimizaciones para empujar la regla de transición a la superclase.

Tenga en cuenta que debemos tener referencias hacia adelante, por lo que nos referimos a las clases por su nombre y usamos eval para traducir un nombre de clase a una clase real. La alternativa es hacer que las variables de instancia de las reglas de transición en lugar de las variables de clase y luego crear las instancias después de que todas las clases estén definidas.

class State( object ):
    def transitionRule( self, input ):
        return eval(self.map[input])()

class S1( State ): 
    map = { "input": "S2", "other": "S3" }
    pass # Overrides to state-specific methods

class S2( State ):
    map = { "foo": "S1", "bar": "S2" }

class S3( State ):
    map = { "quux": "S1" }

En algunos casos, su evento no es tan simple como probar la igualdad de los objetos, por lo que una regla de transición más general es usar una lista adecuada de pares función-objeto.

class State( object ):
    def transitionRule( self, input ):
        next_states = [ s for f,s in self.map if f(input)  ]
        assert len(next_states) >= 1, "faulty transition rule"
        return eval(next_states[0])()

class S1( State ):
    map = [ (lambda x: x == "input", "S2"), (lambda x: x == "other", "S3" ) ]

class S2( State ):
    map = [ (lambda x: "bar" <= x <= "foo", "S3"), (lambda x: True, "S1") ]

Dado que las reglas se evalúan secuencialmente, esto permite una regla "predeterminada".

Answer 11

Tampoco estaba contento con las opciones actuales para state_machines, así que escribí la biblioteca state_machine .

Puede instalarlo por pip install state_machine y usarlo así:

@acts_as_state_machine
class Person():
    name = ''Billy''

    sleeping = State(initial=True)
    running = State()
    cleaning = State()

    run = Event(from_states=sleeping, to_state=running)
    cleanup = Event(from_states=running, to_state=cleaning)
    sleep = Event(from_states=(running, cleaning), to_state=sleeping)

    @before(''sleep'')
    def do_one_thing(self):
        print "{} is sleepy".format(self.name)

    @before(''sleep'')
    def do_another_thing(self):
        print "{} is REALLY sleepy".format(self.name)

    @after(''sleep'')
    def snore(self):
        print "Zzzzzzzzzzzz"

    @after(''sleep'')
    def big_snore(self):
        print "Zzzzzzzzzzzzzzzzzzzzzz"

person = Person()
print person.current_state == person.sleeping       # True
print person.is_sleeping                            # True
print person.is_running                             # False
person.run()
print person.is_running                             # True
person.sleep()

# Billy is sleepy
# Billy is REALLY sleepy
# Zzzzzzzzzzzz
# Zzzzzzzzzzzzzzzzzzzzzz

print person.is_sleeping                            # True