Автоматное програмування — це парадигма програмування, при використанні якої програма або її фрагмент осмислюється як модель якогось формального автомата.
В залежності від конкретної задачі в автоматном програмуванні можуть використовуватися як кінцеві автомати, так і автомати з більш складною будовою.
Визначальними для автоматного програмування є наступні особливості: часовий період виконання програми розбивається на кроки автомата, кожна з яких являє собою виконання певної (однієї і тієї ж для кожного кроку) секції коду з єдиною точкою входу; така секція може бути оформлена, наприклад, у вигляді окремої функції і може бути розділена на підсекції, відповідні окремим станам або категорій станів передача інформації між кроками автомата здійснюється лише через явне безліч змінних, званих станом автомата; між кроками автомата програма (або її частина, оформлена в автоматном стилі) не може містити неявних стану елементів, таких як значення локальних змінних в стеку адресу повернення з функцій, значення поточного лічильника команд і т. п.; інакше кажучи, стан програми на будь-які два моменту входу в крок автомата можуть розрізнятися між собою тільки значеннями змінних, складових стан автомата (причому такі змінні повинні бути чітко позначені як такі).
Повністю виконання коду в автоматном стилі являє собою цикл (можливо, неявний) кроків автомата.
Назва автоматное програмування виправдовується ще й тим, що стиль мислення (сприйняття процесу виконання) при програмуванні в цій техніці практично точно відтворює стиль мислення при складанні формальних автоматів (таких як машина Тьюринга, автомат Маркова та ін)
Нехай, наприклад, потрібно написати програму на мові Сі, що читає зі стандартного потоку вводу текст, що складається з рядків, і для кожного рядка друкувальну перше слово рядка і переклад рядка. Ясно, що для цього під час читання кожного рядка слід спочатку пропустити прогалини, якщо такі є на початку рядка; потім читати букви, складові слово, і друкувати їх, поки слово не скінчиться (тобто або не скінчиться рядок, або не буде зустрінутий пробільний символ); нарешті, коли перше слово успішно були отримані і надруковано, необхідно дочитати рядок до кінця, нічого при цьому не друкуючи. Зустрівши (на будь-якій фазі) символ перекладу рядка, слід надрукувати переклад рядка і продовжити спочатку. При виникненні (знову таки, на будь-якій фазі) ситуації «кінець файлу» слід припинити роботу.
Програма, яка вирішує цю задачу в традиційному імперативному стилі, може виглядати, наприклад, так (мова С):
#include <stdio.h>
int main() { int c;
do { c = getchar(); while (c == ' ') c = getchar(); 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; }
Незважаючи на те, що код явно став довшим, у нього є одна безперечна перевага: читання (тобто виклик функції 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); case after: break; } }
return 0; }
Основоположним у вищенаведеній програмі є як і раніше чітке виділення коду, що відповідає за крок автомата. Цю обставину можна підкреслити ще сильніше, якщо виділити крок автомата в окрему функцію. #include <stdio.h>
enum States { before, inside, after };
void step(enum States &state, int &c) { if (c == '\n') putchar('\n'), state = before; switch (state) { case before: if (c != '') putchar(c), state = inside; break; case inside: if (c == ' ') state = after; else putchar(c); case after: break; } }
int main() { int c; enum States 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:4; int should_putchar:4; } branch;
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; struct branch { enum states new_state:4; unsigned should_putchar:4; }; static struct branch the_table; public: StateMachine() : state(before) {} void FeedChar(int c) { int idx2 = (c == ' ') ? 0 : (c == '\n') ? 1 : 2; struct branch *b = & the_table[state][idx2]; state = b->new_state; if(b->should_putchar) putchar(c); } };
int main() { int c; StateMachine machine; while((c = getchar()) != EOF) machine.FeedChar(c); return 0; }
Зазначимо, що в цьому прикладі ми використовували для введення-виведення бібліотеку мови Сі, щоб уникнути появи «зайвих» (відволікаючих увагу) змін у порівнянні з попереднім прикладом.
Автоматное програмування широко застосовується при побудові лексичних аналізаторів (класичні кінцеві автомати) і синтаксичних аналізаторів (автомати з магазинною пам'яттю)[1].
Крім того, мислення в термінах кінцевих автоматів (тобто розбиття виконання програми на кроки автомата і передача інформації від кроку до кроку через стан) необхідно при побудові подієво-орієнтованих додатків. У цьому випадку програмування в стилі кінцевих автоматів виявляється єдиною альтернативою породження безлічі процесів або потоків управління (тредів).
Часто поняття станів і машин станів використовується для специфікації програм. Так, при проектуванні програмного забезпечення за допомогою UML для опису поведінки об'єктів використовуються діаграми станів (state machine diagrams). Крім того, явне виділення станів використовується в описі мережевих протоколів (див., наприклад, RFC 793[2]).
Мислення в термінах автоматів (кроків і станів) знаходить застосування при описі семантики деяких мов програмування. Так, виконання програми мовою Рефал являє собою послідовність змін поля зору Рефал-машини або, інакше кажучи, послідовність кроків Рефал-автомата, станом якого є вміст поля зору (довільне Рефал-вираження, що не містить змінних).
Механізм продовжень мови Scheme для своєї реалізації вимагає мислення в термінах станів і кроків, незважаючи на те що сам мову Scheme жодним чином не є автоматним. Тим не менш, щоб забезпечити можливість «заморожування» продовження, доводиться при реалізації обчислювальної моделі мови Scheme об'єднувати всі компоненти середовища виконання, включаючи список дій, які залишилося виконати для закінчення обчислень, в єдине ціле, яке також зазвичай називається продовженням. Таке продовження виявляється станом автомату, а процес виконання програми складається з кроків, кожен з яких виводить наступне значення продовження з попереднього.
Олександр Оллонгрен у своїй книзі[] описує так званий Віденський метод опису семантики мов програмування, заснований цілком на формальних автоматах.
В якості одного з прикладів застосування автоматної парадигми можна назвати систему STAT []; ця система, зокрема, включає вбудований мова STATL, що має чисто автоматну семантику.
Існують також пропозиції щодо використання автоматного програмування в якості універсального підходу до створення комп'ютерних програм незалежно від предметної області. Так, автори статті[] стверджують, що автоматное програмування здатне зіграти роль легендарної срібної кулі.
Поняття стану програми не є ексклюзивною особливістю автоматного програмування. Взагалі кажучи, стан виникає при виконанні будь-якої комп'ютерної програми і являє собою сукупність усієї інформації, яка під час виконання може бути змінена. Так, стан програми, виконаної в традиційному імперативному стилі складається з Сукупності значень глобальних змінних і вмісту динамічної пам'яті вмісту регістрів загального призначення вмісту стека (включаючи адреси повернень та значення локальних змінних) поточного значення лічильника команд (тобто поточної позиції в коді програми)
Складові частини стану можна розділити на явні (такі як значення змінних) і неявні (адреси повернень та значення лічильника команд).
У контексті введених визначень програму, оформлену у вигляді моделі кінцевого автомата, можна вважати окремим випадком імперативною програми, таким, в якому роль неявній складової стану зведена до мінімуму. Якщо розглянути автоматну програму в моменти початку чергового кроку автомата, то стану програми в ці моменти будуть відрізнятися тільки явною складової. Ця обставина істотно спрощує аналіз властивостей програми.
В теорії об'єктно-орієнтованого програмування вважається, що об'єкт має внутрішній стан і здатний одержувати повідомлення, відповідати на них, відправляти повідомлення іншим об'єктам і в процесі обробки повідомлень змінювати свій внутрішній стан. Більш наближений до практики поняття виклику методу об'єкта вважається синонімом поняття надсилання повідомлення об'єкту.
Таким чином, з одного боку, об'єкти в об'єктно-орієнтованому програмуванні можуть розглядатися як кінцеві автомати (або, якщо завгодно, моделі кінцевих автоматів), стан яких являє собою сукупність внутрішніх полів, в якості ж кроку автомата можуть розглядатися один або кілька методів об'єкта за умови, що ці методи не викликають самі себе, ні один одного, ні прямо, ні побічно.
З іншого боку, очевидно, що поняття об'єкта являє собою вдалий інструмент реалізації моделі кінцевого автомата. При застосуванні парадигми автоматного програмування в об'єктно-орієнтованих мовах зазвичай моделі автоматів представляються у вигляді класів, стан автомата описується внутрішніми (закритими) полями класу, а код кроку автомата оформляється у вигляді методу класу, причому такий метод швидше за все виявляється єдиним відкритим методом (не рахуючи конструкторів і деструкторів), що змінює стан автомата. Інші відкриті методи можуть служити для одержання інформації про стан автомата, але не змінюють його. Всі допоміжні методи (наприклад, методи-обробники окремих станів чи їх категорій) у таких випадках зазвичай прибирають в закриту частину класу.
Мова послідовних функціональних схем SFC (Sequential Function Chart) — графічний мову програмування широко використовується для програмування промислових логічних контролерів PLC.
В SFC програма описується у вигляді схематичної послідовності кроків, об'єднаних переходами. Дракон-схеми — графічний мова програмування, що використовується для програмування в ракетно-космічній техніці («Буран», «Морський старт», «Тополя»). Існує безкоштовний Дракон-редактор. Мова Рефлекс — Сі-подібний мова програмування, орієнтований на опис складних алгоритмів керування в задачах промислової автоматизації.
