Автоматное программирование - Automata-based programming

Для использования в других целях см. Автоматное программирование (подход Шалыто).
Парадигмы программирования

Автоматное программирование это парадигма программирования в котором программа или ее часть рассматривается как модель конечный автомат (FSM) или любой другой (часто более сложный) формальный автомат (см. теория автоматов ). Иногда вводится потенциально бесконечный набор возможных состояний, и такой набор может иметь сложную структуру, а не просто перечисление.

Программирование на основе конечных автоматов в целом то же самое, но, формально говоря, не охватывает все возможные варианты, поскольку конечный автомат означает конечный автомат, а автоматное программирование не обязательно использует конечные автоматы в строгом смысле этого слова.

Следующие свойства являются ключевыми показателями для программирования на основе автоматов:

  • Временной период выполнения программы четко разделен до автоматные шаги. Каждый шаг фактически представляет собой выполнение раздела кода (одинакового для всех шагов), имеющего единственную точку входа. Этот раздел можно разделить на подразделы, которые будут выполняться в зависимости от различных состояний, хотя в этом нет необходимости.
  • Любая связь между этапами автомата возможна только через явно указанный набор переменных, называемых состояние автомата. Между любыми двумя шагами программа не может иметь неявных компонентов своего состояния, таких как значения локальных переменных, адреса возврата, текущий указатель инструкции и т. Д. То есть состояние всей программы, полученное в любые два момента ввода шаг автомата, может отличаться только значениями переменных, рассматриваемых как состояние автомата.

Полное выполнение кода на основе автоматов является цикл ступеней автомата.

Еще одна причина использования понятия программирования на основе автоматов заключается в том, что стиль мышления программиста о программе в этой технике очень похож на стиль мышления, используемый для решения математических задач с использованием Машины Тьюринга, Марковские алгоритмы, так далее.

Пример

Задача

Рассмотрим задачу чтения текста из стандартный ввод построчно и записывая первое слово каждой строки в стандартный вывод. Сначала мы пропускаем все ведущие пробел персонажей, если есть. Затем печатаем все символы первого слова. Наконец, мы пропускаем все конечные символы, пока не появится новая линия встречается персонаж. Каждый раз, когда последовательность символов новой строки встречается не в начале потока, мы печатаем только первый и пропускаем остальные; иначе мы пропускаем все. Затем мы перезапускаем процесс со следующей строки. Столкнувшись с конец файла состояние (независимо от стадии), останавливаемся.

Традиционная программа

Традиционная программа в C который выполняет указанную выше задачу, может выглядеть так:

#включают <ctype.h>#включают <stdio.h>int главный(пустота) {  int c;  делать {    делать {      c = Getchar();    } пока (isspace(c));    пока (!isspace(c) && c != EOF) {      путчар(c);      c = Getchar();    }        пока (c != ' n' && c != EOF) {      c = Getchar();    }        если (c == ' n') {      путчар(c);    }  } пока (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)

дает:

fooqux

Программа на основе автоматов

Процедурный

Эту же задачу можно решить, если мыслить категориями конечные автоматы. Обратите внимание, что синтаксический анализ строки состоит из трех этапов: пропуск начальных пробельных символов, печать символов первого слова и пропуск конечных символов. Назовем эти состояния автоматов ПЕРЕД, ВНУТРИ и ПОСЛЕ. Автоматизированная версия программы могла бы выглядеть так:

#включают <ctype.h>#включают <stdio.h>перечислить Состояние {ПЕРЕД, ВНУТРИ, ПОСЛЕ};int главный(пустота) {  int c;  перечислить Состояние s = ПЕРЕД;  пока ((c = Getchar()) != EOF) {    выключатель (s) {      кейс ПЕРЕД:        если (!isspace(c)) {          путчар(c);          s = ВНУТРИ;        }                перемена;      кейс ВНУТРИ:        если (c == ' n') {          путчар(c);          s = ПЕРЕД;        } еще если (isspace(c)) {          s = ПОСЛЕ;        } еще {          путчар(c);        }                  перемена;      кейс ПОСЛЕ:        если (c == ' n') {          путчар(c);          s = ПЕРЕД;        }                перемена;    }  }  возвращаться 0;}

