Проектирование конечного автомата на C ++ - PullRequest
7 голосов
/ 24 апреля 2010

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

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

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

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

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

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

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

Ответы [ 7 ]

7 голосов
/ 24 апреля 2010

Обязательно посмотрите библиотеку диаграмм состояний Boost .

3 голосов
/ 24 апреля 2010

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

Сохранение состояния в переменной, скажем, 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% прохождении модульных тестов, когда вы не знаете, правильны ли модульные тесты.

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

1 голос
/ 24 апреля 2010

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

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

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

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

1 голос
/ 24 апреля 2010

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

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

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

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

0 голосов
/ 28 ноября 2013

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

0 голосов
/ 25 апреля 2010

Если вы ищете классическую модель конечного автомата GOF Design Patterns, то посмотрите wikipedia .

Посмотрите на этой странице (на момент написания) пример Java.

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

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

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

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

0 голосов
/ 24 апреля 2010

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...