Дизайн конечного автомата Python

Question

Относительно этого вопроса о переполнении стека (проектирование машины состояния C) , не могли бы вы, ребята из Stack Overflow, поделились со мной своими методами проектирования машины состояния Python (и сообществом)?

На данный момент я собираюсь на двигатель, основанный на следующем:

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

Но я уверен, что есть множество способов достичь этого, используя динамический характер Python (например, динамическую диспетчеризацию).

Я использую методы проектирования для "двигателя", который получает "события" и "отправляет" против тех, которые основаны на "состоянии" машины.

Answer 1

Я не совсем понял вопрос. Шаблон State Design довольно прост. См. Книгу Design Patterns .

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()

Это довольно распространенный шаблон, используемый в Java, C ++, Python (и я уверен, что и в других языках).

Если ваши правила перехода состояний оказываются тривиальными, есть некоторые оптимизации, чтобы перенести само правило перехода в суперкласс.

Обратите внимание, что нам нужны прямые ссылки, поэтому мы ссылаемся на классы по имени и используем eval для перевода имени класса в реальный класс. Альтернативой является создание переменных экземпляра правил перехода вместо переменных класса, а затем создание экземпляров после определения всех классов.

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" }

В некоторых случаях ваше событие не так просто, как проверка объектов на равенство, поэтому более общим правилом перехода является использование правильного списка пар функция-объект.

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") ]

Поскольку правила оцениваются последовательно, это позволяет использовать правило «по умолчанию».

Answer 2

В апрельском выпуске журнала Python за 2009 год я написал статью о встраивании State DSL в Python с использованием pyparsing и imputil. Этот код позволит вам написать модуль 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)

и DSL-компилятор создаст все необходимые классы TrafficLight, Red, Yellow и Green и соответствующие методы перехода между состояниями Код может вызывать эти классы, используя что-то вроде этого:

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()

(К сожалению, imputil был удален в Python 3.)

Answer 3

Существует этот шаблон проектирования для использования декораторов для реализации конечных автоматов.Из описания на странице:

Декораторы используются, чтобы указать, какие методы являются обработчиками событий для класса.это довольно долго, поэтому я не буду вставлять это здесь).

Answer 4

Мне также не понравились текущие параметры для state_machines, поэтому я написал библиотеку state_machine .

Вы можете установить его по pip install state_machine и использовать его так:

@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

Answer 5

Я думаю, что ответ С. Лотта - гораздо лучший способ реализовать конечный автомат, но если вы все еще хотите продолжить свой подход, лучше использовать (state,event) в качестве ключа для dict. Изменение вашего кода:

class HandlerFsm(object):

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

Answer 6

Я бы определенно не рекомендовал реализовывать такой хорошо известный шаблон самостоятельно. Просто перейдите к реализации с открытым исходным кодом, например transitions , и оберните другой класс вокруг него, если вам нужны пользовательские функции. В этом посте я объясняю, почему я предпочитаю именно эту реализацию и ее возможности.

Answer 7

Я думаю, что инструмент PySCXML тоже нуждается в более внимательном рассмотрении.

В этом проекте используется определение W3C: XML диаграммы состояния (SCXML) : нотация конечного автомата для абстракции управления

SCXML предоставляет общую среду исполнения на основе конечного автомата на основе таблиц состояний CCXML и Harel

В настоящее время SCXML является рабочим проектом; но вероятность того, что он скоро получит рекомендацию W3C (это 9-й проект), весьма высока.

Еще один интересный момент, на который следует обратить внимание, - это проект Apache Commons, направленный на создание и поддержку механизма Java SCXML, способного выполнять конечный автомат, определенный с помощью документа SCXML, при абстрагировании интерфейсов среды ...

А для некоторых других инструментов поддержка этой технологии появится в будущем, когда SCXML выйдет из черновика ...

Answer 8

Следующий код - действительно простое решение. Единственная интересная часть:

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

Вся логика для каждого состояния содержится в отдельном классе. «Состояние» изменяется путем замены « __ class __ » работающего экземпляра.

#!/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

Результат:

 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 9

Вероятно, это зависит от того, насколько сложен ваш конечный автомат. Для простых конечных автоматов диктовку диктов (ключей событий для ключей состояния для DFA или ключей событий для списков / наборов / кортежей ключей состояния для NFA), вероятно, будет проще всего написать и понять.

Для более сложных конечных автоматов я слышал хорошие отзывы о SMC , который может скомпилировать декларативные описания конечных автоматов для кода на множестве языков, включая Python.

Answer 10

Я бы не стал искать конечный автомат для обработки XML. Я думаю, что обычный способ сделать это - использовать стек:

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)

Для каждого типа элемента вам нужен класс, который поддерживает методы addCharacters, addElement и close.

РЕДАКТИРОВАТЬ: Чтобы уточнить, да, я имею в виду утверждать, что конечные автоматы, как правило, неправильный ответ, что как метод программирования общего назначения они мусор, и вы должны держаться подальше.

Есть несколько действительно хорошо понятных, четко очерченных проблем, для которых автоматы являются хорошим решением. lex, например, это хороший материал.

Тем не менее, ФСМ обычно не справляются с изменениями. Предположим, когда-нибудь вы захотите добавить немного состояния, возможно, «мы уже видели элемент X?» флаг. В приведенном выше коде вы добавляете логический атрибут к соответствующему классу элементов, и все готово. В конечном автомате вы удваиваете количество состояний и переходов.

Проблемы, для которых сначала требуется конечное состояние, очень часто эволюционируют, требуя еще большего состояния, например, возможно, число , и в этот момент ваша схема FSM является здравой, или, что еще хуже, вы превращаете ее в какой-то вид обобщенный конечный автомат, и в этот момент вы действительно в беде. Чем дальше вы продвигаетесь, тем больше ваши правила начинают действовать как код, но код на медленном интерпретируемом вами языке, который вы изобрели, которого никто не знает, для которого нет отладчика и инструментов.