Войти
Программирование на основе автоматов - это парадигма программирования, в которой программа или ее часть рассматривается как модель конечного автомата (FSM) или любого другого (часто более сложного) формального автомата (см. теория автоматов ). Иногда вводится потенциально бесконечный набор возможных состояний, и такой набор может иметь сложную структуру, а не просто перечисление.
Программирование на основе конечных автоматов в целом то же самое, но, формально говоря, не охватывает все возможные варианты, поскольку конечный автомат обозначает конечный автомат, а автоматное программирование не обязательно использует конечные автоматы в строгий смысл.
Следующие свойства являются ключевыми индикаторами для программирования на основе автоматов:
Все выполнение кода, основанного на автомате, является циклом шагов автомата.
Другая причина использования понятия программирования на основе автоматов заключается в том, что стиль мышления программиста о программе в этой технике очень похож на стиль мышления, используемый для решения математических задач с использованием машин Тьюринга, Марковские алгоритмы и т. Д.
Рассмотрим задачу чтения текста из стандартного ввода построчно и записывая первое слово каждой строки в стандартный вывод. Сначала мы пропускаем все ведущие пробельные символы, если они есть. Затем печатаем все символы первого слова. Наконец, мы пропускаем все завершающие символы до тех пор, пока не встретится символ новой строки. Каждый раз, когда последовательность символов новой строки встречается не в начале потока, мы печатаем только первый и пропускаем остальные; иначе мы пропускаем все. Затем мы перезапускаем процесс со следующей строки. При обнаружении условия конца файла (независимо от этапа) мы останавливаемся.
Традиционная программа на C, которая выполняет вышеуказанную задачу, может выглядеть следующим образом:
#include#include int main (недействительно) {int c; делать {делать {c = getchar (); } while (isspace (c)); в то время как (! isspace (c) c! = EOF) {putchar (c); c = getchar (); } while (c! = '\ n' c! = EOF) {c = getchar (); } если (c == '\ n') {putchar (c); }} while (c! = EOF); возврат 0; }
Например, компиляция и выполнение указанной выше программы на этом входе:
$ 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)
возвращает:
foo qux
Эту же задачу можно решить, если мыслить в терминах конечных автоматов. Обратите внимание, что синтаксический анализ строки состоит из трех этапов: пропуск начальных пробельных символов, печать символов первого слова и пропуск конечных символов. Назовем эти состояния автомата ДО, ВНУТРИи ПОСЛЕ. Версия программы на основе автоматов может выглядеть так:
#include#include enum State {BEFORE, INSIDE, AFTER}; int main (void) {int c; enum State s = BEFORE; while ((c = getchar ())! = EOF) {переключатель (s) {case BEFORE: if (! isspace (c)) {putchar (c); s = ВНУТРИ; } перемена; case INSIDE: if (c == '\ n') {putchar (c); s = ДО; } иначе, если (isspace (c)) {s = AFTER; } else {putchar (c); } перемена; case AFTER: if (c == '\ n') {putchar (c); s = ДО; } перемена; }} return 0; }
Хотя программа теперь выглядит длиннее, у нее есть по крайней мере одно существенное преимущество: есть только одна инструкция чтения (то есть вызов функции getchar). Кроме того, здесь всего одна петля вместо четырех в традиционной версии. Тело цикла while- это шаг автомата, а сам цикл - это цикл шага автомата. Программа реализует работу конечного автомата, показанного на диаграмме состояний.
Самым важным свойством программы является то, что секция кода шага автомата четко локализована. С явной функцией stepдля этапа автоматизации программа лучше демонстрирует это свойство:
#include#include enum State {BEFORE, INSIDE, AFTER}; void step (enum State * const s, int const c) {переключатель (* s) {case BEFORE: if (! isspace (c)) {putchar (c); * s = ВНУТРИ; } перемена; case INSIDE: if (c == '\ n') {putchar (c); * s = ДО; } иначе, если (isspace (c)) {* s = ПОСЛЕ; } else {putchar (c); } перемена; case AFTER: if (c == '\ n') {putchar (c); * s = ДО; } перемена; }} int main (void) {int c; enum State s = BEFORE; в то время как ((c = getchar ())! = EOF) {шаг (s, c); } return 0; }
Теперь программа наглядно демонстрирует основные свойства автоматного кода:
Конечный автомат может быть определен с помощью таблицы переходов между состояниями, строки которой соответствуют текущим состояниям, столбцы - входам, а ячейки - следующим состояниям и действиям для выполнять.
| Ввод Текущее состояние | новая строка | пробел | другое |
|---|---|---|---|
| перед | перед | до | внутри / печать |
| внутри | до / печать | после | внутри / печать |
| после | до / печать | после | после |
 диаграмма состояний конечного автомата, который печатает первое слово каждой строки входной поток. Машина выполняет ровно один переход на каждом шаге, в зависимости от текущего состояния и встречающегося символа. Действие, сопровождающее переход, - это либо отсутствие операции, либо печать обнаруженного символа, обозначенного print. |
