Ефективне використання 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:. . .
Не дуже наочно, чи не так? А тепер уявімо
собі, що ми маємо десятки подій і десятки станів. Такий код переглядати
важко. Особливо тяжкі проблеми виникають при супроводі коду, коли до нього
треба повернутися через кілька місяців і внести виправлення.
Інша можлива реалізація полягає в наборі функцій,
кожна з яких представляє собою стан. Така функція зможе повернути
вказівник на ту функцію, яка відповідає нового стану автомата. Така
реалізація також не полегшує підтримку коду.
Підійдемо до проблеми трохи з іншого боку. Картинка
- Це добре, але у вихідному вигляді вона ніяким чином не може бути перенесена в
вихідний текст. Отже, навіть, якщо рішення буде знайдено, то це буде щось
проміжне між картинкою і звичайним текстом.
Підхід до реалізації автомата
Таким проміжним варіантом подання автомата
може бути таблиця. Цей спосіб відомий давно, наприклад [5]. Складемо таблицю
переходів для нашого автомата (табл. 1).
Події/стану
Порожньо
число
ідентифікатор
неприпустима рядок
буква
ідентифікатор
неприпустима рядок
ідентифікатор
неприпустима рядок
цифра
Число
число
ідентифікатор
неприпустима рядок
Таблиця 1.
Тут у першому рядку перераховані можливі стану,
а в першому стовпці - можливі події. На перетинах вказані стану, в
які повинен здійснитися перехід.
Представлення автомата у вигляді таблиці набагато
наочніше, ніж "розмазані" уявлення того ж автомата у вигляді умовних
операторів або функцій переходів. Таблицю вже можна спробувати перекласти на
код.
Припустимо, що вдалося перекласти таблицю на код.
Яким би хотілося бачити цей код? Сформулюємо вимоги до нього ([7 ]):
Опис автомата (читай - таблиця) має бути
сконцентровано в одному місці. Це дасть легкість читання, розуміння і
модифікації автомата.
Представлення автомата повинно бути тіпобезопасним.
Не повинно бути обмежень на кількість станів і
подій.
Події та стану хотілося б представити у вигляді
абстрактних типів, що визначаються користувачем.
По можливості, автомат хотілося б зробити гнучким і
легко розширюємося.
По можливості, хотілося б перевіряти опис
автомата.
По можливості, хотілося б виключити неправильне
використання автомата.
Вимоги 1 і 7 означають, що всі характеристика автомата
добре було б помістити в конструктор. У конструкторі ж треба перевіряти правильність
опису - вимога 6.
class SFiniteStateMachine
(
public:
SFiniteStateMachine (
<опис автомата>);
. . .
private:
SFiniteStateMachine ();
);
Вимога 4 означає, що потрібно використовувати шаблон,
параметрами якого будуть типи події і стани.
template
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>),
. . .
);
Аналогічним чином зробимо зі списком переходів для
однієї події. Відмінність лише в тому, що кожен список переходів має ще
один атрибут - подія, для якого описуються переходи. Конструктор
STransitionsProxy буде приймати один аргумент: подія, а перевантажений
operator <<прийматиме стану.
STransitionsProxy (
letter) << "identifier" << "unknown" << "identifier"
<< "unknown"
Повернемося до конструктора автомата. У нього теж є
список змінної довжини - рядки таблиці опису переходів або
STransitionsProxy. Вирішимо це завдання вже відомим способом: створення тимчасового
об'єкта і перевантаження operator <<для SStatesListProxy і STransitionsProxy.
SStatesMachineProxy () <<
SStatesListProxy <
Перевантажений 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 >
Transitions;
Алгоритми STL допоможуть знаходити подія в списку
подій:
std:: vector :: 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));
)
Зрозуміло, клас автомата повинен буде мати функцію,
приймаючу та обробну подія. Існує два варіанти. Перший - це
функція, друге - перевантаження будь-якого оператора. Для надання додаткової
гнучкості реалізуємо обидва варіанти:
SFiniteStateMachine &
AcceptEvent (const EventType &
Event)
(
. . .
)
і
inline
SFiniteStateMachine & operator <<(const EventType & Event)
(return AcceptEvent (Event);)
Перевантаження operator <<дасть можливість
використовувати автомат в такому стилі:
//Прийняти події Event1, Event2 і Event3
MyMachine <
Залишається питання: що робити, якщо прийде подія, для
якого у автомата немає опису переходів? Можливі варіанти: просто
проігнорувати таку подію, згенерувати виключення або зробити щось,
визначається користувачем. Скористаємося ідеєю стратегій ([4]) і включимо в
число аргументів шаблону функторів, який буде визначати потрібну стратегію
поведінки. Такий підхід цілком відповідає вимозі 5. При цьому можна
задати стратегію за замовчуванням - наприклад, генерувати виключення. Тепер
заголовок шаблону виглядає так:
template
>
class SFiniteStateMachine (. . . );
У числі заготовлених стратегій є й стратегія
ігнорування невідомого події:
template
class SIgnoreStrategy
(
public:
inline void operator () (
const SEvent &) const (return;)
);
Якщо знадобляться інші дії, завжди можна
написати власний функторів за образом і подобою SIgnoreStrategy і передати його
шаблоном.
Багато джерел, що описують кінцеві автомати,
згадують про можливості виконання функцій при вході і виході зі стану. Таку
можливість легко надати, використовуючи той же підхід стратегій. Опції
входу і виходу зі станів зручно визначати для класу, що представляє
конкретний стан. Згадуючи про вимогу 5, дамо можливість гнучкого
управління такою можливістю. Припускаючи, що функції класу стану будуть
називатися OnEnter і OnExit, можна написати кілька готових функторів: не
викликає ні одну з функцій, що викликає тільки OnEnter, що викликає т?? тілько
OnExit і викликає обидві функції.
template
class SEmptyFunctor
(
public:
inline void operator () (
SState & From, const SEvent
& Event, SState & To) (return;)
);
template
class SOnEnterFunctor
(
public:
inline void operator () (
SState & From, const SEvent
& Event, SState & To)
(To.OnEnter (From, Event);)
);
template
class SOnExitFunctor
(
public:
inline void operator () (
SState & From, const SEvent
& Event, SState & To)
(From.OnExit (Event, To
);)
);
template
class SOnMoveFunctor
(
public:
inline void operator () (
SState & From, const SEvent
& Event, SState & To)
(From.OnExit (Event, To
); To.OnEnter (From, Event);)
);
Стратегію за замовчуванням (не викликати ніяку функцію)
можна передати в якості аргументу шаблону. Стратегія виконання функцій, швидше за
за все, буде мінятися частіше, ніж стратегія дій при невідомому подію.
Тому її має сенс помістити у списку аргументів перед стратегією реакції
на невідоме подія:
template
class SFunctor =
SEmptyFunctor ,
class
SUnknownEventStrategy = SThrowStrategy >
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 <
Результатом роботи автомата є стан, в
яке він перейшов. Для отримання поточного стану напишемо функцію і
перевантажив оператор виводу в потік класу автомата:
inline StateType GetCurrentState (void) const (return CurrentState;
)
template
class SEvent,
class SFunctor,
class
SUnknownEventStrategy>
ostream &
operator <<(ostream &
Stream,
const
SFiniteStateMachine <_SState, _SEvent,
_SFunctor, _SUnknownEventStrategy> & Machine)
(
return Stream <<
Machine.GetCurrentState ();
)
Тепер, якщо для класу стану визначений оператор
виводу в потік, можна написати такий фрагмент коду:
MyMachine
<
cout
<
Як вже говорилося, для скорочення часу набору коду
і легкості читання визначені кілька макросів. Вони вимагають попереднього
визначення підстановки для типів подій і станів. Вимога пов'язано з
тим, що використання вкладених директив препроцесора неможливо. Шаблон ж
використовує Proxy класи, яким також потрібні відомості про типи. Тому для
використання макросів доведеться зробити так:
# define FSMStateType
string// Тип стану
# define FSMEventType int// Тип події
. . .
# undef FSMStateType
# undef FSMEventType
Альтернатива є: повністю вказувати всі типи.
Залишилось помістити шаблон в простір імен. Після
цього їм можна користуватися.
Приклад використання шаблону
Напишемо код для вирішення поставленого на початку статті
завдання.
# include
# include
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 ,
SThrowStrategy
>
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 <
cout << "The
'unknown' state is expected. Current state is: "<
// Увага: круглі дужки в наступному рядку обов'язкові. Вони
забезпечать
// правильний порядок виконання операторів
cout << "Reset the machine.
Current state is: "<<(MyMachine <
MyMachine <
cout << "The
'identifier' state is expected. Current state is: "<
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
Для підготовки даної роботи були використані
матеріали з сайту http://www.rsdn.ru/
