Automata-based programming
≈ 11 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Automata-based programming is a programming paradigm in which the program or part of it is thought of as a model of a finite-state machine (FSM) or any other (often more complicated) formal automaton (see automata theory). Sometimes a potentially infinite set of possible states is introduced, and such a set can have a complicated structure, not just an enumeration. Finite-state machine-based programming is generally the same, but, formally speaking, does not cover all possible variants, as FSM stands for finite-state machine, and automata-based programming does not necessarily employ FSMs in the strict sense. The following properties are key indicators for automata-based programming: * The time period of the program's execution is clearly separated down to the automaton steps. Each step is effectively an execution of a code section (same for all the steps) which has a single entry point. That section might be divided down to subsections to be executed depending on different states, although this is not necessary. * Any communication between the automaton steps is only possible via the explicitly noted set of variables named the automaton state. Between any two steps, the program cannot have implicit components of its state, such as local variables' values, return addresses, the current instruction pointer, etc.…
Automata-based programming is a programming paradigm in which the program or part of it is thought of as a model of a finite-state machine (FSM) or any other (often more complicated) formal automaton (see automata theory). Sometimes a potentially infinite set of possible states is introduced, and such a set can have a complicated structure, not just an enumeration. Finite-state machine-based programming is generally the same, but, formally speaking, does not cover all possible variants, as FSM stands for finite-state machine, and automata-based programming does not necessarily employ FSMs in the strict sense. The following properties are key indicators for automata-based programming: The time period of the program's execution is clearly separated down to the automaton steps. Each step is effectively an execution of a code section (same for all the steps) which has a single entry point. That section might be divided down to subsections to be executed depending on different states, although this is not necessary. Any communication between the automaton steps is only possible via the explicitly noted set of variables named the automaton state. Between any two steps, the program cannot have implicit components of its state, such as local variables' values, return addresses, the current instruction pointer, etc. That is, the state of the whole program, taken at any two moments of entering an automaton step, can only differ in the values of the variables being considered as the automaton state. The whole execution of the automata-based code is a cycle of the automaton steps. Another reason for using the notion of automata-based programming is that the programmer's style of thinking about the program in this technique is very similar to the style of thinking used to solve mathematical tasks using Turing machines, Markov algorithms, etc. include include int main(void) { int c; do { do { c = getchar(); } while (isspace(c)); while (!isspace(c) && c != EOF) { putchar(c); c = getchar(); } while (c != '\n' && c != EOF) { c = getchar(); } if (c == '\n') { putchar(c); } } while (c != EOF); return 0; } For instance, compiling and running the above program on this input: $ clang program.c && (printf "\t\v\f\r \n\n\t\v\f\r foo bar baz\n\n\t\v\f\r qux quux corge" | ./a.out) yields: foo qux include include enum State {BEFORE, INSIDE, AFTER}; int main(void) { int c; enum State s = BEFORE; while ((c = getchar()) != EOF) { switch (s) { case BEFORE: if (!isspace(c)) { putchar(c); s = INSIDE; } break; case INSIDE: if (c == '\n') { putchar(c); s = BEFORE; } else if (isspace(c)) { s = AFTER; } else { putchar(c); } break; case AFTER: if (c == '\n') { putchar(c); s = BEFORE; } break; } } return 0; } Although the program now looks longer, it has at least one significant advantage: there is only one reading (that is, call to the getchar function) instruction. Besides that, there is only one loop instead of the four the traditional version had. The body of the while loop is the automaton step and the loop itself is the cycle of the automaton step. The program implements the work of a finite-state machine shown in the state diagram. The most important property of the program is that the automaton step code section is clearly localized. With an explicit function step for the automation step, the program better demonstrates this property: include include enum State {BEFORE, INSIDE, AFTER}; void step(enum State* const s, int const c) { switch (*s) { case BEFORE: if (!isspace(c)) { putchar(c); *s = INSIDE; } break; case INSIDE: if (c == '\n') { putchar(c); *s = BEFORE; } else if (isspace(c)) { *s = AFTER; } else { putchar(c); } break; case AFTER: if (c == '\n') { putchar(c); *s = BEFORE; } break; } } int main(void) { int c; enum State s = BEFORE; while ((c = getchar()) != EOF) { step(&s, c); } return 0; } The program now clearly demonstrates the basic properties of automata-based code: Time periods of automaton step executions may not overlap; The only information passed from the previous step to the next is the explicitly specified automaton state. A finite automaton can be defined by a state-transition table whose rows stand for the current states, columns stand for the inputs, and cells stand for the next states and actions to perform. Generally speaking, an automata-based program can naturally use this approach. With an explicit two-dimensional array transitions for the state-transition table, the program uses this approach: include include enum State {BEFORE, INSIDE, AFTER}; void nop(int const c) {} void print(int const c) { putchar(c); } struct Branch { enum State const next_state; void (*action)(int); }; struct Branch const transitions[3][3] = { // newline whitespace other Inputs/States {{BEFORE, &nop}, {BEFORE, &nop}, {INSIDE, &print}}, // before {{BEFORE, &print}, {AFTER, &nop}, {INSIDE, &print}}, // inside {{BEFORE, &print}, {AFTER, &nop}, {AFTER, &nop}} // after }; void step(enum State* const s, int const c) { int const row = (*s
BEFORE) ? 0 : (*s
INSIDE) ? 1 : 2; int const column = (c == '\n') ? 0 : isspace(c) ? 1 : 2; struct Branch const* const b = &transitions[row][column]; *s = b->next_state; b->action(c); } int main(void) { int c; enum State s = BEFORE; while ((c = getchar()) != EOF) { step(&s, c); } return 0; } include include enum State {BEFORE, INSIDE, AFTER}; struct Branch { enum State const next_state; void (*action)(int); }; class StateMachine { public: StateMachine(); void feedChar(int); protected: static void nop(int); static void print(int); private: enum State _state; static struct Branch const _transitions[3][3]; }; StateMachine::StateMachine(): _state(BEFORE) {} void StateMachine::feedChar(int const c) { int const row = (_state
BEFORE) ? 0 : (_state
INSIDE) ? 1 : 2; int const column = (c == '\n') ? 0 : isspace(c) ? 1 : 2; struct Branch const* const b = &_transitions[row][column]; _state = b->next_state; b->action(c); } void StateMachine::nop(int const c) {} void StateMachine::print(int const c) { putchar(c); } struct Branch const StateMachine::_transitions[3][3] = { // newline whitespace other Inputs/States {{BEFORE, &nop}, {BEFORE, &nop}, {INSIDE, &print}}, // before {{BEFORE, &print}, {AFTER, &nop}, {INSIDE, &print}}, // inside {{BEFORE, &print}, {AFTER, &nop}, {AFTER, &nop}} // after }; int main() { int c; StateMachine m; while ((c = getchar()) != EOF) { m.feedChar(c); } return 0; } To minimize changes not directly related to the subject of the article, the input/output getchar and putchar functions from the standard library of C are being used. The state design pattern is a way for an object to change its behavior at runtime according to its internal state without resorting to large conditional statements or table lookups thanks to virtual function calls. Its main advantage over code using large conditional statements is that state-specific code is distributed across different objects rather than localized in a monolithic block, which improves maintainability. Its main advantages over code using state-transition tables are that virtual function calls are often more efficient than table lookups, that state-transition criteria are more explicit than in tabular format, and that it is easier to add actions accompanying state transitions. However it introduces a new problem: the number of classes makes the code less compact than the other approaches. The program using the state design pattern could look like this: include include class StateMachine; class State { public: virtual void feedChar(StateMachine*, int) const = 0; }; class Before: public State { public: static State const* instantiate(); virtual void feedChar(StateMachine*, int) const override; protected: Before() = default; private: static State const* _instance; }; class Inside: public State { public: static State const* instantiate(); virtual void feedChar(StateMachine*, int) const override; protected: Inside() = default; private: static State const* _instance; }; class After: public State { public: static State const* instantiate(); virtual void feedChar(StateMachine*, int) const override; protected: After() = default; private: static State const* _instance; }; class StateMachine { public: StateMachine(); void feedChar(int); protected: void setState(State const*); private: State const* _state; friend class Before; friend class Inside; friend class After; }; State const* Before::instantiate() { if (!_instance) { _instance = new Before; } return _instance; } void Before::feedChar(StateMachine* const m, int const c) const { if (!isspace(c)) { putchar(c); m->setState(Inside::instantiate()); } } State const* Before::_instance = nullptr; State const* Inside::instantiate() { if (!_instance) { _instance = new Inside; } return _instance; } void Inside::feedChar(StateMachine* const m, int const c) const { if (c == '\n') { putchar(c); m->setState(Before::instantiate()); } else if (isspace(c)) { m->setState(After::instantiate()); } else { putchar(c); } } State const* Inside::_instance = nullptr; State const* After::instantiate() { if (!_instance) { _instance = new After; } return _instance; } void After::feedChar(StateMachine* const m, int const c) const { if (c == '\n') { putchar(c); m->setState(Before::instantiate()); } } State const* After::_instance = nullptr; StateMachine::StateMachine(): _state(Before::instantiate()) {} void StateMachine::feedChar(int const c) { _state->feedChar(this, c); } void StateMachine::setState(State const* const s) { _state = s; } int main() { int c; StateMachine m; while ((c = getchar()) != EOF) { m.feedChar(c); } return 0; } The example presented above could be expressed according to this view like in the following pseudo-code ('set' activates a logic variable, 'reset' inactivates a logic variable, ':' assigns a variable, and '=' tests for equality): newline: '\n' whitespace: ('\t', '\n', '\v', '\f', '\r', ' ') states: (before, inside, after) setState(c) { if before and (c != newline and c not in whitespace) then set inside if inside then (if c in whitespace then set after else if c = newline then set before) if after and c = newline then set before } doAction(c) { if before and (c != newline and c not in whitespace) then write(c) if inside and c not in whitespace then write(c) if after and c = newline then write(c) } cycle { set before loop until (c: readCharacter) = EOL { setState(c) doAction(c) } } The separation of routines expressing cycle progression on one side, and actual action on the other (matching input and output) allows clearer and simpler code. Polikarpova N. I., Shalyto A. A. Automata-based programming SPb.: Piter. 2009 (rus) ITMO University, "Programming Technology" department
Text derived from https://en.wikipedia.org/w/index.php?oldid=1282644115 under CC BY-SA 4.0; modifications have been made.