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