Хотя программа теперь выглядит длиннее, у нее есть как минимум одно существенное преимущество: есть только одно чтение (то есть вызов Getchar функция) инструкция. Кроме того, здесь всего одна петля вместо четырех в традиционной версии. Тело пока петля шаг автомата а сам цикл - это цикл шага автомата. Программа реализует работу конечного автомата, показанного на диаграмме состояний.

Самым важным свойством программы является то, что секция кода шага автомата четко локализована. С явной функцией шаг для этапа автоматизации программа лучше демонстрирует это свойство:

#включают <ctype.h>#включают <stdio.h>перечислить Состояние {ПЕРЕД, ВНУТРИ, ПОСЛЕ};пустота шаг(перечислить Состояние* const s, int const c) {  выключатель (*s) {    кейс ПЕРЕД:      если (!isspace(c)) {        путчар(c);        *s = ВНУТРИ;      }            перемена;    кейс ВНУТРИ:      если (c == ' n') {        путчар(c);        *s = ПЕРЕД;      } еще если (isspace(c)) {        *s = ПОСЛЕ;      } еще {        путчар(c);      }              перемена;    кейс ПОСЛЕ:      если (c == ' n') {        путчар(c);        *s = ПЕРЕД;      }            перемена;  }}int главный(пустота) {  int c;  перечислить Состояние s = ПЕРЕД;  пока ((c = Getchar()) != EOF) {    шаг(&s, c);  }  возвращаться 0;}

Теперь программа наглядно демонстрирует основные свойства автоматного кода:

  • сроки выполнения шагов автоматов не могут перекрываться;
  • единственная информация, передаваемая с предыдущего шага на следующий, - это явно указанная состояние автомата.

Конечный автомат можно определить как таблица переходов между состояниями строки которых обозначают текущие состояния, столбцы обозначают входные данные, а ячейки обозначают следующие состояния и действия, которые необходимо выполнить.

Таблица перехода состояний
Вход
Текущее состояние
новая линияпробелДругой
передпередпередвнутри / печать
внутридо / печатьпослевнутри / печать
последо / печатьпослепосле
Диаграмма состояний
В диаграмма состояний конечного автомата, который печатает первое слово каждой строки входного потока. Машина выполняет ровно один переход на каждом шаге, в зависимости от текущего состояния и встречающегося символа. Действие, сопровождающее переход, - это либо бездействие, либо печать встретившегося символа, обозначенного Распечатать.

Вообще говоря, автоматная программа может естественно использовать этот подход. С явным двумерным массивом переходы для таблицы переходов между состояниями программа использует такой подход:

#включают <ctype.h>#включают <stdio.h>перечислить Состояние {ПЕРЕД, ВНУТРИ, ПОСЛЕ};пустота нет(int const c) {}пустота Распечатать(int const c) {  путчар(c);}структура Ответвляться {  перечислить Состояние const next_state;  пустота (*действие)(int);};структура Ответвляться const переходы[3][3] = {  // новая строка пробела другие входы / состояния  {{ПЕРЕД,   &нет}, {ПЕРЕД, &нет}, {ВНУТРИ, &Распечатать}},  // перед  {{ПЕРЕД, &Распечатать}, {ПОСЛЕ,  &нет}, {ВНУТРИ, &Распечатать}},  // внутри  {{ПЕРЕД, &Распечатать}, {ПОСЛЕ,  &нет}, {ПОСЛЕ,    &нет}}   // после};пустота шаг(перечислить Состояние* const s, int const c) {  int const ряд = (*s == ПЕРЕД) ? 0 : (*s == ВНУТРИ) ? 1 : 2;  int const столбец = (c == ' n') ? 0 : isspace(c) ? 1 : 2;  структура Ответвляться const* const б = &переходы[ряд][столбец];  *s = б->next_state;  б->действие(c);}int главный(пустота) {  int c;  перечислить Состояние s = ПЕРЕД;  пока ((c = Getchar()) != EOF) {    шаг(&s, c);  }  возвращаться 0;}

