Загрузка...
Учебная работа. Реферат: Эффективное использование STL и шаблонов
Сергей Сацкий
Введение
При помощи конечных автоматов (дальше просто автомат) можно удачно решать широкий класс задач. Это событие подмечено издавна, потому в литературе по проектированию программного обеспечения нередко приводятся рассуждения на тему внедрения автоматов ([2], [5], [8]). Но в процессе моделирования автомат рассматривается с наиболее высочайшего уровня, нежели это делается в момент его реализации с внедрением определенного языка программирования.
Крайний раз журнальчик C / C++ User’s Journal обращался к дилемме проектирования конечных автоматов (Finite State Machine) в майском выпуске 2000 года ([1]). В этом номере была написана статья Дэвида Лафренье (David Lafreniere), где создатель описывал использованный им подход. С того времени прошло много времени, и в данной статье будет изготовлена попытка применить иной подход к проектированию конечного автомата с учетом современных тенденций в проектировании программного обеспечения.
Для удобства разглядим обычной пример, который будет употребляться дальше. Допустим, что нужно найти, является ли входная последовательность знаков целым числом, допустимым идентификатором, либо недопустимой строчкой. Под допустимыми идентификаторами будем осознавать такие идентификаторы, которые начинаются с буковкы и дальше содержат буковкы и «/», либо числа. автомат, который поможет решить задачку, показан на рисунке 1. На рисунке употребляется нотация UML (Unified Modeling Language).
Набросок 1. автомат, позволяющий узнать, что представляет собой входная строчка.
Необходимо подчеркнуть, что разные источники наделяют схожий автомат разными атрибутами. Фаворитом по их количеству, наверняка, является UML ([2]). тут можно отыскать отложенные действия (deferred events), внутренние переходы (internal transitions), параметризованные триггеры событий (event triggers with parameters), доп условия переходов (guard conditions), входные функции (entry action), выходные функции (exit action), действия, генерируемые по таймеру (time events) и т.д. Но тут мы для простоты изложения опустим доп атрибуты (к неким из их мы вернемся позднее) и сосредоточимся на обычной модели, где есть состояния, действия и переходы меж состояниями.
На данный момент все, что мы имеем – это приятная и комфортная для внесения конфигураций модель. Как сейчас перейти от нее к коду на языке С++? Самый обычной из методов реализации – это набор операторов if в том либо ином виде. к примеру:
switch ( CurrentState )
{
case State1: if ( CurrentEvent == Event1 )
{
. . .
}
if ( CurrentEvent == Event2 )
{
. . .
}
. . .
case State2: . . .
Не очень наглядно, не так ли? А сейчас представим для себя, что мы имеем 10-ки событий и 10-ки состояний. Таковой код просматривать тяжело. В особенности тяжкие препядствия появляются при сопровождении кода, когда к нему нужно возвратиться через несколько месяцев и внести исправления.
Иная вероятная реализация состоит в наборе функций, любая из которых представляет собой состояние. Таковая функция сумеет вернуть указатель на ту функцию, которая соответствует новенькому состоянию автомата. Таковая реализация также не упрощает поддержку кода.
Подойдем к дилемме незначительно с иной стороны. Картина – это отлично, но в начальном виде она никаким образом не быть может перенесена в начальный текст. Означает, даже, если решение будет найдено, то это будет нечто промежуточное меж картинкой и обыденным текстом.
Подход к реализации автомата
Таковым промежным вариантом представления автомата быть может таблица. Этот метод известен издавна, к примеру [5]. Составим таблицу переходов для нашего автомата (таблица 1).
Действия / состояния
Пусто
число
идентификатор
недопустимая строчка
буковка
идентификатор
недопустимая строчка
идентификатор
недопустимая строчка
цифра
Число
число
идентификатор
недопустимая строчка
Таблица 1.
тут в первой строке перечислены вероятные состояния, а в первом столбце – вероятные действия. На пересечениях указаны состояния, в которые должен осуществиться переход.
Представление автомата в виде таблицы еще нагляднее, чем “размазанное” хотелось созидать этот код? Сформулируем требования к нему ([7]):
Описание автомата (читай – таблица) обязано быть сконцентрировано в одном месте. Это даст легкость чтения, осознания и модификации автомата.
Представление автомата обязано быть типобезопасным.
Не обязано быть ограничений на количество состояний и событий.
Действия и состояния хотелось бы представить в виде абстрактных типов, определяемых юзером.
По способности, автомат хотелось бы создать гибким и просто расширяемым.
По способности, хотелось бы инспектировать описание автомата.
По способности, хотелось бы исключить неверное внедрение автомата.
Требования 1 и 7 означают, что все описание автомата отлично бы поместить в конструктор. В конструкторе же нужно инспектировать корректность описания – требование 6.
class SFiniteStateMachine
{
public:
SFiniteStateMachine( <описаниеавтомата> );
. . .
private:
SFiniteStateMachine();
};
Требование 4 значит, что необходимо употреблять шаблон, параметрами которого будут типы действия и состояния.
template <class SState, class SEvent>
class SFiniteStateMachine
{
. . .
};
Требование 2 значит, что не обязано употребляться никаких опасных операций вида reinterpret_cast.
О требовании 5 побеседуем позднее, а на данный момент обсудим требование 3. В общем случае количество вероятных состояний (другими словами количество столбцов в таблице) непонятно. Непонятно также и количество событий (другими словами количество строк в таблице). Выходит, что у конструктора класса, который будет представлять собой автомат, переменное количество аргументов. С первого взора кажется, что эту делему просто решить при помощи функций языка C va_arg(), va_copy(), va_end() и va_start() ([6]). Но, не все так просто. Для этих функций непременно необходимо предугадать признаки окончания списков, а у нас количество частей в строчках и столбцах непонятно. Размерность же задавать не нужно. Не считая того, эти функции работают гарантированно лишь для POD (Plain Old Data), а для случайных типов вероятны проблемы.
Подойдем с иной стороны. Напишем, каким хотелось бы созидать конструктор автомата:
SFiniteStateMachine A(
<Стартовое состояние>,
<Перечень состояний>,
<Перечень переходов для состояний>
);
При таком вызове конструктора методом форматирования текста, набранного моноширинным шрифтом, описанию автомата получится придать вид таблицы. Пофантазируем:
SFiniteStateMachine A(
“empty”,
“empty”, “number”, “identifier”, “unknown”,
letter, “identifier”, “unknown”, “identifier”, “unknown”,
digit, “number”, “number”, “identifier”, “unknown”
);
Со стартовым состоянием все просто: это всего только объект класса, представляющего состояние. Со перечнем состояний и тем наиболее со перечнем переходов дело труднее. Перечислить состояния через запятую не получится. Наиболее того, для SFiniteStateMachine было бы комфортно иметь фиксированное количество аргументов. Оказывается, это может быть. Ведь мы можем сделать временные объекты, любой из которых будет заниматься своим перечнем.
SFiniteStateMachine(
const SState & StartState,
SStatesListProxy( <списоксостояний> ),
STransitionsProxy( <перечень переходов для действия 1> ),
STransitionsProxy( <перечень переходов для действия 2> ),
. . .
);
Разглядим перечень состояний. тут остается та же неувязка – неопределенное количество состояний. Посодействовать в ее решении может перегрузка операторов и конструктор по дефлоту. Перечислить аргументы через запятую все равно не удалось бы, но заместо запятой подошел бы и иной разделитель. Таковым разделителем быть может <<, другими словами обработку перечня состояний можно записать так:
SStatesListProxy() << “empty” << “number” << “identifier” << “unknown”
Перегруженный operator<< для SStatesListProxy проверит, что посреди состояний нет циклических, а не считая того обеспечит типобезопасность для состояний. Переменное количество состояний при таковой записи тоже не неувязка. Конструктор для SFiniteStateMachine сейчас можно записать так:
SFiniteStateMachine( const SState & StartState,
(SStatesListProxy() << “empty” << “number” << “identifier” << “unknown”),
STransitionsProxy( <перечень переходов для действия 1> )
STransitionsProxy( <перечень переходов для действия 2> ),
. . .
);
Аналогичным образом поступим со перечнем переходов для 1-го действия. Отличие будет только в том, что любой перечень переходов имеет еще один атрибут – событие, для которого описываются переходы. Конструктор STransitionsProxy будет принимать один аргумент: событие, а перегруженный operator<< будет принимать состояния.
STransitionsProxy( letter ) << “identifier” << “unknown” << “identifier” << “unknown”
Вернемся к конструктору автомата. У него тоже есть перечень переменной длины – строчки таблицы описания переходов либо STransitionsProxy. Решим эту задачку уже известным методом: создание временного объекта и перегрузка operator<< для SStatesListProxy и STransitionsProxy.
SStatesMachineProxy() << SStatesListProxy << STransitionsProxy
Перегруженный operator<< проверит, что поначалу идет перечень состояний, что перечень состояний лишь один, что в перечнях переходов нет циклических событий и в переходах указаны лишь состояния, обозначенные в перечне состояний. operator<< также проверит, что количество состояний в перечнях переходов равно количеству состояний в перечне состояний. В итоге конструктор SFiniteStateMachine будет смотреться так:
SFiniteStateMachine( const StateType & StartState,
const SFiniteStateMachineProxy & ProxyMachine );
сейчас очередь за реализацией обрисованных выше мыслях. Запишем конструктор автомата для рассматриваемого примера вполне.
SFiniteStateMachine FirstMachine(
“empty”,
(SFiniteStateMachineProxy() <<
(SStatesListProxy() << “empty” << “number” << “identifier” << “unknown”) <<
(STransitionsProxy(letter) << “identifier” << “unknown” << “identifier” << “unknown”) <<
(STransitionsProxy(digit) << “number” << “number” << “identifier” << “unknown”)
)
);
На конструктор SFiniteStateMachine будет возложена задачка проверки исходного состояния. Оно обязано быть в перечне состояний.
Методом форматирования текста уже удалось придать аргументам конструктора вид таблицы. Но это еще не все. При описании автомата были опущены все детали, связанные с шаблонами. На практике это значит, что при конструировании также придется указывать типы, что добавочно “замусорит” текст. Невзирая на препядствия, связанные с препроцессором, он тут поможет. Запись аргументов конструктора станет приблизительно таковой:
FSMBEGIN( “empty” )
FSMSTATES “empty” << “number” << “identifier” << “unknown”
FSMEVENT(letter) “identifier” << “unknown” << “identifier” << “unknown”
FSMEVENT(digit) “number” << “number” << “identifier” << “unknown”
FSMEND
Таковая запись уже применима для ежедневного использования.
Детали реализации
Реализация обязана включать ряд вспомогательных частей, а именно, исключения. автомат будет выдавать их в случае ошибки в описании состояний и переходов. При разработке собственного класса исключений можно пользоваться наследованием от класса обычного исключения. Это даст возможность указать в блоке catch лишь ссылку на базисный обычный класс исключений. Собственный класс исключений можно найти так:
class SStateMachineException : public std::exception
{
private:
const std::string Message;
public:
SStateMachineException( const std::string & Msg ) : Message( Msg ) {}
SStateMachineException( const char * Msg ) : Message( Msg ) {}
virtual ~SStateMachineException() throw() {}
virtual const char * what( void ) const throw() { return Message.c_str(); }
private:
SStateMachineException();
};
В главный программке, использующей класс автомата, можно будет написать так:
. . .
try
{
. . .
создание и внедрение автомата
. . .
}
catch ( std::exception & Exception )
{
// Поймаем и обычное исключение и исключение, сгенерированное автоматом
}
Вернемся к конструкторам. Так как они имеют дело со перечнями переменной длины, то для сохранения частей разумно пользоваться контейнерами, предоставляемыми библиотекой STL ([3]). Для хранения одномерного перечня воспользуемся контейнером Vector, а для таблицы переходов – вектором векторов:
std::Vector< std::vector<StateType> > Transitions;
Методы STL посодействуют отыскивать событие в перечне событий:
std::Vector<EventType>::const_iterator k( std::find( Events.begin(),
Events.end(), EntryEvent ) );
Так как контейнер Vector поддерживает operator [], то для поиска состояния, в которое нужно совершить переход, в таблице переходов можно пользоваться схожей конструкцией:
NewState = Transitions[ EventIndex ] [ StateIndex ];
где надлежащие индексы могут быть вычислены при помощи метода STL distance:
inline int GetStateIndex( const StateType & State ) const
{
return std::distance( States.begin(), std::find( States.begin(), States.end(), State ) );
}
Очевидно, класс автомата должен будет иметь функцию, принимающую и обрабатывающую событие. Существует два варианта. 1-ый – это функция, 2-ой – перегрузка какого-нибудь оператора. Для придания доборной гибкости реализуем оба варианта:
SFiniteStateMachine & AcceptEvent( const EventType & Event )
{
. . .
}
и
inline SFiniteStateMachine & operator << ( const EventType & Event )
{ return AcceptEvent( Event ); }
Перегрузка operator << даст возможность употреблять автомат в таком стиле:
// Принять действия Event1, Event2 и Event3
MyMachine << Event1 << Event2 << Event3;
Остается вопросец: что созодать, если придет событие, для которого у автомата нет описания переходов? Вероятны варианты: просто проигнорировать такое событие, сгенерировать исключение либо создать что-то, определяемое юзером. Воспользуемся мыслью стратегий ([4]) и включим в число аргументов шаблона функтор, который будет определять подходящую стратегию поведения. Таковой подход полностью соответствует требованию 5. При всем этом можно задать стратегию по дефлоту – к примеру, генерировать исключение. сейчас заголовок шаблона смотрится так:
template <class SState, class SEvent, class SUnknownEventStrategy = SThrowStrategy<SEvent> >
class SFiniteStateMachine { . . . };
В числе заготовленных стратегий есть и стратегия игнорирования неведомого действия:
template <class SEvent>
class SIgnoreStrategy
{
public:
inline void operator() ( const SEvent & ) const { return; }
};
Если пригодятся остальные деяния, постоянно можно написать свой функтор по виду и подобию SIgnoreStrategy и передать его шаблону.
Почти все источники, описывающие конечные автоматы, упоминают о способности вызова функций при входе и выходе из состояния. Такую возможность просто предоставить, используя этот же подход стратегий. Функции входа и выхода из состояний комфортно определять для класса, представляющего конкретное состояние. Памятуя о требовании 5, дадим возможность гибкого управления таковой возможностью. Предполагая, что функции класса состояния будут называться OnEnter и OnExit, можно написать несколько готовых функторов: не вызывающий ни одну из функций, вызывающий лишь OnEnter, вызывающий лишь OnExit и вызывающий обе функции.
template <class SState, class SEvent>
class SEmptyFunctor
{
public:
inline void operator() ( SState & From, const SEvent & Event, SState & To ) { return; }
};
template <class SState, class SEvent>
class SOnEnterFunctor
{
public:
inline void operator() ( SState & From, const SEvent & Event, SState & To )
{ To.OnEnter( From, Event ); }
};
template <class SState, class SEvent>
class SOnExitFunctor
{
public:
inline void operator() ( SState & From, const SEvent & Event, SState & To )
{ From.OnExit( Event, To ); }
};
template <class SState, class SEvent>
class SOnMoveFunctor
{
public:
inline void operator() ( SState & From, const SEvent & Event, SState & To )
{ From.OnExit( Event, To ); To.OnEnter( From, Event ); }
};
Стратегию по дефлоту (не вызывать никакую функцию) можно передать в качестве аргумента шаблона. Стратегия вызова функций, быстрее всего, будет изменяться почаще, чем стратегия действий при неведомом событии. Потому ее имеет смысл поместить в перечне аргументов перед стратегией реакции на неведомое событие:
template <class SState, class SEvent,
class SFunctor = SEmptyFunctor<SState,SEvent>,
class SUnknownEventStrategy = SThrowStrategy<SEvent> >
class SFiniteStateMachine { . . . };
Еще один вопросец, связанный с событиями, заключается в том, что событие быть может сгенерировано снутри функции, вызываемой при выходе либо входе в состояние. Для обработки таковых событий нужно подходящим образом спроектировать функцию, принимающую событие. С учетом таковых “внутренних” событий, нужно предугадать очередь, в которую будут помещаться действия. Код, который обрабатывает переходы, должен будет созодать это до того времени, пока очередь не опустеет. В качестве контейнера, пригодного для хранения событий, воспользуемся deque из STL. Так как нам необходимы лишь вставка частей в начало и исключение из конца контейнера, без случайного доступа, контейнер deque подойдет лучше всего.
Осталось совершенно незначительно. Время от времени необходимо привести автомат в начальное состояние. Как и в случае с событиями предусмотрим два варианта: рядовая функция и перегруженный operator <<. Для перегруженного operator << необходимо найти особый манипулятор:
enum SMachineManipulator
{
ResetMachine = 0
};
. . .
inline SFiniteStateMachine & operator << ( SMachineManipulator Manipulator )
{
if ( Manipulator == ResetMachine )
return Reset();
return *this;
}
сейчас можно будет написать так:
// Принять событие Event1 и сбросить автомат в изначальное состояние
MyMachine << Event1 << RestMachine;
Результатом работы автомата является состояние, в которое он перебежал. Для получения текущего состояния напишем функцию и перегрузим оператор вывода в поток класса автомата:
inline StateType GetCurrentState( void ) const { return CurrentState; }
template <class SState,
class SEvent,
class SFunctor,
class SUnknownEventStrategy >
ostream &
operator<< (ostream & Stream,
const SFiniteStateMachine<_SState, _SEvent,
_SFunctor,_SUnknownEventStrategy> & Machine )
{
return Stream << Machine.GetCurrentState();
}
сейчас, если для класса состояния определен оператор вывода в поток, можно написать таковой фрагмент кода:
MyMachine << Event1 << RestMachine;
cout << MyMachine; // Эквивалентно cout << MyMachine.GetCurrentState();
Как уже говорилось, для сокращения времени набора кода и удобочитаемости определены несколько макросов. Они требуют подготовительного определения подстановки для типов событий и состояний. Требование соединено с тем, что внедрение вложенных директив препроцессора нереально. Шаблон же употребляет proxy классы, которым также необходимы сведения о типах. Потому для использования макросов придется создать так:
#define FSMStateType string // Типсостояния
#define FSMEventType int // Типсобытия
. . .
#undef FSMStateType
#undef FSMEventType
Кандидатура есть: вполне указывать все типы.
Осталось поместить шаблон в место имен. Опосля этого им можно воспользоваться.
Пример использования шаблона
Напишем код для решения поставленной сначала статьи задачки.
#include <iostream>
#include <string>
using namespace std;
#include «FiniteStateMachine.h»
using namespace FSM;
// Определимтипдлясобытий
enum Events { letter = 0, digit = 1 };
int main( int argc, char ** argv )
{
#define FSMStateType string
#define FSMEventType Events
SFiniteStateMachine< StateType,
EventType,
SEmptyFunctor<StateType,EventType>,
SThrowStrategy<EventType>
>
MyMachine(
FSMBEGIN( «empty» )
FSMSTATES «empty» << «number» << «identifier» << «unknown»
FSMEVENT(letter) «identifier» << «unknown» << «identifier» << «unknown»
FSMEVENT(digit) «number» << «number» << «identifier» << «unknown»
FSMEND
);
#undef FSMStateType
#undef FSMEventType
cout << «StartState is: » << MyMachine << endl;
MyMachine << digit << digit << letter;
cout << «The ‘unknown’ state is expected. Current state is: » << MyMachine << endl;
// внимание: круглые скобки в последующей строке неотклонимы. Они обеспечат
// верный порядок выполнения операторов
cout << «Reset the machine. Current state is: » << (MyMachine << ResetMachine) << endl;
MyMachine << letter << digit << letter;
cout << «The ‘identifier’ state is expected. Current state is: » << MyMachine << endl;
return 0;
}
В примере преднамеренно опущены такие детали, как обработка исключений и введение функций, вызываемых при входе и выходе из состояния. Чтоб показать возможность определения стратегий юзера, в конструкторе MyMachine указаны все характеристики, включая характеристики по дефлоту.
Требования к клиентским приложениям
Требования малочисленны. Для классов событий и состояний должны быть определены operator==, operator= и конструктор копирования. operator== употребляется для поиска событий и состояний в перечнях методом STL find. operator= употребляется при копировании частей списков. Конструктор копирования употребляется при инициализации списков и остальных частей.
Если клиент пользуется предоставленным функтором для вызова функций входа и выхода, то класс состояния должен реализовывать надлежащие функции: OnExit и OnEnter.
Достоинства и недочеты предложенного решения
Достоинства:
Шаблон строго типизирован. Это значит, что некорректно написанный код не будет принят компилятором, и ошибка не дойдет до времени выполнения программки.
Расширены понятия состояния и действия. сейчас это произвольные классы, написанные юзером.
Не употребляется оператор reinterpret_cast<…>, способный привести к неверным результатам.
Все описание автомата сосредоточено в одном месте. Нет привязки к последовательности описания реакций на действия.
Упругость поведения определяется пользовательскими функторами. Предоставляется набор уже готовых функторов.
Может быть динамическое создание описания конечного автомата. К примеру, можно сделать экземпляры Proxy-классов, прочесть из файла описание автомата, а потом сделать экземпляр SFiniteStateMachine.
Нет операций сотворения и удаления объектов при помощи операторов new и delete.
Нет никаких требований к классам состояний и событий (не считая способности их сопоставления).
Недочеты:
Много операций копирования при разработке автомата. Но этот недочет частично возмещается тем, что обычно автомат создается один раз, а употребляется неоднократно.
нужно писать две директивы препроцессора либо употреблять длиннющий префикс. Но это только неувязка набивки текста.
Лично я готов мириться с сиим маленьким перечнем недочетов ради приобретенных преимуществ.
Вероятные пути усовершенствования шаблона
Внимательный читатель увидит, что можно прирастить упругость и повысить производительность шаблона. В последующем перечне перечислены улучшения, лежащие на поверхности:
Можно отрешиться от промежного класса SFiniteStateMachineProxy. Это дозволит сберечь на копированиях, но занесет потенциальную возможность неверного использования шаблона.
Можно ввести манипуляторы, которые дозволят в очевидном виде при описании переходов указывать такие, которые нужно игнорировать, либо генерировать исключение при их возникновении.
Потоковая сохранность
В шаблоне употребляются контейнеры STL, операции с которыми в многопоточной среде могут привести к дилеммам. Так как при проектировании шаблона ставилась цель создать независящее от платформы решение, то никаких средств синхронизации в шаблоне нет. наличие средств синхронизации, как понятно, зависимо от ситуации быть может как достоинством, так и недочетом. Если они не необходимы, их наличие лишь породит доп затратные расходы. Добавить же средства синхронизации в шаблон опытнейшему разрабу не составит труда.
Перечень литературы
C/C++ User’s Journal, May 2000
Booch G., Rumbaugh J., Jacobson I. The Unified Modeling Language User Guide. Addison-Wesley, 2001
Meyers S. Effective STL. Addison-Wesley, 2001
Alexandrescu A. Modern C++ Design. Addison-Wesley, 2002
Lewis P., Rosenkrantz D., Stearns R. Compiler Design Theory. Addison-Wesley, 1976
Schildt H. С/С++ Programmer’s Reference. Second Edition. Williams, 2000
Meyers S. Effective C++. Second Edition. Addison-Wesley, 1998 and More Effective C++. Addison-Wesley, 1996
Sutter G. Exceptional C++. Addison-Wesley, 2002
]]>