Проектирование конечного автомата на C++

У меня есть небольшая проблема, связанная с моделированием конечного автомата.

Мне удалось немного заняться инженерией знаний и «обратным проектированием» набора примитивных детерминированных правил, которые определяют состояние, а также переходы между состояниями.

Я хотел бы знать, что касается лучших практик:

  • Как тщательно проверить мои состояния и переходы состояний, чтобы убедиться, что система не может оказаться в неопределенном состоянии.

  • Как обеспечить соблюдение требований перехода между состояниями (например, не должно быть возможности перейти напрямую из stateFoo в StateFooBar, т. е. наполнить каждое состояние «знаниями» о состояниях, в которые оно может перейти.

В идеале я хотел бы использовать чистый дизайн, основанный на шаблонах, с шаблонами везде, где это возможно.

Однако мне нужно с чего-то начать, и я был бы признателен за любые указатели (без каламбура), которые присылаются мне.


person skyeagle    schedule 24.04.2010    source источник
comment
поиск формальной проверки конечного автомата   -  person bobah    schedule 29.11.2013


Ответы (7)



Гоша, это не так сложно, как кажется. Код конечного автомата очень прост и короток.

Сохраните состояние в переменной, скажем, в myState.

Ваша конечная машина будет оператором switch, разветвляющимся по значению переменной myState для выполнения кода для каждого состояния.

Код будет заполнен такими строками:

myState = newState;

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

void DoSafeStateTransition( int newState )
{
// check myState -. newState is not forbidden
// lots of ways to do this
// perhaps nested switch statement

switch( myState ) {

 …

case X:  switch( newState ) 
    case A: case B:  case Z: HorribleError( newState );
    break;

 ...

}

// check that newState is not undetermined

switch( newState ) {

// all the determined states
case A: case B: case C … case Z: myState = newState; break;
default: HorribleError( newState );
}
}
void HorribleError( int newState )
{  printf("Attempt to go from %d to %d - disallowed\n",
       myState, newState );
   exit(1);
}

Я предполагаю, что это просто и достаточно коротко, чтобы проверка работала лучше, чем модульное тестирование - это, безусловно, будет намного быстрее!

На мой взгляд, смысл модульного тестирования в том, чтобы тестовый код был проще тестируемого кода, чтобы его было легче проверить на правильность, а затем использовать для тестирования сложного кода. Часто проще проверить код конечного автомата, чем тестовый код конечного автомата. Нет особого смысла сообщать о 100% прохождении юнит-тестов, если вы плохо представляете, верны ли юнит-тесты.

Скажем иначе: написать конечный автомат легко, а спроектировать правильный — сложно. Модульные тесты сообщат вам только о том, правильно ли вы закодировали дизайн, а не о том, был ли дизайн правильным.

person ravenspoint    schedule 24.04.2010

Тестирование мало связано с паттернами, шаблонами и т. д. Я бы порекомендовал фреймворк для тестирования, такой как CppUnit (часть семейства xUnit), чтобы охватить все ваши тестовые случаи. Количество, конечно, будет зависеть от сложности конечного автомата.

Ваш вопрос об обеспечении переходов между состояниями лежит в основе дизайна вашего класса для конечного автомата. Я бы сказал, что состояние будет иметь набор дочерних состояний, в которые оно может перейти, а также событие, которое вызовет каждое из них. Если у события Foo нет дочернего элемента FooBar, то перейти к нему невозможно.

Я бы погуглил «объектно-ориентированные конечные автоматы», чтобы начать получать некоторые дизайнерские идеи.

Когда я думал о подобных проблемах, я думал, что шаблон проектирования Composite может быть частью этого, потому что State может представлять более сложный FSM. У меня был бы интерфейс State с реализациями SimpleState и CompositeState. Придется начинать заново и смотреть, получится ли все.

person duffymo    schedule 24.04.2010

Время от времени всплывает вопрос об использовании конечных автоматов. Обычно я делаю так, как предложил Рейвенспойнт, и просто делаю оператор switch. Но это работает только в том случае, если состояния не слишком велики. Это похоже на ваш случай. Принимая это во внимание, я думаю, что лучше всего начать с хорошей архитектуры, которая позволит делать некоторые вещи, которые вы хотите сделать. Я принял предложение duffymo и попробовал Google. Эта статья показалась интересной — объектно-ориентированные конечные автоматы . Это может быть излишним, но я думаю, что это даст структуру, которую будет легко протестировать с помощью чего-то вроде CppUnit.

Некоторые другие хорошие ссылки из поиска Google

Структура конечного автомата

Объектно-ориентированные конечные автоматы

person zooropa    schedule 24.04.2010

Звучит как нетронутое приложение для модульного тестирования. Существует множество фреймворков для модульного тестирования. Мне нравится Boost one.

person Ben Collins    schedule 24.04.2010

Если вы ищете классический шаблон конечного автомата GOF Design Patterns, загляните в Википедию.

Взгляните на эту страницу (на момент написания статьи) на пример Java.

У него есть класс StateContext, как видно из примера использования, есть клиенты, которые знают о методе writeName. Реализация такова: this.myState.writeName(this, name); что означает, что он перенаправляет вызов в текущее состояние, передавая себя в качестве первого аргумента.

Теперь посмотрите на interface State, у него есть метод writeName, который соответствует описанному выше использованию. Если вы посмотрите как на StateA, так и на StateB, они обратятся к контексту, устанавливающему новое состояние.

Вот большая часть State Pattern. Единственное, что нужно понимать, это то, что класс StateContext может содержать все данные, связанные с его работой, включая ссылку (в C++ это должен быть указатель) на текущее состояние. Все состояния вместе содержат все поведение, но нет данных, вместо этого откладывая данные (плюс вспомогательные методы) в контексте.

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

person quamrana    schedule 24.04.2010

Если вам нравится шаблон проектирования состояния, я провел эксперимент и переместил этот шаблон в библиотеку: https://code.google.com/p/dpsmlib/

person AlexTheo    schedule 28.11.2013