Объектно-ориентированный

Если язык реализации поддерживает объектно-ориентированного программирования, простой рефакторинг программы заключается в инкапсулировать автомат в объект, тем самым скрывая детали его реализации. Программа в C ++ использование объектно-ориентированного стиля может выглядеть так:

#включают <ctype.h>#включают <stdio.h>перечислить Состояние {ПЕРЕД, ВНУТРИ, ПОСЛЕ};структура Ответвляться {  перечислить Состояние const next_state;  пустота (*действие)(int);};учебный класс Государственный аппарат {  общественный:    Государственный аппарат();    пустота feedChar(int);  защищенный:    статический пустота нет(int);    статический пустота Распечатать(int);  частный:    перечислить Состояние _государственный;    статический структура Ответвляться const _transitions[3][3];};Государственный аппарат::Государственный аппарат(): _государственный(ПЕРЕД) {}пустота Государственный аппарат::feedChar(int const c) {  int const ряд = (_государственный == ПЕРЕД) ? 0 : (_государственный == ВНУТРИ) ? 1 : 2;  int const столбец = (c == ' n') ? 0 : isspace(c) ? 1 : 2;  структура Ответвляться const* const б = &_transitions[ряд][столбец];  _государственный = б->next_state;  б->действие(c);}пустота Государственный аппарат::нет(int const c) {}пустота Государственный аппарат::Распечатать(int const c) {  путчар(c);}структура Ответвляться const Государственный аппарат::_transitions[3][3] = {  // новая строка пробела другие входы / состояния  {{ПЕРЕД,   &нет}, {ПЕРЕД, &нет}, {ВНУТРИ, &Распечатать}},  // перед  {{ПЕРЕД, &Распечатать}, {ПОСЛЕ,  &нет}, {ВНУТРИ, &Распечатать}},  // внутри  {{ПЕРЕД, &Распечатать}, {ПОСЛЕ,  &нет}, {ПОСЛЕ,    &нет}}   // после};int главный() {  int c;  Государственный аппарат м;  пока ((c = Getchar()) != EOF) {    м.feedChar(c);  }  возвращаться 0;}

Примечание. - Чтобы минимизировать изменения, не связанные напрямую с тематикой статьи, ввод, вывод Getchar и путчар функции из стандартной библиотеки C используются.

В государственный шаблон проектирования это способ объекта изменить свое поведение во время выполнения в соответствии с его внутренним состоянием без использования больших условных операторов или поиска в таблицах благодаря вызовам виртуальных функций. Его главное преимущество перед кодом, использующим большие условные операторы, заключается в том, что код, зависящий от состояния, распределен по разным объектам, а не локализован в монолитном блоке, что улучшает ремонтопригодность. Его основные преимущества по сравнению с кодом, использующим таблицы перехода состояний, заключаются в том, что вызовы виртуальных функций часто более эффективны, чем поиск в таблице, критерии перехода между состояниями более явны, чем в табличном формате, и что легче добавлять действия, сопровождающие переходы состояний. Однако это создает новую проблему: количество классов делает код менее компактным, чем другие подходы. Программа, использующая шаблон проектирования состояний, может выглядеть так:

