Эффективное использование STL и шаблонов (стр. 1 из 3)

Эффективное использование 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 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> ), . . . );

Аналогичным образом поступим со списком переходов для одного события. Отличие будет лишь в том, что каждый список переходов имеет еще один атрибут – событие, для которого описываются переходы. Конструктор STransitionsProxy будет принимать один аргумент: событие, а перегруженный operator<< будет принимать состояния.

STransitionsProxy( letter ) << “identifier” << “unknown” << “identifier” << “unknown”

Вернемся к конструктору автомата. У него тоже есть список переменной длины – строки таблицы описания переходов или STransitionsProxy. Решим эту задачу уже известным способом: создание временного объекта и перегрузка operator<< для SStatesListProxy и STransitionsProxy.

SStatesMachineProxy() << SStatesListProxy << STransitionsProxy

Перегруженный operator<< проверит, что сначала идет список состояний, что список состояний только один, что в списках переходов нет повторяющихся событий и в переходах указаны только состояния, указанные в списке состояний. operator<< также проверит, что количество состояний в списках переходов равно количеству состояний в списке состояний. В результате конструктор SFiniteStateMachine будет выглядеть так: