Введение

Парадигма программирования, основанная на формальных автоматах.

Программирование на основе автоматов — это парадигма программирования, в которой программа или её часть рассматривается как модель конечного автомата (КА) или любого другого (часто более сложного) формального автомата (см. теорию автоматов). Иногда вводится потенциально бесконечный набор возможных состояний, который может иметь сложную структуру, а не просто перечисление. Программирование на основе конечных автоматов обычно сопоставимо, но, строго говоря, не охватывает все возможные варианты, поскольку КА подразумевает конечное число состояний, а программирование на основе автоматов не обязательно использует КА в строгом смысле. Ключевыми признаками программирования на основе автоматов являются следующие свойства:
Временной период выполнения программы чётко разделен на шаги автомата. Каждый шаг фактически представляет собой выполнение секции кода (одинаковой для всех шагов), имеющей единственную точку входа. Эта секция может быть разделена на подсекции, выполняемые в зависимости от различных состояний, хотя это необязательно. Любое взаимодействие между шагами автомата возможно только через явно определённый набор переменных, называемый состоянием автомата. Между любыми двумя шагами программа не может иметь неявных компонентов состояния, таких как значения локальных переменных, адреса возврата, текущий указатель инструкции и т.п. Иными словами, состояние всей программы в любой момент входа в шаг автомата может отличаться только значениями переменных, рассматриваемых как состояние автомата. Полное выполнение кода на основе автомата представляет собой цикл шагов автомата. Ещё одна причина использования термина «программирование на основе автоматов» заключается в том, что стиль мышления программиста в этой технике очень похож на стиль мышления, используемый при решении математических задач с помощью машин Тьюринга, алгоритмов Маркова и т.д.

Задача

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

Приложения

Программирование на основе автоматов широко используется в лексическом и синтаксическом анализе. Кроме того, мышление в терминах автоматов (то есть разбиение процесса выполнения на шаги автомата и передача информации от шага к шагу через явное состояние автомата) необходимо для событийного программирования как единственной альтернативы использованию параллельных процессов или потоков. Понятия состояний и конечных автоматов часто используются в области формальной спецификации. Например, разработка архитектуры программного обеспечения на основе UML использует диаграммы состояний для спецификации поведения программы. Также различные протоколы связи часто определяются с использованием явного понятия состояния (например, ). Мышление в терминах автоматов (шагов и состояний) также может использоваться для описания семантики некоторых языков программирования. Например, выполнение программы, написанной на языке Refal, описывается как последовательность шагов так называемой абстрактной машины Refal; состояние машины – это представление (произвольное выражение Refal без переменных). Продолжения в языке Scheme требуют мышления в терминах шагов и состояний, хотя сама Scheme никоим образом не связана с автоматами (она рекурсивна). Чтобы функция `call/cc` работала, реализация должна быть способна захватить полное состояние выполняемой программы, что возможно только при отсутствии неявной части в состоянии. Такое захваченное состояние и есть продолжение, и его можно рассматривать как состояние (относительно сложного) автомата. Шаг автомата – это вывод следующего продолжения из предыдущего, а процесс выполнения – цикл таких шагов. Александр Олонгрен в своей книге объясняет так называемый Венский метод описания семантики языков программирования, который полностью основан на формальных автоматах. Система STAT является хорошим примером использования подхода на основе автоматов; эта система, помимо прочих функций, включает встроенный язык под названием STATL, который ориентирован исключительно на автоматы.

История

Техники, основанные на автоматах, широко применялись в областях, где используются алгоритмы, основанные на теории автоматов, например, в формальном анализе языков. Одно из самых ранних упоминаний программирования на основе автоматов как общей техники встречается в статье Питера Наура, 1963 года. Автор называет этот подход машино-тюринговским, однако в статье не представлена реальная машина Тьюринга; вместо этого описывается техника, основанная на последовательности шагов и состояниях.

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

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