#включают <ctype.h>#включают <stdio.h>учебный класс Государственный аппарат;учебный класс Состояние {  общественный:    виртуальный пустота feedChar(Государственный аппарат*, int) const = 0;};учебный класс Перед: общественный Состояние {  общественный:    статический Состояние const* создать экземпляр();    виртуальный пустота feedChar(Государственный аппарат*, int) const отменять;  защищенный:    Перед() = дефолт;  частный:    статический Состояние const* _пример;};учебный класс Внутри: общественный Состояние {  общественный:    статический Состояние const* создать экземпляр();    виртуальный пустота feedChar(Государственный аппарат*, int) const отменять;  защищенный:    Внутри() = дефолт;  частный:    статический Состояние const* _пример;};учебный класс После: общественный Состояние {  общественный:    статический Состояние const* создать экземпляр();    виртуальный пустота feedChar(Государственный аппарат*, int) const отменять;  защищенный:    После() = дефолт;  частный:    статический Состояние const* _пример;};учебный класс Государственный аппарат {  общественный:    Государственный аппарат();    пустота feedChar(int);  защищенный:    пустота setState(Состояние const*);  частный:    Состояние const* _государственный;    друг учебный класс Перед;    друг учебный класс Внутри;    друг учебный класс После;};Состояние const* Перед::создать экземпляр() {  если (!_пример) {    _пример = новый Перед;  }  возвращаться _пример;}пустота Перед::feedChar(Государственный аппарат* const м, int const c) const {  если (!isspace(c)) {    путчар(c);    м->setState(Внутри::создать экземпляр());  }}Состояние const* Перед::_пример = nullptr;Состояние const* Внутри::создать экземпляр() {  если (!_пример) {    _пример = новый Внутри;  }  возвращаться _пример;}пустота Внутри::feedChar(Государственный аппарат* const м, int const c) const {  если (c == ' n') {    путчар(c);    м->setState(Перед::создать экземпляр());  } еще если (isspace(c)) {    м->setState(После::создать экземпляр());  } еще {    путчар(c);  }}Состояние const* Внутри::_пример = nullptr;Состояние const* После::создать экземпляр() {  если (!_пример) {    _пример = новый После;  }  возвращаться _пример;}пустота После::feedChar(Государственный аппарат* const м, int const c) const {  если (c == ' n') {    путчар(c);    м->setState(Перед::создать экземпляр());  }}Состояние const* После::_пример = nullptr;Государственный аппарат::Государственный аппарат(): _государственный(Перед::создать экземпляр()) {}пустота Государственный аппарат::feedChar(int const c) {  _государственный->feedChar(это, c);}пустота Государственный аппарат::setState(Состояние const* const s) {  _государственный = s;}int главный() {  int c;  Государственный аппарат м;  пока ((c = Getchar()) != EOF) {    м.feedChar(c);  }  возвращаться 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: стадия c: условие s1 | | -c2 | s2 | ---------- | | | -c31 | -c32 | | s31 s32 | | | -c41 | -c42 | | ---------- | s4

Приложения

Автоматное программирование широко используется в лексический и синтаксический анализ.[1]

Кроме того, мышление автоматами (то есть разбиение процесса выполнения на автоматные шаги и передачу информации от шага к шагу через явный состояние автомата) необходимо для событийно-ориентированное программирование как единственная альтернатива использованию параллельных процессов или потоков.

Понятия состояний и конечных автоматов часто используются в области формальная спецификация. Например, UML при разработке архитектуры программного обеспечения диаграммы состояний чтобы указать поведение программы. Также различные протоколы связи часто указываются с использованием явного понятия состояния (например, RFC  793 ).

Мышление в терминах автоматов (шагов и состояний) также может использоваться для описания семантики некоторых языки программирования. Например, выполнение программы, написанной на Рефал язык описывается как последовательность шаги так называемой абстрактной рефалевской машины; состояние машины Посмотреть (произвольное выражение Рефаля без переменных).

Продолжение в Схема язык требует мышления в терминах шагов и состояний, хотя сама Scheme никоим образом не связана с автоматами (она рекурсивна). Чтобы сделать возможным вызов / cc Чтобы функция работала, реализация должна иметь возможность улавливать все состояние выполняющейся программы, что возможно только тогда, когда в состоянии нет неявной части. Такое пойманное состояние и есть то, что называется продолжение, и его можно рассматривать как состояние (относительно сложного) автомата. Шаг автомата выводит следующее продолжение из предыдущего, а процесс выполнения - это цикл таких шагов.

Александр Оллонгрен в своей книге[2] объясняет так называемый Венский метод описания семантики языков программирования, полностью основанного на формальных автоматах.

