Автоматное программирование

В книге рассматривается автоматное программирование — подход к разработке программных систем со сложным поведением, основанный на модели автоматизированного объекта управления (расширении конечного автомата). Предлагаемый подход позволяет создавать качественное программное обеспечение для ответственных систем, охватывая все этапы его жизненного цикла и поддерживая его спецификацию, проектирование, реализацию, тестирование, верификацию и документирование. Книга предназначена для специалистов в области программирования, информатики, вычислительной техники и систем управления, а также аспирантов и студентов, обучающихся по специальностям «Прикладная математика и информатика», «Управление и информатика в технических системах» и «Вычислительные машины, системы, комплексы и сети».

Поликарпова Н. И., Шалыто А. А. Автоматное программирование / Н. И. Поликарпова, А. А. Шалыто, 2-е изд., Санкт-Петербург: Питер, 2011. 176 c.

Классификация программных систем по Харелу (Harel, Pnueli “On the development of reactive systems”):

  • трансформирующие
  • интерактивные
  • реактивные

Другие названия: программирование от состояний, программирование с явным выделением состояний. Это метод создания программ, поведение которых описывается автоматами.

Простое и сложное поведение сущностей в ПО - автоматное программирование применимо для сущностей со сложным поведением.

Одна из основных идей автоматного программирования - отделение описания логики поведения (при каких условиях необходимо выполнить те или иные действия) от описания его семантики (собственно смысла каждого из действий).

Состояние можно рассматривать как особую характеристику, которая в неявной форме объединяет все входные воздействия прошлого, влияющие на реакцию сущности в настоящие момент времени. Реакция зависит теперь только от входного воздействия и текущего состояния.

Автомат - сущность, объединяющая (ставящая в соответствие) множество состояний и конечное множество входных воздействий. Конечный автомат - это автомат, имеющий одно или несколько выходных воздействий.

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

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

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

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

Для произвольной сущности явное выделение управляющих состояний - сложная задача, различия между управляющими и вычислительными состояниями трудно формализовать.

Неформальные основные различия:

  1. Управляющие состояния:
    • число обычно не велико;
    • каждое имеет определенный смысл и качественно отличается от других;
    • определяют действия, которые совершает сущность.
  2. Вычислительные состояния:
    • число либо бесконечно, либо очень велико;
    • большинство не имеет обособленного смысла, отличаются друг от друга лишь количественно;
    • непосредственно определяют лишь результаты действий.

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

Сущность со сложным поведением естественно разделить на две части:

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

Парадигма автоматного программирования состоит в представлении сущностей со сложным поведением в виде автоматизированных объектов управления (объект управления, интегрированный с системой управления).

Процедурное автоматное программирование

Один из основных недостатков метода сверху вниз состоит в том, что при проектировании в первую очередь задается вопрос “Что делает система?”, а ведь именно этот ее аспект более всего подвержен изменениям [29]. В результате архитектура построенной таким образом системы обладает недостаточной расширяемостью.

В программировании с явным выделением состояний главный вопрос — “В каких состояниях может находиться система?” Множество управляющих состояний — более устойчивая характеристика системы, чем ее главная функция. Поэтому архитектура, построенная на основе управляющих состояний, является более расширяемой.

На практике чаще используется не проектирование “сверху вниз”, а проектирование от объектов управления и событий:

  1. Исходными данными задачи считается не только словесное описание целевого поведения системы, но и (более или менее) точная спецификация набора событий, поступающих в систему из внешней среды, и множеств запросов и команд всех объектов управления.
  2. Строится набор управляющих состояний.
  3. Каждому запросу объектов управления ставится в соответствие входная переменная автомата, каждой команде — выходная. На основе управляющих состояний, событий, входных и выходных переменных строится автомат, обеспечивающий заданное поведение системы.

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

Два вида подчиненных автоматов по отношению к вышестоящему (при этом целесообразно во всей системе использовать только один вид подчинения, иначе возникают серьезные семантические сложности):

  • вызываемый - синхронная передача управления, автомат работает, пока не сформирует выходное воздействие и не вернет управление вызвавшему его автомату.
  • вложенный - запускается при возникновении входного воздействия в вышестоящем автомате, работает один такт.

Декомпозировать проектируемую систему можно двумя разными способами:

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