Автома́тное программи́рование — парадигма программирования, при использовании которой программа или её фрагмент осмысливается как модель какого-либо формального автомата. Известна также и другая «парадигма автоматного программирования, состоящая в представлении сущностей со сложным поведением в виде автоматизированных объектов управления, каждый из которых представляет собой объект управления и автомат». При этом о программе, как в автоматическом управлении, предлагается думать, как о системе автоматизированных объектов управления.
В зависимости от конкретной задачи в автоматном программировании могут использоваться как конечные автоматы, так и автоматы с более сложным строением.
Определяющими для автоматного программирования являются следующие особенности: временной период выполнения программы разбивается на шаги автомата, каждый из которых представляет собой выполнение определённой (одной и той же для каждого шага) секции кода с единственной точкой входа; такая секция может быть оформлена, например, в виде отдельной функции и может быть разделена на подсекции, соответствующие отдельным состояниям или категориям состояний передача информации между шагами автомата осуществляется только через явно обозначенное множество переменных, называемых состоянием автомата; между шагами автомата программа (или её часть, оформленная в автоматном стиле) не может содержать неявных элементов состояния, таких как значения локальных переменных в стеке, адреса возврата из функций, значение текущего счётчика команд и т. п.; иначе говоря, состояние программы на любые два момента входа в шаг автомата могут различаться между собой только значениями переменных, составляющих состояние автомата (причём такие переменные должны быть явно обозначены в качестве таковых).
Полностью выполнение кода в автоматном стиле представляет собой цикл (возможно, неявный) шагов автомата.
Название автоматное программирование оправдывается ещё и тем, что стиль мышления (восприятия процесса исполнения) при программировании в этой технике практически точно воспроизводит стиль мышления при составлении формальных автоматов (таких как машина Тьюринга, автомат Маркова и др.)
Пример с использованием конечного автомата Пусть, к примеру, требуется написать на языке Си программу, читающую из потока стандартного ввода текст, состоящий из строк, и для каждой строки печатающую первое слово этой строки и перевод строки. Ясно, что для этого во время чтения каждой строки следует сначала пропустить пробелы, если таковые есть в начале строки; затем читать буквы, составляющие слово, и печатать их, пока слово не кончится (то есть либо не кончится строка, либо не будет встречен пробельный символ); наконец, когда первое слово успешно считано и напечатано, необходимо дочитать строку до конца, ничего при этом не печатая. Встретив (на любой фазе) символ перевода строки, следует напечатать перевод строки и продолжить с начала. При возникновении (опять таки, на любой фазе) ситуации «конец файла» следует прекратить работу.
Императивная программа Программа, решающая эту задачу в традиционном императивном стиле, может выглядеть, например, так (язык С): #include <stdio.h>
int main() { int c;
do { do c = getchar(); while (c == ' ');
while (c != ' ' && c != '\n' && c != EOF) { putchar(c); c = getchar();
putchar('\n'); while (c != '\n' && c != EOF) c = getchar(); } while (c != EOF);
return 0; }
Программа в автоматном стиле Ту же задачу можно решить, применив мышление в терминах конечных автоматов. Заметим, что разбор строки разделяется на три фазы: пропуск лидирующих пробелов, печать слова и пропуск символов остатка строки. Назовём эти три фазы состояниями before, inside и after. Программа теперь может выглядеть, например, так:
#include <stdio.h>
int main() { enum states { before, inside, after } state; int c;
state = before; while ((c = getchar()) != EOF) { switch (state) { case before: if (c == '\n') { putchar('\n'); } else if (c != ' ') { putchar(c); state = inside;
break; case inside: switch (c) { case ' ': state = after; break; case '\n': putchar('\n'); state = before; break; default: putchar(c);
break; case after: if (c == '\n') { putchar('\n'); state = before;
return 0; }
или так:#include <stdio.h>
static void (*state)(int);
static void before(int c); static void inside(int c); static void after(int c);
void before(int c) { if (c == '\n') { putchar('\n'); } else if (c != ' ') { putchar(c); state = &inside;
void inside(int c) { switch (c) { case ' ': state = &after; break; case '\n': putchar('\n'); state = &before; break; default: putchar(c);
void after(int c) { if (c == '\n') { putchar('\n'); state = &before;
int main() { int c;
state = &before; while ((c = getchar()) != EOF) { (*state)(c);
return 0; }Несмотря на то, что код явно стал более длинным, у него имеется одно несомненное достоинство: чтение (то есть вызов функции getchar()) теперь выполняется ровно в одном месте. Кроме того, необходимо заметить, что вместо четырёх циклов, использовавшихся в предыдущей версии, цикл теперь используется только один. Тело цикла (за исключением действий, выполняемых в заголовке) представляет собой шаг автомата, сам же цикл задаёт цикл работы автомата.
Программа реализует (моделирует) работу конечного автомата, изображённого на рисунке. Буквой N на диаграмме обозначен символ конца строки, буквой S — символ пробела, буквой A — все остальные символы. За один шаг автомат делает ровно один переход в зависимости от текущего состояния и прочитанного символа. Некоторые переходы сопровождаются печатью прочитанного символа; такие переходы на диаграмме обозначены звёздочками.
Строго соблюдать разделение кода на обработчики отдельных состояний, вообще говоря, не обязательно. Более того, в некоторых случаях само понятие состояния может складываться из значений нескольких переменных, так что учесть все возможные их комбинации окажется практически невозможно. В рассматриваемом примере можно сэкономить объём кода, если заметить, что действия, выполняемые по символу «конец строки», от состояния не зависят. Программа, эквивалентная предыдущей, но написанная с учётом такого замечания, будет выглядеть так:
#include <stdio.h>
int main() { enum states { before, inside, after } state; int c;
state = before; while ((c = getchar()) != EOF) { if (c == '\n') { putchar('\n'); state = before; continue;
switch (state) { case before: if (c != ' ') { putchar(c); state = inside;
break; case inside: if (c == ' ') state = after; else putchar(c); break; case after: break;
return 0; }
Выделение шага автомата в отдельную функцию Основополагающим в вышеприведённой программе является по-прежнему чёткое выделение кода, отвечающего за шаг автомата. Это обстоятельство можно подчеркнуть ещё сильнее, если выделить шаг автомата в отдельную функцию.
#include <stdio.h>
enum state_t { before, inside, after };
static void step(enum state_t *state, int *c) { if (*state == before) { if (*c == '\n') putchar('\n'); else if (*c != ' ') *state = inside; } if (*state == inside) { if (*c == ' ') { *state = after; } else if (*c == '\n') { putchar('\n'); *state = before; } else { putchar(*c);
if (*state == after) { if (*c == '\n') { putchar('\n'); *state = before;
int main() { int c; enum state_t state = before;
while ((c = getchar()) != EOF) step(&state, &c);
return 0; }
Этот пример наглядно демонстрирует основное свойство, благодаря которому код можно считать оформленным в стиле автоматного программирования: отдельные шаги автомата выполняются в неперекрывающиеся временные периоды единственным средством передачи информации между шагами является явно определённое состояние (в данном случае переменная state)
Программа с явно заданной таблицей переходов Конечный автомат, как известно, может быть задан и таблицей переходов. Вообще говоря, код программы, моделирующей конечный автомат, вполне может отражать и это свойство автомата. В следующей программе массив the_table задаёт таблицу переходов. Строки таблицы соответствуют трём состояниям автомата, столбцы — читаемым символам (первый столбец — пробел, второй столбец — перевод строки, третий столбец — все остальные символы). Каждая ячейка таблицы содержит номер нового состояния и признак необходимости печати символа (в приведённом коде используются битовые поля для экономии памяти). Конечно, в реальной задаче могла бы потребоваться гораздо более сложная структура таблицы, содержащая, например, указатели на функции для выполнения каких-либо действий, связанных с переходами, но в рассматриваемом примере это не нужно: #include <stdio.h>
enum states { before = 0, inside = 1, after = 2
typedef struct branch { enum states new_state; int should_putchar; } branch;
static const branch the_table = { /* ' ' '\n' others */ /* before */ { {before, 0}, {before, 1}, {inside, 1} }, /* inside */ { {after, 0}, {before, 1}, {inside, 1} }, /* after */ { {after, 0}, {before, 1}, {after, 0} }
static void step(enum states *state, int c) { int idx2 = (c == ' ') ? 0 : (c == '\n') ? 1 : 2; branch *b = &the_table[*state][idx2];
*state = b->new_state; if (b->should_putchar) putchar(c); }
int main() { int c; enum states state = before;
while ((c = getchar()) != EOF) step(&state, c);
return 0; }
Использование объектно-ориентированных возможностей Если используемый язык программирования поддерживает объектно-ориентированные возможности, логично будет инкапсулировать конечный автомат в объект, скрыв детали реализации. Например, аналогичная программа на языке C++ может выглядеть так: #include <stdio.h>
class StateMachine { enum states { before = 0, inside = 1, after = 2 } state; typedef struct { enum states new_state; unsigned should_putchar; } branch; static const branch the_table; public: StateMachine() : state(before) {} void FeedChar(int c) { int idx2 = (c == ' ') ? 0 : (c == '\n') ? 1 : 2; branch *b = &the_table[state][idx2]; state = b->new_state; if(b->should_putchar) putchar(c);
const StateMachine::branch StateMachine::the_table = { /* ' ' '\n' others */ /* before */ { {before, 0}, {before, 1}, {inside, 1} }, /* inside */ { {after, 0}, {before, 1}, {inside, 1} }, /* after */ { {after, 0}, {before, 1}, {after, 0} }
int main() { int c; StateMachine machine; while((c = getchar()) != EOF) machine.FeedChar(c); return 0; }Также каждое состояние конечного автомата можно описать как класс.#include <stdio.h>
class State { public: virtual ~State() {} virtual void Action(int ch, const State *&next_state) const = 0;
template <class T> class TState : protected State { static State *p; public: static State *Get() { if(!p) p = new T; return p;
protected: TState() {}
class Before : public TState<Before> { virtual void Action(int ch, const State *&next_state) const; }; class Inside : public TState<Inside> { virtual void Action(int ch, const State *&next_state) const; }; class After : public TState<After> { virtual void Action(int ch, const State *&next_state) const; }; template <> State *TState<Before>::p = 0; template <> State *TState<Inside>::p = 0; template <> State *TState<After>::p = 0;
void Before::Action(int ch, const State *&next_state) const { if(ch != ' ' && ch != '\n') { putchar(ch); next_state = Inside::Get();
void Inside::Action(int ch, const State *&next_state) const { if(ch != ' ' && ch != '\n') { putchar(ch); } else { putchar('\n'); next_state = (ch == '\n' ? Before::Get() : After::Get());
void After::Action(int ch, const State *&next_state) const { if(ch == '\n') next_state = Before::Get(); }
class FiniteStateMashine { const State *state; public: FiniteStateMashine() : state(Before::Get()) {} void Step(int ch) { state->Action(ch, state); }
int main() { FiniteStateMashine fsm; int ch; while((ch = getchar()) != EOF) fsm.Step(ch); return 0;