Система STAT [1] является хорошим примером использования автоматного подхода; эта система, помимо других функций, включает встроенный язык, называемый STATL который является чисто автоматно-ориентированным.

История

Методы, основанные на автоматах, широко использовались в тех областях, где есть алгоритмы, основанные на теории автоматов, такие как анализ формального языка.[1]

Одна из первых работ по этому поводу - Johnson et al., 1968.[3]

Одно из самых первых упоминаний о программировании на основе автоматов как об общей технике содержится в статье Питер Наур, 1963.[4] Автор называет методику Подход машины Тьюрингано не настоящий Машина Тьюринга приводится в статье; вместо этого описывается техника, основанная на шагах и состояниях.

Сравнение с императивным и процедурным программированием

Понятие государственный не является исключительной собственностью программирования на основе автоматов.[5]Вообще говоря, состояние (или состояние программы ) появляется при выполнении любого компьютерная программа, как совокупность всей информации, которая может измениться во время выполнения. Например, состояние традиционного императив программа состоит из

  • значения всех переменных и информации, хранящейся в динамической памяти;
  • значения, хранящиеся в регистрах;
  • содержимое стека (включая значения локальных переменных и адреса возврата);
  • текущее значение указателя инструкции.

Их можно разделить на явный часть (например, значения, хранящиеся в переменных) и скрытый часть (адреса возврата и указатель инструкции).

При этом автоматную программу можно рассматривать как частный случай императивной программы, в которой неявная часть состояния минимизирована. Состояние всей программы, полученное в два разных момента входа в шаг Раздел кода может отличаться только состоянием автомата. Это упрощает анализ программы.

Отношения объектно-ориентированного программирования

В теории объектно-ориентированного программирования, объект как говорят, имеет внутренний государственный и способен получение сообщений, отвечающий им, отправка сообщения другим объектам и изменение его внутреннего состояния во время обработки сообщений. В более практической терминологии вызвать метод объекта считается так же, как отправить сообщение объекту.

Таким образом, с одной стороны, объекты объектно-ориентированного программирования можно рассматривать как автоматы (или модели автоматов), чьи государственный представляет собой комбинацию частных полей, и один или несколько методов считаются шаг. Такие методы не должны вызывать друг друга или самих себя, ни прямо, ни косвенно, иначе объект не может считаться реализованным на основе автоматов.

С другой стороны, объект хорош для реализации модели автомата. Когда подход, основанный на автоматах, используется в объектно-ориентированном языке, автоматная модель обычно реализуется классом, состояние представлено частными полями класса, а шаг реализуется как метод; такой метод обычно является единственным непостоянным общедоступным методом класса (помимо конструкторов и деструкторов). Другие общедоступные методы могут запрашивать состояние, но не меняют его. Все вторичные методы (например, обработчики определенных состояний) обычно скрыты в частной части класса.

Смотрите также

Рекомендации

  1. ^ а б Ахо, Альфред V .; Ульман, Джеффри Д. (1973). Теория разбора, перевода и компиляции. 1. Энглвуд Клиффс, штат Нью-Джерси: Прентис-Холл. ISBN  0-13-914564-8.
  2. ^ Оллонгрен, Александр (1974). Определение языков программирования путем интерпретации автоматов. Лондон: Academic Press. ISBN  0-12-525750-3.
  3. ^ Johnson, W. L .; Porter, J. H .; Ackley, S. I .; Росс, Д. Т. (1968). «Автоматическая генерация эффективных лексических процессоров с использованием методов конечного состояния». Связь ACM. 11 (12): 805–813. Дои:10.1145/364175.364185.
  4. ^ Наур, Питер (сентябрь 1963 г.). "Дизайн компилятора GIER ALGOL Часть II". BIT вычислительная математика. 3 (3): 145–166. Дои:10.1007 / BF01939983.
  5. ^ «Автоматное программирование» (PDF). Научно-технический журнал информационных технологий, механики и оптики (53). 2008.

внешняя ссылка