Автоматное программирование — это парадигма программирования , в которой программа или ее часть рассматривается как модель конечного автомата (FSM) или любого другого (часто более сложного) формального автомата (см. Теория автоматов ). Иногда вводится потенциально бесконечное множество возможных состояний, и такое множество может иметь сложную структуру, а не просто перечисление.
Программирование на основе конечных автоматов в целом то же самое, но, формально говоря, не охватывает все возможные варианты, поскольку FSM означает конечный автомат, а программирование на основе автоматов не обязательно использует FSM в строгом смысле.
Следующие свойства являются ключевыми показателями для автоматного программирования:
Все выполнение кода на основе автомата представляет собой цикл шагов автомата.
Еще одной причиной использования понятия автоматного программирования является то, что стиль мышления программиста о программе в этой технике очень похож на стиль мышления, используемый при решении математических задач с использованием машин Тьюринга , алгоритмов Маркова и т. д.
Рассмотрим задачу чтения текста из стандартного ввода построчно и записи первого слова каждой строки в стандартный вывод . Сначала мы пропускаем все начальные пробельные символы, если таковые имеются. Затем мы печатаем все символы первого слова. Наконец, мы пропускаем все конечные символы, пока не встретим символ новой строки . Всякий раз, когда последовательность символов новой строки встречается не в начале потока, мы печатаем только первый из них и пропускаем оставшиеся; в противном случае мы пропускаем все. Затем мы перезапускаем процесс со следующей строки. При обнаружении условия конца файла (независимо от стадии) мы останавливаемся.
Традиционная программа на языке C , выполняющая указанную выше задачу, может выглядеть следующим образом:
#include <ctype.h> #include <stdio.h> int main ( void ) { int c ; делать { делать { c = getchar (); } пока ( 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 ); вернуть 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 ) урожайность:
фу кьюксЭту же задачу можно решить, думая в терминах конечных автоматов . Разбор строки состоит из трех этапов: пропуск начальных пробельных символов, вывод символов первого слова и пропуск конечных символов. Назовем эти состояния автомата BEFORE, INSIDEи AFTER. Версия программы на основе автомата может выглядеть так:
#include <ctype.h> #include <stdio.h> enum State { ДО , ВНУТРИ , ПОСЛЕ }; int main ( void ) { int c ; enum Состояние s = ДО ; 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 ; } } вернуть 0 ; } Хотя программа теперь выглядит длиннее, у нее есть по крайней мере одно существенное преимущество: есть только одна инструкция чтения (то есть вызова функции getchar). Кроме того, есть только один цикл вместо четырех, которые были в традиционной версии. Тело цикла while— это шаг автомата , а сам цикл — это цикл шага автомата. Программа реализует работу конечного автомата, показанного на диаграмме состояний.
Важнейшим свойством программы является то, что раздел кода шага автомата четко локализован. С явной функцией stepдля шага автоматизации программа лучше демонстрирует это свойство:
#include <ctype.h> #include <stdio.h> enum State { ДО , ВНУТРИ , ПОСЛЕ }; void step ( enum State * const s , int const c ) { switch ( * s ) { case BEFORE : if ( ! isspace ( c )) { putchar ( c ); * s = ВНУТРИ ; } break ; case INSIDE : if ( c == '\n' ) { putchar ( c ); * s = ПЕРЕД ; } else if ( isspace ( c )) { * s = ПОСЛЕ ; } else { putchar ( c ); } break ; case AFTER : if ( c == '\n' ) { putchar ( c ); * s = ПЕРЕД ; } break ; } } int main ( void ) { int c ; enum Состояние s = ДО ; пока (( c = getchar ()) != EOF ) { шаг ( & s , c ); } вернуть 0 ; } Программа теперь наглядно демонстрирует основные свойства кода на основе автоматов:
Конечный автомат можно определить с помощью таблицы переходов состояний, строки которой соответствуют текущим состояниям, столбцы — входным данным, а ячейки — следующим состояниям и действиям, которые необходимо выполнить.
Вообще говоря, программа на основе автоматов может естественным образом использовать этот подход. С явным двумерным массивом transitionsдля таблицы переходов состояний программа использует этот подход:
#include <ctype.h> #include <stdio.h> enum State { ДО , ВНУТРИ , ПОСЛЕ }; 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 ] = { // новая строка пробельные символы другие Входы/Состояния {{ 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 == 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 Состояние s = ДО ; пока (( c = getchar ()) != EOF ) { шаг ( & s , c ); } вернуть 0 ; } Если язык реализации поддерживает объектно-ориентированное программирование , простой рефакторинг программы заключается в инкапсуляции автомата в объект, таким образом скрывая детали его реализации. Программа на C++, использующая объектно-ориентированный стиль, может выглядеть так:
#include <ctype.h> #include <stdio.h> enum State { ДО , ВНУТРИ , ПОСЛЕ }; struct Branch { enum State const next_state ; void ( * action )( int ); }; class StateMachine { public : StateMachine (); void feedChar ( int ); защищено : static void nop ( int ); static void print ( int ); private : enum State _state ; статическая структура Branch const _transitions [ 3 ][ 3 ]; }; StateMachine :: StateMachine () : _state ( ДО ) {} 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 ] = { // новая строка пробельные символы другие Входы/Состояния {{ 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 ); } вернуть 0 ; } Для минимизации изменений, не имеющих прямого отношения к теме статьи, используются ввод/вывод getchar и putcharфункции из стандартной библиотеки языка Си .
Шаблон проектирования состояний — это способ для объекта изменять свое поведение во время выполнения в соответствии со своим внутренним состоянием, не прибегая к большим условным операторам или табличным поискам благодаря вызовам виртуальных функций. Его главное преимущество перед кодом, использующим большие условные операторы, заключается в том, что код, специфичный для состояний, распределяется по разным объектам, а не локализуется в монолитном блоке, что улучшает удобство обслуживания. Его главные преимущества перед кодом, использующим таблицы переходов состояний, заключаются в том, что вызовы виртуальных функций часто более эффективны, чем табличные поиски, что критерии переходов состояний более явны, чем в табличном формате, и что проще добавлять действия, сопровождающие переходы состояний. Однако он вносит новую проблему: количество классов делает код менее компактным, чем другие подходы. Программа, использующая шаблон проектирования состояний, может выглядеть следующим образом:
#include <ctype.h> #include <stdio.h> класс StateMachine ; class State { public : virtual void feedChar ( StateMachine * , int ) const = 0 ; }; класс До : public State { public : static State const * instantiate (); virtual void feedChar ( StateMachine * , int ) const override ; защищено : До () = по умолчанию ; private : статическое состояние const * _instance ; }; класс Внутри : публичное Состояние { публичное : статическое Состояние const * инстанцировать (); виртуальный void feedChar ( StateMachine * , int ) const переопределение ; защищено : Внутри () = по умолчанию ; private : статическое состояние const * _instance ; }; класс После : public State { public : static State const * instantiate (); virtual void feedChar ( StateMachine * , int ) const override ; защищено : После () = по умолчанию ; private : статическое состояние const * _instance ; }; class StateMachine { public : StateMachine (); void feedChar ( int ); защищено : void setState ( State const * ); private : State const * _state ; дружественный класс До ; дружественный класс Внутри ; дружественный класс После ; }; Состояние const * До :: instantiate () { if ( ! _instance ) { _instance = new До ; } возврат _экземпляра ; } void Перед :: feedChar ( StateMachine * const m , int const c ) const { if ( ! isspace ( c )) { putchar ( c ); m -> setState ( Внутри :: instantiate ()); } } Состояние const * До :: _instance = nullptr ; Состояние const * Внутри :: инстанцировать () { if ( ! _instance ) { _instance = new Внутри ; } возврат _экземпляра ; } void Внутри :: feedChar ( StateMachine * const m , int const c ) const { if ( c == '\n' ) { putchar ( c ); m -> setState ( До :: instantiate ()); } else if ( isspace ( c )) { m -> setState ( После :: instantiate ()); } else { putchar ( c ); } } Состояние const * Внутри :: _instance = nullptr ; Состояние const * После :: инстанцировать () { if ( ! _instance ) { _instance = new После ; } возврат _экземпляра ; } void После :: feedChar ( StateMachine * const m , int const c ) const { if ( c == '\n' ) { putchar ( c ); m -> setState ( До :: instantiate ()); } } Состояние const * После :: _instance = nullptr ; StateMachine :: StateMachine () : _state ( До :: инстанцировать ()) {} void StateMachine :: feedChar ( int const c ) { _state -> feedChar ( this , c ); } void StateMachine :: setState ( Состояние const * const s ) { _state = s ; } int main () { int c ; StateMachine m ; в то время как (( c = getchar ()) != EOF ) { m . feedChar ( c ); } вернуть 0 ; } Программирование на основе автоматов действительно близко соответствует потребностям программирования в области автоматизации .
Производственный цикл обычно моделируется следующим образом:
Различные специализированные языки программирования позволяют выразить такую модель более или менее сложными способами.
Представленный выше пример можно выразить в соответствии с этим представлением следующим псевдокодом («set» активирует логическую переменную, «reset» деактивирует логическую переменную, «:» назначает переменную, а «=» проверяет равенство):
новая строка: '\n'пробел: ('\t', '\n', '\v', '\f', '\r', ' ')состояния: (до, внутри, после)установитьСостояние(с) { если до и (c != новая строка и c не в пробеле), то установить внутри если внутри, то (если c в пробеле, то установить после, иначе если c = новая строка, то установить перед) если после и c = новая строка, то установить перед}сделатьДействие(c) { если до и (c != новая строка и c не в пробеле), то write(c) если внутри и c не в пробеле, то write(c) если после и c = новая строка, то write(c)}цикл { установить перед цикл до тех пор, пока (c: readCharacter) = EOL { установитьСостояние(c) doAction(c) }}Разделение процедур, выражающих ход цикла, с одной стороны, и фактических действий — с другой (сопоставление ввода и вывода), позволяет сделать код более понятным и простым.
В области автоматизации переход от шага к шагу зависит от входных данных, поступающих от самой машины. Это представлено в программе путем считывания символов из текста. В действительности эти данные информируют о положении, скорости, температуре и т. д. критических элементов машины.
Как и в программировании GUI , изменения в состоянии машины можно рассматривать как события, вызывающие переход из одного состояния в другое, пока не будет достигнуто окончательное. Комбинация возможных состояний может генерировать широкий спектр событий, тем самым определяя более сложный производственный цикл. Как следствие, циклы обычно далеки от простых линейных последовательностей. Обычно существуют параллельные ветви, работающие вместе, и альтернативы, выбранные в соответствии с различными событиями, схематически представленными ниже:
s:этап c:состояние с1 | |-c2 | с2 | ---------- | | |-c31 |-c32 | | с31 с32 | | |-c41 |-c42 | | ---------- | с4
Автоматное программирование широко используется в лексическом и синтаксическом анализе . [1]
Кроме того, для событийно-управляемого программирования как единственной альтернативы использованию параллельных процессов или потоков необходимо мышление в терминах автоматов (то есть разбиение процесса выполнения на шаги автомата и передача информации от шага к шагу через явное состояние автомата ).
Понятия состояний и конечных автоматов часто используются в области формальной спецификации . Например, разработка архитектуры программного обеспечения на основе UML использует диаграммы состояний для указания поведения программы. Также различные протоколы связи часто указываются с использованием явного понятия состояния (например, RFC 793).
Мышление в терминах автоматов (шагов и состояний) также может быть использовано для описания семантики некоторых языков программирования . Например, выполнение программы, написанной на языке Refal, описывается как последовательность шагов так называемой абстрактной Refal-машины; состояние машины — это представление (произвольное Refal-выражение без переменных).
Продолжения в языке Scheme требуют мышления в терминах шагов и состояний, хотя сам Scheme никак не связан с автоматами (он рекурсивен). Чтобы функция call/cc могла работать, реализация должна иметь возможность перехватывать целое состояние исполняемой программы, что возможно только тогда, когда в состоянии нет неявной части. Такое перехваченное состояние и есть то, что называется continuation , и его можно рассматривать как состояние (относительно сложного) автомата. Шаг автомата выводит следующее продолжение из предыдущего, а процесс выполнения — это цикл таких шагов.
Александр Оллонгрен в своей книге [2] излагает так называемый Венский метод описания семантики языков программирования, который полностью основан на формальных автоматах.
Система STAT [1] является хорошим примером использования подхода, основанного на автоматах; эта система, помимо других функций, включает в себя встроенный язык STATL , который ориентирован исключительно на автоматы.
Методы, основанные на автоматах, широко использовались в областях, где существуют алгоритмы, основанные на теории автоматов, например, в формальном языковом анализе. [1]
Одна из ранних статей на эту тему была написана Джонсоном и др. в 1968 г. [3]
Одно из самых ранних упоминаний программирования на основе автоматов как общей методики можно найти в статье Питера Наура 1963 года. [4] Автор называет эту методику подходом машины Тьюринга , однако в статье не приводится никакой реальной машины Тьюринга ; вместо этого описывается методика, основанная на шагах и состояниях.
Понятие состояния не является исключительной собственностью программирования на основе автоматов. [5] Вообще говоря, состояние (или состояние программы ) появляется во время выполнения любой компьютерной программы , как совокупность всей информации, которая может изменяться во время выполнения. Например, состояние традиционной императивной программы состоит из
Их можно разделить на явную часть (например, значения, хранящиеся в переменных) и неявную часть (адреса возврата и указатель инструкций).
При этом автоматную программу можно рассматривать как частный случай императивной программы, в которой неявная часть состояния минимизирована. Состояние всей программы, взятое в два различных момента входа в секцию кода шага , может отличаться только состоянием автомата. Это упрощает анализ программы.
В теории объектно-ориентированного программирования говорят , что объект имеет внутреннее состояние и способен получать сообщения , отвечать на них, отправлять сообщения другим объектам и изменять свое внутреннее состояние во время обработки сообщений. В более практической терминологии вызов метода объекта считается тем же, что и отправка сообщения объекту .
Таким образом, с одной стороны, объекты объектно-ориентированного программирования можно рассматривать как автоматы (или модели автоматов), состояние которых представляет собой комбинацию приватных полей, а один или несколько методов считаются шагом . Такие методы не должны вызывать друг друга или самих себя, ни напрямую, ни косвенно, в противном случае объект нельзя считать реализованным на основе автоматов.
С другой стороны, объект хорош для реализации модели автомата. Когда подход на основе автоматов используется в объектно-ориентированном языке, модель автомата обычно реализуется классом, состояние представляется приватными полями класса, а шаг реализуется как метод; такой метод обычно является единственным неконстантным публичным методом класса (помимо конструкторов и деструкторов). Другие публичные методы могут запрашивать состояние, но не изменять его. Все вторичные методы (такие как конкретные обработчики состояний) обычно скрыты в приватной части класса.