Вообще говоря, автоматная программа, естественно, может использовать этот подход. С явным двумерным массивом переходовдля таблицы переходов состояний программа использует следующий подход:
#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 (* действие) (число); }; struct Branch const transitions [3] [3] = {// новая строка пробела других входов / состояний {{BEFORE, nop}, {BEFORE, nop}, {INSIDE, print}}, // перед {{BEFORE, print}, {AFTER, nop}, {INSIDE, print}}, // внутри {{BEFORE, print}, {AFTER, nop}, {AFTER, nop}} // после}; void step (enum State * const s, int const c) {int const row = (* s == BEFORE)? 0: (* s == ВНУТРИ)? 1: 2; int const column = (c == '\ n')? 0: isspace (c)? 1: 2; struct Branch const * const b = переходы [строка] [столбец]; * s = b->next_state; б->действие (в); } int main (void) {int c; enum State s = BEFORE; в то время как ((c = getchar ())! = EOF) {шаг (s, c); } return 0; }
Если язык реализации поддерживает объектно-ориентированное программирование, простой рефакторинг программы заключается в инкапсуляции автомата в объект, таким образом скрывая детали его реализации. Программа на C ++ с использованием объектно-ориентированного стиля может выглядеть так:
#include#include enum State {BEFORE, INSIDE, AFTER}; struct Branch {enum State const next_state; void (* действие) (число); }; класс StateMachine {общественности: StateMachine (); void feedChar (число); protected: static void nop (int); статическая пустота print (int); частные: enum State _state; статическая структура Branch const _transitions [3] [3]; }; StateMachine :: StateMachine (): _state (BEFORE) {} void StateMachine :: feedChar (int const c) {int const row = (_state == BEFORE)? 0: (_state == ВНУТРИ)? 1: 2; int const column = (c == '\ n')? 0: isspace (c)? 1: 2; struct Branch const * const b = _transitions [строка] [столбец]; _state = b->next_state; б->действие (в); } void StateMachine :: nop (int const c) {} void StateMachine :: print (int const c) {putchar (c); } struct Branch const StateMachine :: _ transitions [3] [3] = {// новая строка пробела другие входы / состояния {{BEFORE, nop}, {BEFORE, nop}, {INSIDE, print}}, // перед {{BEFORE, print}, {AFTER, nop}, {INSIDE, print}}, // внутри {{BEFORE, print}, {AFTER, nop}, {AFTER, nop}} // после}; int main () {int c; StateMachine m; в то время как ((c = getchar ())! = EOF) {m.feedChar (c); } return 0; }
Примечание. - Для минимизации изменений, не связанных напрямую с тематикой статьи, функции input/output getcharи putcharиз стандартной библиотеки C уже используются.
Шаблон проектирования состояния - это способ для объекта изменить свое поведение во время выполнения в соответствии с его внутренним состоянием, не прибегая к большим условным операторам или просмотру таблиц благодаря вызовам виртуальных функций. Его главное преимущество перед кодом, использующим большие условные операторы, заключается в том, что код, зависящий от состояния, распределен по различным объектам, а не локализован в монолитном блоке, что улучшает ремонтопригодность. Его основные преимущества перед кодом, использующим таблицы перехода состояний, заключаются в том, что вызовы виртуальных функций часто более эффективны, чем поиск в таблицах, критерии перехода между состояниями более явны, чем в табличном формате, и что легче добавлять действия, сопровождающие переходы состояний. Однако это создает новую проблему: количество классов делает код менее компактным, чем другие подходы. Программа, использующая шаблон проектирования состояний, может выглядеть так:
#include#include class StateMachine; class State {public: виртуальная пустота feedChar (StateMachine *, int) const = 0; }; class Перед: общественное состояние {общественное: статическое состояние const * instantiate (); виртуальная пустота feedChar (StateMachine *, int) const override; protected: Before () = по умолчанию; частный: статическое состояние const * _instance; }; класс Внутри: общественное состояние {общественное: статическое состояние const * instantiate (); виртуальная пустота feedChar (StateMachine *, int) const override; защищенный: Внутри () = по умолчанию; частный: статическое состояние const * _instance; }; класс После: общественное состояние {общественное: статическое состояние const * instantiate (); виртуальная пустота feedChar (StateMachine *, int) const override; защищенный: After () = по умолчанию; частный: статическое состояние const * _instance; }; класс StateMachine {общественности: StateMachine (); void feedChar (число); защищенный: void setState (состояние const *); частный: состояние const * _state; класс друзей До; Friend class Inside; класс друзей После; }; Состояние const * Before :: instantiate () {if (! _Instance) {_instance = new Before; } return _instance; } void Before :: feedChar (StateMachine * const m, int const c) const {если (! isspace (c)) {putchar (c); m->setState (Внутри :: instantiate ()); }} Состояние const * Before :: _ instance = nullptr; Состояние 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 (До :: instantiate ()); } иначе если (isspace (c)) {m->setState (After :: instantiate ()); } else {putchar (c); }} Состояние const * Внутри :: _ instance = nullptr; Состояние 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 (До :: instantiate ()); }} Состояние 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; пока ((c = getchar ())! = EOF) {m.feedChar (c); } return 0; }
Программирование на основе автоматов действительно близко соответствует потребностям программирования в области автоматизации.
Производственный цикл обычно моделируется как:
Различные специализированные языки программирования позволяют выразить такую модель более или менее изощренно.
Пример, представленный выше, может быть выражен в соответствии с этим представлением, как в следующем псевдокоде ('set' активирует логическую переменную, 'reset' деактивирует логическую переменную, ':' присваивает переменную, а '=' проверяет равенство):
новая строка: '\ n' пробел: ('\ t', '\ n', '\ v', '\ f ',' \ r ',' ') состояния: (до, внутри, после) setState (c) {если до и (c! = новая строка и c не в пробеле), то установить внутри, если внутри then (если c в пробеле затем установить после else, если c = новая строка, затем установить до), если после и c = новая строка, затем установить до} doAction (c) {если до и (c! = новая строка и c не в пробеле), то напишите (c) если внутри и c не в пробеле, то напишите (c) если после и c = новая строка, то напишите (c)} cycle {установить перед циклом до (c: readCharacter) = EOL {setState (c) doAction (c)}}Разделение подпрограммы, выражающие прогрессию цикла с одной стороны, и фактическое действие с другой (согласование ввода и вывода) позволяют более четко и просто код лера.
В области автоматизации переход от шага к шагу зависит от входных данных, поступающих от самой машины. В программе это представлено чтением символов из текста. В действительности эти данные сообщают о положении, скорости, температуре и т. Д. Критических элементов машины.
Как и в программировании GUI, изменения в состоянии машины, таким образом, можно рассматривать как события, вызывающие переход из одного состояния в другое, пока не будет достигнуто последнее. Комбинация возможных состояний может генерировать большое количество событий, определяя более сложный производственный цикл. Как следствие, циклы обычно далеки от простых линейных последовательностей. Обычно существуют параллельные ветви, идущие вместе, и альтернативы, выбираемые в соответствии с различными событиями, схематично представлены ниже:
s: stage c: condition s1 | | -c2 | s2 | ---------- | | | -c31 | -c32 | | s31 s32 | | | -c41 | -c42 | | ---------- | s4
Программирование на основе автоматов широко используется в лексическом и синтаксическом анализе.
. Кроме того, мышление в терминах автоматов (то есть разбиение процесса выполнения на этапы автоматизации и передача информации от этапа к этапу через явное состояние автомата) необходимо для событийно-ориентированного программирования как единственной альтернативы использованию параллельных процессов или потоков.
Понятия состояний и конечных автоматов часто используются в области формальной спецификации. Например, при разработке архитектуры программного обеспечения на основе UML используются диаграммы состояний для определения поведения программы. Также различные протоколы связи часто указываются с использованием явного понятия состояния (например, RFC 793 ).
Мышление в терминах автоматов (шагов и состояний) также может использоваться для описания семантики некоторых языков программирования. Например, выполнение программы, написанной на языке Refal, описывается как последовательность шагов так называемой абстрактной машины Refal; состояние машины - это представление (произвольное выражение Рефаля без переменных).
Продолжение в языке Scheme требует мышления в терминах шагов и состояний, хотя сама Scheme никоим образом не связана с автоматами (она рекурсивна). Чтобы функция call / cc могла работать, реализация должна иметь возможность улавливать все состояние выполняющейся программы, что возможно только тогда, когда в состоянии нет неявной части. Такое пойманное состояние и есть то, что называется продолжением, и его можно рассматривать как состояние (относительно сложного) автомата. Шаг автомата выводит следующее продолжение из предыдущего, а процесс выполнения - это цикл таких шагов.
Александр Оллонгрен в своей книге объясняет так называемый венский метод описания семантики языков программирования, полностью основанный на формальных автоматах.
Система STAT [1] - хороший пример использования подхода, основанного на автоматах; эта система, помимо других функций, включает встроенный язык под названием STATL, который ориентирован исключительно на автоматизацию.
Методы, основанные на автоматах, широко использовались в тех областях, где есть алгоритмы, основанные на теории автоматов, такие как анализ формального языка.
Одна из ранних работ по это Джонсон и др., 1968.
Одно из самых ранних упоминаний о автоматном программировании как об общем методе содержится в статье Питера Наура, 1963. Автор называет подход машины Тьюринга, однако в статье не приводится реальная машина Тьюринга ; вместо этого описывается техника, основанная на шагах и состояниях.
Понятие состояния не является исключительным свойством автоматного программирования. Вообще говоря, состояние (или состояние программы ) появляется во время выполнения любой компьютерной программы как комбинация всей информации, которая может изменяться во время выполнения. Например, состояние традиционной императивной программы состоит из
Их можно разделить на явную часть (например, значения, хранящиеся в переменных) и неявную часть ( адреса возврата и указатель инструкции).
Сказав это, автоматная программа может рассматриваться как частный случай императивной программы, в которой неявная часть состояния минимизирована. Состояние всей программы, полученное в два разных момента входа в секцию кода шага, может отличаться только состоянием автомата. Это упрощает анализ программы.
В теории объектно-ориентированного программирования считается, что объект имеет внутреннее состояние и способен принимать сообщения, отвечая на их, отправляя сообщения другим объектам и изменяя свое внутреннее состояние во время обработки сообщений. В более практической терминологии вызов метода объекта рассматривается как отправка сообщения объекту.
Таким образом, с одной стороны, объекты из объектно-ориентированного программирования могут рассматриваться как автоматы (или модели автоматов), состояние которых является комбинацией частных полей, а один или несколько методов считаются этапом. Такие методы не должны вызывать друг друга или самих себя, ни прямо, ни косвенно, иначе объект не может считаться реализованным на основе автоматов.
С другой стороны, объект хорош для реализации модели автомата. Когда подход, основанный на автоматах, используется в объектно-ориентированном языке, автоматная модель обычно реализуется классом, состояние представлено частными полями класса, а шаг реализуется как метод; такой метод обычно является единственным непостоянным общедоступным методом класса (помимо конструкторов и деструкторов). Другие общедоступные методы могут запрашивать состояние, но не меняют его. Все второстепенные методы (например, обработчики определенных состояний) обычно скрыты в частной части класса.
